[每天两道题]坚持找到工作为止

66. Plus One
这道题我曾经经常面试别人，哈哈哈。
这道题没有什么算法的运用，就是单纯地考对语言的运用熟练度。本题主要难点在于进位的处理，最后的答案可能比原来的数组多一位。然后就是进位的处理，我自己实际面试过程种，90%的人都会卡在进位的处理，以及数组长度可能多一位上面。

其实进位处理已经是基本常识，连这个都不会，那么我认为你根本没有准备过如何面试。一个刷过题的人我认为起码要知道用mod去计算当前位置，用/去计算进位。

然后就是多一位的问题，其实只有极端情况才会多一位，也就是数组中每一位都是9。并且多一位的话，最后的数字一定是100 1000 10000这样的整数。所以最后若是多一位只要定义一个新数组，第一位更新成1就可以了。
当然我没有这么写，啊哈哈，因为我自己看了答案才知道这个

1. class Solution {
   
2.     public int[] plusOne(int[] digits) {
   
3.         int carry = 0;
   
4.         digits[digits.length - 1]++;
   
5.         for(int i = digits.length - 1; i >= 0; i--) {
   
6.             if(digits[i] + carry > 9) {
   
7.                 digits[i] = (digits[i] + carry) % 10;
   
8.                 carry = 1;
   
9.             }else{
   
10.                 digits[i] = digits[i] + carry;
    
11.                 carry = 0;
    
12.             }
    
13.         }
    
14.         
    
15.         if(carry > 0) {
    
16.             int[] rs = new int[digits.length + 1];
    
17.             rs[0] = 1;
    
18.             return rs;
    
19.         }
    
20.         return digits;
    
21.     }
    
22. }

复制代码

67. Add Binary
这道题其实没有难度，唯一就是数学知识，如何像十进制那样处理二进制的进位。其实还是一样的，mod 2得出本位置的数字，/ 2得出进位。
就没有了，这道题我感觉非常没意思，故意刁难人，实际面试中，这种题我都会不会出给对方的。

1. public String addBinary(String a, String b) {
   
2.         int carry = 0;
   
3.         char[] ac = a.toCharArray();
   
4.         char[] bc = b.toCharArray();
   
5.         
   
6.         int ia = ac.length - 1;
   
7.         int ib = bc.length - 1;
   
8.         
   
9.         StringBuilder sb = new StringBuilder();
   
10.         while(ia >= 0 || ib >= 0) {
    
11.             int n1 = 0;
    
12.             int n2 = 0;
    
13.             if(ia >= 0) n1 = ac[ia] - '0';
    
14.             if(ib >= 0) n2 = bc[ib] - '0';
    
15.             
    
16.             int sum = n1 + n2 + carry;
    
17.             sb.append(sum % 2);
    
18.             carry = sum / 2;
    
19.             ia--;
    
20.             ib--;
    
21.         }
    
22.         if(carry > 0) sb.append(carry);
    
23.         
    
24.         return sb.reverse().toString();
    
25.         
    
26.     }

复制代码

68. Text Justification
这道题非常恶心，和上一道题一样恶心，没有任何算法技巧，单纯地考验编程。实际面试中，这种题根本不可能写对。

不过，我的做法，我认为比其他方法都更好更直观一些。因为我运行的结果是最快，且代码行数远远少于其他大部分答案。

说说我的解法。
首先，我们要解决第一个问题，是每一行都有哪些单词。这个问题，其实是一个滑动窗口问题，我们定义左右两个指针left right ，每次移动一次右指针right，然后判断窗口里的单词拼起来会不会超过最大长度。
这个判断就是第一个难点，单词之间必然有一个空格，所以若是窗口里面有n个单词，这n个单词一共有m个字母，那么它们之间至少有n -1个空格。所以此时，窗口内，最后拼出来的字符串，起码的长度有 n - 1 + m 个字符长。所以我们判断条件是，若是string[right]也加入窗口了，然后n - 1 + m + words[right]> maxWidth了，那么说明此时right指针的位置，就是一个换行的地方。也就是区间[left, right - 1]里面的单词，就是一行。

然后我们考虑如何更新左右指针，可以发现，右指针是可以无脑一步一步向右移动的，所以这意味着我们可以用一个for循环，来更新右指针。而左指针更新也很简单，只要我们发现换行了，那么我们就把left指到当前righ的位置。伪代码就是:

m = 0;(m表示窗口里面有多少个字符）
n = 0;（n表示窗口里有多少个单词);
for(int right = 0; right < words.length; right++) {
        if(n - 1 + m  + words[i]> maxWidth) {
        String row = helper(left, right - 1);//helper函数用于拼接出符合要求的一行。我们拼接[left, right-1]这几个单词
        left = right;
        m = words[right];
        n = 1;
}else{
        m = m +  words[right]
        n = n + 1;
}
}

这样，我们就可以找出每一行需要处理的单词了，然后用helper函数单独处理每一行。注意此时，当right走到终点结束之后，left并没有走到终点，这是因为我们需要特殊处理最后一行。因为最后一行我们不需要扩展空格了，直接拼接起来即可，所以我们把最后一行的处理加入刚才的代码中

m = 0;(m表示窗口里面有多少个字符）
n = 0;（n表示窗口里有多少个单词);
for(int right = 0; right < words.length; right++) {
        if(n - 1 + m  + words[i]> maxWidth) {
        String row = helper(left, right - 1);//helper函数用于拼接出符合要求的一行。我们拼接[left, right-1]这几个单词
        left = right;
        m = words[right];
        n = 1;
}else{
        m = m +  words[right]
        n = n + 1;
}
}
//处理最后一行
StringBuilder sb = new StringBuilder();
for(int i = left; i < words.length; i++){
     sb.append(words[i]);
     if(i < words.length - 1) sb.append(" ");
}
while(sb.length() < maxWidth) sb.append(" ");

至此，我们的如何找出每一行的单词，并且处理最后一行，这个主逻辑就完成了。接下来，我们要处理如何正确地写出helper，也就是如何拼接单词，处理空格。

－－－－－－－－－－－－－－－－－－－－－－
这个题第二个难度就在于，怎么样去处理空格的问题，它给的说法非常复杂，说要尽量平均，若是无法平均，尽量左边多于右边。

这个描述，我认为是出题者为了增加难度，故意说得很模糊。很多答案都用平均数，然后再计算mod等等。
我后来仔细想了想，突然发现这个说辞简直就是坑爹，为了增加难度而增加难度而已。它的意思其实非常简单。就是数手指游戏。

首先，我们知道每一行的长度，一定是maxWidth, 并且我们知道一共有n个单词，这n个单词，一共有m个字符。
那么我们马上可以知道，这一行一共有 maxWidth - m 个空格。并且这些空格，要按照要求填在n - 1个坑里。

比如举个例子example  of text
这个例子中，我们一共有n = 3个单词， 这3个单词，一共有13个字符，它的maxWidth ＝ 16。也就是要求一行有16个字符，所以这一行一共有16 －13 ＝ 3个空格，要填在3 - 1 = 2个坑里。

填坑的方法其实非常简单，我们初始化一个数组，长度为坑的长度。每一个数组，表示每一个坑我们要填多少空格，顺序就是左到右。比如这个例子中，我们就建一个数组[0,0]。
然后我们从左到右，每一位加1 ，并且记录我们加了多少次1了，若是到末尾了，但是加的1的次数没有到3个空格，我们就从头再来。直到我们填1的次数等于这一行需要的空格数：

[0, 0] -> [1,0] -> [1,1] -> [2, 1];
那么此时，这个数组，就表示我们每一个坑有多少个空格。就这么简单，无需计算什么余数，平均数之类的。非常无脑。

那么我们计算出每一个坑需要填的空格数之后，这个题所有的难点就都解决完了。
接下来就拼字符串好了，先填单词，再填坑，再填单词，再填坑……

注意这里有一个特殊情况，就是这一行只有一个单词的时候，此时坑的数量依然是1，我们在初始化填坑数组的时候，不能无脑定义成int[right - left]。因为right 可能等于left。也就是一行有2个单词，只有一个坑，一行有一个单词，也有一个坑。所以数组的长度len = right - left == 0? 1 : right - left;

这样，这道题就做完了，接下来只要拼字符就可以了，没有任何难度。那么我们的代码就是

1. class Solution {
   
2.     public List<String> fullJustify(String[] words, int maxWidth) {
   
3.         List<String> rs = new ArrayList<>();
   
4.         
   
5.         int rowLen = 0;
   
6.         int left = 0;
   
7.         for(int i = 0; i < words.length; i++) {
   
8.             if(rowLen + (i - left) + words[i].length() > maxWidth) {
   
9.                 rs.add(helper(left, i - 1, words, maxWidth, rowLen));
   
10.                 left = i;
    
11.                 rowLen = words[i].length();
    
12.             }else{
    
13.                 rowLen += words[i].length();
    
14.             }
    
15.         }
    
16.         
    
17.         //last row
    
18.         StringBuilder sb = new StringBuilder();
    
19.         for(int i = left; i < words.length; i++){
    
20.             sb.append(words[i]);
    
21.             if(i < words.length - 1) sb.append(" ");
    
22.         }
    
23.         
    
24.         while(sb.length() < maxWidth) sb.append(" ");
    
25.         rs.add(sb.toString());
    
26.         return rs;
    
27.     }
    
28.    
    
29.     private String helper(int left, int right, String[] words, int max, int w_len) {
    
30.         int spacelen = right - left == 0 ? 1 : right - left;
    
31.         int[] space = new int[spacelen];
    
32.         int totalspace = max - w_len;
    
33.         int idx = 0;
    
34.         while(totalspace > 0) {
    
35.             space[idx]++;
    
36.             idx = idx == space.length - 1 ? 0: idx + 1;
    
37.             totalspace--;
    
38.         }
    
39.         
    
40.         idx = 0;
    
41.         StringBuilder sb = new StringBuilder();
    
42.         for(int i = left; i <= right; i++) {
    
43.             sb.append(words[i]);
    
44.             int len = sb.length();
    
45.             if(idx < space.length){
    
46.                 while(sb.length() < len + space[idx]) sb.append(" ");
    
47.                 idx++;
    
48.             }
    
49.         }
    
50.         
    
51.         return sb.toString();
    
52.         
    
53.     }
    
54. }

复制代码

69. Sqrt(x)
数学题，记住公式 —— 牛顿法 Xn+1 = (Xn + a / Xn ) / 2
n越大，精度越高。一直更新Xn,直到 |Xn * Xn - a| > 0.00001即可

1. class Solution {
   
2.     public int mySqrt(int x) {
   
3.         double n = 1.0;
   
4.         double p = 1e-5;
   
5.         while(Math.abs(n * n - x) > p) {
   
6.             n = (n + (x / n)) / 2.0;
   
7.         }
   
8.         return (int)n;
   
9.     }
   
10. }

复制代码

70. Climbing Stairs
这个题一看就是dp题，公式也非常好写//dp[n] = dp[n] + dp[n - 1]; 其实就是斐波那契数列。

1. class Solution {
   
2.     public int climbStairs(int n) {
   
3.         //dp[n] = dp[n] + dp[n - 1];
   
4.         if(n < 3){
   
5.             return n == 1 ? 1 : 2;
   
6.         }
   
7.         int[] dp = new int[n + 1];
   
8.         
   
9.         dp[0] = 0;
   
10.         dp[1] = 1;
    
11.         dp[2] = 2;
    
12.         
    
13.         for(int i = 3; i <= n; i++) {
    
14.             dp[i] = dp[i - 1] + dp[i - 2];
    
15.         }
    
16.         return dp[n];
    
17.             
    
18.     }
    
19. }

复制代码

71. Simplify Path
这道题没什么难度，就是split“/"之后，看string[]中每一个string是什么。然后用一个stack记录。若是..就出栈。若是“ . ” 或者 “”就跳过。其它情况也就是字母或者横线，就入栈。

最后把栈里的字符串拼接，两两用"/“分开，最后开头补一个"/"即可。注意stack是倒叙的，所以生成答案的时候也要反着加字符串；

1. class Solution {
   
2.     public String simplifyPath(String path) {
   
3.         String[] strs = path.split("/");
   
4.         
   
5.         Stack<String> s = new Stack<>();
   
6.         
   
7.         for(int i = 0; i < strs.length; i++) {
   
8.             if(strs[i].equals("..")) {
   
9.                 if(!s.isEmpty()) s.pop();
   
10.             }else if(strs[i].equals(".") || strs[i].equals("")) {
    
11.                 continue;
    
12.             }else{
    
13.                 s.push(strs[i]);
    
14.             }
    
15.         }
    
16.         
    
17.         String rs = "";
    
18.         while(!s.isEmpty()) {
    
19.             rs = s.pop() + rs;
    
20.             rs = "/" + rs;
    
21.         }
    
22.         rs = rs == "" ? "/" : rs;
    
23.         return rs;
    
24.     }
    
25. }

复制代码

72. Edit Distance
这道题很难，多年前我店面时居然遇到过。当时完全不会做，如今花半个小时可以想出来。也算是进步。

这个题是二维dp。 dp[i][j]表示 w1[0~i] 和w2[0~j]转化的最小次数。这个是题目的第一个难度，如何确定dp的含义，其实只要知道是dp。那么只要问自己一个问题：怎么样能缩小问题规模？
这样就可以得出结论，缩短字符串的长度。但是怎么缩小呢？我们发现若是两个字符串最后一个字符一样，那么显然可以拿掉这两个一样的字符串，只比较前面的。所以我们就可以想到dp[][]的含义就是 w1[0~i] 和w2[0~j]转化的最小次数。

同时我们也得出了第一个转化公式 ： w1[i] == w2[j] dp[i][j] = dp[i - 1[j - 1];
然后我们再想不等于的情况，其实也很简单，不一样的话，那么
要么是去掉一个字符，也就是dp[i - 1][j] + 1
要么是换一个字符,dp[i - 1][j - 1] + 1
要么是增加一个字符 dp[i][j - 1] + 1

所以，我们取这三个值的最小值就可以了。

最后看如何初始化dp。由于有""的情况，其实这个题给你""的情况，是帮助你解题的。所以我们dp的长度必须比字符串多一位，处理0长度空字符串。
那么初始化也非常简单了，任何一个字符串为0，那么修改次数就是另一个字符串的长度，所以 dp[0][j] = j  dp[i][0] = i。
然后从i= 1， j = 1开始挨个按照上面的公式计算即可。所以代码其实非常简单：

1. class Solution {
   
2.     public int minDistance(String word1, String word2) {
   
3.         // if w1[i - 1] == w2[j - 1]
   
4.         //     dp[i][j] = dp[i - 1][j - 1];
   
5.         // else
   
6.         //     dp[i][j] = dp[i][j - 1] + 1,  dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1
   
7.         
   
8.         // dp[i][0] = w1[i] == i
   
9.         // dp[0][j] = w1[0] == j
   
10.       
    
11.         
    
12.         
    
13.         int len1 = word1.length();
    
14.         int len2 = word2.length();
    
15.         if(len1 == 0) return len2;
    
16.         if(len2 == 0) return len1;
    
17.         int[][] dp = new int[len1 + 1][len2 + 1];
    
18.         
    
19.         char[] w1 = word1.toCharArray();
    
20.         char[] w2 = word2.toCharArray();
    
21.         
    
22.         for(int i = 0; i <= w1.length; i++) {
    
23.             dp[i][0] =i;
    
24.         }
    
25.         
    
26.         for(int j = 0; j <= w2.length; j++) {
    
27.             dp[0][j] = j;
    
28.         }
    
29.         
    
30.         for(int i = 1; i <= len1; i++) {
    
31.             for(int j = 1; j <= len2; j++) {
    
32.                 if(w1[i - 1] == w2[j - 1]) {
    
33.                     dp[i][j] = dp[i - 1][j - 1];
    
34.                 }else{
    
35.                     dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
    
36.                 }
    
37.             }
    
38.         }
    
39.         
    
40.         return dp[len1][len2];
    
41.     }
    
42. }

复制代码

73. Set Matrix Zeroes
这个题难度在于in-place。若是即时更新，那么我们就不知道哪些是原来的0，那些是更新出来的0。所以我们要找个方法记录哪些列，或者哪些行需要更新。
最简单的方法，就是我代码写的样子。用两个set分别记录一下哪些行，哪些列需要更新。然后按照set里的内容更新即可。

若是要做到完全的o(1)空间复杂度，那么我们也可以用第一行，和第一列记录。
我们先扫一遍举证，看到m[x][y] ＝0。那么我们就把m[0][y] = 0, m[x][0] = 0;
这样我们第一行和第一列就等于之前的两个set，分别记录了那些行和列需要更新。然后我们再扫一遍矩阵，看到m[x][y] ＝ 1时候，若是m[x][0] == 1 || m[0][y] == 1。那么我们就把m[x][y]= 0;

但是这么做，我们不知道第一行或者第一列要不要更新，因为这俩行里面若是原来有0的话，会和更新进来的0混淆。所以。我们再开始之前，先扫一遍第一行和第一列，用两个boolean记录一下它们要不要更新，若是要更新，那么当其他格子都更新完之后，我们就更新它们为0.

1. class Solution {
   
2.     public void setZeroes(int[][] matrix) {
   
3.         Set<Integer> zi = new HashSet<>();
   
4.         Set<Integer> zj = new HashSet<>();
   
5.         
   
6.         for(int i = 0; i < matrix.length; i++) {
   
7.             for(int j = 0; j < matrix[0].length; j++) {
   
8.                 if(matrix[i][j] == 0) {
   
9.                     zi.add(i);
   
10.                     zj.add(j);
    
11.                 }
    
12.             }
    
13.         }
    
14.         
    
15.         for(int i : zi) {
    
16.             Arrays.fill(matrix[i], 0);
    
17.         }
    
18.         
    
19.         for(int j : zj) {
    
20.             for(int k = 0; k < matrix.length; k++)
    
21.                 matrix[k][j] = 0;
    
22.         }
    
23.     }
    
24. }

复制代码

74. Search a 2D Matrix
这个题没什么好说的，就是二分法标准模版，先竖着搜，找x，再横着搜找y。这里最大的坑，就是竖着搜的时候，要搜最后一列。也就是搜索m[m.length - 1]这一列。

不能用第一列也就是m[i][0]的原因是，当目标值比m[i][0]还大的的时候，其实你是不知道目标是在本行，还是在下一行的。因为都有可能，但是反过来，若是m[i][m.len - 1]比目标值小，那么目标值一定在下一行。
我一开始没有意识到这一点，所以当矩阵只有一行的时候，我的代码在竖着找的时候，总是返回目标值在第二行，但是因为矩阵只有一行，这导致我的代码出现越界错误。

后来看了答案才反应过来，原来这里也有门道。
最后我们的代码就是[/i][/i][/i][i][i][i]

1. class Solution {
   
2.     public boolean searchMatrix(int[][] matrix, int target) {
   
3.         int x = 0 ,y = matrix.length - 1;
   
4.         int k = matrix[0].length -1;
   
5.         if(target < matrix[0][0] || target > matrix[matrix.length-1][matrix[0].length-1]) return false;
   
6.         while(x <= y) {
   
7.             int mid = x + ((y - x) >> 1);
   
8.             if(matrix[mid][k] == target) return true;
   
9.             else if(matrix[mid][k] > target) {
   
10.                 y = mid - 1;
    
11.             }else if(matrix[mid][k] < target) {
    
12.                 x = mid + 1;
    
13.             }
    
14.         }
    
15.         
    
16.         int rs_x = x;
    
17.         x = 0;
    
18.         y = matrix[0].length - 1;
    
19.         
    
20.         while(x <= y) {
    
21.             int mid = x + ((y - x) >> 1);           
    
22.             if(matrix[rs_x][mid] == target) return true;
    
23.             if(matrix[rs_x][mid] > target) {
    
24.                 y = mid - 1;
    
25.             }else x = mid + 1;
    
26.         }
    
27.         
    
28.         return matrix[rs_x][x] == target;
    
29.         
    
30.     }
    
31.    
    
32.    
    
33. }

复制代码

[/i][/i][/i]

76. Minimum Window Substring
经典的滑动窗口题。
这题难度在于，
第一，如何判断窗口里，已经包含所有的字符。
第二，如何伸缩窗口

由于给定的字符串，可能有重复的字符，所以我的办法就是建立一个hashmap。key是t里面的字符，value是这个字符的个数。
所以若是t是aaaaa这样的，最后map = { a : 5 }

然后我们再用一个int count = 0，记录窗口了，出现的字符的次数。
那么怎么记录呢？
办法就是，我们扫描字符串，若是遇到一个字符s[i]，是map的一个key。 那么就说明这个字符是在t里面，也就是窗口里出现了一个要包含的字符。所以我们把map.get(s[i]) - 1，也就是map里的计数减1。
此时我们要判断一下，这个字符，是不是一个多余的字符。
比如我们t = abc。 s = abbc
那么我们在扫描abbc的时候，会遇到两个b之后，才会遇到第一个c，此时，也我们遇到第二个b的时候，会让map里面，map.get(b) = -1。那么此时-1就可以认为，是一个多余的b，我们不需要增加count的计数。
反过来，当我们遇到第一个b的时候，是map.get(b) = 0 >=0，那么就意味着这个b是个需要统计到结果里的字符，那我们就要把count ++;
当count = t.length()的时候，说明我们窗口里已经包含了所有的需要的字符(甚至可能还会多一些）。那么我们就把此时窗口里的子串截取出来，若是比较短，那么更新一下最后答案为当前的字串。

第二，如何伸缩窗口
当上面的步骤，显然我们每次都可以伸展右侧。那么什么时候缩小窗口呢。

当然就是我们找到一个答案的时候，我们就要缩小左边的窗口了。
我们建立一个Deque，每次在s里面遇到一个t里面的字符，我们就把它的坐标放进Deque里面。
当我们得到一个答案的时候，deque里面的[head，trail + 1]就是一个字串。然后我们开始弹出head。注意，每弹出一个 head，我们就要更新一下map里面head对应的计数。把计数加1，表示我们需要再找下一个head。此时，若是计数加1之后依然<=0，说明这是个多余的字符，我们需要继续弹出下一个head，再更新计数，直到我们弹出一个 head，更新完计数之后，它的计数> 0了，说明它是一个必须要存在的字符，我们就结束循环不再弹出了。

这样，这个问题就解决了。其实这个题不算特别难，找字串一定是用滑动窗口。滑动窗口，伸缩和判断窗口合法性，永远是最难的点。

所以，我们的答案就是：

1. class Solution {
   
2.     public String minWindow(String s, String t) {
   
3.         String rs = "";
   
4.         Map<Character, Integer> map = new HashMap<>();  
   
5.         
   
6.         for(int i = 0; i < t.length(); i++) {
   
7.             int temp = map.getOrDefault(t.charAt(i), 0);
   
8.             map.put(t.charAt(i), temp + 1);
   
9.         }
   
10.         
    
11.         Deque<Integer> dq = new LinkedList<>();
    
12.         int count = 0;
    
13.         int left = 0;
    
14.         char[] sc = s.toCharArray();
    
15.         
    
16.         for(int i = 0; i < sc.length; i++) {
    
17.            
    
18.             char c = sc[i];
    
19.             if(map.containsKey(c)) {
    
20.                 int temp = map.get(c) - 1;
    
21.                 map.put(c, temp);
    
22.                
    
23.                 if(temp >= 0) count++;
    
24.                 dq.offer(i);
    
25.             }
    
26.             
    
27.            
    
28.             while(!dq.isEmpty() && count == t.length()) {
    
29.                 String temprs = s.substring(dq.peekFirst(), dq.peekLast() + 1);
    
30.                 if(temprs.length() < rs.length() || rs.length() == 0) rs = temprs;
    
31.                
    
32.                 int tempIndex = dq.pollFirst();
    
33.                 char tempc = sc[tempIndex];
    
34.                 int tempCount = map.get(tempc);
    
35. 
    
36.                 if(tempCount < 0) {
    
37.                     map.put(tempc, tempCount + 1);
    
38.                 }else{
    
39.                     map.put(tempc, tempCount + 1);
    
40.                     count--;
    
41.                     break;
    
42.                 }
    
43.             }  
    
44.         }
    
45.         return rs;
    
46.     }
    
47. }
    

复制代码