学渣的刷题笔记

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

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我们没有读到！ 好吧，第二招，稍微不那么笨的，就是把当

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

题目简单。最开始一个一个加起来的，还感觉这简直太简单了。后来果然不出所料，超时了。。。然后被逼无奈，打算建一个一维数组，前面所有数字的和。 可以用两种方法做的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]; } }

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) 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);

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