本文主要是介绍赛码网OJ题目--股神，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 题目描述
2. 第一版
import java.util.Scanner;
public class 股神 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int day;
while (scanner.hasNext()) {
day = scanner.nextInt();
long time1 = System.currentTimeMillis();
System.out.println(getMoney(day));
long time2 = System.currentTimeMillis();
System.out.println(time2-time1);
}
}
public static int getMoney(int day){
int total = 0;
for (int i = 1; i <= day; i++) {
if(isIncr(i)){
total++;
}else{
total--;
}
}
return total;
}
public static boolean isIncr(int day){
int interval = 3;
int temp = 3;
while (temp<day) {
temp += interval++;
}
if(temp==day){
return false;
}else{
return true;
}
}
}
结果发现：
| Time Limit Exceeded | TLE | 您的程序运行的时间已经超出了题目的时间限制。 |
问题就出在每个数字都要进行判断
比如10000000 结果是9991060 而所需时间是20467ms 20多秒才能计算出来
3. 第二版
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int day;
while (scanner.hasNext()) {
day = scanner.nextInt();
long time1 = System.currentTimeMillis();
System.out.println(getMoney(day));
long time2 = System.currentTimeMillis();
System.out.println(time2-time1);
}
}
public static int getMoney(int day) {
if(day==1){
return 1;
}else{
int curr = 1;
int cycleNum = 1;
int total = 1;
while (curr < day) {
// 执行一个循环
{
// 第一个循环是 第二天 第三天
// 第二个循环是 第四天 第五天 第六天...
for (int i = 0; i < cycleNum; i++) {
total++;
curr++;
if (curr == day) {
return total;
}
}
// 完成循环的最后一步
total--;
curr++;
}
if (curr == day) {
return total;
}
cycleNum++;
}
return total;
}
}
}
比如10000000 结果是9991060 而所需时间是7ms
4. 总结
算法优化是多么明显地带来计算效率的提升！
这篇关于赛码网OJ题目--股神的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
