Posts

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. 只要满足

[Leetcode] 643. Maximum Average Subarray I

643. Maximum Average Subarray I Given an array consisting of  n  integers, find the contiguous subarray of given length  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: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75 Note: 1 <=  k  <=  n  <= 30,000. Elements of the given array will be in the range [-10,000, 10,000]. easy难度的,应该没啥弯弯绕。但是有一点,要问清楚每个数字大小,数组有多少数字。确保1. 每个数字不overflow了Max int 2. 他们的和不overflow了Max int 如果数字太大, 就要用string 求和的方法了。鉴于这道题是easy,题目给的note里就有限制了,所以这道题我们不用担心。 尝试了一格一格挪,每次取k个数加起来的最原始办法, 复杂度应该是nk果然超时了TLE。。。就在用这个原始方法的时候,也出了问题了,我在for循环里的limit是nums.length-k,实际上应该是nums.length-k+1. 然鹅,事实是这个样子滴,在我们单独讲循环某个数组的时候,limit应该是小于这个数组的长度,因为等于长度就读不出来数了,当从0开始算index的时候。 但是向这类的移动平均值呢,这个limit的物理意义是,我们要移动多少下。不举具体数字栗子,就干想我们有一个数组,长度是n,要取window长度为k的平均值。我们把长度为n的数组和长度为k的数组上下摞起来,多出来的就是n-k。但是!我们并不能设置limit为n-k,因为,这样我们就少移动了一次,最后一个k的window我们没有读到! 好吧,第二招,稍微不那么笨的,就是把当

[Leetcode] 304. Range Sum Query 2D - Immutable

https://leetcode.com/problems/range-sum-query-2d-immutable/description/ 这道题是上一道题的升级版 http://xuezha.blogspot.ca/2017/08/leetcode303-range-sum-query-immutable.html   数组变成了二维数组,要求几乎一样。左上到右下,可以确定一个方块,把他们的和加起来。于是,我以左上为坐标零点,然后出发,到每一格,求他到坐标零点围成的方块的值。这个值就是当前格左边和上面的和减去左上角的数值。因为左上角的数值我们加了两次,在左边值和上面值里都有。 这个二维数组建好了之后呢,求和就是右下角的大方块到原点的值,减去上边界大方块,减去左边界大方块,加上左上方块。自己把思路写出来都觉得好复杂,看来真的有可以优化的地方。有重复计算。 我自己写的AC代码,虽然不好看吧,但是思路清晰。然而,时间很长。 class NumMatrix { int[][] n; public NumMatrix(int[][] matrix) { if(matrix != null && matrix.length !=0){ n = new int[matrix.length][matrix[0].length]; n = matrix; n[0][0] = matrix[0][0]; for(int i=0; i<matrix.length; i++){ for(int j=0; j<matrix[0].length; j++){ if(i==0){ if(j==0){ continue; } n[i][j] = n[i][j-1] + n[i][j]; continu

[Leetcode]303. Range Sum Query - Immutable

题目简单。最开始一个一个加起来的,还感觉这简直太简单了。后来果然不出所料,超时了。。。然后被逼无奈,打算建一个一维数组,前面所有数字的和。 可以用两种方法做的dp。 public class NumArray {     int[] n;     int l;     public NumArray(int[] nums) {         this.n = new int[l];         this.n = nums;         int l = nums.length;         if(nums != null && l > 0){             n[0] = nums[0];             for(int i=1; i<l; i++){             n[i] = n[i-1] + nums[i];             }         }     }     public int sumRange(int i, int j) {         return i==0 ? n[j] : n[j] - n[i-1];     } } 思路一样,但是下面这个别人的比我的快,代码也好看一些似乎。 class NumArray { private int[] sums; public NumArray(int[] nums) { if(nums.length != 0){ sums = new int[nums.length]; sums[0] = nums[0]; for(int i=1; i<nums.length; i++){ sums[i] = nums[i] + sums[i-1]; } } } public int sumRange(int i, int j) { return i==0 ? sums[j] : sums[j]-sums[i-1]; } }

[Leetcode] 381. Insert Delete GetRandom O(1) - Duplicates allowed

381. Insert Delete GetRandom O(1) - Duplicates allowed https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/ 这个是 上一道题 升级版,难度也变成了hard,看来不可小觑! 看着和第一道题没啥区别,实际上区别大了!上一道题我们用hashset,这个东西key不能重复啊。我已开始想的是key指向的value换成list,list里面是一堆position,后来发现insert 还好办,delete不是常数复杂度啊,没办法,只能key里面再来一个hashMap了。坚持不看答案,以看答案为耻,恩!我发现自己太依赖答案了。从现在起,自己做,实在不行了再看答案。还有就是要强迫自己总结,不然都熊瞎子掰苞米了,简直了。这道题的考点上来说和上一道题一样的,都是hash map和list,目前看来是这样,只是更复杂了一点。仔细想了一下也不对啊,如果list of position的话也没什么不妥,反正,每个position的值一样,随便拿掉一个就行了嘛。最后看看list of posittion里面剩下东西没有,没剩下的话把那个hashMap entry 删除 以后每道题都自己做,有思路的就坚决不看答案。长时间没有思路的看思路,然后还是自己写出来,不然依赖答案太严重了!一定要独立! 这道题随机读取要于数字的个数成比例,这个好办,就把hashMap里面东西拿出来,然后放进一个list,然后和第一题一样随机读取就行了。但是这样有额外的空间要占用,所以,做完之后看看答案有没有啥好办法。 确实尝试独立来着,结果两天也没搞出来,基本思路对的,但是就是implement不出来。难度不高,但是需要炒鸡细心,我的错误是吧其中应该放在括号外面的一行放在了括号里面。导致错的很离谱。 用了一堆println 才搞定,最后两是print的函数,大家需要的话调用好了。 AC Solution: public class RandomizedCollection { // Integer key is the value HashMap<Integer, HashSet<Integer&g

[leetcode] 380. Insert Delete GetRandom O(1)

[leetcode] 380. Insert Delete GetRandom O(1) https://leetcode.com/problems/insert-delete-getrandom-o1/description/ 看见题第一反应,用hashSet啊,hashtable都不用,直接set。但是忘了考虑一点,hashSet添加和删除都是O(1),但是拿随机的item是O(n)。我用hashSet做了一遍,也AC了但是 是错的!!! 是错的!!! 这个是错的!! :重要的事情说三遍 public class RandomizedSet { HashSet<Integer> set = new HashSet<Integer>(); /** Initialize your data structure here. */ public RandomizedSet() { } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ public boolean insert(int val) { return set.add(val); } /** Removes a value from the set. Returns true if the set contained the specified element. */ public boolean remove(int val) { return set.remove(val); } /** Get a random element from the set. */ public int getRandom() { int size = set.size(); Random rand = new Random(); int index = rand.nextInt(size);

[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的小白我看了半天才看懂那个维基百科链接。看完之后,呵呵,

Popular posts from this blog

LeetCode] 644.Maximum Average Subarray II

[Leetcode]375. Guess Number Higher or Lower II

[Leetcode] 643. Maximum Average Subarray I