脚本宝典收集整理的这篇文章主要介绍了

赛码模拟题:股神 stockmaster (java8)

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

题目: 股票会有以下变化:第一天不变,以后涨一天,跌一天,涨两天,跌一天,涨三天,跌一天...依此类推。
为方便计算,假设每次涨和跌皆为1,股票初始单价也为1,请计算买股票的第n天每股股票值多少钱?
例子:
输入: 1 2 3 4 5 (分别代表第1 2 3 4 5天)
输出: 1 2 1 2 3 (对应每天的股价)

输入声明:
输入包括多组数据;
每行输入一个n,1<=n<=10^9 。


赛码网的题跟Leetcode不同的是:赛码要求我们写读取输入的代码,Leetcode只要写函数就行。赛码主要使用Scanner来读取输入(有套路),题目的输入输出都挺简洁,大多只是数字,字符串或数组,不会像LeetCode的输出会有长串的链表,有些看着会很复杂。
有人说赛码的编译很不好,但有些是使用者自身代码质量问题,至少我用Java到现在没有出现过什么问题,如果编译不对可以看看别人的代码。
我认为赛码的题挺有趣的其实,所以还是值得做。


解法:

  1. 这题我一开始想用的是用递归来做,第n天的股价递归到第1天开始算起,但要注意n的范围是10^9,递归算法会导致层数太多内存溢出,所以通不过测试。还有要注意的就是n很大不能用int装,java里可以用Integer,当然double也可以。

  2. 可以两个循环一天天算,这样时间复杂度是O(n)吧,可以做。

  3. 还有更快的方法,举例发现股价和天数之间是有一些规律的:

clipboard.png

发现同一递增周期内股价与天数的差值相同。
接下来只要能总结出天数和差值的关系就能知道股价了。
发生跳转的天数位1,3,6,10....对应的差值为0,2,4,6...
发现天数为累加和:
1=1
3=1+2
6=1+2+3
10=1+2+3+4
...
刚好差值又是线性等差
那么就可以找到这样的关系: 天数=(1+(差值/2+1))/2; 股价=天数+差值


代码:

import java.util.*; public class Main {      private static Integer stockPrice(Integer temp) {         int sum = 1, count = 1;         while(sum <= temp) {             count++;             sum+=count;         }         return  temp == 1 ? 1 : temp - 2 * (count - 2);     }      public static void main(String args[]) {          Scanner cin = new Scanner(System.in);          while (cin.hasNextInt()) {             Integer output= 0;             Integer temp = cin.nextInt();             System.out.println(stockPrice(temp));          }          cin.close();      }  } 

时间:216ms 话说整个时间我真不确定是不是跟网速有关系。。。

总结

以上是脚本宝典为你收集整理的

赛码模拟题:股神 stockmaster (java8)

全部内容,希望文章能够帮你解决

赛码模拟题:股神 stockmaster (java8)

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过