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

adbase

86. Partition List
这道题难点在于如何把后面的节点挪到前面去。首先是找到第一个比x大的数字，但是注意不要找到这个第一个节点，而是要找打它的上一个节点，也就是第一个first.next >＝ x。
然后再用第二个指针，从这个x往后找second.next < x的节点。找到了，就可以重新链接了，注意链接的顺序，最好画画图。我是先用一个临时节点记录temp = second.next。也就是要转移的节点。然后先把后面的断开再连上：second.next = second.next.next。然后再把temp插入到first的后面, 注意是从后往前接, temp.next = first.next; first.next = temp.
这样就转移完了。然后注意的是，我们同时把first和second往后移。可是更要注意的是，second也许下一个节点还是需要重新接，所以若是second.next.val < x，我们就不移动second了。

代码

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
//[1,4,3,0,2,5,2]
// ^
// ^
ListNode dummy = new ListNode();
dummy.next = head;
ListNode first = dummy;
while(first.next != null && first.next.val < x) {
first = first.next;
}
ListNode smaller = first;
while(smaller !=null && smaller.next != null) {
// System.out.println(smaller.val + " " + first.val);
if(smaller.next.val < x) {
ListNode snext = smaller.next;
smaller.next = smaller.next.next;
snext.next = first.next;
first.next = snext;
first = first.next;
}
if(smaller.next != null && smaller.next.val >= x) smaller = smaller.next;
}
return dummy.next;
}
}

复制代码

adbase

85. Maximal Rectangle
这道题研究了好久，以为是dp。当然dp的确可以做，但是属于自找麻烦。
这个题就是84. Largest Rectangle in Histogram的进阶。
每一行，我往上看，其实就是84题。
比如我们的矩阵是
[["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]]

我们记录一下每一行上面的1的高度就是
1 0 1 0 0
2 0 2 1 1
3 1 3 2 2
4 0 0 3 0

然后我们再把每一行都看作是84题就可以了。最后我十分钟写完。
果然没有复习的画，即使是昨天做的题，也许依然想不起来。不过这个题的确是个好题，想起来，我第一次面试亚麻的时候，对方给我的就是这道题。我估计他肯定准备了follow up。

代码，我把84题的部分写得更精炼了一些

class Solution {
public int maximalRectangle(char[][] matrix) {
int w = matrix.length;
int h = matrix[0].length;
int[][] dp1 = new int[w][h];
for(int i = 0; i < w; i++) {
for(int j = 0; j < h;j++) {
if(i == 0) dp1[i][j] = matrix[i][j] - '0';
else if(matrix[i][j] == '1') dp1[i][j] = dp1[i - 1][j] + 1;
}
}
int max = 0;
for(int r = 0; r < dp1.length; r++) {
max = Math.max(helper(dp1[r]), max);
}
return max;
}
private int helper(int[] h) {
Stack<Integer> stack = new Stack<>();
int max = 0;
for(int i = 0; i < h.length; i++) {
while(!stack.isEmpty() && h[i] < h[stack.peek()]) {
int idx = stack.pop();
int left = stack.isEmpty() ? 0 : stack.peek() + 1;
max = Math.max(h[idx] * (i - left), max);
}
stack.add(i);
}
while(!stack.isEmpty()) {
int idx = stack.pop();
int left = stack.isEmpty() ? 0: stack.peek() + 1;
max = Math.max(h[idx] * (h.length - left ), max);
}
return max;
}
}

复制代码

adbase

87. Scramble String
今天花了太多的时间在这道题，就不写心得和code了

88. Merge Sorted Array
这道题要从后往前比大小，定义三个指针
89. Gray Code
数学题，一个自然二进制数转格雷数的公式是 gary num = x ^ (x >>1) 也就是保留第一位，其余位置异或。

adbase

91. Decode Ways
第一反应是回溯法，当然是可以做的，并且若是要求你返回所有的字符串，那么回溯法当然就是唯一选择，但是这个题就是让你算一下一共有多少个组合。那么就可以考虑就dp。
dp并不难想，dp[i] = dp[i - 1] + dp[i -2]。但是是有条件的，若是s[i-1, i］是个0，那么就不能加dp[i-1]。因为当前位是0，没有合法对应的字母。同样,dp[i-2]要求s[i-2,i]必须在区间[10,26]。超出范围，说明要么是0开头，要么是个大于26的数字无法匹配。

所以代码就是

class Solution {
public int numDecodings(String s) {
// dp[i] = dp[i - 1] + dp[i - 2];
// s[i-1, i] != 0 s[i - 2, i] >=10 <=26
int[] dp = new int[s.length() + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for(int i = 2; i <= s.length(); i++) {
if(s.charAt(i-1) != '0') {
dp[i] += dp[i - 1];
}
int n = Integer.parseInt(s.substring(i - 2, i));
if(n >= 10 && n <= 26){
dp[i] += dp[i -2];
}
}
return dp[s.length()];
}
}

复制代码

adbase

90. Subsets II
和之前的Subset是一样的，就是要去重。组合数去重，方法都是排序，然后每次递归的时候，从之前递归的下一位开始，除了第一次遇到重复数字，之后再遇到重复的数字要跳过。
代码既是

class Solution {
List<List<Integer>> rs = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
helper(nums, 0, new ArrayList<>());
return rs;
}
private void helper(int[] nums, int idx, List<Integer> curr) {
rs.add(new ArrayList<>(curr));
for(int i = idx; i < nums.length; i++) {
if(i != idx && nums[i] == nums[i - 1]) continue;
curr.add(nums[i]);
helper(nums, i + 1, curr);
curr.remove(curr.size() - 1);
}
}
}

复制代码

adbase

93. Restore IP Addresses
这道题不难，一看要求返回所有可能性，那么就是暴力回溯法。每次我们取出1到3位最前面的字符，看看它们是不是属于1～255。注意不能是0开头的字符串，除非是单独的一个0.
然后我们把它们存到一个list里，当存满了4个，并且没有剩余字符，那么就是一个合法解。我把它处理成ip字符串放到最终答案里即可。

这个题唯一难度就是如何判断字符是不是"0~255"。其他就没有了
class Solution {
List<String> rs = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
      if(s.length()<4) return rs;
      helper(s, new ArrayList<>());
      return rs;
}

private void helper(String s, List<Integer> curr) {
      //System.out.println(s + " " + curr);
      if(s.length() == 0) return;
      if(curr.size() == 3) {
         if(s.length() > 3) return;
         //System.out.println("rs = " + s + " " + curr);
         int num = Integer.parseInt(s);
         if(s.length() > 1 && s.charAt(0) == '0') return;
         if(num <= 255) {
            curr.add(num);
            addRs(curr);
            curr.remove(curr.size() - 1);
         }
         return;
      }

      for(int i = 1; i <= Math.min(3, s.length()) ; i++) {

         int num = Integer.parseInt(s.substring(0, i));
         if(i > 1 && s.charAt(0) == '0') break;
         if(num <= 255) {
            curr.add(num);
            helper(s.substring(i), curr);
            curr.remove(curr.size() - 1);
         }
      }
}

private void addRs(List<Integer> curr) {
      StringBuilder sb= new StringBuilder();
      for(int num : curr) {
         sb.append(num).append(".");
      }

      sb.deleteCharAt(sb.length() - 1);
      if(!rs.contains(sb.toString()))
         rs.add(sb.toString());
}
}

adbase

92. Reverse Linked List II
这个题还是老思路，linkednod的题都是这么些套路。我的建议就是画图，主要就是要知道我们的指针指向哪里，需要定义几个指针。
这道题我们需要一个指针指向left的上一个节点，还需要两个指针，用于翻转链条。
总的难度有两点，
第一个是如何确定开头和结尾。我们要找到left上一个节点，把它断开，然后从left开始翻转，翻转到right为止。这里其实就是我们用right计数，当总得移动次数到达right次的时候，我们就停止。

第二个难点，其实也不算难点，就是比较绕。怎么把链条再接回去。我有了left上一个节点，那么它的下一个是谁呢？其实就是翻转之后最后的pre节点。返回来，尾巴节点是谁？当然就是left节点了。所以我们在断开left和left pre之前，要保存一下left，然后再把它的下一位指向最后的curr，就可以了。
这样处理就是one pass，只刷一遍就可以完成。

class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if(head.next == null) return head;
if(left ==right) return head;
ListNode dummy = new ListNode();
dummy.next = head;
ListNode preLeft = dummy;
left--;
while(left > 0 ) {
preLeft = preLeft.next;
left--;
right--;
}
ListNode curr = preLeft.next;
ListNode pre = null;
while(right > 0) {
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
right--;
}
ListNode leftNode = preLeft.next;
preLeft.next = pre;
leftNode.next = curr;
return dummy.next;
}
}

复制代码

adbase

96. Unique Binary Search Trees
dp题。当然也可以用递归找出所有答案再计算size。这个题的转移公式不好想。dp[i]表示有i个数字的时候，有多少种可能性。
显然，dp[1] ＝ 1 dp[0] = 1。因为n = 0，没有树也是一种情况。
然后想转移方程，首先问自己，怎么样才能缩小问题规模。显然，左子树，或者右子树，就是一个更小规模的问题。那么左子树有m种组合方式，右子树有n种组合方式。那么dp[i]就是＝m * n
那么左子树的组合方式是怎么往前找呢？

这里就是最难的地方，我们先假设一个数字当root，比如我们要算dp[2]。那么1或者2都有可能当root。
那么我们就分别讨论，root=1的时候，显然另一个节点2只能是右子树，root=2的时候，另一个节点1只能是左子树。所以 dp[2] = dp[0] * dp[1] + dp[1] * dp[0];

继续看dp[3]，root =1 de时候, 只有右子树 dp[0] * dp[2]. root=2的时候，左右都有树 dp[1] * dp[1], root=3 只有左子树 dp[2]* dp[0]

所以，规律就是dp[i] += dp[j][j - 1 - i] j >= 0 && j < i
这样，这个题就做完了，我们最后返回dp[n]即可

class Solution {
public int numTrees(int n) {
//dp[2] = dp[0] * dp[1] + dp[1] *dp[0]
//dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0];
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i - 1 - j];
}
}
return dp[n];
}
}

复制代码

adbase

95. Unique Binary Search Trees II
class Solution {

public List<TreeNode> generateTrees(int n) {
      if(n == 0) return  new ArrayList<>();
      return helper(1, n);
}

private List<TreeNode> helper(int l, int r) {
      List<TreeNode> rs = new ArrayList<>();
      if(r < l){
         rs.add(null);
         return rs;
      }
      for(int i = l; i <= r; i++) {

         List<TreeNode> leftNodes = helper(l, i - 1);
         List<TreeNode> rightNodes = helper(i + 1, r);
         for(TreeNode left : leftNodes) {
            for(TreeNode right : rightNodes) {
                  TreeNode root = new TreeNode(i);
                  root.left = left;
                  root.right = right;
                  rs.add(root);
            }
         }
      }
      return rs;
}
}

adbase

97. Interleaving String
思路，看题目，是排列组合，然后问能不能排列组合出来。但凡排列组合，本质上就是树的遍历，然后若是不要求你返回具体的排列组合形式，只是问你能不能组合出来，或者有多少种组合，那么就可以考虑dp。
这个题dp不难想，还是dp[i][j]表示i个s1的字符，j个s2的字符是否可以组合。转移方程就是问老问题，怎么样缩小问题规模。显然，若是s3一个字符和s1或者s2 相同，那么dp[i][j] = dp[i-1][j] || dp[i][j-1];
由于字符串可以为空，所以dp要多一位，并且dp[0][0] ＝ true；表示都为空的画为真。这个题难度在于初始化第一行和第一列，除了比较字符是否相同，还要考虑前一位是否相同，若是前一位不同，那么下一位就算字符相同也不能为真。因为dp[i][0]意思就是s2为空，那么我们就是在比较s1和s3的异同，只有每一位都相同，dp[i][0]为真。
所以代码就是
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {

      if (s3.length() != s1.length() + s2.length()) {
         return false;
      }
      int m = s1.length();
      int n = s2.length();
      char[] s1c = s1.toCharArray();
      char[] s2c = s2.toCharArray();
      char[] s3c = s3.toCharArray();
      boolean[][] dp = new boolean[m+1][n+1];


   //System.out.println("test");
      dp[0][0] =true;
      for(int i = 1; i <=m; i++) {
         dp[i][0] = s1c[i - 1] == s3c[i - 1] && dp[i- 1][0];
      }
      for(int j = 1; j <= n; j ++) {
         dp[0][j] = s2c[j - 1] == s3c[j - 1] && dp[0][j - 1];
      }
      for(int i = 1; i <= m; i++) {
         for(int j = 1; j <=n; j++) {

            dp[i][j] =  (dp[i - 1][j] && s1c[i - 1] == s3c[i + j - 1]) ||                                  (dp[i][j - 1] && s2c[j - 1] == s3c[i + j - 1]);

         }
         //System.out.println(Arrays.toString(dp[i]));
      }
      return dp[m][n];
}
}