Note for LeetCode in Java (1~100)

刷题。祝我好运。

1. Two Sum

给定一串整型数组，给一个目标值，求数组中唯一的一对数字，相加得到该目标值。
ME：先排序，然后二分查找遍历一遍看看给定数字a能否找到数字b = target - a。确定后再回到原数组扫出a和b的位置。时间nlogn + n*logn + n.
TA：利用HashMap，从头到尾扫原数组，先查看b = target - a是否在HashMap的Key中，不在则把值和索引分别作为键和值加入HashMap。一旦扫到符合的即可输出，时间为n。（Java的HashMap查找是O(1)的，C++中是O(logn)）

2. Add 2 Num

给两个链表，每个节点是一个数字，输出也是一个链表，每个节点就是那两个输入链表对应节点的值之和。
ME：就是个简单版模拟加法，和归并排序总体思路差不多，都是一个将两个链表相加直到其中一个为空，再把剩余内容继续倒出来，只不过要考虑多个进位问题。开始没通过就是因为没考虑两个链表都加完了，进位可能还得加的情况。
TA：想法一样，但代码简洁很多。我的三个while循环可以归整到一个while里面，在里面再判断链表谁空了；进位和加法整合，上一步的进位直接用到这一步的加法中，省去了一个变量；少了first_flag因为他直接设了一个sentinel，它的下一位才是要返回的内容。

3. Longest substring

给一个字符串，找其中不含重复字符的最长子串的长度。
ME：利用HashMap，再利用一个log数组记录每个字符的对应的长度计数（其实可以不用），然后从前往后扫
-> 若不在HashMap中则直接把char, index插入，并在log的对应位置赋值为前面一位计数值+1；
-> 若已经出现过，则取『前面一位计数值+1』和『距离HashMap中存放index的距离』二者的较小值。
TA：引入了双指针而不需要我这样的log数组，左指针指向在HashMap出现过的字符get到的index的下一位，右指针一直向后遍历。两个指针之间的距离就是所求的最大子串了。还有一种DP动态规划的方法，用一个数组模拟HashMap，初始值为-1，每个字符出现时就会更新为它的索引，不过它也需要和ME的方法一样用到一个取max的过程来保证更新最大长度时不出错。
HashMap的get(key)返回的value需要强制转换一下才能用。(???当时为啥写这句)
Two pointers. three fails.

4. Median of 2 sorted arrays

给两个int数组，返回二者合并后的中位数，要求在O(log(m+n))的时间复杂度以内。
ME：很直接地想到mergeSort的最后一步，将两个有序数组合并，然后合并到总长度一半的时候就知道中位数了。但这个方法时间复杂度似乎是O((m+n)/2)？虽然AC了但并不符合要求。。。其实看到有序、logN，还能想到的就是二分查找了。
TA：中位数是用来将数组分割成相等长度的两部分的，因此使用二分查找找出刚好能分成登等长的两部分并且前部分的最大值<=后部分的最小值。边缘情况真的特别复杂，比较难理解，怪不得是hard题。

BinarySearch. know nothing about the method of split and check.

 class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return 0;
        }
        int m = nums1.length, n = nums2.length;
        if (nums1.length > nums2.length) {  // ensure the len of 1 <= 2
            return findMedianSortedArrays(nums2, nums1);
        }
        
        // to ensure equality of the two parts after merged, i + j = m - i + n - j
        int iLo = 0, iHi = m, allMid = (n + m + 1) / 2; // merge odd / even case
        
        // i stands for "how many num taken from nums1 as front part" 0 ~ i-1 | i ~ m-1
        // j stands for "how many num taken from nums2 as front part" 0 ~ j-1 | j ~ n-1
        while (iLo <= iHi) {
            int i = (iLo + iHi) / 2, j = allMid - i;
            
            // nums1[i-1], nums2[j-1] are the largest element of front part of nums1, nums2
            // nums1[i], nums2[j] are the smallest of lag part of nums1, nums2
            if (i < m && nums2[j - 1] > nums1[i]) { // i not big enough
                iLo = i + 1;
            } else if (i > 0 && nums1[i - 1] > nums2[j]) {
                iHi = i - 1;
            } else {
                int maxLeft = 0, minRight = 0;
                if (i == 0) {
                    maxLeft = nums2[j - 1];
                } else if (j == 0) {
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                
                if ((m + n) % 2 == 1) { // I think thats why to make (allMid = (n + m + 1)/2)
                    return maxLeft;     // -- to make left part always at least no fewer than right
                }
                
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums1[i], nums2[j]);
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        
        return 0;
    }
}

5. Longest palindromic substring

给一个字符串，返回最长的回文子串（对称）。
ME：没有想出来高招，暴力法果断超时。。暴力法就是一个指针从头开始，另一个指针从尾巴往回扫，看看是否和前面指针相同，相同就进一步分别向右挪/向左挪，以此类推。。。
TA：这个似乎也是暴力法，只是用了更优雅的方式——双指针分别扩展，而我的暴力法是双指针向中间合拢，扩展的方式在worst case下复杂度也是O( n^2)。
Brute force - expanding to double side index. edge case mistakes…
DP也可以解决。

6. zigzag-conversion

给一个字符串和行数，输出转换为zig-zag形式的对应字符串。
ME：找规律找出来的，直接用下标变化规律，不像是在解算法题，或者说只是我运气好找到了规律。（话说回来，我的代码速度还挺快的，毕竟是直接套规律搞出来的）
TA：按照真正的zig-zag式分布来写，每一行都定义了一个StringBuffer，从上往下再从下往上将每一行的字符串逐步拼接起来，最后汇总一下即可，这样的代码非常方便别人理解，不像你的要是不解释下标的变化规律别人怎么可能看得懂。
String转char[]用s.toCharArray()。
Just using stringbuilder appending to simulate the process. Two fails for numRows too small / charCount too small.

7. reverse-integer

给一个32bit的带符号整数，输出倒序的这个数字并保持符号。若越界则返回0.
ME：简单粗暴取商、取模来做，负数则直接取反来搞。两次WA，一是越界判断是用『加完后变为负值』而实际上越界可以一越越到了正值部分，所以不可以这样；而是-2147483648这个值直接取反会越界，我后来直接处理着情况了。。。有点jian。
TA：直接使用取商、取模而不理会正值或负值，在JAVA中负数取模会尽量让商更大（-7 % 3 = -1），看起来就是正数取模加个负号罢了。而越界判断使用的是计算出的值减去个位数除以10看看是否等于计算前的值。
Ok. Just mod and divide. Negetive mod is very similar to positive mod in Java.

9. palindrome-number

给一个整数，判断它是不是回文数。要求不能额外申请对象空间，也就不能转成字符串处理了。
ME：简单粗暴，头尾分别取数字对比。边缘情况包括0和负数。但跑测试用例速度巨慢。。。
TA：在这个方法中直接改变原数字x，取x的前半部分和后半部分之reverse对比，不过除了x==rev，还有一种情况是奇数时rev比x多一位，这时需要判定x==rev/10。边缘情况是负数和个位为0直接判定false，0不用。
Forgot the method of cutting into half and reverse the latter to compare. the condition to end the loop of splitting into half is awesome. Fail at case x=10 because 0 digit in the right half can’t be represented properly into front after reversed.

10. regular-expression-matching

实现一个字符串正则表达式匹配函数，需要实现.和*。
ME：真心不会。。。看了讨论板块发现要用到DP，必须学一波动态规划了。
TA：参考了一个带有比较详细解释的C++帖子。动态规划DP关键是找到状态以及状态之间的转换规律，在这题中，既然是目标字符串s和正则字符串p之间相互比较，就需要维护一个boolean的二维数组dp[i][j]，表示s[0~i-1]与p[0~j-1]是否匹配。观众朋友会问了，那么dp[i][0]和dp[0][j]表示什么呢？
-> dp[i][0]就是正则字符串p为空的情况，显然dp[0][0]为真，而只要s不为空就不可能用空的p来匹配上它，因此dp[i][0]除了首位，全部初始化为false；
-> dp[0][j]就表示目标字符串s为空的情况，由于p可能有一个bug级的'*'存在，不能轻易全部赋值为false，例如a*b*c*就可以匹配空的s，对于dp[0][j]就需要动用状态转移了，dp[0][j]取决于当前字符p[j-1]是否为'*'且往前两位字符处的匹配情况dp[0][j-2]。
至此，dp数组初始状态设置完成。下面正式讨论状态转移。
-> 当前字符p[j-1]不是'*': dp[i][j]取决于当前字符p[j-1]是否等于s[s-1]且须考虑前一个字符的匹配情况dp[i-1][j-1]。
-> 当前字符p[j-1]是'*'，则又要讨论这个'*'前面的字符p[j-2]应该算几个：
i) 算0个：说明把p[j-2]和p[j-1]抽离后不影响判断，由s[0~i-1]和p[0~j-3]决定，即dp[i][j-2];
ii) 算>=1个：说明把目标字符串s末尾若干个与p[j-2]相同的元素抽离后不影响判断，那么此处就以抽离一个为判断依据，除了判断s[i-1] == p[j-2]，还要考虑抽离s[i-1]后的s[0~i-2]也与p[0~j-1]匹配（'*'前面的这个字符在这里大不了算0次，但这也是之前就出来的结果了，这一步直接用就好）
至于'.'字符就在判断各个字符的时候单独拎出来判断一下就好了。

Not able to analyse DP, let alone implementing.

class Solution {
  public boolean isMatch(String s, String p) {
      if (s == null || p == null || s.equals(p)) {
          return true;
      }
      char[] sChar = s.toCharArray(), pChar = p.toCharArray();
      int m = sChar.length, n = pChar.length;
      boolean[][] dp = new boolean [m + 1][n + 1];
      
      // initial the dp states
      dp[0][0] = true;
      for (int j = 2; j <= n; j++) {
          dp[0][j] = pChar[j - 1] == '*' && dp[0][j - 2];
      }
      
      for (int i = 1; i <= m; i++) {
          for (int j = 1; j <= n; j++) {
              if (pChar[j - 1] == '*') {  
                  // check if ignoring curr pattern
                  // OR (the char is matched AND ignoring curr pattern)
                  dp[i][j] = (dp[i][j - 2]) 
                      || ((sChar[i - 1] == pChar[j - 2] || pChar[j - 2] == '.') && dp[i - 1][j]);
              } else {
                  // check if char is matched for curr pattern
                  dp[i][j] = dp[i - 1][j - 1] 
                      && (sChar[i - 1] == pChar[j - 1] || pChar[j - 1] == '.');
              }
          }
          // note that match means char equalation or equal to dot
      }
      return dp[m][n];
  }
}

container-with-most-water

给一串int数组，取其中两个作为高、Index距离作为宽组成的面积最大是多少。
ME：只想到暴力法，果断超时。。。
TA：利用双指针，分别从头和尾向中间移动来更新max值，每次移动二者之间的较小值。证明在此，若左边小于右边则向右移动左指针的道理是，左指针既然已经小过右指针了，此时体积就由左边决定，右指针往左移只会让面积越变越小没有计算的意义，而左指针往右移倒可能碰上更高的边从而有更大的面积；若右边小于左边则向左移动右指针的道理也类似，既然右边都小了你再让左边挪过来缩短宽度只会让面积更小，移右边才可能有更大面积。

Fail to come up with double pointer method from front and end. Implementation OK after knowing it.

class Solution {
  public int maxArea(int[] height) {
    if (height == null || height.length == 0) {
      return 0;
    }
    // initial two pointers starting from front and end
    int left = 0, right = height.length - 1, area = 0;
    while (left != right) {
      if (height[left] < height[right]) {
        area = Math.max(area, height[left] * (right - left));
        left ++;
      } else {
        area = Math.max(area, height[right] * (right - left));
        right --;
      }
    }
    return area;
  }
}

integer-to-roman

给一个int，转化为罗马数字字符串。
ME：暴力法，每次取一位数字来决定输出多少M D C L X V I，速度贼慢。
TA：直接用一个数组把1000、100、10、1级别的0~9都定义在数组里，每次直接取了append到字符串即可。服。

Seems a boring problem…But at first glance, still unable to figure out the simplified appending method above. Implementation OK.

class Solution {
  public String intToRoman(int num) {
    if (num < 0) {
      return "";
    }
    final String[] ONES = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    final String[] TENS = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    final String[] HDRS = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    final String[] THSS = {"", "M", "MM", "MMM"};
    return THSS[(num / 1000)] + HDRS[(num % 1000)/100] + TENS[(num % 100)/10] + ONES[(num % 10)];
  }
}

roman-to-integer

给一个罗马数字，转化为int.
ME：开了switch case语句和一堆判断。速度竟然超过96%的方法，惊了。
TA：二楼是比较整洁的代码。

Still unable to come up with the method using table and simple add/substract. The rule of add/subtarct is subtle. Implementation with error of MISSING NEW!!!!

class Solution {
  public int romanToInt(String s) {
    if (s == null || s.length() == 0) {
      return 0;
    }
    Map<Character, Integer> map = new HashMap<>();
    map.put('I', 1);
    map.put('V', 5);
    map.put('X', 10);
    map.put('L', 50);
    map.put('C', 100);
    map.put('D', 500);
    map.put('M', 1000);
    int ans = 0, prev = 0;
    char[] sChar = s.toCharArray();
    for (int i = sChar.length - 1; i >= 0; i--) {
      int curr = map.get(sChar[i]);
      if (curr < prev) {
        ans -= curr;
      } else {
        ans += curr;
      }
      prev = curr;
    }
    return ans;
  }
}

14. longest-common-prefix

给一串字符串数组，求这些字符串开头的公共部分。
ME：暴力解之，每次取较短的作为终止长度，逐个字符判断。
TA：用了Array.sort将字符串数组从小到大排序，只比较最短的和最长的前置部分有什么相同的。不过从复杂度来说，排序的nlogn是逃不掉的。最主要省时间的地方是比较，它只比较最前和最后的两个，而你的是每个都要比较。
OK.

15. 3 Sum

给一个int数组，列出三个数使得它们的和为0.
ME：排序之后暴力一前一后暴力找，果断超时，连2Sum时想到的二分查找都没想到，还自鸣得意地用一前一后两个指针在挪着着，果断慢啊，思考又复杂写出来还慢，实在浪费脑力和时间呀。改成二分查找就AC了，但是速度巨慢只超过6%的人。（老是忘记在函数入口确认传入参数的合法性！）
TA：好像和我刚开始想法差不多，也是两个指针怼，只不过是确定最小的去找中间的和最大的来凑成triplets。我不服啊。。。
List、ArrayList用法。List是抽象类，不能直接用；返回值类型是List<List<Integer>>可以用两层ArrayList不断add来生成。

Update two pointers’ condition not clear at first…

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }   
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            // 固定nums[i]用双指针找后面两个数b, c，使b + c == 0 - nums[i]
            int left = i + 1, right = nums.length - 1, target = 0 - nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    List<Integer> currList = new ArrayList<>();
                    currList.add(nums[i]);
                    currList.add(nums[left]);
                    currList.add(nums[right]);
                    ans.add(currList);
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) {    // 避免重复
                        left++;
                    }
                    while (right > left && nums[right] == nums[right + 1]) {  // 避免重复
                        right--;
                    }
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return ans;
    }
}

3sum-closest

给一个int数组，给一个target，求数组中哪三个数之和最接近target，输出这个和。
ME：本打算直接在3sum的基础上改一改，让二分查找当没有找到时返回最接近该目标值的位置，但始终调不好，一次都没有提交。
TA：玛德，看答案居然是三指针O(n^2)暴力解法，不服啊。。

O(N^2) OK

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        
        int diff = Integer.MAX_VALUE, ans = 0;
        // set target as target - nums[i] for two pointer search
        for (int i = 0; i < nums.length; i++) {
            int newTarget = target - nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[left] + nums[right], newDiff = Math.abs(sum - newTarget);
                
                // update diff if closer is found
                if (diff > newDiff) {
                    diff = newDiff;
                    ans = sum + nums[i];
                }
                
                // 
                if (sum == newTarget) {
                    return target;
                } else if (sum < newTarget) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return ans;
    }
}

17. letter-combinations

给一串数字的字符串，求这些数字可能输出的所有字母字符串，对应关系为手机的按键。
ME：组合问题，DFS搞定。至于数字到字母的映射用了一个HashMap刷这么些题第一次自己写出来迭代，毕竟DFS不复杂。
TA：映射完全不必那么复杂，可以用String搞定，而key就是当前数字与字符’0’之差，完美变为数组的index。DFS属于recursive的方法，可以直接改成遍历iterative的方法，还有一种是使用FIFO队列，用了LinkedList的peek函数获取当前队列头元素，总共三重循环。第一重遍历digits读取数字，第二重获取队首元素长度若尚未append本轮新读取数字对应的字母，则取出这个队首并进入最后一重循环把所有可能的字母加在后面。复杂度不低但代码优雅，巧妙的就是在第二重循环入口利用长度来判断是否需要拼接。
搞熟普通数组、ArrayList的初始化！HashMap映射对象为数组时怎么写（虽然在这题其实是没必要的）！

OK. Just DFS.

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits == null || digits.length() == 0 
           || digits.indexOf('1') >= 0 || digits.indexOf('0') >= 0) {
            return ans;
        }
        final char[][] num2Char = new char [][] {
            {}, 
            {}, 
            {'a', 'b', 'c'}, 
            {'d', 'e', 'f'}, 
            {'g', 'h', 'i'},
            {'j', 'k', 'l'}, 
            {'m', 'n', 'o'}, 
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'}, 
            {'w', 'x', 'y', 'z'}
        };
        
        char[] str = digits.toCharArray();
        dfs(str, 0, num2Char, new StringBuilder(), ans);
        return ans;
    }
    private void dfs(char[] str, int index, final char[][] num2Char,
                     StringBuilder sb, List<String> ans) {
        if (index == str.length) {
            ans.add(sb.toString());
            return;
        }
        int temp = str[index] - '0';
        for (int i = 0; i < num2Char[temp].length; i++) {
            sb.append(num2Char[temp][i]);
            dfs(str, index + 1, num2Char, sb, ans);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

4 Sum

给一个int数组，给一个target值，返回所有quadruplets四元组使它们之和等于target。
ME：想一招鲜，从头到尾三个指针挪，最后一个数二分查找找出来，然而超时了。没法子了。
TA：我只能说你死脑筋，这都第三次做这种题了怎么还不会用双指针？老想着二分查找快，但你在循环最里层加个logN的查找，有可能快吗？这种sum的题，套路差不多都是这样：Arrays.sort排个序，外面套几层循环不管，最重要的是到2Sum时里面是双指针一前一后往中间夹逼，根据当前求得的sum和target作比较来确定双指针下一步怎么移，这里有个kSum的推广了。你在2sum能用二分查找只能说运气好，确实是一种方法，但O(N^m * logN)的复杂度当m变高自然就没法通过了。

OK. These kind of k-sum problem can all be solved by sorting and two-pointer moving strategy.

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int newTarget = target - (nums[i] + nums[j]);
                int left = j + 1, right = nums.length - 1;
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum == newTarget) {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        do {
                            left++;
                        } while (left < right && nums[left] == nums[left - 1]);
                        do {
                            right--;
                        } while (left < right && nums[right] == nums[right + 1]);
                  
                    } else if (sum < newTarget) {
                        do {
                            left++;
                        } while (left < right && nums[left] == nums[left - 1]);
                    } else {
                        do {
                            right--;
                        } while (left < right && nums[right] == nums[right + 1]);
                    }
                }
                while (j + 1 < nums.length && nums[j + 1] == nums[j]) {
                    j++;
                }
            }
            while (i + 1 < nums.length && nums[i + 1] == nums[i]) {
                i++;
            }
        }
        return ans;
    }
}

remove-nth-node-from-end-of-list

给一个链表的头结点，给一个整数n，要求删除倒数第n个节点，返回删完后的链表头，n可以保证合法。要求one-pass。
ME：既然没有空间要求，那我就用一个ArrayList来存这个链表了，然后按索引把前一节点的next指向后一节点。交了个WA，玛德又是边界条件没考虑到，一个是删除头结点，一个是删除最后的节点。
TA：快慢指针。一开始我确实有想到这个，不过考虑的是在判断链表有环无环时所用的2倍速度快指针，而这里是固定间隔为n+1的快慢指针，同时还有一个trick是在head之前建一个dummy节点使其next指向head，快慢指针从此处开始向后遍历即可（不是同时开始！快指针先动n+1步）。如果要消除dummy节点，这个方法直接指向head，快指针先动n+1步，利用n的合法性应对删除头结点的情况，其实跟前面的没什么差别。

fail to come up with two pointer slow/fast method.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        
        // fast move first
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        if (fast == null) { // fast reaches end means deleting first node
            return head.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;   // move slow to the front node of the one to be deleted
        }
        slow.next = slow.next.next; // change prev node.next reference
        return head;
    }
}

20. valid-parentheses

给一个字符串，判断其中三种括号(), [], {}是否匹配。
ME：Stack数据结构搞定，左括号入栈，碰到右括号就出栈看看二者是否一对。
TA：也是Stack，不过左括号本身并不入栈，而是它对应的右括号入栈，这样当右括号出现的时候只需判断二者是否相等或者是否栈已经空了即可。
Ignored..

21. merge-two-sorted-lists

给两个已从小到大排好序的链表头结点，归并两个链表，返回合并后的链表头结点。
ME：归并排序的一部分，挺熟悉了，不过之前都是用数组高的，现在用链表也没差。
TA：recursive的写法，高大上一些，每次都把较小的值的节点设为头结点返回，一层一层调用最终就归并好了。还有一个极其简洁版的，省去了头结点变量，每次直接返回较小的节点。

OK. Iterative and recursive.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        
        ListNode fakeHead = new ListNode(0);
        ListNode curr1 = l1, curr2 = l2, curr = fakeHead;
        while (curr1 != null && curr2 != null) {
            if (curr1.val > curr2.val) {
                curr.next = curr2;
                curr = curr2;
                curr2 = curr2.next;
                curr.next = null;
            } else {
                curr.next = curr1;
                curr = curr1;
                curr1 = curr1.next;
                curr.next = null;
            }
        }
        if (curr1 != null) {
            curr.next = curr1;
        }
        if (curr2 != null) {
            curr.next = curr2;
        }
        return fakeHead.next;
    }
}
// recursive
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

22. generate-parentheses

给一个int表示括号的对儿数，输出所有符合括号匹配规则的字符串，存入List中返回。
ME：一兴奋想用前面letter-combinations刚学到的用LinkedList + 长度判断 + String拼接来做组合，结果手抖点了下提交，怒得WA，因为这个还要求括号匹配合法，更何况列举个数都不同，输入n出来的长度2*n呢。后来还是改回了我的DFS，左右括号分别用一个int来记录确保右括号数量不超过左括号就可以了。还是熟悉的好哇。
TA：这题竟然也可以用DP动态规划，然而我还没有掌握。还有一种想法是找规律，也是动态规划的一部分，因为有个状态转移，虽然答主没提到DP。

DFS OK. Did not come up with DP, which seems expensive (O(N^4))…

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        if (n < 1) {
            return ans;
        }
        
        dfs(n, 0, 0, "", ans);
        return ans;
    }
    private void dfs(int n, int left, int right, String s, List<String> ans) {
        if (left == n && right == n) {
            ans.add(s);
            return;
        }
        if (left < n)
            dfs(n, left + 1, right, s + "(", ans);
        
        if (right < left)
            dfs(n, left, right + 1, s + ")", ans);
    }
}
class Solution {
    public List<String> generateParenthesis(int n) {
        List<List<String>> dp = new ArrayList<>();
        if (n < 1) {
            return new ArrayList<String>();
        }
        
        dp.add(Arrays.asList(""));
        for (int i = 1; i <= n; i++) {
            List<String> curr = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                for (String first : dp.get(j)) {
                    for (String second : dp.get(i - 1 - j)) {
                        curr.add("(" + first + ")" + second);
                    }
                }
            }
            dp.add(curr);
        }
        
        return dp.get(n);
    }
}

23. merge-k-sorted-lists

给一个ListNode节点数组，分别是排好序的若干链表头，要求输出合并后的新链表头。题目特别提示注意时间复杂度。
ME：一开始硬上，每次都遍历一遍链表头来获取最小值，然而超时。我又考虑既然每次都只需要一个最小值，那完全可以维护一个小根堆，直接取根节点就好，然而改了半天还是超时。没辙了。其实这个想法是可以的，看下面就知道为什么了，现在看来你之前整理的堆排序也是错的。
TA：看了tag，写着分治法、堆，说明我用小根堆的思路是其中一种。这个用了Java内建的PriorityQueue，其实就和小根堆是一回事。令我吃惊的是后面这个答案明明也是维护了一个小根堆，怎么他就可以呢？原来他对于小根堆分成了两个函数，一个是create从尾到头确保小根、一个是adjust从根向下每次*2一次性调整完毕，而我全程用的create来调整，复杂度自然高了。于是我也拆成create和maintain两个，怒AC。看看分治，前面做过了mergeTwoLists，那这里分治就是把原链表数组拆分后再两两归并，最终合体。借助归并排序的分治法思想实现了一波，比小根堆快一点。

2 fails with PriorityQueue because of null ListNode condition. Did not come up with Divide and Conquer method. But what about implementing your own Heap structure? Ummm, skipping the manual heap method…

class Solution {
    // divide and conquer
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        // last two params are used to divide into sub problems
        return mergeKLists(lists, 0, lists.length);
    }
    
    private ListNode mergeKLists(ListNode[] lists, int start, int end) {
        if (end - start == 1) { // only one list
            return lists[start];
        } else if (end - start == 2) {  // merge two lists
            return mergeTwoLists(lists[start], lists[start + 1]);
        } else {
            int mid = start + (end - start) / 2;
            // cut into first and second halves
            return mergeTwoLists(mergeKLists(lists, start, mid), 
                                 mergeKLists(lists, mid, end)); // warning not mid + 1
        }
    }
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

24. swap-nodes-in-pairs

给一个链表头，要去反转所有相邻的节点，返回反转后的头。不可以修改头的val，这能修改next。
ME：设一个伪头部，然后建一个反转后续两个节点的函数，搞定。
TA：基本都是我这样了吧。有一个用recursion的，我总感觉能不用就不用吧，一个是不好懂，一个是递归对栈的消耗不是constant space。
OK.

reverse-nodes-in-k-group

给一个链表头和小组内节点个数，按小组倒转链表，返回分组反转后的头。
ME：伪头部之后，将k长度的节点存入数组方便访问，然后循环一波调整各自的next指向。
TA：除了我这种迭代的方法，另外就是递归了，不得不说，递归的代码真心短，所以不太好懂。答主做法是一直往后找到最后一段需要反转的k元组，其中利用curr和head两个指针来反转还是比我用数组的优雅很多。话说回来，我用了数组的话，也相当于额外申请了空间哎，题目要求constant memeory。。。吓得我改造了一发把数组给改掉了，改造的时候要特别注意NullPointerException，因为我用了一个伪头部而答主没有。

Don’t know how to reverse the array at all!

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k < 1) {
            return head;
        }
        int count = 0;
        ListNode curr = head;
        
        // locate curr at the next node of k-tuple group
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }
    
        if (count == k) {
            // set curr as starting head to reverse the following groups recursively
            curr = reverseKGroup(curr, k);
            while (--count >= 0) {
                ListNode headNext = head.next;
                head.next = curr;
                curr = head;    // curr is moving forward since head.next = curr
                head = headNext;
            }
            return curr;
        }
        return head;
    }
}

remove-duplicates-from-sorted-array

给一个已排好序的int数组，删除其中的重复项，返回长度。玛德我一开始以为只需要返回一个长度而不用对原数组开刀，还在想这题这么衣洗。题目说的leave beyond length是说该长度之后数组里是什么内容不关心，又不是说besides。。。
ME：既然不在意长度之后的内容，那我就直接用后面的覆盖掉前面最后一次重复的元素，省去了数组删除需要移动一大堆元素的过程。
TA：想法差不多，这个显得更优雅，因为已经排好序所以后面的只要不同就一定比前面的大。

Did not come up with elegant lazy move method.

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[len] != nums[i]) { // lazy move len
                nums[++len] = nums[i];  // when num[i] is diff from nums[len]
            }
        }
        return ++len;   // since last one cannot be compared to next different element
    }
}

remove-element

给一个任意排序的int数组，给一个key，要求返回删除这个key元素的新长度，同样不关心该长度之后的内容，同时返回时数组内的key顺序可以换。同样要求in-place.
ME：从前往后找key，一旦发现就从后往前找不是key的元素就覆盖掉前面的。
TA：当大家想法差不多，就会开始比谁的代码短。。。这个真心短，答主不是从后往前找不是key的元素覆盖，而是直接按顺序来。这样要考虑的坑少一些，我那个又是正的又是反的，跟这个比就复杂了。

OK.

class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] == val) {
                nums[i--] = nums[--len];
            }
        }
        return len;
    }
}

28. implement-strStr

实现一个strStr函数，给一个字符串在其中找子字符串第一次出现的索引。
ME：手动实现呗。第一次WA竟然是因为在字符串中找””永远返回0。
TA：这个代码很优雅，直接上双重循环，一旦有一位字符不同就跳出内层循环；如果长度超过了原字符串，说明找不到；如果能在内层循环顺利达到target的长度说明找到了，返回外层循环的当前索引即可。
String转char数组用toCharArray。注意strStr在Java中对应的是indexOf，Java中并没有strStr。

KMP在text中找pattern。

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null || needle.isEmpty()) {
            return 0;
        }
        int len = needle.length();
        int[] dp = new int[len];
        for (int i = 1; i < len; i++) {
            int j = dp[i - 1];
            while (j > 0 && needle.charAt(j) != needle.charAt(i)) {
                j = dp[j - 1];
            }
            if (needle.charAt(j) == needle.charAt(i)) {
                j++;
            }
            dp[i] = j;
        }
        
        int lenFull = haystack.length();
        int j = 0;
        for (int i = 0; i < lenFull; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = dp[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == len) {
                return i - len + 1;
            }
        }
        return -1;
    }
}

29. divide-two-integers

给两个数字，不使用乘、除、模运算前者除以后者之商，若结果越界则返回MAX_INT。
ME：直接用个循环一点一点叠加除数看看sum是否>=被除数，符号则是统一把两个数都变为负数，毕竟负数的界比正数多1。然而超时了。。。

TA：玛德忘记了除了加减乘除还有位运算这种东西。我原本确实想过通过翻倍来加速求sum的过程，不过当时并没有想到位运算，只是想着通过数组从被除数开始往后一直翻倍记录increment，不过在极限情况下（-2147483648 / -1）的情况下，数组要2^16这么大，把我吓跑了。按照这个C++的答案改造成了Java，果然优雅。事实上题目所说的越界情况也就只有 -2147483648 / -1 而已，所以我之前超时的那个很多判断都是没必要的。

class Solution {
    public int divide(int dividend, int divisor) {
        if ((dividend == Integer.MIN_VALUE && divisor == -1) || divisor == 0) {
            return Integer.MAX_VALUE;
        }
        int a = Math.abs(dividend), b = Math.abs(divisor), shiftCount = 0, ans = 0;
        while (a - b >= 0) {    // 这里a是MIN时会时负数，因此不能直接比a >= b
            // 注意这里b经过shift可能会越界成负数，因此不能直接比较a >= (b << shiftCount << 1)
            for (shiftCount = 0; a - (b << shiftCount << 1) >= 0; shiftCount++);
            a -= (b << shiftCount);
            ans += (1 << shiftCount);
        }
        return (dividend > 0) == (divisor > 0) ? ans : -ans;
    }
}

30. substring-with-concatenation-of-all-words

给一个长字符串s，然后一个相同长度m的word字符串的数组，要求找出该数组中字符串各种可能排列成的新字符串在s中出现的位置
ME：使用DFS将所有可能的target字符串拼接出来存入HashSet，然后逐个取出使用indexOf找。然而超时。。。
TA：给出的tag又是双指针，或者说是滑动窗口，这个双指针有点无敌啊。我的方法最耗时的部分应该就是DFS拼接所有可能的target那部分，在这个方法中，直接把每个word作为独立个体看待。首先利用一个mapping为各个word分配索引，然后从头到尾扫一遍s每次取长度为m的子串看看能否在mapping中get到，get的索引存在smapping中。固定窗口长度为m，总共滑动m次，每次循环都是一左一右两个指针扫smapping，右指针先以m的步长扫smapping获得索引并相应减去该索引的word的计数，当所有word都用完了，就挪左指针扫smapping（其实就是重走了一段右指针走过的路），扫到第一个属于word的就看看长度是否为k*m，因为各个word的长度相同所以我们只要简单判断长度就能知道这部分内容满不满足要求。还有一个更简短的，这里直接把构建table的过程简化成map搞定，同时省去了构建smapping的过程而直接在大循环中get，面试时相同的思路当然是代码越短越好，才写得完嘛。
Set的遍历，数组赋值Arrays.fill。

Did not come up with the method of mapping and search. After knowing and implementing it, still time limit exceeded, because calling containsKey too much. But actually there is a much faster one, which use raw array to implement the mapping relations, including finding the matched substrings in s.

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        if (words == null || words.length == 0) {
            return ans;
        }
        
        // construct map for each word and its count
        Map<String, Integer> wordCount = new HashMap<String, Integer>();
        for (int i = 0; i < words.length; i++) {
            wordCount.put(words[i], wordCount.containsKey(words[i])? wordCount.get(words[i]) + 1: 1);
        }
        
        // check each slot in s with fixed length wordLen
        int wordLen = words[0].length();
        int end = s.length() - words.length * wordLen;
        for (int i = 0; i <= end; i++) {
            Map<String, Integer> temp = new HashMap<>(wordCount);
            int j = i;  // increase from i, each time increase by wordLen
            while (j < s.length()) {
                if (j + wordLen <= s.length()) {    // in case substring exceed boundary
                    String currStr = s.substring(j, j + wordLen);
                    if (!temp.containsKey(currStr)) {
                        break;
                    } else {
                        int leftCount = temp.get(currStr);
                        if (leftCount == 1) {
                            temp.remove(currStr);
                        } else {
                            temp.put(currStr, leftCount - 1);
                        }
                    }
                }
                j += wordLen;
            }
            if (temp.isEmpty()) {
                ans.add(i);
            }
        }
        return ans;
    }
}
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        if (words == null || words.length == 0) {
            return ans;
        }
        
        // map each word with unique index into map; Count unique wordNum
        int wordNum = 0;
        Map<String, Integer> map = new HashMap<>();
        int[][] table = new int [2][words.length];
        for (int i = 0; i < words.length; i++) {
            Integer index = map.get(words[i]);
            if (index == null) {
                index = wordNum++;
                map.put(words[i], index);
            }
            table[0][index]++;
        }
        
        // tarverse s and check each index if it has word in words[], mark the wordIndex
        int[] sIndex = new int [s.length()];
        Arrays.fill(sIndex, -1);
        int wordLen = words[0].length();
        int end = s.length() - wordLen + 1;
        for (int i = 0; i < end; i++) {
            String sub = s.substring(i, i + wordLen);
            Integer mapResult = map.get(sub);
            if (mapResult != null) {
                sIndex[i] = mapResult;
            }
        }
        
        // use left ptr to recover word repo, right to consume word
        int expectedLen = wordLen * words.length;
        for (int i = 0; i < wordLen; i++) {
            int left = i, right = i;
            int wordRemain = wordNum;
            Arrays.fill(table[1], 0);
            while (right < end) {
                // move right with slot len == wrodLen
                while (wordRemain > 0 && right < end) { // make sure there'r still word to consume
                    int hitIndex = sIndex[right];   // get hitIndex from sIndex in step 2
                    if (hitIndex != -1 && ++table[1][hitIndex] == table[0][hitIndex]) {
                        wordRemain--;   // increase the corresponding count
                                        // when all is consumed, this word is drained to 0
                    }
                    right += wordLen;
                }
                
                // move left to recover the consumed words until at least one word exists
                while (wordRemain == 0 && left < right) {
                    int hitIndex = sIndex[left];
                    if (hitIndex != -1 && table[1][hitIndex]-- == table[0][hitIndex]) {
                        wordRemain++;   // when this word comes from fully consumed
                                        // recover the wordRemain
                        
                        if (right - left == expectedLen) {
                            ans.add(left);  
                        }
                    }
                    left += wordLen;
                }
            }
        }
        
        return ans;
    }
}

31. next-permutation

给一个int数组，将它改造成按字典序的下一个排列，若不存在则直接按从小到大的顺序调整。要求In-place对原数组操作，不能申请额外空间。
ME：考虑最右顺序对，这个和归并求逆序对有点像。既然求最右那就需要把原本的merge函数改成从右往左找，但写成了代码才发现不对！！！没辙了。
TA：这个想法从右往左找相邻的两个数使得first < second，然后再从右往左找首次出现的比first大的数，二者对调，然后将second及其之后的内容reverse一下即可。这才是正解，和我的思路差别还是略大。这是值得警惕的倾向，看到一个题就像往熟悉的东西上面套，套上了就很难抽出来。另外，这里给出了问题的来源，原来是一个很古老的问题了，而且可以应用在Permutation问题中，对重复也可以处理。

Forgot the method of finding ascending pair, swap and reverse.

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                int j = nums.length - 1;
                while (j > i) {
                    if (nums[j] > nums[i]) {
                        swap(nums, i, j);
                        reverse(nums, i + 1);
                        return;
                    }
                    j--;
                }
            }
        }
        reverse(nums, 0);
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    private void reverse(int[] nums, int start) {
        for (int i = start, j = nums.length - 1; i < j; i++, j--) {
            swap(nums, i, j);
        }
    }
}

longest-valid-parentheses

给一个只包含了(和)的字符串，求其中合法匹配的最大子字符串长度。
ME：一开始直接用stack判断括号匹配的思路做，左括号++，右括号出现时则左括号–。但是对于()(()就错了。于是考虑那从右往左再来一次，求左右二个max的较小者？但是又一次被())()()(()打败，左边右边对称，算出来都是错的。
TA：一开始参考这个写，维护一个存索引的stack，左括号则直接把索引push进去，右括号则看看栈顶的索引对应是否为左括号，是则弹出，否则把右括号的索引push进去，完成遍历后栈里面留下的就是造成invalid的一个个分割处的索引，遍历一遍栈的内容即得最长。不过照着实现一波之后发现超时。于是又参考这个，把之后的那一步遍历stack给融合到了前面的字符串遍历当中：同样维护一个存放int的stack，左括号直接入栈，右括号则需要分叉，若栈为空则说明不匹配，把left标记挪到当前这个索引；若非空则匹配成功，直接pop（因为栈中索引只可能是左括号的），弹出后再判断栈是否为空，若空了则之前的一长串括号都成功匹配了，用当前索引减去left即得这一段的长度；若非空则使用当前索引减去栈顶的索引表示当前已匹配的长度。很神奇，挺好懂的。当然，这题给的tag是DP，所以这个也要学习下。DP主要是状态转移方程，这里维护一个数组存放以当前索引结尾的字符串的最长valid长度。对于str[i] == '('，不可能以它为结尾，故直接设longest[i] = 0；对于str[i] == ')'，若前一位字符为左括号，则longest[i] = longest[i-2] + 2，若前一位字符为右括号，则需要看这个右括号所能匹配的最远的距离的再前一个字符是否为左括号，即str[i-longest[i-1]-1] == '('，若满足则不仅要加2，而且还要加上该左括号之前以为的valid长度（处理连续两个独立的且都是valid的括号组），即longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]。DP真的优雅，关键是找到这种『当前结果依赖之前结果』的规律，不一定是『前一项』，可以是往前若干项的结合。这题很漂亮。

Forgot the DP method!!

class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] dp = new int [s.length()];    // maxLen till curr char (only for valid ')')
        char[] sChar = s.toCharArray();
        int ans = 0;
        for (int i = 0; i < sChar.length; i++) {
            // only) is count as valid bit
            if (sChar[i] == ')') {      // "xxx)"
                if (i > 0) {        
                    if (sChar[i - 1] == '(') {  // prev is (, simply add 2 to prevprev
                        dp[i] = 2 + (i > 1? dp[i - 2]: 0);
                    } else {                    // prev is (
                        int prev = i - dp[i - 1] - 1;   // move to the very front of prev slot
                        if (prev >= 0 && sChar[prev] == '(') {  // only ( can match curr)
                            dp[i] = (prev > 0? dp[prev - 1]: 0) + 2 + dp[i - 1];    // check ('s prev
                        }
                    }
                    ans = Math.max(ans, dp[i]);
                }
            }
            
        }
        return ans;
    }
}

search-in-rotated-sorted-array

给一个已排好序但可能前后两段换了位置（例如12345变成45123），给一个target找出它的索引。
ME：排好序、查找，很自然想到二分，但是这个边界条件搞死我了。这个rotated的结果只有三种：left < mid < right, mid < right < left, right < left < mid，在这里面再分别对target讨论，很琐碎，面试时恐怕很难想周全，leetcode还可以在WA时告诉你是什么样例通不过，面试可就没这么好了。
TA：我的天，为什么这个可以这么简洁？！思想是，总有一半的数组是有序的，需要确认target在哪一半，这个代码真的是一看就懂，比你的不知高到哪里去了。

Trapped in edge conditions of your own method, which is complicated and impossible to debug in interview. After knowing the method of splitting into ascending part and mixed part, implementation is still not bug-free, because of edge cases in binary search.

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // firstly decide which part is ascending order
            // warning: although no duplicate in nums[],
            // there is an = here! because when left == mid, nums[left] == nums[mid]
            if (nums[left] <= nums[mid]) {  // first half is in order
                if (target >= nums[left] && target < nums[mid]) {   // nums[mid] excluded
                    right = mid - 1;    // target is in range of first half
                } else {
                    left = mid + 1;
                }
            } else {    // second half in order
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;     // target in range of second half
                } else {
                    right = mid - 1;
                }
            }
        }
        // 
        return nums[left] == target? left: -1;
    }
}

find-first-and-last-position-of-element-in-sorted-array

给一个已排好序的数组，给一个target，找出这个target出现的索引范围，存入length为2的int数组。要求时间复杂度为logn的常数倍。
ME：二分查找到了之后，再往左和往右分别继续进行二分查找，找到leftMost和rightMost的索引。
TA：这个是C++写的，直接用一个二分找左界，然后再额外找一个右界。稍微改一下二分，可以让它变为『查找首次出现的target索引』或者『最后一次出现的target索引』，这个要灵活一点。

Fail to implement the binary search which returns the first occurred index of target… For left, actually it’s non interrupt return version on BS, first index is at left; for right, need to prompt mid (add 1) to biase to right and last index is at right.

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int [] {-1, -1};
        }
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] != target) {
            return new int [] {-1, -1};
        }
        int leftMost = left;
        right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2 + 1;
            if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        int rightMost = right;
        return new int[] {leftMost, rightMost};
    }
}

search-insert-position

给一个已排好序的、不存在重复元素的数组，给一个target，找出他的索引或者他应该插入的位置。
ME：直接用刚刚学到的“第一个出现位置”的二分查找搞。末尾直接返回lo而不用判断，因为如果不等于的话其实也就相当于他应该插入的位置了。但是又忘记了边缘情况，例如hi取不取到length、数组中没有元素或者只有一个元素怎么办？
TA：毕竟是个衣洗提，大家想法差不多，比短码就没啥意思了，本来就没多少行。。。

Similar to previous return first binary search result function, but need to consider if the final return value should check target v.s. nums[left] or not: in the middle, nuh; in the rightmost end, yep.

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // warning: terminate condition should consider the rightmost insertion
        return left == right && target > nums[left]? left + 1: left;
    }
}

36. valid-sudoku

给一个二维char数组，里面是一个未完成的数独9x9棋盘，要求每一行、每一列、每个3x3方块中数字1-9有且仅有出现一次。判断这个棋盘是否符合数独规则，返回布尔值。
ME：一脸懵逼地用了个四重循环解决了。。。说是四重循环其实也就是遍历一遍9x9的棋盘，这应该是必须的。分别借助两个9x9的数组记录行和列的数字使用情况，再用一个长度为9的一维数组记录每个小正方形的，数组的索引通过字符-'1'获得，这样就省得用Map了。
TA：思想差不多吧，这个就是用Map的。这个是利用Set然后定义了一种String来记录是否出现过，利用set.add的返回值判断该字符串是否出现过，这个方法挺绝的。

Kinda boring…just check if current board is valid, not checking if it is solvable.

class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        Set<String> set = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.') {
                    if (!set.add(board[i][j] + " in row " + i) 
                        || !set.add(board[i][j] + " in col " + j) 
                        || !set.add(board[i][j] + " in block " + (i / 3) + '-' + (j / 3))) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

37. sudoku-solver

给一个二位char数组，里面是一个未完成的数独9x9棋盘，要求每一行、每一列、每个3x3方块中数字1-9有且仅有出现一次。解出数独，解有且仅有一种，直接在原二维数组中将.改为数字的char。
ME：纠结了半天，感觉是一个dfs的节奏，但是迟迟疑疑不敢下手怕是浪费时间，于是偷偷瞄了一眼discuss，发现就是用backtrack回溯，回溯和DFS在这里感觉是一回事？？于是用上一题的row col sqr记录来判断行、列、小方块是否合法，dfs搞定。
TA：偷瞄的就是这个。答主没有用辅助函数，直接遍历，然后另外用一个函数循环一波来判断是否合法。这个想法非常直接，一目了然。

DFS, use prev encoded string set.

class Solution {
    final String inRow = " in row ";
    final String inCol = " in col ";
    final String inBlk = " in blk ";
    public void solveSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0].length != 9) {
            return;
        }
        
        Set<String> set = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    set.add(board[i][j] + inRow + i);
                    set.add(board[i][j] + inCol + j);
                    set.add(board[i][j] + inBlk + i/3 + "-" + j/3);
                }
            }
        }
        dfs(board, set);
    }
    private boolean dfs(char[][] board, Set<String> set) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (int c = 0; c < 9; c++) {
                        char temp = (char)(c + '1');
                        String row = temp + inRow + i;
                        String col = temp + inCol + j;
                        String blk = temp + inBlk + i/3 + "-" + j/3;
                        if (!set.contains(row) && !set.contains(col) && !set.contains(blk)) {
                            set.add(row);
                            set.add(col);
                            set.add(blk);
                            board[i][j] = temp;
                            if (dfs(board, set)) {
                                return true;
                            } else {
                                set.remove(row);
                                set.remove(col);
                                set.remove(blk);
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
}

count-and-say

从1开始变化，数每个数字连续出现的个数代替原数字，例如1, 11, 21, 1211, 111221, 312211这样。给一个int表示往后的次数。
ME：用循环数连续出现数字的个数，相应的字符串用一个StringBuffer不断往后append就好。
TA：差不多吧，这是个衣洗题，不管了。

class Solution {
    public String countAndSay(int n) {
        if (n < 1) {
            return "";
        }
        StringBuilder sb = new StringBuilder("1");
        while (--n != 0) {
            int i = 0, len = sb.length();
            StringBuilder temp = new StringBuilder();
            while (i < len) {
                int count = 1;
                char curr = sb.charAt(i++);
                while (i < len && sb.charAt(i) == curr) {
                    i++;
                    count++;
                }
                temp.append(count);
                temp.append(curr);
            }
            sb = temp;
        }
        return sb.toString();
    }
}

combination-sum

给一个全为正整数的、不含重复项的int数组和一个正整数target，求任意个数组元素的list使得它们的和为target。
ME：全是正整数，立刻想到了桶排序，但这个『任意个元素组合』很不好搞，一时想不出来。。。
TA：依然是回溯法，似乎没人考虑怎么排序+二分使之更高效。这里有个大神总结了一个套路可以任意放在组合问题中，很强。受到这个点拨之后，这题和下一题都写出来了。以后要是还碰到这种回溯题，你得会了啊。需要指出的是，这题似乎是一个典型的动态规划题，因为涉及到了状态转换方程，解出target - candidate[x]的组合则target自然也就出来了。由于结果是二维的，DP就需要维护一个三维的List了。这次我竟然看懂了DP，自己也试了一波，下次争取盲写出来吧。不过跑出来比backtrack慢，大概是因为算了一些没必要的东西吧，毕竟要维护一个三维数组呢。。

Still DFS… I think it is a good point to conclude DFS as In-and-Out: Put sth in and assume it can count into result can go deeper, after that pop it out. There is also DP solution.

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return ans;
        }
        Arrays.sort(candidates);
        dfs(candidates, 0, target, 0, new ArrayList<Integer>(), ans);
        return ans;
    }
    private void dfs(int[] candidates, int index, int target, int sum, List<Integer> curr, List<List<Integer>> ans) {
        for (int i = index; i < candidates.length; i++) {
            int newSum = sum + candidates[i];
            if (newSum > target) {
                break;
            } else {
                curr.add(candidates[i]);
                if (newSum == target) {
                    List<Integer> temp = new ArrayList<>(curr);
                    ans.add(temp);
                } else {
                    dfs(candidates, i, target, newSum, curr, ans);
                }
                curr.remove(curr.size() - 1);
            }
            // remove duplicate because if this number has answer
            // it is already solved in the previous DFS iterations
            // Actually fits next problem....
            while (i + 1 < candidates.length && candidates[i + 1] == candidates[i]) {
                i++;
            }
        }
    }
}
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return ans;
        }
        
        Arrays.sort(candidates);    // still need to guarantee the order
        // dp[t] means the List<List<>> that sums up at t+1
        List<List<Integer>>[] dp = new List[target + 1];
        for (int i = 1; i <= target; i++) {
            dp[i] = new ArrayList<List<Integer>>(); // allocate memory
                                                // make sure candidate no larger than curr target i
            for (int j = 0; j < candidates.length && candidates[j] <= i; j++) {
                if (candidates[j] == i) {       // exact match -> 
                    dp[i].add(Arrays.asList(i));
                    break;  // actually no use. because there's no duplicate in cdds[]
                } else {
                    int index = i - candidates[j];
                    for (List<Integer> l: dp[index]) {
                        if (candidates[j] <= l.get(0)) {
                            List<Integer> temp = new ArrayList<>();
                            temp.add(candidates[j]);
                            temp.addAll(l);
                            dp[i].add(temp);
                        }
                    }
                }
            }
        }
        return dp[target];
    }
}

combination-sum-ii

给一个全为正整数的、可能含重复项的int数组和一个正整数target，求数组元素的list使得它们的和为target且每个元素最多只能用一次。
ME：和上面一样，backtrack小改一下搞定。试了一下DP，在三维的情况下对于标记『某元素已经使用过』比较麻烦，就没试了。
Almost the same. Skep it.

41. first-missing-positive

给一个乱序整数数组，要求返回所缺正整数中的最小值。要求constant space，O(n).
ME：看到O(n)和整数我就想到了木桶排序，这个想法肯定可行，但实现后发现Memory Limit Exceeded，看来题目并不给我开太大的数组。改小之后对小数据还是可以的，但总感觉借助了额外的空间不太符合要求。。。
TA：看了这个答案简直了，算是个技巧题吧，基本思想类似于往k+1个桶里扔k个有标号的球，漏掉的那个总会出现在1~k+1之间，那只需要把标号对应的球投入桶中，再从头遍历一遍找到空桶即得。在这题里，就是把正数k通过交换放到k-1处，从头到尾处理过一遍之后，总会有部分位置i的值不等于i+1，这个就是所求了。

O(N) time DOES NOT MEAN ONE-PASS!!! Fail to come up with this swapping and overwrite method. Critical at conditioning.

class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        
        int i = 0;
        while (i < nums.length) {
            if (nums[i] == i + 1 || nums[i] <= 0 || nums[i] > nums.length) {
                i++;
            } else if (nums[nums[i] - 1] != nums[i]) { // warning: not nums[i] != i + 1
                // critical: avoid re-overwriting that corrent spot
                swap(nums, i, nums[i] - 1); // i is curr index, nums[i] - 1 is where it should be
            } else {
                i++;
            }
        }
        i = 0;
        while (i < nums.length && nums[i] == i + 1) {
            i++;
        }
        return i + 1;
    }
    private void swap(int[] nums, int i, int j) {
        int temp =  nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

42. trapping-rain-water

给一个int数组，其中包含每个索引处墙的高度。求装满水时的横截面的积水的面积。
ME：扫一遍获得每个索引处的左侧最高墙和右侧最高墙，再从头扫一遍，若是凹形（比较小值还小）则用该较小值减去本索引的高度得到该索引处水的高度，即是面积了。
TA：服气，这个答案又见双指针，直接把我的两个分开的循环合并到一次里面完成了。其中的plank跟我的leftHi很像，都是从左往右遍历的过程中只能增加，但是plank是一次性比较两个指针的较小值，和我那个单向的比较高端（难懂）。代码越短越不好懂，类似的方法可能这个C++的好懂一丢丢。自己学着写了一波，速度稍微快了那么一点。

Ok for my own method with two auxiliary arrays. But if follow-up asks me to do it in constant space, need to know the method of two pointers.

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int[] hiLeft = new int [height.length];     // leftward highest
        int[] hiRight = new int [height.length];    // rightward highest
        int left = height[0], right = height[height.length - 1];
        for (int i = 1, j = height.length - 2; i < height.length; i++, j--) {
            hiLeft[i] = left;
            left = Math.max(left, height[i]);
            
            hiRight[j] = right;
            right = Math.max(right, height[j]);
        }
        
        int area = 0;
        for (int i = 0; i < height.length; i++) {
            int h = Math.min(hiLeft[i], hiRight[i]);
            if (height[i] < h) {
                area += (h - height[i]);
            }
        }
        return area;
    }
}
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int area = 0, maxLeft = 0, maxRight = 0;
        int left = 0, right = height.length - 1;
        while (left <= right) {
            if (height[left] <= height[right]) {    // 左指针处高度不大于右指针
                if (maxLeft <= height[left]) {
                    maxLeft = height[left];
                } else {                            // 只有当前高度完美小于左侧最大值才能储水
                    area += maxLeft - height[left]; 
                }
                left++;
            } else {    // 左指针处高度完美大于右指针
                if (maxRight <= height[right]) {
                    maxRight = height[right];
                } else {
                    area += maxRight - height[right];
                }
                right--;
            }
        }
        return area;
    }
}

43. multiply-strings

给两个字符串形式的int，模拟乘法求他们的积，返回字符串。
ME：这种数组模拟大数运算的题目我有点提不起劲，于是瞄了一眼答案做出来了。。。
TA：这个利用索引的小trick，一看就明。

44. wildcard-matching

和前面的regular-expression-matching很像，但这里用?代表任意一个字符、用*代表任意长度的任意字符而不依赖它前面的字符（而且不只能匹配单一个字符，直接匹配任意长度的任意字符组合）。总的来说比上一题简单，要讨论的情况少了。
ME：按照刚刚学习的动归DP思路维护一个二维boolean数组，dp[i][j]表示s[0~i-1]和p[0~j-1]是否匹配。初始化方面，对于空的p，dp[i][0]仍是除dp[0][0]外全部false，不可能用空的p去匹配非空的s；对于空的s，dp[0][j]就要看当前是否是'*'且考虑dp[0][j-1]。接着双重循环更新dp
-> 若当前字符p[j-1]是'*'，则考虑忽略它时，s[0~i-1]和p[0~j-2]的匹配情况，即dp[i][j-1]；或将'*'假设为s[i-1]那个字符，看看s[0~i-2]与p[0~i-1]的匹配情况，即dp[i-1][j]。
-> 若当前字符p[j-1]不是'*'，就直接看s[i-1]和p[j-1]的匹配情况再结合dp[i-1][j-1]了。
除了DP，这个题目似乎还可以用贪心给两个字符串分别用一个指针一直向后挪。

Misunderstood the problem, especially the ‘*’.

class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null || s.equals(p)) {
            return true;
        }
        int m = s.length(), n = p.length();
        char[] sChar = s.toCharArray(), pChar = p.toCharArray();
        boolean[][] dp = new boolean [m + 1][n + 1];
        dp[0][0] = true;    // "" fits ""
        for (int j = 1; j <= n; j++) {   // only "x*" can fit ""
            if (pChar[j - 1] == '*') {
                dp[0][j] = dp[0][j - 1];
            } else {
                dp[0][j] = false;
            }
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (pChar[j - 1] == '*') {  // don't take * or view * as one char or just
                                            // get rid of the char in sChar
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 1][j];
                } else {
                    if (pChar[j - 1] == sChar[i - 1] || pChar[j - 1] == '?') {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = false;
                    }
                }
            }
        }
        return dp[m][n];
    }
}

jump-game-ii

给一个元素非负的int数组，每个元素表示最多向后移几步，从index=0开始求最少经过几个节点到达末尾（含起点）。
ME：维护多一个一维数组，表示当前点一跳最远可以到达什么索引。贪心法，每次都选当前可达节点中下一步能跳得最远的点。
TA：这个似乎不需要额外的数组，毕竟每次你只关注『后续节点中最远可达的索引』。还有一种方式是考虑成BFS『分层问题』，当前可达的节点属于同一层，一直找到末尾节点所在的层数。

Know part of the idea but fail to implement it bug-freely…because you missed the condition to add step count.

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        int farthest = 0, step = 0, currEnd = 0, endIndex = nums.length - 1;
        for (int i = 0; i < endIndex; i++) {    // warning: not nums.length
            farthest = Math.max(farthest, nums[i] + i);
            if (i == currEnd) {     // reaches edge means you have to add 1 to go farther
                step++;
                currEnd = farthest;
            }
        }
        return step;
    }
}

permutations

给一个各元素不同的int数组，求全排列。
ME：回溯法（或者说带有visited标志的DFS）搞定。
TA：如果面试官要求不能用recursive的方法，那这个iterative的方法就可以搬出来了。思想是每次借助上一次的结果，把当前元素依次往每个位置插而产生新的排列。由于要利用上一次的结果，那么就在第一重循环之前先给ans放入只有一个nums[0]元素的序列，然后每次取出一个ans中的序列并来一波循环插入新元素。

DFS OK.

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        boolean[] used = new boolean [nums.length];
        dfs(nums, used, new ArrayList<Integer>(), ans);
        return ans;
    }
    private void dfs(int[] nums, boolean[] used, List<Integer> curr, List<List<Integer>> ans) {
        if (curr.size() == nums.length) {
            ans.add(new ArrayList<Integer>(curr));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] == false) {
                curr.add(nums[i]);
                used[i] = true;
                dfs(nums, used, curr, ans);
                curr.remove(curr.size() - 1);
                used[i] = false;
            }
        }
    }
}

permutations-ii

给一个可能有重复元素的int数组，求全排列，不可以有重复。
ME：也是回溯法，与上一题区别在于需要先排个序，然后每次往里放元素之前先判断是否和前面空闲元素相等，若相等则不能选取，因为前面相等的元素空闲说明这个位置它已经排列过了。
TA：按照上一题的那个iterative的方法改造了一下，去重只需要排序+在插入时判断要插入位置前一个字符是否相同即可，相同就跳过了。

Pretty much the same thing to previous one.

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        Arrays.sort(nums);  // sort for duplication avoidance
        
        boolean[] used = new boolean [nums.length];
        dfs(nums, used, new ArrayList<Integer>(), ans);
        return ans;
    }
    private void dfs(int[] nums, boolean[] used, List<Integer> curr, List<List<Integer>> ans) {
        if (curr.size() == nums.length) {
            ans.add(new ArrayList<Integer>(curr));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                    continue;
                }
                used[i] = true;
                curr.add(nums[i]);
                dfs(nums, used, curr, ans);
                curr.remove(curr.size() - 1);
                used[i] = false;
            }
        }
    }
}

rotate-image

给一个n*n的int数字矩阵，顺时针旋转90°。
ME：直接走in-place了，思路是每一条正方形上边缘的n-1个元素来挪动，沿边的长度挪动n-1次，然后再到内部的正方形去继续移动，直到n-1 < 1，说明只剩一个元素或没有元素了。在纸上写了一堆矩阵找规律，好歹找出来了。
TA：我还以为自己好不容易找到一个还不错的规律，没想到还能通过对角线对称+左右对称搞定。这个可以扩展到顺时针（左右swap）、逆时针（上下swap）的通用解法。

fail to come up with the above symmetric method. Even know the idea, I just didn’t make the diagnol symmetric correct. diagnol is from top-left to bottom-right

class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int n = matrix.length;
        // firstly get diagonal symmetric
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        
        // then flip left and right part
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = temp;
            }
        }
    }
}

group-anagrams

给出一个String的数组，找出其中的『同字母异序』字符串并归类存入二维String数组返回。
ME：先对原数组排序，然后对每个字符串转成char数组，计算各位char的ascii码之和并重新排序，将这些整理后的string一个个再存入新的数组，然后再双重循环往后比较。被String默认的sort（compareTo）坑了，他是先找有没有字母不同，然后再看长度。后来利用传入自定义的Comparator，结果超时了。
TA：这个方法每次都把原数组中抓到的String转成char[]再排个序，把这个再转为String作为key来查找HashMap>，每次对应上了就往List里add就可以了，好简单。。。这个方法有点像我最开始想采用的，就是利用每个字符串的字母本身形成某种与顺序无关的唯一性，而ascii码相加显然不够我就多弄了点手段，而这个方法利用的是素数来创建key，可以保证字母一样的字符串求出的key相同。利用素数乘积这个想法真的强。
自定义Arrays.sort的第二个参数Comparator，需要实现其中的compare方法，用匿名类就可以了。自定义类的排序则是使用Collections.sort。

Once know the sorting method, its done.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        if (strs == null || strs.length == 0) {
            return ans;
        }
        
        Map<String, Integer> map = new HashMap<>();
        for (String str: strs) {
            char[] sChar = str.toCharArray();   // sort str
            Arrays.sort(sChar);             
            String newStr = new String(sChar);  // the key to get the index in ans
            if (map.containsKey(newStr)) {
                int index = map.get(newStr);
                ans.get(index).add(str);
            } else {
                map.put(newStr, ans.size());
                List<String> temp = new ArrayList<>();
                temp.add(str);
                ans.add(temp);
            }
        }
        
        return ans;
    }
}

powx-n

给一个double为底数、一个int为幂，求pow(x, n)。
ME：一开始想直接暴力用循环乘乘乘搞出来，结果超时。小看了一波解答，通过递归解决了，原理是在传入下一层递归之前，底数放大同时缩小指数，毕竟之前超时的版本中最耗时的就是根据指数来循环。
TA：这里有一个集锦，列举了五种解法。
取模操作%可以用与操作&代替，因为单数的最后一位必定是一，这样x&1的结果就不是0了。

Wow, there is an update in test cases. Fail to come up with the recusive method.

 class Solution {
    public double myPow(double x, int n) {
        if (n == 0 || x == 1) {
            return 1;
        }
        if (n == Integer.MIN_VALUE) {   // warning overflow if simply reverse n in this case
            return (1.0 / x) * myPow(x, n + 1);
        }
        if (n < 0) {
            n = -n;
            x = 1.0 / x;
        }
        return (n & 1) != 0? x * myPow(x*x, n/2): myPow(x*x, n/2);
    }
}

n-queens

N皇后问题，国际象棋中的皇后可以任意攻击横+竖+45°的棋子，给一个整数n表示有n个皇后，返回这个n*n棋盘上所有可能的皇后位置。
ME：DFS（或者叫回溯？？），很经典的算法嘛。利用一个辅助的table记录当前放下的这个皇后的杀伤范围（五个方向），然后到下一行去dfs搜索是否有位置放。
TA：都是要用到递归的。这里有一个比较巧妙的validate函数，两个对角线的皇后判别利用的是横纵坐标相加相等（/对角）和横纵坐标交叉相加相等（\对角）这种方式。其实后者这个对角线验证用横纵坐标之差相等更好理解=_=。

It should be a easy problem for DFS…but still fail because of diagonal conflict detection.

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        if (n <= 0) {
            return ans;
        }
        char[][] table = new char [n][n];        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                table[i][j] = '.';  // all . at first
            }
        }
        
        dfs(table, 0, ans);
        return ans;
    }
    private void dfs(char[][] table, int col, List<List<String>> ans) {
        if (col == table[0].length) {
            ans.add(generate(table));
            return;
        }
        for (int i = 0; i < table.length; i++) {
            if (isValid(table, i, col)) {   // if put Q at (i, col)
                table[i][col] = 'Q';
                dfs(table, col + 1, ans);
                table[i][col] = '.';
            }
        }
    }
    private boolean isValid(char[][] table, int x, int y) {
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < y; j++) { // warning don't go further than y
                if (table[i][j] == 'Q' 
                    && (i == x || (x + y) == (i + j) || (x - i) == (y - j))) {
                    // the diagnol judgement is error-tempting
                    return false;
                }
            }
        }
        return true;
    }
    private List<String> generate(char[][] table) {
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < table.length; i++) {
            String row = new String (table[i]);
            ret.add(row);
        }
        return ret;
    }
}

n-queens-ii

N皇后问题简略版，不用把棋盘输出，只是输出解的个数。
ME：我是没想到更快的办法，还是用table[][]的老路子。
TA：这个就用到了横纵坐标相加/相减的办法来标记主/副对角线是否冲突。使用了三个set来维护列和两个对角的占用情况，就不用每次都循环一遍table来更新占用情况了，直接在set.add就好，用完了就remove，快很多。

Actually your initial thought for previous question can be used here, that is to mark the usage on 2 diagnols and rows and cols.

class Solution {
    private Set<Integer> colSet = new HashSet<>();
    private Set<Integer> diogSet1 = new HashSet<>();
    private Set<Integer> diogSet2 = new HashSet<>();
        
    public int totalNQueens(int n) {
        if (n <= 0) {
            return 0;
        }
        return dfs(0, 0, n);
    }
    private int dfs(int row, int count, int n) {
        if (row == n) {
            return ++count;
        }
        for (int col = 0; col < n; col++) {
            if (colSet.contains(col)
               || diogSet1.contains(row + col)
               || diogSet2.contains(row - col)) {
                continue;
            }
            
            // row,col is valid
            colSet.add(col);
            diogSet1.add(row + col);
            diogSet2.add(row - col);
            count = dfs(row + 1, count, n);
            colSet.remove(col);
            diogSet1.remove(row + col);
            diogSet2.remove(row - col);
        }
        return count;
    }
}

53. maximum-subarray

求一个数组中的sum最大的连续子串。
ME：玛德一道衣洗题想半天，还差点用O(n^2)暴力法搞了。想着用动归的思路维护一个二维数组，但是在找规律的过程中发现并不需要这么大的一个table，每次只用到了当前项和到前一项为止的最大值加上当前项，二者做个比较取较大者，于是一个O(n)，一个curr，一个max就搞定了。这种最优化问题，通常都能用DP的思路来解决。
TA：提示里说不要满足于O(n)的方法，用分治来搞更subtle。自己想了半天没想出来怎么分治，看了这个才明白。分治关键是怎么拆分问题，分成两半后最大子串要么在左半边、要么在右半边、要么在中间交叉的位置。因此，不断划分并求这三个sum，取三者中最大值作为当前划分的最大子串和返回。求交叉位置之和是，就是从mid开始往左累加刷新最大的leftsum、从mid+1开始向右累加刷新最大的rightsum，求left+right即为交叉子串的最大和了。不得不说，不太好懂啊。

Not quite smooth with this question tagged EASY. The divide-and-conquer is even more difficult to come up with.

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int ans = Integer.MIN_VALUE, prev = 0;
        for (int i = 0; i < nums.length; i++) {
            prev = Math.max(prev + nums[i], nums[i]);
            ans = Math.max(ans, prev);
        }
        return ans;
    }
}
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return getMax(nums, 0, nums.length - 1);
    }
    private int getMax(int[] nums, int left, int right) {
        if (left == right) {    // end case
            return nums[left];
        }   
        int mid = (right + left) / 2;
        int leftMax = getMax(nums, left, mid);          // get max subarray only with left elements
        int rightMax = getMax(nums, mid + 1, right);    // get max ~ right
        int midMax = getMidMax(nums, left, mid, right); // get max sub that uses both left and right
        return Math.max(leftMax, Math.max(rightMax, midMax));
    }
    private int getMidMax(int[] nums, int left, int mid, int right) {
        int leftMax = Integer.MIN_VALUE, rightMax = Integer.MIN_VALUE;
        int sum = 0;    
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftMax = Math.max(sum, leftMax);   // at least take one element from left
        }
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {    
            sum += nums[i]; 
            rightMax = Math.max(sum, rightMax); // at least take one element from right
        }
        return leftMax + rightMax;
    }
}

spiral-matrix

给一个二维数组表示的int矩阵，螺旋式输出这个矩阵。
ME：就直接按照规则，螺旋式输出，从左到右、从上到下、从右到左、从下到上。然后进入里面一层，一圈一圈遍历。边缘情况就是在四个方向中1切换到2和2切换到3时判断一下是否已经超过了边界，防止重复输出。
TA：似乎玩不出花样了。

Fails with edge cases. this problem uncovers your disability to raise as much special edge cases as possible. Each condition need different constriants on iterating variables.

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return ans;
        }
        int m = matrix.length, n = matrix[0].length;
        int level = 0, limit = Math.min((m + 1) / 2, (n + 1) / 2);
        while (level < limit) {
            int i = level, j = level;
            while (j < n - level) {
                ans.add(matrix[i][j++]);
            }
            j = n - level - 1;
            i++;
            if (i == m - level) {   // for single line
                break;
            }
            while (i < m - level) {
                ans.add(matrix[i++][j]);
            }
            i = m - level - 1;
            j--;
            if (j < level) {    // for single column
                break;
            }
            while (j >= level) {
                ans.add(matrix[i][j--]);
            }
            j = level;
            i--;
            while (i > level) {
                ans.add(matrix[i--][j]);
            }
            level++;
        }
        return ans;
    }
}

jump-game

给一个数组，每一个位置表示最大跳多少步，返回boolean看能否从首位跳到末尾。
ME：贪心法，维护一个『当前可到达最远的索引』，能到最后算你赢。
TA：也玩不出什么花样了吧。已然O(n)。

OK. constant space.

class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length < 2) {
            return true;
        }
        int i = 1, farthest = nums[0], lastIndex = nums.length - 1;
        while (i <= farthest) {
            farthest = Math.max(nums[i] + i, farthest);
            if (farthest >= lastIndex) {
                return true;
            }
            i++;
        }
        return false;
    }
}

56. merge-intervals

给一个Interval类的list，将重叠部分进行合并，返回合并之后的list。
ME：自定义根据各Interval的左边界排序，然后判断当前Interval的左边界是否与前一个Interval的右边界有重合，有则将当前Interval的边界进行更新，然后remove掉前一个Interval。AC时发现耗时比较多，大概是这个remove比较不划算吧。但是你说改成LinkedList，那get又变得很不划算了，所以这个办法总的来说就不是很高效。
TA：这里有一个使用stack的方法，也是先根据左边界排序。然后遍历，若当前的Interval比栈顶的右边界大，直接入栈；否则就更新栈顶的右边界为二者右边界的较大值。很优雅，不过也没有快多少。在提交界面倒是看到最快的哪个答案是用一个left和一个right数组来搞的，
自定义类的排序使用Collections.sort，需要指定comparator。在Java8中还有个更简洁的lambda写的comparator。stack转List不需要什么遍历插入，只需要直接构造子传入就可以了。

When knows the method of sorting and stacking, OK.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null) {
            return new ArrayList<Interval>();
        }
        Collections.sort(intervals, (a, b) -> {
            if (a.start != b.start) {
                return a.start - b.start;
            } else {
                return a.end - b.end;
            }
        });
        Stack<Interval> stack = new Stack<>();
        for (Interval itv: intervals) {
            if (stack.isEmpty()) {
                stack.push(itv);
            } else {
                Interval curr = stack.peek();
                if (itv.start > curr.end) {
                    stack.push(itv);
                } else {
                    stack.peek().end = Math.max(itv.end, curr.end);
                }
            }
        }
        // directly get List from stack with constructor
        return new ArrayList<Interval>(stack);
    }
}
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> ans = new ArrayList<Interval>();
        if (intervals == null) {
            return ans;
        }
        int len = intervals.size();
        int[] left = new int [len];     // all left boundary
        int[] right = new int [len];    // all right boundary
        for (int i = 0; i < len; i++) {
            left[i] = intervals.get(i).start;
            right[i] = intervals.get(i).end;
        }
        Arrays.sort(left);
        Arrays.sort(right);
        // fast will select right bound and fast+1 is the candidate for next left bound
        // when candidate is valid, store curr interval (slow, fast) and move slow to candidate
        // for next left bound
        for (int fast = 0, slow = 0; fast < len; fast++) {
            if (fast == len - 1 || left[fast + 1] > right[fast]) {
                ans.add(new Interval(left[slow], right[fast]));
                slow = fast + 1;
            }
        }
        return ans;
    }
}

insert-interval

给一个互不交叉的Interval类的list，给一个newInterval插入进去，并进行相应的合并if necessary，返回合并之后的list。
ME：遍历原list，取出时与newInterval比较看看是否重叠，若有重叠则合并后作为新的newInterval继续比较，若无重叠则看看谁更小，若newInterval更小说明已经结束，后面都不会有重叠的了，加入结果的ArrayList即可。边缘情况是若从头到尾都没有重叠且都小于newInterval，则需要额外把newInterval加入。
TA：想法都差不多吧，不过你的边缘情况似乎有点多余。因为在判断的时候可以知道什么时候『之后的都不会有重叠的了』，此时跳出循环，把newInterval加入，然后把剩余部分直接塞入结果即可。

With edge case failing at inserting into the very last postion of original list because at first I used non-check binarysearch, which will not get the correct insert position. Implementing verbosely…

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> ans = new ArrayList<Interval>();
        if (intervals == null || intervals.size() == 0) {
            if (newInterval == null) {
                return ans;
            } else {
                ans.add(newInterval);
                return ans;
            }
        }
        
        // find the pos for left bound to insert(equal or small than the start at that index)
        int len = intervals.size();       
        int lo = 0, hi = len - 1;
        while (lo <= hi) {      // warning: need to make sure the correctness of insert index
            int mid = lo + (hi - lo) / 2;
            if (newInterval.start > intervals.get(mid).start) {
                lo = mid + 1;
            } else if (newInterval.start == intervals.get(mid).start) {
                lo = mid;
                break;
            } else {
                hi = mid - 1;
            }
        }
        
        int frontNum = 0;
        // if equals
        if (lo < len && intervals.get(lo).start == newInterval.start) {
            frontNum = lo;  // no overlap for first lo intervals
        } else {
            if (lo > 0) {   // compare to prev's end bound
                if (newInterval.start > intervals.get(lo - 1).end) {
                    // no overlap with prev, check 
                    frontNum = lo;
                } else {
                    frontNum = --lo;    // lo need to back to prev because of overlap
                    newInterval.start = intervals.get(lo).start;
                }
            } else {    // newInterval insert at very first
                frontNum = 0;
            }
        }
        System.out.println(frontNum);
        // get the OK part in the front from 0 to frontNum
        int i = 0;
        while (i < frontNum) {
            ans.add(intervals.get(i++));
        }
        
        // deal with overlapping parts
        // expand newInterval's end if overlapping with following intervals
        while (i < len && newInterval.end >= intervals.get(i).start) {
            newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
            i++;
        }
        ans.add(newInterval);
        
        // add the rest non-overlapping intervals
        while (i < len) {
            ans.add(intervals.get(i++));
        }
        return ans;
    }
}

length-of-last-word

给一个只包含字母和空格的字符串，返回最后一个独立单词的长度。
ME：从尾巴往前遍历，找到空格或首部即为最后一个单词的长度。
TA：没什么花样，毕竟衣洗题。

OK.

class Solution {
    public int lengthOfLastWord(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] sChar = s.toCharArray();
        int i = sChar.length - 1;
        while (i >= 0 && sChar[i] == ' ') { // actually can use trim at s firstly...
            i--;
        }
        if (i < 0) {
            return 0;
        }
        int anchor = i;
        while (i >= 0 && sChar[i] != ' ') {
            i--;
        }
        return anchor - i;
    }
}

59. spiral-matrix-ii

给一个整数n，生成一个n*n的二维数组方阵，使得螺旋式遍历的结果为1,2,3,…,n^2。
ME：就按照螺旋的顺序赋值呗。
TA：没啥花样。

OK.

class Solution {
    public int[][] generateMatrix(int n) {
        if (n <= 0) {
            return new int [0][0];
        }
        int[][] ans = new int [n][n];
        int level = 0, end = (n + 1) / 2, num = 1;
        while (level < end) {
            int i = level, j = level; 
            while (j < n - level) {     // left to right at top
                ans[i][j++] = num++;
            }
            
            j = n - level - 1;  
            i++;
            if (i == n) {       // for single line
                break;
            }   
            while (i < n - level) {     // top to bottom at right
                ans[i++][j] = num++;
            }
            
            i = n - level - 1;
            j--;
            if (j < level) {     // for single column
                break;
            }
            while (j >= level) {        // right to left at bottom
                ans[i][j--] = num++;
            }
            
            j = level;
            i--;
            while (i > level) {         // bottom to top at left
                ans[i--][j] = num++;
            }
            level++;
        }
        return ans;
    }
}

permutation-sequence

给两个整数n和k，求这个n产生的全排列中的第k个排列，返回这个字符串。
ME：全排列已经挺熟练的了，先把正常版本的全排列写出来，然后考虑如何加速。既然求的是第k个，那么在确定了当前这一位之后需要看看剩下的选择数还能产生多少可能性，如果这个可能性小于k，说明以当前这一位不能达到第k个排列，因此继续向后找；若这个可能性大于等于k，说明这第k个就落在当前这一位确定的情况下，所以确定这一位，相应更新一下标记数组和剩余可选择数，继续搜索。一开始想一步到位搞了半天，其实应该先把正常的写出来，再考虑怎么优化以适应这道题的要求。
TA：我的方法是recursive的，解答里给出了不少iterative的，例如这个，用了一波发现比递归快呢。阶乘没必要每次都求啊，可以直接存入一个阶乘值的数组。

Come up with iterative method, but it seems that months ago I solve it recursively..

class Solution {
    private int[] factorial;
    public String getPermutation(int n, int k) {
        if (n <= 0) {
            return "";
        }
        boolean[] used = new boolean[n];
        factorial = new int [n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        if (k > factorial[n]) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        int currK = 0, level = 1;
        while (level <= n) {
            // check where is k
            int index = 0;  // the number to include
            while (currK + factorial[n - level] < k) { // k is still behind
                currK += factorial[n - level];  // take next number as leading element
                index++;
            }
            // put the #index available number into sb
            for (int i = 0, j = 0; i < n; i++) {
                if (!used[i]) {
                    if (j++ == index) {
                        sb.append(i + 1);
                        used[i] = true;
                        break;
                    }
                }
            }            
            // update k and currK for next iteration
            k -= currK;
            currK = 0;
            level++;
        }
        return sb.toString();
        
    }
    
}

rotate-list

给一个链表，给一个整数k,要求把链表最右k个元素放到链表最前面。
ME：滑动窗口/快慢指针呗，左右指针从伪头部出发，先让右指针移k，之后左指针再开始移，直到右指针来到末尾。调整一下四个位置链表节点的指向即可。但一开始超时，这是因为对于k超出链表长度的情况，没有灵活处理。当右指针已经来到末尾而左指针还没有出发，说明k比较大，那么就用链表长度取个模，再把右指针丢回伪头部重新出发，根据这个新的k来滑动。
TA：这个也是快慢指针，简化了很多判断，直接把快指针挪到末尾得到长度，然后再让慢指针根据k和链表长度取模的结果移到所需节点，然后操作一发。

Idea is OK, but not able to get it bug-free at once, because of the order that judge the k == 0 condition.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        ListNode fast = head, slow = head;
        int len = 0;
        while (k-- > 0) {   // get the len (if k is larger than k) or move fast k steps firstly
            fast = fast.next;
            len++;
            if (fast == null) { 
                fast = head;
                k %= len;       // adjust k to [0, len)
                if (k == 0) {   // warning need to return here not before k % len.
                    return head;
                }
            }
        }
        // move both slow and fast. when fast.next == null, it's the last element
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // at this point, slow.next is the new head, and need to link original head to the tail
        ListNode newHead = slow.next;
        fast.next = head;
        slow.next = null;
        return newHead;
    }
}

unique-paths

给两个整数m和n，表示m*n的棋盘，去从左上角的棋子到达右下角的路径数，棋子每次只能向下或者向右。
ME：找到了规律，在m*n的数组中，每个(i,j)处的值表示到达该处的路径数，除了左边缘和上边缘的路径数为1，其余的位置都由其上方和左方路径数决定，相加即可。一开始没找到这个还用了深度优先，结果超时了。。。
TA：原来我这个思路也能叫作DP了，因为当前结果是依赖前面的运算结果的。这个可以优化成只是用一维数组。反正我也用不着除了右下角的其他值，那我每次都一波流叠加就行了，不用维护完整的table。

Ummm, not really solved by my own. After know the method of DP, OK.

class Solution {
    public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        
        int[] dp = new int [n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {   // iterate by row
            for (int j = 1; j < n; j++) {   // iterate by column
                dp[j] = dp[j] + dp[j - 1];  // prev dp[j] means coming from top
                                            // dp[j - 1] means coming from left
            }
        }
        return dp[n - 1];
    }
}

unique-paths-ii

给一个二维数组，0表示可以走、1表示走不通，仍然求左上角到右下角的路径数。
ME：直接给了个二维数组，那就直接在二维数组上操作之。实现起来很快，但是！边缘情况真是搞死我辣，WA了好多次。。因为初始化的时候不能够像上一题一样直接对左边缘和上边缘直接赋值为1了，需要根据障碍情况来赋值，所以也是需要用到前面棋盘的结果的。此外还有终点/起点本身就走不通这种小妖精。。。
TA：这个同样可以简化成一维数组，只不过就不是in-place了。三楼指出了这个思路下数组的含义：dp[j]表示当前行到达第j列的可能路径数。

Pretty much similar to previous one, but need to pay attention to dimention of dp array(= =) and when updating each row, you have to consider if the obstacle happens at the very first one so your loop variable cannot start from 1 as it is in previou question.

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
            return 0;
        }
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;   // can't be reached if it is natrually blocked
        }
        
        int[] dp = new int [n];
        dp[0] = 1;
        for (int j = 1; j < n; j++) {
            // if obstacled, set as 0
            if (obstacleGrid[0][j] == 1) {
                dp[j] = 0;
            } else {
                dp[j] = dp[j - 1];    // only viable from previous in the same row
            }
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else {
                    if (j > 0) {    // if obstacle is at the first of line
                        dp[j] = dp[j - 1] + dp[j];
                    }
                }
            }
        }
        return dp[n - 1];
    }
}

minimum-path-sum

给一个m*n的非负数的矩阵，求一个从左上角到右下角的路径使得经过的数字之和最小，返回这个最小之和。同样每次只能向右或向下移。
ME：还是累加，遍历一遍棋盘，每次更新的时候选择左/上之间较小者加上当前位置的数字。
TA：没啥花样了，基本都是DP。

OK. Greedy cannot work because it can only be tempted to choose the smaller one between the only two elements it can see, but optimal might be hidden somewhere else. Here use

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int[][] result = new int [grid.length][grid[0].length];
        for (int[] temp: result) {
            Arrays.fill(temp, -1);
        }
        return getMinSum(grid, result, 0, 0);
    }
    private int getMinSum(int[][] grid, int[][] result, int x, int y) {
        if (result[x][y] != -1) {
            return result[x][y];
        }
        if (x == grid.length - 1) { // at the bottom row
            if (y == grid[0].length - 1) {  // at the right most column
                result[x][y] = grid[x][y];
            } else {   // only move right
                result[x][y] = grid[x][y] + getMinSum(grid, result, x, y + 1);
            }
        } else {
            if (y == grid[0].length - 1) {  // at the right most column
                result[x][y] = grid[x][y] + getMinSum(grid, result, x + 1, y); // only move downward
            } else {        // try both right and bottom
                result[x][y] = grid[x][y]
                    + Math.min(getMinSum(grid, result, x, y + 1), getMinSum(grid, result, x + 1, y));
            }
        }
        return result[x][y];
    }
}

valid-number

给一个字符串，判断它是否是合法的数字，返回布尔值。
ME：这个跟算法没什么关系吧，就是考虑各种情况，看够不够细心。除了0~9，只可能出现+、-、e、.四种额外字符。写了个helper函数，传入起始位置和这四个符号的flag。、
TA：没啥算法吧。。
Ignoring…

plus-one

给一个数组，每一个索引存储的是对应的一位数字，返回这个数字加1的结果的数组。
ME：搞一个LinkedList负责不断往头部插入当前这一位的数字，进位为0后就直接赋值了。但是我的runtime特别特别慢，只打败1%！估计是LinkedList这里拖后腿了。
TA：这个方法告诉你，你的这个LinkedList没有必要，如果没有进位的话直接inplace就可以办到，当这个数字小于9，直接加上1就可以返回原数组了；如果等于9，则改为0后还要往前一位再判断；如果全部都遍历完还是没有返回，说明全是9，那么这时才需要额外申请一个规模大1位数组，直接把首位赋值为1就可以返回了。关键是很可能提前结束循环，不需要完全遍历原数组，节省了很多时间。
List类型存储的都是对象，因此没有办法直接用toArray()方法转成基本数值类型的数组。只能遍历一遍放入。

OK if know the trick to check when to allocate another array with extended size.

class Solution {
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length == 0) {
            return new int [0];
        }
        // add 1 and check if there is a carry.
        int len = digits.length;
        for (int i = len - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            } else {
                digits[i] = 0;
            }
        }
        // if still not returned, it means the number is 9999...9
        int[] ans = new int [len + 1];
        ans[0] = 1;
        return ans;
    }
}

67. add-binary

给两个String表示的二进制数，返回二者相加后的二进制字符串。
ME：学习了一个，注意了提前return，所以这次写出来速度打败98%！两个数组对应位置数字相加再加个进位，超过1就-=2并更新进位。
TA：这个比较简洁，全程用StringBuffer搞，算一位append一位，最后reverse一下即可。
进位的英文是carry。

Fail to come up with the graceful sb and reverse solution. WA because forget the condition where carry will be add to the most significant position.

class Solution {
    public String addBinary(String a, String b) {
        if (a == null || a.length() == 0) {
            return b;
        } else {
            if (b == null || b.length() == 0) {
                return a;
            }
        }
        StringBuilder sb = new StringBuilder();
        char[] aChar = a.toCharArray(), bChar = b.toCharArray();
        int i = aChar.length - 1, j = bChar.length - 1, carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;    // from prev result
            if (i >= 0) {
                sum += aChar[i--] - '0';
            }
            if (j >= 0) {
                sum += bChar[j--] - '0';
            }
            sb.append(sum % 2); // what's left after taking out carry
            carry = sum / 2;    // 3,2 -> 1; 1,0 -> 0
        }
        if (carry != 0) {
            sb.append(carry);   // warning! the most significant position
        }
        return sb.reverse().toString();
    }
}

text-justification

给一个String的数组和每行的字符数，要求把这些字符串单词依次输出到每一行中，如果到末尾有空余又塞不下后面的单词的话，需要让该行最后一个单词向右靠并尽量让行中的空格平均分布，若无法很平均则前面的空格可以稍多于后面的。
ME：这题说是哈德，其实也一般吧。没啥好说的，先逐步读入单词看看什么时候放不下了，就调用辅助函数将这些单词尽量平均分步，利用取模/整数除法计算应该塞多少空格。写完了之后确实没什么好说的，没什么精妙之处。
TA：听说可以用DP，不过高票答案都是和我差不多的。。。

sqrtx

给一个int，返回它的开方。负数直接返回本身。
ME：和之前做过的一个pow有点像，得考虑如何加速。我能想到的就是折半、折半…这样，找到n*n < x的时候，再一点点加，找到合适的值。需要注意的是越界的情况，因为x/2得到的n平方一下可能特别大。提交后发现贼慢，只超过2%！
TA：这个总结了个牛顿法出来，我的思路和它有点像，不过它更优雅，因为没有最后那个++的过程。另外这个二分查找的方法比较合我心意。另外，一个避免越界的办法是不要用n*n，改成用x/n来判断。奇怪的是，我写的这个二分也不快，但是看最快的那个方法基本和我一样啊摊手。这里还有一个利用位运算的方法，这个真的就是程序员的思路了，先把整数最高位设为1（1<<15）存入h，然后从高到低挪，与一个ans取或运算之后，把这个ans与x/ans做比较，若大于说明太大了，ans与h取个异或把这一位1给拿掉，再继续挪h。。这么说可能也不是很好懂吧，确实是比较计算机的思维。位运算确实还是比较快的，打败了77%。还有一个方法是利用sqrt(x) = (2sqrt(x))/2 = 2sqrt(x/4)来求的，边缘情况是非完全平方数的时候，需要将结果加个1再判断一下。一个衣洗题搞出这么多花样，服气。

climbing-stairs

给一个整数n表示阶梯的级数，每次只能跳1或2级，求跳到最高级的路径数。
ME：自从用了DP，根本停不下来，特别是这种带有状态变化的。当前这一级只可能是前一级或前两级跳过来的，因此把这俩的路径数一加就是当前这一级的路径数了。用dfs也可以做，但超时了，而且不太好解释呢。
TA：高人点出这就是一个斐波那契数列。这个更是直接套了公式了。

simplify-path

给一个Unix风格的路径字符串，返回经过简化的路径字符串。例如.., .这些都需要简化。
ME：很容易想到用栈来处理路径中的..，不过一开始并不知道Stack可以使用List的接口直接转为List，实际上我是直接用一个ArrayList模拟了栈的操作。提示里有两个边缘情况，你自己再回忆一下吧，不剧透了。我这个方法一不小心打败了99%呢。
TA：这个提醒了我，Stack的遍历顺序是反的，那可以用Deque。同时答主利用了String.split来产生一组根据/划分的字符串集合，然后遍历这些字符串看看是否属于"..", "."以及""，若不是说明是路径名，push即可。前面的三个字符存在一个HashSet中，这个空字符串是为了应对//这种情况。

72. edit-distance

给两个字符串word1, word2，求使用addition, replacement, removement三种操作的情况下最少多少步可以从word1转换成word2。
ME：卡了很久，搞了一上午，真心不知道怎么搞，情况实在太多太复杂了，一点都不清晰。
TA：原来要用DP啊，关键是我做的时候不知道怎么定义状态就没往这儿想了囧。看了这个解释笋干明咗。dp[i][j]表示当前长度i的子字符串1转换成长度j的子字符串2最少需要的操作数。初始条件显然是dp[0][x] = dp[x][0] = x。对于任意一个dp[i][j]，需要由上、左上、左三个方格的计算结果决定，往上dp[i-1][j]表示一个deletion，往左dp[i][j-1]表示一个addition，左上dp[i-1][j-1]表示一个replacement。每次选取三者中最小的，加上1就是当前的最小操作数了。明白了DP原理之后，真的是秒杀。。。以后没思路就考虑是不是得DP一下了。此外，还有一种将DP二维数组简化成一维的的，点最快那个可以看到。

set-matrix-zeroes

给一个二维int数组的矩阵，当某元素m[i][j]为0时，将行和列的所有元素都设为0.要求inplace完成。
ME：借助规模分别为m和n的辅助数组记录在哪行、哪列出现了0，后续再遍历到的时候就可以直接设为0了。一开始误会了inplace，还以为完全不可以使用额外的空间。inplace的意思是不允许复制到另外的数组并返回。感觉已经最优，不过时间居然还不是最快，有个循环了两轮的反而更快，大概是判断更少更简洁？？follow up要求使用constant space而不是O(m+n) space。想了一下想不出来。。。
TA：看了这里才明白，原来O(1) space利用的是每一行/每一列的首位元素作为标志为，出现了一个0后对应的行首/列首就设为0！需要额外注意的是当行首/列首本身就是0的话，得最后再来一波赋值。妙哉啊妙哉！

search-a-2d-matrix

完成一个二维数组版本的二分查找，这个矩阵是已经排好序的，每一行从左到右是递增的，下一行的最小元素也一定比上一行的大。返回布尔值。
ME：警告，我好像又有点忘记了经典的二分查找，赶紧看看Princeton的笔记。两层二分查找嵌套，利用行首、行末来决定是否真的要换行。
TA：如果不考虑超大的m*n的越界问题（而这个很可能不会发生，毕竟都能存储在内存中，数组的规模又怎么会越界呢？），这个方法挺好的，直接利用运算把二维的当作一维的来处理了，索引使用了整数除法和模运算。不过这里有大神提到了cache hit，不太明。

75. sort-colors

给一个数组，只含有0，1，2三种元素，排序。
ME：显然木桶排序最快，不过这个我已经很熟了就不想写了，还是老老实实复习了一遍quickSort。没想到followup要求用one-pass解决，我不禁陷入了沉思。。只有三个元素，都知道1是pivot了，那感觉用quickSort的思路，on-pass确实是可以解决的！但是写出来就是不知哪里有问题，借助eclipse才发现是判断的时候错误地使用了&&导致else分支中的情况其实不是预想的。改了之后，果断速度超快。
TA：真是人才济济，这道米迪恩题竟然有人搞出了四种解法。第一种桶排序，第二种是定义了n2,n1,n0三个索引，表示在什么位置插入2/1/0，这个真的妙哉。第三第四似乎差不多，定义两个索引对应0和2的插入位置，若当前位置是0，则与0的索引swap；若为2，则与2的索引swap。0的索引初始在最前，2的索引初始在最末，注意交换后要继续判断新交换过来的这位数字。

minimum-window-substring

给两个字符串s和t，要求在s中找到最短的子字符串使得它可以包含所有在t中出现的字符，就算t中重复那也要在s中重复。要求复杂度在O(n)。
ME：先对t的字符建立一个hashMap，方便获取各字符出现了多少次。但是对于O(n)的解法，我实在没辙，就算是DP那也要建立二维数组啊，那也不是O(n)啊，更何况DP的状态转换也没想出来。。。不愧是哈德题。
TA：你的HashMap完全可以用一个规模为128的数组代替，因为总共字符就128种。他喵的substring题又是双指针破解，要报警辣。这个C++的双指针解答速度超快，而且总结了一个给力的substring问题双指针破解模版，但是简洁的后果就是不太好懂，我也解释不清楚。只可意会不可言传啊。。。

combinations

给两个整数n和k，k表示组合的元素数，n表示可以有1~n这些数字作为元素，返回所有可能的组合。
ME：DFS秒杀。（还是叫回溯法来着？？？）
TA：回溯法是主流，还有一个非主流的递归方法，根据数学公式C(n,k)=C(n-1,k-1)+C(n-1,k)来的，有点头大。还看到了this，很久没见过这个关键字了。。。

subsets

给一个元素各不相同的数组，求它的所有不重复的组合。
ME：DFS还可以秒杀。此外，洗澡时还想到一个『利用已有List』的方法，即把当前元素都插入到之前的List末尾，直到全部搞完。
TA：同样有大神总结了general的回溯法解决子集、排列、组合等。还有一种用位运算实现组合的方法，我依稀记得大一的时候有听说过，现在看到才猛然想起来还有此等绝招。

word-search

给一个char的二维数组，再给一个String，在char[][]中尝试查找这个字符串，不一定是按顺序的查找，而是上下左右任意扭曲，但不能重复使用字符。能找到算你赢。
ME：DFS+状态记录搞定。本来不想搞多一个table的，但是如果只记录『搜索方向』，还是可能出现重复。
TA：这个方法就不需要额外的空间了，因为是直接对原char[][]开刀，利用一个异或操作，char是1byte即8bit的，那么我异或一个256（9bit）就可以让字符不合法了（不过为什么不会越界呢），这样后续操作时碰到不合法的字符就知道它已经被访问过了。访问完之后的复原也很方便，再异或一下256即可。

remove-duplicates-from-sorted-array-ii

给一个排好序的int数组，对它进行操作使得其中任意元素至多出现两次，返回经过修改后的数组长度。至于该长度之后的内容怎样，并不在意。
ME：之前有过做过类似的，思路就是把不符合『至多出现两次』的元素用后续的元素覆盖掉。这里也用到了双指针去搞，不过效率非常低，只打败了3%orz。
TA：双指针的generalize在这里，但是不用双指针的这个更加逆天。感到一丝危机，我虽然能写出来，但是代码略长，面试时的时间可没这么多呢。

search-in-rotated-sorted-array-ii

给一个排好序的、但经过一次随机前后rotate的int数组，给一个target，实现高效的查找方法，返回布尔值。
ME：利用之前看到的思路，假设数组的某一半是正常顺序，在进行正常的二分查找时额外判断一下target与两端的大小关系。然而这个思路碰到了重复的情况下比较麻烦，例如[1,1,1,3,1]，前中后三个都相等，这样就没法判断哪一半是正常顺序了，我的办法是把二分查找改造成递归的形式，遇到无法判断的时候，就进入两侧继续二分。
TA：这个解决duplicate的办法是只用前和中的大小关系判断前半部分还是后半部分排好序了，若前和中相等则直接lo++。

remove-duplicates-from-sorted-list-ii

给一个排好序的链表，要求移除所有重复出现的元素，保留只出现了一次的元素，返回新链表头。
ME：三指针，一个prev用于保证前面元素的指向，一个slow作为基准，一个fast看看后续是否与基准重复。在最后循环结束后，需要再设置一下prev的next，因为又可以slow和fast怎么找也找不到下一个不重复的元素了，最后一个元素直接指向null准没错。
TA：这里竟然有个recursive的方法，不太好懂。

remove-duplicates-from-sorted-list

给一个排好序的链表，要求移除多余元素使得所有元素只出现一次。刚好是上一题我理解错题意的时候写出来的。。。
ME：没啥。
TA：也有一个recursive的解答，大神用递归6得飞起。

largest-rectangle-in-histogram

给一个int数组表示柱状图各柱的高度，这些柱状图组成的最大完整矩形面积。
ME：使用暴力O(n^2)超时，不论是老老实实地往后一个个找，还是使用向左向右扩展的方法都是超时，即便跳过重复项也超时。。

TA：这个使用Stack即时更新，妙哉啊妙哉！使用栈记录索引，若栈为空则直接入栈，若当前索引对应的高度比栈顶索引的高度小，说明以栈顶元素为宽的矩形的长就在此时确定，计算一下矩形长度就可以把栈顶弹出了，然后继续比较当前索引和栈顶，直到当前索引的高度大于栈顶索引的高度。使用Java自带的Stack会比直接用数组模拟栈慢很多。这个方法则是我原本那个方法的一个加速版，我原来的向前后扩展找小于当前索引的位置使用的是一点点挪的办法，而加速就在于用两个额外的数组记录前/后的小于当前索引的第一个索引，在记录的过程中『跳跃』式地更新指针，不再是一点点地挪，原来苦苦寻找的加速就在这里！还有一个分治法最大值要么在左半部分、要么在右半部分、要么在中间交叉部分，这个分类讨论似曾相识啊，前两天才做的maximum-subarray就有个subtle的devide and conquer。

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int maxHeight = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                maxHeight = Math.max(maxHeight, heights[stack.poll()] * (i - 1 - stack.peek()));
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            maxHeight = Math.max(maxHeight, heights[stack.poll()] * (heights.length - 1 - stack.peek()));
        }
        return maxHeight;
    }
}

85. maximal-rectangle

给一个二维char数组，只包含0和1两种字符，求矩形所能围成的最大面积使得其中的元素都为1.
ME：憋了半天毫无思路，看了一下tag，提到了HashTable, Stack, DP。

TA：先介绍这个DP解法，这里的DP不再是死板的x维数组这样，而是通过right, left, height三个一维数组，height[j]维护当前行的第j个元素的从上往下的最长高度，left[j]从左到右维护当前行的第j个元素能到达的最左字符1的索引，right[j]从右到左维护当前行的第j个元素能到达的最右的索引，只有当前元素为1（对应height不为0）的时候才会计算面积。

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int rows = matrix.length, cols = matrix[0].length, maxArea = 0;
        int[] height = new int[cols];
        int[] left = new int[cols];
        int[] right = new int[cols];
        Arrays.fill(right, cols - 1);
        for (int row = 0; row < rows; row++) {
            int rightBoundary = cols - 1;
            for (int col = cols - 1; col >= 0; col--) {
                if (matrix[row][col] == '1') {
                    right[col] = Math.min(right[col], rightBoundary);
                } else {
                    right[col] = cols - 1;
                    rightBoundary = col - 1;
                }
            }
            int leftBoundary = 0;
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == '1') {
                    left[col] = Math.max(left[col], leftBoundary);
                    height[col]++;
                    maxArea = Math.max((right[col] - left[col] + 1) * height[col], maxArea);
                } else {
                    left[col] = 0;
                    leftBoundary = col + 1;
                    height[col] = 0;
                }
            }
        }
        return maxArea;
    }
}

然后介绍这个基于上一道题largest-rectangle-in-histogram的解法，柱状图对应于这道题当中的每一列累计的1，这样一转换瞬间就变成做过的题了，妙哉。同样可以用两个数组代替Stack，速度奇快。

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int rows = matrix.length, cols = matrix[0].length, maxArea = 0;
        int[] heights = new int[cols];
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                heights[col] = matrix[row][col] == '1' ? heights[col] + 1 : 0;
            }
            maxArea = Math.max(maxArea, getMaxArea(heights));
        }
        return maxArea;
    }
    private int getMaxArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int retVal = 0, len = heights.length;
        stack.push(-1);
        for (int i = 0; i < len; i++) {
            while (stack.peek() != -1 && heights[i] <= heights[stack.peek()]) {
                retVal = Math.max(retVal, heights[stack.pop()] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            retVal = Math.max(retVal, heights[stack.pop()] * (len - stack.peek() - 1));
        }
        return retVal;
    }
}

partition-list

给一个链表，给一个整数x，要求调整链表节点顺序使得链表前面部分都是小于x的、后面部分是大于等于x的。
ME：三指针+伪头部呗，直接在原链表上搞。
TA：这个定义了两部分的头结点，作为两个子链表来处理，非常好懂，要思考的细节也少一些。

scramble-string

将一个字符串任意拆分成两个非空的子字符串作为两个子节点，一路拆分下去形成一个二叉树。交换任意一个非叶子节点的两个子节点，形成新的字符串，称为scramble。给两个字符串，判断s2能否由s1这样scramble得到。
ME：一脸懵逼。。。。。。。。。。。。。看了tag，居然又他喵的是DP。。。感觉很多这种毫无头绪的题给的hint都是用DP。又观察了一波，似乎如果字符各不相同的话，只要每个字符都出现了，就一定有办法表示成二叉树的scramble，直接bucket标记就可以搞定。字符如果有重复的情况，似乎也可以？提交了一波，WA，例如abcd和bdac这种完美交错的就不可能了。
TA：竟然可以用暴力法，不断截取子字符串，只要同时满足前后子串都是scramble的或者经过位置交换后满足前后子串都是scramble的就可以了。事实上这种暴力递归的速度并不慢，这个三维DP的解法还慢一些。为什么一开始想不出DP，因为三维实在不太好画出来。dp[i][j][k]表示s1[i...i+k-1]是否是s2[j...j+k-1]的scramble，k取1时为base case，直接比较s1[i]和s2[j]即可，k取len即为最终结果。DP需要判断所有的情况，给一个分割点q，从1一直遍历到k-1地找当前这个长度k的所有划分情况。循环的边界应取到len。

merge-sorted-array

给两个排好序的数组，并给出他们原本有多少已排好序数字，将后者合并到前者中。前者的容量一开始已经设为大雨等于两个数组规模之和。
ME：一开始一位要Inplace，想了半天，可以做但是索引搞来搞去的不好写。之后借助了额外的空间Queue来记录A中比B大的元素，但他喵的居然WA，足足改了一上午加一下午，还是没有把这道衣洗题搞出来！实在是不能忍！！！
TA：原来确实可以Inplace，而且根本不用判断那么多情况，自己给自己设套。既然第一个数组尾部有多余的空间，那么可以从后往前塞，这样就防止了正常从前往后比较赋值时元素被覆盖的问题。这个总共只用了一次循环，比我的三个循环简洁很多。
Queue使用了LinkedList实现类。LinkedList类还可以实现栈的功能。

gray-code

给一个整数表示有多少bit，相邻的两个数只有一个bit不同成为grey code，返回符合grey code格式下对应的整数数组。
ME：递归使用之前的计算结果，n bit实际上就是在n-1 bit的基础上，首位为0一波、首位为1逆序一波两个。但隐约觉得似乎有位运算本身的规律？
TA：果然是位运算王道。很强。同时，你这个方法还可以『去递归』，就像这样。所谓优化，除了算法本身，剩下的无非是去递归、减小DP使用的辅助空间等。

subsets-ii

给一个含有int的collection，其中的元素可能有重复，返回所有可能的子集。
ME：还是回溯法，在循环开头加了个判断防止重复，若当前元素和之前元素相同则跳过，这样就不会出现你方唱罢我登台的场景。但是，速度好慢。。
TA：这个又是去递归的，只用了两重循环，第一重是每次从原collection中取不重复的元素，第二重就是向已有的结果中添加该元素并存入结果。需要注意的是若当前元素不是重复的，则在第二重循环中就需要把全部结果都取出来并加上当前元素；若是重复元素，则继续往里加就行了，毕竟你还从头加的话实际上前面相同的元素已经干过了。这个和你的一样都是递归，但人家的条件怎么就能精简不少呢？而且你的table也没有必要，因为不可能都循环到后面了还从前面调取元素放进来，那样肯定重复。

91. decode-ways

给一个纯数字的字符串，看有多少中方式解析成对应的字母A-Z。如12可解析为AB或L两种，返回2。
ME：一开始纯DFS，超时。暗中观察，发现可能是计算有重复的，后一步运算可以用到前一步运算的结果，这时我就想到用DP了。用dp[len+1]的数组记录状态，从右往左刷新，若当前字符为0则直接dp设为0；若为1或2再判断是否属于10~26的两位数范围，符合了就是后一位和后两位dp结果之和（即取一位和取两位两种情况）。不过已经写了递归就先把递归过了，然后改写成iterative，速度一样。
TA：大神们很多用了substring然后转成数值来判断是否属于1~26的，我不太喜欢。
字符串转数字用Integer.valueOf(s.substring(start, end));。

reverse-linked-list-ii

给一个链表，给范围[m, n]，要求in-place, one-pass地将第m个和第n个之间的节点全部反转。
ME：四指针搞起，需要借助伪头部处理反转头结点的问题。prev指向反转之前的一位，用于完成后续反转后指向新的后续头结点；start用于查找第m位，end用于查找第n位，first用于记录开始反转的首位；当找到m之后就开始找n，此时每一个新的end指向的节点都直接作为新的头结点，并调整start, end的指向，需要借助first和newNext完成end后续节点和end本身的更新。这么说有点复杂，在纸上写写就懂了。
TA：看了这个发现没必要多出来一个first，因为你的prev已经记录了原本它之后是什么元素，也就是first了。因此每次都更新prev.next就行，所以还是三指针。这个就有点争议了，因为额外用了一个sublist的头结点，每次直接把sublist的伪头部指向读入的节点，这样得到的sublist就是一个反了的第m到第n个节点子链表了，再改一下指向拼回去即可。这个挺直接的。

restore-ip-addresses

给一个由数字组成的字符串，返回将这些数字通过.分隔形成的所有合法的IP地址。
ME：DFS搞定，每次分别取一位、两位、三位数字，再往后判断。需要特别注意0，出现0就只能取一位了，因为不能出现010这样的IP地址嘛。若原字符串长度小于4或多于12直接就不用管了。但速度好慢。。
TA：大神们又改成了三重循环的Iterative了。这个的思路是在原字符串中插入三个小数点得到四个整数，判断是否在[0, 255]范围内，然后再利用长度的trick处理010的情况，即转成整数后拼接而成的IP地址字符串长度并不是原字符串长度+3，因为开头的0在转成整数的过程中给抹掉了。妙哉！
- Integer.parseInt(str)。

binary-tree-inorder-traversal

给一个树的根节点，返回中序遍历的结果。
ME：树的基础了，没啥好说的吧，DFS。
TA：又有大神改成Iterative了。。这个是基于Stack的，当前节点直接入栈然后一直往左边子树钻，钻到头就把栈顶元素输出，然后再到他的右子树去，继续往左钻。还有一个更神奇的Morris Traversal，不用Stack也不递归，前序/中序遍历都可以用（后序略复杂），空间是O(1)，时间是O(N)还是O(NlgN)有点疑惑。更多解析参考这里，和中文的千种后续关键是『让右节点遍历完之后能找到它下一步应该怎么回到还没有打印过的祖先节点』。用到了current和prev两个节点引用：current从根出发，一直往左子树钻，钻不动了说明自己该打印出来了，然后current往右子树钻。若current的左子树不是空，说明当前节点还不能打印，需要在将来告诉左子树的最右节点（因为它一定是子树中最后一个打印的）自己还没有打印、你要回到我这儿，所以设置prev指向current的左子树，然后让prev一直往右钻，直到钻不动就把该子树的右节点指向current。但如果在钻的过程中发现最右子树已经指向了自己，则说明子树全部遍历结束，current该打印了，打印了之后，current再往右子树钻。

Recursive OK, iterative not ok, even if I know about using stack, got endless loop.

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Stack<TreeNode> s = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !s.isEmpty()) {
            while (curr != null) {
                s.push(curr);
                curr = curr.left;
            }
            curr = s.pop();
            ans.add(curr.val);
            curr = curr.right;
        }
        return ans;
    }
}

95. unique-binary-search-trees-ii

只给一个整数n表示二分查找树的节点数，返回所有结构不同的树。而上一问则只是输出不同树的个数，只是个小DP。
ME：我能联想到DP的状态转换，即下一层加入的节点左右子树可以利用之前的结果，而且连右子树的offset都想到了。但是就是写不出来。。。逻辑混乱，写得糊里糊涂的。

TA：这个的思路跟你一模一样，你他喵的还用List作为dp，简直是作死。dp的状态存储用数组！！！上面这个po主思路很清楚，dp[i]表示当节点数为i个时所有可能形状的树结构，因此初始化时dp[0]的ArrayList直接插入一个null，省去了很多判断。然后开始向后刷新直到长度为n，即为结果。每一次刷新都需要充分使用之前的结果，左子树的节点数从0一直到i-1，右子树节点数对应地就是i-1到0了，右子树的节点的value需要额外刷新一下，因为左子树和当前节点占用掉了j+1，要相应地累加给右子树的所有节点才行。此外，分治法我也一开始就想到了，但是觉得不划算，因为没法记录之前计算的结果，但这个写出来感觉还行。

class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>[] dp = new List[n + 1];
        dp[0] = new ArrayList<TreeNode>();
        if (n < 1) {
            return dp[0];
        }
        
        dp[0].add(null);    // notation for empty subtree
        
        // BST: left children all smaller, right all larger.
        // each time fix the root, take prev as left subtree, and prev with offset as right subtree.
        for (int nodeNum = 1; nodeNum <= n; nodeNum++) {
            dp[nodeNum] = new ArrayList<TreeNode>();
            for (int leftNum = 0; leftNum < nodeNum; leftNum++) {
                for (TreeNode leftNode: dp[leftNum]) {
                    for (TreeNode rightNode: dp[nodeNum - leftNum - 1]) {
                        TreeNode curr = new TreeNode(leftNum + 1);
                        curr.left = leftNode;
                        curr.right = addOffset(rightNode, leftNum + 1);
                        dp[nodeNum].add(curr);
                    }
                }
            }
        }
        return dp[n];
    }
    // its kinda tricky to come up with this offset
    private TreeNode addOffset(TreeNode node, int offset) {
        if (node == null) {
            return null;
        }
        TreeNode newNode = new TreeNode(node.val + offset);
        newNode.left = addOffset(node.left, offset);
        newNode.right = addOffset(node.right, offset);
        return newNode;
    }
}
// Divide and conquer
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n < 1) {
            return new ArrayList<TreeNode>();
        }
        return generate(1, n);
    }
    private List<TreeNode> generate(int start, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (start > end) {      // recursion end condition
            result.add(null);
            return result; 
        }
        // take i as root val
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = generate(start, i - 1);   // generate all possible left subtree
            List<TreeNode> right = generate(i + 1, end);    // gennerate all possible right subtree
            for (TreeNode l: left) {
                for (TreeNode r: right) {
                    TreeNode node = new TreeNode(i);    // set root val
                    node.left = l;
                    node.right = r;
                    result.add(node);
                }
            }
        }
        return result;
    }
}

96. unique-binary-search-trees

求含有值1～n的BST的可能形状数目。

每次固定root，左子树一定都是小于它的、右子树一定都是大于它的，而总体可能形状恰好就是左右各自形状数目的乘积。

class Solution {
    public int numTrees(int n) {
        if (n < 1) {
            return 0;
        }
        int[] dp = new int [n + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) {  // 总节点数
            for (int j = 1; j <= i; j++) {   // 固定root的值
                dp[i] += (dp[j - 1] * dp[i - j]);  // 左侧右j-1个节点、右侧有i-j个节点
            }
        }
        return dp[n];
    }
}

97. interleaving-string

给三个字符串s1, s2, s3，判断s3是否由s1和s2拼接而成，这里的拼接可以是交错的，但必须维持字符原本的出现顺序。
ME：一开始直接贪心法递归下去找，取s1的字符往后尝试，碰壁了再取s2的字符尝试，心想怎么这么简单，结果超时。。感觉着有点像之前的棋盘题，当时也是深度搜索超时改成DP就秒了，看了一下tag，果然是DP，但这题的状态转换并不好找。
TA：哇去，我原本非常接近真相了啊，棋盘都画出来了。这个是C++的二维数组的行为s2，列为s1，dp[i][j]表示s3取i+j-1个字符的子字符串是否是s2取i-1个字符、s1取j-1个字符的interleaving。直接双重循环更新这个dp二维数组即可，对于左边缘和上边缘只有一个移动方向，而其余的位置可能来自左边（选择了s1的字符）或上边（选择了s2的字符），这就依赖于之前的状态以及取的这个字符了，这就是DP的状态转换。DFS如果加上了cache也可以通过，不过这还不如DP来得方便。此外，BFS通常用于求『最小值』类问题，在这里也可以用，比如这个，与DFS的区别在于DFS每次先处理一个方向，走不通再return回来走另一条；而BFS则是通过入队，每次都照顾到两个方向。BFS本身并不比DFS快，这里也还是用了一个visited二维数组防止走回头路。

Once know about DP, implementation is OK.

// DP
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
        if (len1 + len2 != len3) {
            return false;
        }
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(), cs3 = s3.toCharArray();
        boolean[][] dp = new boolean [len1 + 1][len2 + 1];
        
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                if (i == 0) {
                    if (j == 0) {
                        dp[i][j] = true; 
                    } else {
                        dp[i][j] = cs2[j - 1] == cs3[i + j - 1] && dp[i][j - 1];
                    }
                } else {
                    if (j == 0) {
                        dp[i][j] = cs1[i - 1] == cs3[i + j - 1] && dp[i - 1][j];
                    } else {
                        // take char from s1(move i) or from s2(move j)
                        dp[i][j] = (dp[i - 1][j] && cs1[i - 1] == cs3[i + j - 1])
                            || (dp[i][j - 1] && cs2[j - 1] == cs3[i + j - 1]);
                    }
                }
            }
        }
        return dp[len1][len2];
    }
}
// DFS
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length()) {
            return false;
        }
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(), cs3 = s3.toCharArray();
        boolean[][] invalid = new boolean [cs1.length + 1][cs2.length + 1];
        return dfs(cs1, cs2, cs3, 0, 0, invalid);
    }
    private boolean dfs(char[] cs1, char[] cs2, char[] cs3, int i, int j, boolean[][] invalid) {
        if (invalid[i][j]) {
            return false;
        }
        if (i + j == cs3.length) {  // end case: reach the end of s3
            return true;
        }
        if ((i < cs1.length && cs1[i] == cs3[i + j] && dfs(cs1, cs2, cs3, i + 1, j, invalid))
            || (j < cs2.length && cs2[j] == cs3[i + j] && dfs(cs1, cs2, cs3, i, j + 1, invalid))) {
            return true;
        }
        invalid[i][j] = true;
        return false;
    }
}
// BFS
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length()) {
            return false;
        }
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(), cs3 = s3.toCharArray();
        boolean[][] visited = new boolean [cs1.length + 1][cs2.length + 1];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {0, 0});
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            if (visited[curr[0]][curr[1]]) {
                continue;
            }
            if (curr[0] + curr[1] == cs3.length) {  // reaches the end of s3
                return true;
            }
            if (curr[0] < cs1.length && cs1[curr[0]] == cs3[curr[0] + curr[1]]) {
                q.add(new int[] {curr[0] + 1, curr[1]});
            }
            if (curr[1] < cs2.length && cs2[curr[1]] == cs3[curr[0] + curr[1]]) {
                q.add(new int[] {curr[0], curr[1] + 1});
            }
            visited[curr[0]][curr[1]] = true;
        }
        return false;
    }
}

98. validate-binary-search-tree

给一个二叉树的根节点，判断这棵树是不是合法的二分查找树。
ME：写了半天，各种边缘条件判断。先左子树再右子树，同时为了保持左子树所有节点都小、右子树所有节点都大，还需要维护min、max，而为了防止出现Integer的MIN/MAX_VALUE，我还引入了boolean来标记min和max是否经过修改。
TA：这个的思路和你一样，也是需要维护min和max，但它的trick是使用了Long的MIN/MAX_VALUE，这样就省去了boolean，不过并不是一个好方法。这个提示你，合法的BST的中序遍历应当是从小到大不含重复元素的序列，因此可以用中序遍历的方法，把每个节点依次入栈，在弹出时用一个prev指向它（对应于中序遍历的靠前的节点），方便之后弹出的元素与他比较，当前必须完美大于prev才是合法的。这个递归的方法思路是一样的，但不需要Stack，而是用递归搞prev和node两个节点，也是必须prev完美小于当前node。注意在递归入口，prev是不会变的，当开始遍历当前节点的右子树时才会更新到该节点。

WA several times…because coming from next one. quite similar actually.

class Solution {
    private TreeNode prev = null;   // warning
    public boolean isValidBST(TreeNode root) {
       
        return dfs(root);
    }
    private boolean dfs(TreeNode curr) {
        if (curr == null) {
            return true;
        }
        if (!dfs(curr.left)) {
            return false;
        }
        if (prev != null && prev.val >= curr.val) { // prev should be smaller than curr normally
            return false;
        }
        prev = curr;
        return dfs(curr.right);
    }
}

99. recover-binary-search-tree

给一个二分查找树的根节点，其中有两个节点调换了顺序，要求恢复成合法的二分查找树。
ME：有点投机取巧的方法，先DFS中序遍历把所有节点存入一个ArrayList，然后Collections.sort排个序，再DFS一次把值全部重新赋一遍。在绝望的时候随便试了一发，都做好TLE的准备了，竟然AC了。不过follow up说，空间O(n)的很容易想到，但如果是O(1)空间要怎么做？
TA：你这么做并不能令人信服。主要的问题是如何找到这两个放错了位置的点呢？这个告诉你，其实就是把在中序遍历的时候，找逆序对，若是直接相连的两个节点反了，则只有一对逆序对，若不直接相连，则是两对逆序对，把前者的靠前者与后者的靠后者交换即可。使用到了三指针，prev指针实际上是初始化成了一个虚拟的最左子节点，初始值为Integer.MIN_VALUE。至于O(1)，当然就是之前听说过的Morris Traversal。

Prev, first, second. reverse pair.

class Solution {    
    TreeNode first = null, second = null;   // for getting the reverse pair
    TreeNode prev = new TreeNode(Integer.MIN_VALUE);    // prevent unwanted setting of first
    private void dfs(TreeNode root) {
        if (root == null) {
            return ;
        }
        // inorder
        dfs(root.left);
        if (first == null && prev.val >= root.val) {// prev is less than curr node normally
            first = prev;                           // if not, prev is the one that misplaced
        }
        if (first != null && prev.val >= root.val) {// put curr node as swap target
            second = root;
        }
        prev = root;
        dfs(root.right);
    }
    public void recoverTree(TreeNode root) {
        dfs(root);
        if (first != null && second != null) {
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
    }
}

100. same-tree

OK.给两个二叉树的根节点，判断这两个树是否完全相同。
ME：递归搞定。先判断节点是否为Null，然后判断当前节点的值是否相等，再依次深入左子树、右子树递归判断。但发现我的写法比较慢。。。
TA：你的慢是因为太多if-else嵌套，看这个，思路是一样的，但是省去了很多条件分叉。这又是优化的一个点了。