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

8. String to Integer (atoi)
题目大意：
给一个string，要求你识别出其中包含的数字，数字可以是负数的。
然后有一些规律，比如数字不能包含在字符串里面。前面必须是空格，或者单独一个正负号。数字后面可以链接字符或者.。
若是数字太大或者太小溢出的话，就返回int的最大或者最小值。

题目分析和解答：
还是老规矩，把string 当成是一个array。
这个题不同于之前我们遇到的那种在array里面找到某些元素。这个题其实就是array另一种大类别，根据某种规则，生成一个新的array。
虽然最后结果返回的是数字，但是其实也是从字符转化而来。

这类atoi的问题，有一个万能做法就是有限状态机。
我自己是无脑用状态机去讨论各种条件的，否则就要用DP去进行复杂的if else判断。DP题通常都太难，在面试中效果不好，前几年大厂流行了一阵子，现在好像又都尽量不出DP题了。

我自己是用有限状态机去解答的。
有限状态机就是你定义一个矩阵，矩阵的行数，表示你输入了一个东西，可以是字符，可以是数字等等。矩阵的列数，表示某种状态。
aoti问题中，行和列组合起来，就是输入了某个东西之后的状态。

通常，输入我们就选择string中所有字符的类型，比如数学，符号，点，空格和字母。
状态，我们就是输入＋开始和结束状态。

然后我们就对着填表就可以了。这里不做详细说明，很简单就能理解。
另外有限状态机是游戏引擎的核心之一，游戏引擎本质上就是有限状态机，根据用户的输入产生不用的结果。

这道题除了有限状态机，我想重点是溢出的判断。这里我们可以发现，我们生成数字的时候，依然是从高位生成到低位的。也就是42我们先生成4，再生成2。

那么判断溢出的时候，当然就立刻可以运用上一道题目中的方法，我们依然是判断倒数第二步，一旦发现倒数第二步的时候，数字已经大于integer.max_value ／10 ，或者等于integer.max_value ／10但是 接下来最后一位大于7，那么我们就知道数字已经溢出了，此时根据题目要求，我们就不用进行任何操作了，根据正负号，直接返回integer.MAX_VALUE或者Integer.MIN_VALUE即可。这样判断非常方便和实用。
所以leetcode仔细品读，可以发现早期的题目安排得还是很有趣的。

所以我的答案就是，不会有限状态机的同学可以看看这个矩阵是怎么定义的 －

1. public int myAtoi(String s) {
   
2.         int[][] states ={
   
3.         //      init num char -   +  blank  end  re 0
   
4.         // state 0 ,  1,  2,  3,  4,   5,    6,   7  
   
5.                 {1,   1,  7,  1,  1,   1,    6,   7},//input is a num
   
6.                 {2,   6,  7,  7,  7,   7,    7,   7},//input is a char or .
   
7.                 {3,   6,  7,  7,  7,   7,    7,   7},//input is a -
   
8.                 {4,   6,  7,  7,  7,   7,    7,   7},//input is a  +
   
9.                 {0,   6,  7,  7,  7,   7,    7,   7}, //input is a blank
   
10.             
    
11.         };
    
12.         
    
13.         int state = 0;
    
14.         int number = 0;
    
15.         int sign = 1;
    
16.         char[] sc = s.toCharArray();
    
17.         
    
18.         for(char c : sc){
    
19.            
    
20.             if(state == 6){
    
21.                 return sign * number;
    
22.             }
    
23.             
    
24.             if(state == 7){
    
25.                 return 0;
    
26.             }
    
27.             
    
28.             if(c >= '0' && c<= '9'){
    
29.                 state = states[0][state];
    
30.                 if(number > Integer.MAX_VALUE / 10 ||
    
31.                   (number == Integer.MAX_VALUE / 10 && (c-'0') > 7) ){
    
32.                     return sign > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
    
33.                 }
    
34.                 number = number * 10 + (c - '0');
    
35.             }else if((c >= 'a' && c <= 'z') ||
    
36.                      (c >= 'A' && c <='Z') ||
    
37.                      c == '.'){
    
38.                 state = states[1][state];
    
39.             }else if(c == '-'){
    
40.                 if(state == 0) sign = -1;
    
41.                 state = states[2][state];
    
42.                
    
43.             }else if(c == '+'){
    
44.                 state = states[3][state];
    
45.             }else if(c == ' '){
    
46.                 state = states[4][state];
    
47.             }
    
48.         }
    
49.         
    
50.         if(state == 6 || state == 1){
    
51.             return sign * number;
    
52.         }
    
53.         return 0;
    
54.     }

复制代码

9. Palindrome Number
题目大意
给你一个数字，让你判断，这个数字是不是一个回文串。也就是是轴对称的数字，比如2021年12月2日，写起起来就是20211202 。这个数字反过来还是20211202 ，那天有个热搜叫做对称日，实际上就是指这个数字是一个回文串。

题目分析和解答

这道题可以说非常简单了。但是面试如果遇到这种简单题，就对你可能有点要求了，不能完全简单地直接作答。
比如这个题最普通的思路就是转换成string，然后把它翻转过来，在比较是不是原来的string相同。
直接写几行code是很容易的，所以此时面试官可能会看看你对编程语言的熟练度。
比如我是用java，那么面试官就会要求我 － 请问一行code写出解答

1. public boolean isPalindrome(int x) {   
   
2.         return String.valueOf(x).equals(new StringBuilder(String.valueOf(x)).reverse().toString());
   
3.     }

复制代码

再比如，就是题目中要求的，不能转换成string，进行解答

1. public boolean isPalindrome(int x) {   
   
2.          if(x < 0 || (x % 10 == 0 && x != 0)) {
   
3.             return false;
   
4.         }
   
5. 
   
6.         int revertedNumber = 0;
   
7.         while(x > revertedNumber) {
   
8.             revertedNumber = revertedNumber * 10 + x % 10;
   
9.             x /= 10;
   
10.         }
    
11.         return x == revertedNumber || x == revertedNumber/10;
    
12.     }

复制代码

10. Regular Expression Matching
题目大意
这道题给你两个字符串s和p。其中字符串p，是一个正则表达式。让你判断字符串s，是不是匹配这个表达式。

这里，这个正则表达的规则，比普通的更简单一些：点表示匹配任意一个字符。星号表示前面一个字符可以有从0到无数个。
注意这里隐含了一种情况，就是“.*"，意思就是可以有无数个点，也就是可以匹配任意字符串。

题目分析和解答
这道题是hard，是一道非常非常非常难的题。也是一道好题，它的点赞很高，但是提交正确率只有28.2%，可以说是最难的几十道题之一。
这道题最常规的做法，是DP － 动态规划。但是我个人是不太理解的。我这里介绍一个我自己的思路，虽然按照这个思路我写出来的答案，效率非常低，有时候会报超时。但是也是一种万能的套路吧……之后类似的题应该都能用这个模版解答。

首先，这个是一个字符串匹配的题，还是老规则array这种匹配的问题，万能办法就是状态机。
但是不同于之前的aoti问题，这个正则表达式的状态机，不是一个固定的东西，而是根据你输入的正则表达式的不同，而有不同。

比如 "a*bc"                                 
它的状态机就是 ： start - >  a*  - > b - > c  -> end
                                             |_|
a*下面那一圈表示它可以指向自己。
这个状态机，其实就是一个linkedlist，它里面的节点，都代表一个个状态。每个状态的值，就是一开始给我们的字符串p，也就是正则表达式里面的某一个字符。并且这个状态的前后顺序，和正则表达式里面字符的顺序是一致的。

然后就是start星号的处理，星号其实就是指，某一个状态，它的下一个状态，可以是正则表达式里下一个字符，也可以是自己。就如同例子里的a状态。

然后我们给出的字符串s，其实就是指令，每一个指令就是字符串s里每一个字符。
比如 s = aabc

那么输入的指令就是 a -> a -> b -> c
我们说，这个s是可以和p匹配的，本质就是说，输入完指令之后，这个状态机可以抵达终点。

比如还是这个例子，我们按顺序输入a 、a、b、c。
第一个a输入，此时状态机的状态是在第一个a*节点。此时是匹配的，那么它的下一个状态可能有两个
           状态1，它移动到了下一个节点 状态b，
           状态2，它回到了a*这个状态。

第二个a输入，此时由于可能有两个状态，
          若是在状态b节点，那么就不匹配了，这条路不通。。结束输入
          若是在状态a*节点，此时是匹配的，那么它的下一个状态还是可能有两个
                 状态1，它移动到了下一个节点 状态b，
                  状态2，它回到了a*这个状态。
第三个b输入， 此时依然有两个可能的状态：
           若是在状态b节点，它是不匹配了，那么它移动到下一个状态c 节点。
          若是在状态a*节点，此时是不匹配的，此时不通。结束输入
第四个人c输入，此时是状态c节点，所以是匹配的。移动到end节点。

最后我们输入完成，检查是否状态机是否增经达到过end节点。我们看到之前的确有一条路可通让状态达到end节点，所以，s和p是匹配的。

同样，点的处理也很简单了：对于状态点，你输入任何字符都是给予匹配的，可以进行到下一个状态就可以了。

好，我们再看一下之前的输入的过程，以及状态机的状态的转化，可以看到，在输入过程中，状态机的状态是不确定的，虽然状态有限，但是流程可能有不同。
这种状态机，叫做非确定有限状态自动机 NFA

我想要找出非确定有限状态自动机所有的流程分支，大家应该马上就能意识到，遍历这些流程分支，其实就是遍历一个树。那么我们当然可以用递归的方法，去遍历它。

那么做到这里，实际上这个题就做完了。
解题的步骤就是：
1、根据p，构建一个NFA。也就是一个linkedlist。这个linkedlist里面每一个节点，包含三个属性，有没有星号，它的值，以及它下一个状态的列表
2、然后我们根据s，构建出输入的指令。
3、我们用递归的方法，去输入指令，并且根据指令去遍历状态机所有的状态。
4、若是我们最后有一次遍历，能走到终点，并且同时输入也正好完成，那么我们就认为s和p是匹配的。


这个套路，理论上可以解答所有正则表达式，或者字符串匹配的问题，只是非常麻烦，代码效率也很低。
不过它的好处是非常容易理解……

当然，这道题里面还有一些坑

第一个坑是如何判断遍历已经结束。
一开始我最简单的想法是 ： 输入完成，遍历也跟着就结束了，但是这是不对的。
比如 s = a , p = ab*。
这个答案显然是true。不过s输入一次之后，输入就结束了，但是p的遍历，却不能结束，因为b*有可能匹配一个空值，所以我们还要继续遍历，直到走到结束节点或者不匹配为止。

第二个坑是，当状态转移之后，它的下一次输入是什么
实际上，当a* 表示空值的时候，此时我们是跳过这个节点的，而不是视为匹配。
当跳过节点的时候，下一次输入我们要重新输入一次，而不是输入下一个指令。
所以实际上有三个动作可以产生状态转移 － 输入匹配，输入不匹配，跳过。

解决完这些坑之后，我们就得到了最后的答案。
实际上，这个答案可以优化，或者加速。

第一个优化就是 － 我们不必真正去定义一个nfa，我们也可以直接用双指针，去指向正则表达式，这样我们可以避免定义复杂的linkedlist数据结构。加快处理过程。

第二个优化，就是记忆化搜索，因为我们是用递归，完全遍历整个树。但是其实，很多分支的节点状态是一样的，所以我们可以用map，把已经运行过的状态，记录下来，下次再遇到这个状态，我们就直接拿出这个状态返回，不必再继续走它的子节点了。这样做其实就是DP，也就是动态规划。
若是dp特别熟练的人，可以立刻意识到这种解法，然后给出记录策略和分支讨论，得出最后的答案。
但是由于我没有这个本事，只能从头一步一步地推到暴力解。

我最后也没有写出优化过的代码，不过官方的答案，其实就是按照这两个优化给出的，大家可以参考官方的答案。
我自己的代码是

1. class Solution {
   
2.     boolean rs = false;
   
3.    
   
4.     public boolean isMatch(String s, String p) {
   
5.         char[] pc = p.toCharArray();
   
6.         List<Node> list = new ArrayList();
   
7.         
   
8.         for(int i = 0; i < pc.length; i++){
   
9.             char c = pc[i];
   
10.             
    
11.             if(c == '*'){
    
12.                 Node lastNode = list.get(list.size() - 1);
    
13.                 lastNode.hasStar = true;
    
14.                 list.set(list.size() - 1, lastNode);
    
15.             }else{
    
16.                 list.add(new Node(c, false));
    
17.             }
    
18.         }
    
19.         
    
20.         char[] sc = s.toCharArray();
    
21.         helper(sc, 0, 0, list);
    
22.         return rs;
    
23.     }
    
24.    
    
25.     private void helper(char[] sc, int pi, int sci, List<Node> list){
    
26.         if(rs) return;
    
27.         if(sci > sc.length - 1){
    
28.             while(pi < list.size()){
    
29.                 Node node = list.get(pi);
    
30.                 if(!node.hasStar){
    
31.                     return;
    
32.                 }
    
33.                 pi++;
    
34.             }
    
35.             rs = true;
    
36.             return;
    
37.         }
    
38.         if(pi > list.size() - 1){
    
39.             return;
    
40.         }
    
41.         char curr_c = sc[sci];
    
42.         Node curr_node = list.get(pi);
    
43.         
    
44.         if(sci == sc.length - 1 && pi == list.size() - 1 &&
    
45.           curr_node.isMatch(curr_c)){
    
46.              rs = true;
    
47.              return;
    
48.         }
    
49.         
    
50.         if(curr_node.isMatch(curr_c)){
    
51.             if(curr_node.hasStar){
    
52.                 helper(sc, pi, sci+1, list);
    
53.                 helper(sc, pi + 1, sci, list);
    
54.             }
    
55.             helper(sc, pi + 1, sci + 1, list);
    
56.             
    
57.         }else{
    
58.             if(curr_node.hasStar){
    
59.                 helper(sc, pi + 1, sci, list);
    
60.             }
    
61.         }
    
62.     }
    
63. }
    
64. 
    
65. class Node{
    
66.     public char value;
    
67.     public boolean hasStar;
    
68.    
    
69.     public Node(char V, boolean hasStar){
    
70.         this.value = V;
    
71.         this.hasStar = hasStar;
    
72.     }
    
73.    
    
74.     public boolean isMatch(char c){
    
75.         if(this.value == '.' || c == this.value)
    
76.             return true;
    
77.         return false;
    
78.     }
    
79. }
    

复制代码

11. Container With Most Water
题目大意
给你一个array，每一个数字表示一个高度。请你找出两个高度，它们组成的矩阵面积最大。这个矩阵的长度就是两个高度在array之间的距离，宽度是两个高度之间更小的那个。
如同这两个高度就是两个板，你往里面灌水，问哪两个板灌得水最多

题目分析和解答
这个题目非常经典，有1万多个赞。我几年前真正面试亚麻遇到的第一个算法题。

还是老规则，这个题给了我们一个array，让后让我们按照某种规律找其中的某些值。
我们知道若是要找的值是连续的，我们可以用滑动窗口。但是这个题的值不是连续的，而是分散于数组的不同位置，那么怎么办？

这种值分散在array不用的位置，最粗暴的方法，当然就是你要我找几个值，我就定义几个指针。这道题一次只要我们找两个值，所以我们定义两个指针就可以了～
所以暴力解当然就是写两个for循环，遍历所有两两的组合，就可以计算出所有的矩阵面积，然后记录一下最大值即可。

然后我们来优化一下，
记得two sum里，我们可以用map来加速查找，我一开始觉得这道题当然也可以这么做。比如我们用for loop从0号位开始挨个看高度，把这个高度当作右边的板子。
然后我们就去map里找左边，那么找什么样的左边呢？当然就是找比它高的板子，然后取离它最远的一个，计算一下面积，记录下来。若是没有比它高的，那么我们什么都不做。
最后我们把当前的板子高度记录在map里。便于之后查找。
但是这么想却有一个问题，我们并不知道比当前板子更高的板子，它们的高度到底有哪些值。这不同于two sum问题，two sum中，我们可以很确定地知道我们要找的另外一个值。但是这道题却是让我们找比当前值更大的某些值，那么此时hashmap就不太适合了。
当然我们还有其他的办法，比如我们可以用treemap或者priorirtqueue，把放进去的高度排序，每次我们一次弹出最高的一个，计算一下面积，直到弹出的高度小于当前值即可。
但是这么做，时间复杂度也很高，因为每次插入一个新的值我们都要重新排序。并且最坏的情况，我们每次还是要弹出所有的值。

那么这道题有没有更快的方法呢？
当然有，那就是贪心法了
这道题就是经典的贪心算法，我们从两边开始，因为我们的矩形要尽量的高，又要尽量的宽。所以我们一开始就看最宽的两个板子，记录一下此时的面积。

谈后，贪心算法要求我们改变其中一个值，让它尽可能地更好。因为我们只能向内移动板子，所以宽度一定是变小的，那么想让矩形面积更大的话，我们就只能期望找到一个更高的板子。那么显然，我们要移动的是两边较矮的那个板子，往内移动一格，期望接下来它的板子可以更高。直到两个板子重合。

所以，我们的最后的集体就是：
1、初始化，双指针指向头尾两边，记录此时的面积
2、向内移动较矮的一个指针
3、重新计算面积，看看是否要更新最大值。
4、重复2，直到两个指针相遇

这就是最后的程序逻辑。非常简单。
贪心法，真正的难点在于，我们怎么知道什么时候可以用贪心法？也就是什么样的问题可以用贪心法去解决，或者你怎么知道用贪心法得出来的答案，就一定是最优解？
可以用贪心算法解决的题目需要满足以下性质：
最优子结构：一个问题的最优解包含其子问题的最优解
贪心选择性：所求问题的整体最优解可以通过一系列局部最优的选择来到达，即通过贪心选择来达到
这个论述是非常模糊的，也非常难以理解。基本上，我认为我自己是不足以判断出什么题可以用贪心法去做的。这种类型的问题，恐怕只能依靠背诵。
当然，我认为暴力解法，加上对map的思考，是可以推理出什么题可以用贪心来解决的。只是目前我还没有总结出特别好的套路。若是有大神可以指点一下就好了
所以，我的最后的答案就是：

1. class Solution {
   
2.     public int maxArea(int[] height) {
   
3.         if(height == null || height.length == 1){
   
4.             return 0;
   
5.         }
   
6.         int left = 0;
   
7.         int right = height.length - 1;
   
8.         
   
9.         int max = 0;
   
10.         
    
11.         while(left < right){
    
12.             max = Math.max(max, (right - left) * Math.min(height[right], height[left]));
    
13.             if(height[left] > height[right]){
    
14.                 right--;
    
15.             }else{
    
16.                 left++;
    
17.             }
    
18.         }
    
19.         return max;
    
20.     }
    
21. }

复制代码

12. Integer to Roman
题目大意
给一个数字，让你转换成罗马数字的字符串。

题目分析和解答。
这个题很经典。通常，给我们一个纯数字，那么这个题很有可能是个数字题。我第一反应是错误的，我以为让拼字符串，应该可以用有限状态机去解答。理论上也可以这么做，但是实际画一下就知道状态太多了，导致转移非常复杂，每一个位数都有三种状态，这道题可以有4位数，所以一共有十种状态。

这么做等于为难自己，更好的方法当然是用数学去解答。

数学的方法是这样的：
首先，我们把1000 900 500 400…9 5 4 1存成一个array记作values。再把对应的罗马数字 M CM D CM… IX, V IV I按顺序存成另一个array记作roman。因为是一一对应的，所以这两个array长度相等。
当然，你选择其他的数据结构也可以，看你自己的设计。
然后，我们从两个数列的0号位开始，每次比较一下当前数字作values[i]值的大小。
若是当前数字比values[i]大，说明我们要把这一位转化成罗马数字。
那么转化多少次呢，我们就用当前数字除以values[i]就可以了。
转化完成之后，我们把原来的数字 % values[i]。也就是去掉最高的这一位数，继续看下一位。
比如我们要转化2454。
先看values[0] = 1000。 2454 大于1000。并且2454 /1000 = 2。所以我们的答案添加两个MM。然后我们用 2545 % 1000 = 545。再继续看下一个900。900 > 545。于是跳过，继续看500，545 > 500。要添加，所以答案继续添加一个D变成MMD。然后545 ％500= 45。
继续，下一个values[i] = 400跳过，100跳过，90跳过，50跳过，到了40, 40 < 45所以我们添加一个XL在答案里面MMDXL。然后45 %40 = 5。继续values[i] = 5跳过, 4 ＝ 4所以添加进答案 MMDXLIV，最后4 % 4 =0，结束。

这个方法巧妙之处在于如何处理4和9，因为这它们需要前面的一位罗马数字比自己小。
所以我们从大到小构建了values，当我们用num 去比较values[i]的时候，实际上我们就是在看num是否属于［values[i], values[i-1])。所以比如只有某个数字确定是4、9的时候，我们才能提起出来，因为values中, 4的上一位总是5，所以只有4才能落到区间[4,5)当中。通过区间巧妙的设计，保证了我们可以取出正确的罗马数字。
最后代码是这样的

1. public String intToRoman(int num) {
   
2.         String[] roman = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
   
3.         int[] values = {1000, 900,500,400, 100, 90, 50, 40,  10, 9 ,5, 4, 1};
   
4.         
   
5.         StringBuilder sb = new StringBuilder();
   
6.       
   
7.         for(int i = 0; i < values.length; i++){
   
8.             int v = values[i];
   
9.             if(num >= v){
   
10.                 for(int n = 0; n < num/v; n++){
    
11.                     sb.append(roman[i]);
    
12.                 }
    
13.             }
    
14.             num = num % v;
    
15.         }
    
16.         return sb.toString();
    
17.             
    
18.         
    
19.     }
    

复制代码

13. Roman to Integer
题目大意
给一格罗马数字，求它对应的阿拉伯数字的值
题目解答

这个题是上一道的反向，但是难度降低了不少。思路也相当直接，我们从左到右看罗马字母对应的数字，直接把它累加进答案。
通常罗马数字是从左到右，数字依次减少。
唯一要特殊处理的，是数字4和9，因为它们是后一位比前一位更大。比如IV是四。
那么我们就用双指针，每一次比较一下之前的数字，若是当前的罗马数字比之前一位的更大，说明这是一个4或者9开头的数。
那么我们只要把前面一位减去就可以了。

所以，代码就是

1. Map<Character, Integer> map = new HashMap<>();
   
2.         map.put('I',1);
   
3.         map.put('V',5);
   
4.         map.put('X',10);
   
5.         map.put('L',50);
   
6.         map.put('C',100);
   
7.         map.put('D',500);
   
8.         map.put('M',1000);
   
9.         
   
10.         char[] sc = s.toCharArray();
    
11.         int rs = 0;
    
12.         for(int i = 0; i< sc.length; i++){
    
13.             if(i > 0 && map.get(sc[i]) > map.get(sc[i-1])){
    
14.                 rs = rs + map.get(sc[i]) - 2 * (map.get(sc[i-1]));
    
15.             }else{
    
16.                 rs += map.get(sc[i]);
    
17.             }
    
18.         }
    
19.         return rs;
    
20.     }

复制代码

题目大意
给你一个string[]，让你找出这些string，最大的公共前缀。

题目分析和解答
这个题也很简单，我们一看string ，就当成array来处理，这个题还是让我们找出对应的值。找多少字母，就要多少个指正。我们发现找前缀，就是是从头开始，挨个看字母是不是一样的。所以每次就找一个字母，所以就定义一格指正就够了。
只不过，每一次更新指正，我们都要去比较每一个string这一位是不相同的。

另外这个题有个小技巧，那就是因为字符不相同，我们如何确定指针走完了呢？
我自己的想法是，这个最长前缀，最长的可能性就是最短的一个string。所以我先循环了依次，找出最短的字符的长度，然后移动指正的时候，当移动到这个最短长度之后，就停止了。

后来看了其他人的答案，发现有点多此一举，我们只要随便找一个里面的字符，作为参照即可，比如可以把strs[0]作为参考，其他人和它一位一位比，直到某一个字符结束，或者出现不同即可
所以我的不太好的代码是

1. class Solution {
   
2.     public String longestCommonPrefix(String[] strs) {
   
3.         int minL = Integer.MAX_VALUE;
   
4.         for(String s : strs){
   
5.             minL = Math.min(minL, s.length());
   
6.         }
   
7.         int p = 0;
   
8.         StringBuilder sb =new StringBuilder();
   
9.         
   
10.         while(p < minL){
    
11.             char c = strs[0].charAt(p);
    
12.             for(String str : strs){
    
13.                 if(str.charAt(p) != c){
    
14.                     return sb.toString();
    
15.                 }
    
16.             }
    
17.             sb.append(c);
    
18.             p++;
    
19.         }
    
20.         return sb.toString();
    
21.     }
    
22. }

复制代码

15. 3Sum
给一个数列，找出所有三个数之和等于0的组合。

题目分析和解答
这个题算是比较难的，找数字并不难，就是把一个数固定，然后题目就变成了twoSum。
但是这里有个难度在于如何去掉重复的答案。就算用暴力解也会面临这个问题。

所以这里我们做题思路要多一个心眼。
当做array题目的时候，通常都是让我们找某些数字。若是找多个数字，并且这些数字不是连续的，是可能出现在任意位置的，并且题目并没有让我们返回下标。

那么我们就要考虑，是否可以对数组进行排序。

排序的好处是，相同数字都是相邻的，我们就可以跳过相同的数字，达到去重复的目的。
而这道题排序还有一个好处是剪枝，因为三数之和为零，那么要么都是0，要么必然有正有负。
而从负数找正数，和从正数找负数，答案必然是一样的。所以我们就不用去管正数了，教研到0就停止了。

所以最后的代码是

1. 
   
2. class Solution {
   
3.     public List<List<Integer>> threeSum(int[] nums) {
   
4.         List<List<Integer>> rs = new ArrayList<>();
   
5.         if(nums == null || nums.length < 3){
   
6.             return rs;
   
7.         }
   
8.         Arrays.sort(nums);
   
9.         
   
10.         
    
11.         for(int i = 0 ; i < nums.length; i++){
    
12.             if(i > 0 && nums[i] == nums[i-1]) continue;
    
13.             if(nums[i] > 0) break;
    
14.            
    
15.             int p1 = i + 1;
    
16.             int p2 = nums.length - 1;
    
17.             while(p1 < p2){
    
18.                 if(nums[p1] + nums[p2] + nums[i] == 0){
    
19.                     List<Integer> temp = new ArrayList<>(
    
20.                         Arrays.asList(nums[p1],nums[p2], nums[i]));
    
21.                     rs.add(temp);
    
22.                     
    
23.                     while(p1 < p2 && nums[p1] == nums[p1 + 1]) p1++;
    
24.                     while(p1 < p2 && nums[p2] == nums[p2 - 1]) p2--;
    
25.                     p1++;
    
26.                     p2--;
    
27.                 }else if(nums[p1] + nums[p2] + nums[i] > 0){
    
28.                     p2--;
    
29.                 } else p1++;
    
30.                
    
31.             }
    
32.          
    
33.         }
    
34.         return rs;
    
35.     }
    
36. }

复制代码

16. 3Sum Closest
题目大意
给一个数组，和一个目标值，找出一个三个数之和，这个和是最接近目标值的值。

题目分析
这个题看起来比3sum更吓人，但是其实更简单。
还是老套路，若是给了一个数组，让我们找某些数字，你让我找几个数字，我就定义几个指针，这个题是三数之和，那么就定义三个指针。
然后看看能不能排序，是可以的，因为这三个指针可以不连续。

这个题比3sum简单在于，我们只要找出某一个值就可以了，不用非要返回是哪三个数。
那么暴力解就是三个for循环了，很简单就能想到。
那么如何优化暴力解？还是如同3sum那样，我们固定一位数，然后去它的后面找两个数的时候，我们就把左指针放在 i + 1，右指针放在末尾。看它们的和比target更大还是更小，若是更大，说明末尾的数太大了，我们就把右指针减少一位，若是更小，说明i+1太小了，我们要一更大的值，所以左指针增大一位。这样我们就到了一个新的值，把这个值与目标值的差的绝对值记录下来，若是它比之前的记录更小，那么我们就更新答案为当下的三数之和。

这个方法，其实可以继续优化，比如可以跳过重复的值，因为它们的和是一样的。
另外这个题似乎可以用二分法，不过我没想出来。希望大神指点吧
我的代码是：

1. class Solution {
   
2.     public int threeSumClosest(int[] nums, int target) {
   
3.         int rs = 0;
   
4.         if(nums.length <= 3){
   
5.             for(int num : nums) rs += num;
   
6.             return rs;
   
7.         }
   
8.         
   
9.         Arrays.sort(nums);
   
10.         int min = Integer.MAX_VALUE;
    
11.         
    
12.         for(int i = 0; i < nums.length; i++){
    
13.             int lo = i + 1;
    
14.             int hi = nums.length - 1;
    
15.             
    
16.             while(lo < hi){
    
17.                
    
18.                 int sum = nums[i] + nums[lo] + nums[hi];
    
19.                 if(Math.abs(sum - target) < min){
    
20.                     min = Math.abs(sum - target);
    
21.                     rs = sum;
    
22.                  }
    
23.                 if(sum > target){
    
24.                     hi--;
    
25.                 }else if(sum < target){
    
26.                     lo++;
    
27.                 }else{
    
28.                     return sum;
    
29.                 }  
    
30.                
    
31.             }
    
32.         }
    
33.         return rs;
    
34.     }
    
35. }

复制代码

17. Letter Combinations of a Phone Number
题目大意，
我们的电话上的键盘，是有英文字母的，给你一串数字，问你这串数字可以代表什么英文字母，返回所有可能性。

题目分析

这个题是经典的回溯法。什么时候用回溯法呢？但凡要求我们找出所有可能性，这种字眼出现的时候，就要考虑回溯法。
若是没有这样的明显的字眼，我们怎么判断什么时候用呢？

当然还是看问题套路，这题给我们一个string，string问题就是array。但是这个题不是让我们找array中的值，而是根据原有的array，进行变化，产生一些新的东西。这个变化，一般有，对array本身的值进行变化，或者根据array的值，进行计算，得出另外一些值。

这个题就是根据array的值，进行计算，得出另外一些值。遇到这种问题，都可以用状态机的思维去思考。
这道题其实就是说，一个位数的字符，对应这状态机这个位置上的三个状态，每一个位数，都可以前进到下一格位数的三个状态中的任意一个。此时问题已经变成了一个方向图。

我们要从开始的三个状态节点，走到终点，问题就是让我们找有多少种走法。很显然是用DFS，走到终点之后，再回头，选另外一条路。那么这显然就是回溯法了～

接下来就是套模板了，这个题基本上没有任何坑，就是套模版写就可以了。唯一麻烦的就是要定义一下数字键盘对应的字母。
所以我的代码是

1. public List<String> letterCombinations(String digits) {        
   
2.         Map<Integer, char[]> map =new HashMap<>();
   
3.         
   
4.         map.put(2, new char[]{'a','b','c'});
   
5.         map.put(3, new char[]{'d','e','f'});
   
6.         map.put(4, new char[]{'g','h','i'});
   
7.         map.put(5, new char[]{'j','k','l'});
   
8.         map.put(6, new char[]{'m','n','o'});
   
9.         map.put(7, new char[]{'p','q','r','s'});
   
10.         map.put(8, new char[]{'t','u','v'});
    
11.         map.put(9, new char[]{'w','x','y','z'});
    
12.         
    
13.         char[] sc = digits.toCharArray();
    
14.         char[] rs = new char[sc.length];
    
15.         List<String> list = new ArrayList();
    
16.         if(digits == null || digits.length() == 0)
    
17.              return list;
    
18.         helper(sc, rs, 0, list,map);
    
19.         return list;
    
20.     }
    
21.    
    
22.     private void helper(char[] sc, char[] rs, int idx, List<String> list,Map<Integer, char[]> map ){
    
23.         if(idx > sc.length - 1){
    
24.             StringBuilder sb = new StringBuilder();
    
25.             for(char c : rs){
    
26.                 sb.append(c);
    
27.             }
    
28.             list.add(sb.toString());
    
29.             return;
    
30.         }
    
31.         char[] cs = map.get(sc[idx] - '0');
    
32.         for(int i = 0; i < cs.length; i++){
    
33.             rs[idx] = cs[i];
    
34.             helper(sc, rs, idx+1, list,map);
    
35.         }
    
36.     }

复制代码