学渣的刷题笔记 序言

本人学渣一枚。一年前算法一窍不通，后为生计奔波，遂走上CS大法好的道路。在这条不归路上走了几米，生计算是有了着落，但学渣的属性并没有改变。严格意义上讲，连渣都算不上，基本是个学沫，学渣还沉底在下面有个渣，而学沫，就是飘在上面的沫沫。


在于算法大神交流过之后，大神一句话点醒梦中人，不，是梦中渣，本渣是操作系统不行。如果每个人都是个AI，我这款AI的算法学习能力差到爆炸，底层系统上就跟别人差出好几个linux，约等于好几十个windows，恩。。。本着只要功夫深，铁杵（学渣）磨成针的不灭信念，决心洗心革面，静心刷题，修炼内功，争取从量变到质变，打造出更好的OS。题记就先写到这里。闲言碎语不要讲，先写几道题。我会把Leetcode上AC的我的答案写上来，在加上我毫无逻辑的学弱的解题思路，抛砖引玉，要刷题的各位亲，大家一起加油！

Comments

Post a Comment

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 我开始用的是暴...
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] 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，因为，这样我们就少移动了一次，最后一...
Keep reading