学渣的刷题笔记

https://leetcode.com/problems/guess-number-higher-or-lower/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 is higher or lower. You call a pre-defined API  guess(int num)  which returns 3 possible results ( -1 ,  1 , or  0 ): -1 : My number is lower 1 : My number is higher 0 : Congrats! You got it! Example: n = 10, I pick 6. Return 6. 看着就是二分搜索，但是每太看懂他的意思，他的guess function用来干啥的呢。 先二分搜索试试看。这个二分跟普通的二分就一点不一样，不是让你二分search 而是二分看是什么数，换汤不换药，以前是已知数让你看在不在，现在是他告诉你大小，你自己缩小范围，信息点给的是一样的，guess（int num）这个函数来指示大了还是小了，我们好挪动范围。这道题最神奇的地方在于，题目对-1， 和1这个返回值 的理解。我一开始就理解反了，真么着都不对，心塞塞，后来调过来就好了，呵呵。还有一个不能饶恕的错误，第一次提交竟然因为没检查low 比 high小 而Stack Overflow 了！不能再犯！ 但是感觉狗家给这个题不是很正常，边界条件要问好，估计这才是重点。 AC Solution, Recursion: public class Solution extends GuessGame { int result = 0; public int guessNumber(in...

[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...

https://leetcode.com/problems/add-strings/description/ Given two non-negative integers  num1  and  num2  represented as string, return the sum of  num1  and  num2 . Note: The length of both  num1  and  num2  is < 5100. Both  num1  and  num2  contains only digits  0-9 . Both  num1  and  num2  does not contain any leading zero. You  must not use any built-in BigInteger library  or  convert the inputs to integer  directly. 整体来说没什么难度啊，注意几个点的就好。 加法要尾巴对齐了加，如果一直有进位，就算一个string结束了也要继续加。 AC Solution： public class Solution { public String addStrings(String num1, String num2) { StringBuilder sb = new StringBuilder(); int l1 = num1.length(); int l2 = num2.length(); int carry = 0; int sum = 0; for(int i = l1 - 1, j = l2 - 1; i>=0 || j>=0 || carry == 1; i--, j--){ int n1 = i < 0 ? 0 : num1.ch...

[Leetcode]388. Longest Absolute File Path https://leetcode.com/problems/longest-absolute-file-path/#/description 据说这是google的OA题目, 改了一些, 原来是求图片文件的路径和, 这里只求最大的文件数, 但是思路还是一样的。 拿到题完全没有头绪。只是觉得\n \t很重要。无论如何肯定要\n不管你是不是属于同一个目录下面的。\t呢就是如果和前一个t一样多，就是同一个目录，如果多一个或者少一个就不是同一个目录了。开始觉得同一个目录里只要比末尾的长短就行了，因为前面是一样长的嘛。但是如果末尾的一个是file另一个是文件夹，这么想就不对，最末尾没文件，只有文件夹的不算到达file最长路径。 初步想法，这是一个找爸爸游戏，n就说明有新换行了，而3个t的爸爸就是2个t，2个t的爸爸就是1个t，1个t的爸爸就是没有t。但是如果按照这个思路想，复杂度是n 2 ，有什么办法可以是n复杂度呢？看过的不要看， 难道是DP？第一个可行的办法是Hashmap，存下来我们已知的路径，等看到它的自路径的时候，直接去找就好了。 解题思路： 思路一：HashMap解法 1. 用HashMap存下来不同深度的文件夹的长度； 2. 遇到file，更新最大file路径长度； 3. 遇到文件夹，更新HashMap里文件夹长度； 我们这里只要储存文件夹长度就行，因为遇到file其实就直接能算出结果了。然后遇到文件夹如果没有那个深度的对应map，就加进去，有的话就更新。Java里put这个函数，有的话直接更新，不用再判断一次了。 我一开始有个担心的地方，就是我们如果更新了这个深度的map，那上一个深度的文件夹长度就不见了啊。但是，这个担心是多余的，因为整个扫的过程是顺序的，我们到达了这个最新的文件夹的时候，上一个文件夹里面的文件已经都处理过了，不需要了。代码十分简洁。 思路二： Stack解法 细心地你一定可以发现，我们上面用HashMap的时候，如果遇到下一个文件夹的时候，可以overwirte上一个在深度map里的长度值。因为当你跳出更深的文件夹之后，来到深度浅的文件夹，以前的深度都没用了，因为上一段说了的原因，就是顺序的读取字符串，我们已经把深度...

[Leetcode]71. Simplify Path 题目链接 https://leetcode.com/problems/simplify-path/#/description 这道题一眼望过去好像也不难的样子呢。关键在于知道并理解linux路径结构。然后就是个玩字符串的事情了。 根据题目来总结规律 Given an absolute path for a file (Unix-style), simplify it. For example, path =  "/home/" , =>  "/home" path =  "/a/./b/../../c/" , =>  "/c" click to show corner cases. Corner Cases: Did you consider the case where path =  "/../" ? In this case, you should return  "/" . Another corner case is the path might contain multiple slashes  '/'  together, such as  "/home//foo/" . In this case, you should ignore redundant slashes and return  "/home/foo" . 这道题让简化给定的路径，光根据题目中给的那一个例子还真不太好总结出规律，应该再加上两个例子 path =  "/a/./b/../c/" , =>  "/a/c"和path =  "/a/./b/c/" , =>  "/a/b/c"，  这样我们就可以知道中间是"."的情况直接去掉，是".."时删掉它上面挨着的一个路径，而下面的边界条件给的一些情况中可以得知，如果是空的话返回"/"，如果有多个...

这道题果然是升级版，思路不像他的弱化版那么好想了。虽然是排序但是排序拍的稍稍有点乱，要捋一捋。猛然醒悟，原来 上面一篇 说的 不太好的O(n)的算法 是这道题的解法。。。 先贴代码, AC答案： public class Solution { public boolean searchMatrix(int[][] matrix, int target) { //Two possible start point, bottom left and top right. Other two corner can not help us exclude numbers //Four edges all have limititions, only corner can make certain decision if(matrix == null || matrix.length == 0){ return false; } int m = matrix.length; int n = matrix[0].length; // i, j is the left bottom corner int i = m - 1; int j = 0; while(i>=0 && j<n){ if(target > matrix[i][j]){ j++; } else if(target < matrix[i][j]){ i--; } else{ return true; } } return false; } } 解题思想呢有点像dp。刚开始没理解思路的时候，上来就写，没找好四个角，出现了一个问题，if里面呢，不知道什么时候往左，什么时候往下，if里面还有个if，后来发...

74. Search a 2D Matrix 这道题是medium的，但是那道题第一反应就是二分法。聪明的我建了个数组，把2D的数组瞬间降低纬度变成1D，low到爆炸有木有，然后正常的二分顺利做出来，当然时间只击败了个位数个百分比。。。这是第一反应的代码。简单的题我就不讲思路了哈，直接上代码。就是这个简单的二分法，我竟然都不是一次写对的，忘了mid-1和mid+1，可耻！下不为例。不写这俩，有时候就会陷入死循环，无法让high比low小了，切记不可再犯。 public class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix == null || matrix.length == 0){ return false; } ArrayList<Integer> list = new ArrayList<Integer>(); for (int i=0; i<matrix.length; i++){ for(int j=0; j<matrix[0].length; j++){ list.add(matrix[i][j]); } } int n = list.size(); int[] l = new int[n]; int index = 0; for(int i : list){ l[index++] = i; } return binarySearch(l, target, 0, n-1); } private boolean binarySearch(int[] list, int target, int low, int high){ if(high < low){ return false; } ...

[Leetcode] 28. Implement strStr() 这道题在leetcode里面是easy，显然，leetcode是没希望我们用KMP来解题的。但是KMP是最优策略。我们就用KMP来尝试解题，也借用此题，来彻底弄懂KMP。这篇 从头到尾彻底理解KMP 文章  介绍KMP炒鸡详细而且深入浅出。 这个视频 讲的也很好当然，这个题要是能用API的话，String.indexOf()秒搞定。。。这篇文章也很好 KMP算法详解 题目大意： 在一串字符串中，找到匹配串。 解题思路： 1. 最简单的暴力破解。一个一个对比，匹配上，上（i）下(j)全移动到下一个，匹配不上，j返回起点0，i = i-j+1. i 向后挪一格。复杂度O(mn)的我的暴力代码： public class Solution { public int strStr(String haystack, String needle) { int l1 = haystack.length(); int l2 = needle.length(); int result = -1; if(l2==0){ return 0; } if(l1 == 0){ return result; } int i=0; int j=0; while(i&ltl1 && j&ltl2){ if(haystack.charAt(i) == needle.charAt(j) ){ i++; j++; } else{ i = i-j+1; j = 0; } } if(j == l2){ result = i-j; } ...