Posts

Showing posts from September, 2017

LeetCode] 644.Maximum Average Subarray II

LeetCode 644. Maximum Average Subarray II lintcode 671 Given an array consisting of  n  integers, find the contiguous subarray whose  length is greater than or equal to   k  that has the maximum average value. And you need to output the maximum average value. Example 1: Input: [1,12,-5,-6,50,3], k = 4 Output: 12.75 Explanation: when length is 5, maximum average value is 10.8, when length is 6, maximum average value is 9.16667. Thus return 12.75. Note: 1 <=  k  <=  n  <= 10,000. Elements of the given array will be in range [-10,000, 10,000]. The answer with the calculation error less than 10 -5  will be accepted. 题目大意： 给定包含n个整数的数组，寻找长度大于等于k的连续子数组的平均值的最大值。 没有买leetcode，所以复制粘贴了题目，这道题看起来跟 他的兄弟 差不多，但是实际上差很多。。。 lintcode 671  这个一模一样的就是hint和限制条件没有。所以可以用这个来测。 这个解释的很详细  https://leetcode.com/articles/maximum-average-subarray-ii/ 这个也很好  http://blog.csdn.net/zjucor/article/details/75199933 我开始用的是暴力解法，就是把它兄弟重复很多遍，当然，超时哦。然后就不知道怎么办了，看的答案，看完恍然大悟，原来里面有套路： 1. 只要满足
Post a Comment
Keep reading

Popular posts from this blog

LeetCode] 644.Maximum Average Subarray II

LeetCode 644. Maximum Average Subarray II lintcode 671 Given an array consisting of  n  integers, find the contiguous subarray whose  length is greater than or equal to   k  that has the maximum average value. And you need to output the maximum average value. Example 1: Input: [1,12,-5,-6,50,3], k = 4 Output: 12.75 Explanation: when length is 5, maximum average value is 10.8, when length is 6, maximum average value is 9.16667. Thus return 12.75. Note: 1 <=  k  <=  n  <= 10,000. Elements of the given array will be in range [-10,000, 10,000]. The answer with the calculation error less than 10 -5  will be accepted. 题目大意： 给定包含n个整数的数组，寻找长度大于等于k的连续子数组的平均值的最大值。 没有买leetcode，所以复制粘贴了题目，这道题看起来跟 他的兄弟 差不多，但是实际上差很多。。。 lintcode 671  这个一模一样的就是hint和限制条件没有。所以可以用这个来测。 这个解释的很详细  https://leetcode.com/articles/maximum-average-subarray-ii/ 这个也很好  http://blog.csdn.net/zjucor/article/details/75199933 我开始用的是暴力解法，就是把它兄弟重复很多遍，当然，超时哦。然后就不知道怎么办了，看的答案，看完恍然大悟，原来里面有套路： 1. 只要满足
Keep reading

[Leetcode]375. Guess Number Higher or Lower II

https://leetcode.com/problems/guess-number-higher-or-lower-ii/description/ We are playing the Guess Game. The game is as follows: I pick a number from  1  to  n . You have to guess which number I picked. Every time you guess wrong, I'll tell you whether the number I picked is higher or lower. However, when you guess a particular number x, and you guess wrong, you pay  $x . You win the game when you guess the number I picked. Example: n = 10, I pick 8. First round: You guess 5, I tell you that it's higher. You pay $5. Second round: You guess 7, I tell you that it's higher. You pay $7. Third round: You guess 9, I tell you that it's lower. You pay $9. Game over. 8 is the number I picked. You end up paying $5 + $7 + $9 = $21. Given a particular  n ≥ 1 , find out how much money you need to have to guarantee a  win . 上一道题 GuessNumber 的升级版。然鹅，并看不懂题目。。。一开始想的是用二分法继续，求值，就像一道数学题，写完测试，不对。。。然后就很蒙圈，看提示，说要用dp，说要用mixmax，不知道啥是minmax的小白我看了半天才看懂那个维基百科链接。看完之后，呵呵，
Keep reading

[Leetcode]282. Expression Add Operators

[Leetcode]282. Expression Add Operators Given a string that contains only digits  0-9  and a target value, return all possibilities to add  binary  operators (not unary)  + ,  - , or  * between the digits so they evaluate to the target value. Examples:  "123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"] "105", 5 -> ["1*0+5","10-5"] "00", 0 -> ["0+0", "0-0", "0*0"] "3456237490", 9191 -> [] 拿到题目完全没思路啊，想不到除了暴力拆解加暴力加各种符号之外更好的例子。能想到的两点就是小细节：1. 字符串这东西这么长，分分钟overflow啊，2.0开头的各种字符串应该不算吧，0自己除外，3. 有乘号，乘号优先级高，要是从前往后算的话要处理一下运算顺序才行。 解决方法是： 1. 用long， 2. 0开头的，除了0自己，都忽略不算， 3. 为了解决乘号优先级，例如2+3*2，顺序算的话，我们先算出来2+3=5，看到乘号，我们用5-3=2，恢复到之前，再算3*2=6，然后加上之前的2，6+2=8。我们设置两个变量，一个是curSum 上一步的和，一个是diff， 上一步末尾的计算的数，如果是乘以出来的结果，就是那个结果, 有负号的话记得把负号也连带着用上。curSum = 2, diff = 3, curSum = 5; 运算到遇到了乘号，就用（curSum - diff ）+ diff*i。更新 curSum = 8， diff = dif
Keep reading