Lexi's Leetcode solutions

Posts Tagged ‘hard

比如 {1, 1, 1, 2, 3},x = 3, 结果就是{111}{12}{3}。这个题挺难想的,和上一题又不一样。正常stack,把1push进去,然后直接在2上recurse x=2的(因为1只能用一次)。这样一直做到x==0。这样就会有重复:当stack pop空了之后,回到第二个1上,又开始push,那stack的第0个又是1了,刚才已经做过stack第0个是1的一遍了(左边的一遍肯定包括了最多种的情况),所以现在再把1放里面就会重复。所以要在做“要不要在当前layer试一下下一个数?”的决定的时候,要看“下一个数和当前数是否相等?因为当前数已经做过了,同一层layer说明是同一个position,再放当前数就会重复)。

总结:

  • combination/set: 用stack,因为长度不固定。
  • permutation: 用int[],keep一个pos pointer。
  • 主函数里面不要循环,就一个以初始值call副函数的语句就行。
  • 副函数是循环里面call自己。
public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
  Arrays.sort(num);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  Stack<Integer> path = new Stack<Integer>();
  combinationSum(num, target, 0, path, result);
  return result;
}
private void combinationSum(int[] arr, int target, int start, Stack<Integer> path, ArrayList<ArrayList<Integer>> result) {
  if (target == 0) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.addAll(path);
    result.add(list);
    return;
  }
  for (int i = start; i < arr.length; i++) {
    if (arr[i] > target)
      return;
    path.push(arr[i]);
    combinationSum(arr, target - arr[i], i + 1, path, result);
    path.pop();
    //do we want to place arr[i + 1] at the same position arr[i] has been?
    while (i + 1 < arr.length && arr[i] == arr[i + 1]) {
      i++;
    }
  }
}

subset 1:  array本身都是distinct number,所以往里一个一个插不用担心重复。{}, 放第一个,放第二个。。

//inintialize a {}, keep inserting, mark as used (distinct nums)
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
    Arrays.sort(S);
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    result.add(new ArrayList<Integer>());
    for (int i = 0; i < S.length; i++) {
        ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
        for (ArrayList<Integer> prevSubset : result) {
            ArrayList<Integer> newSubset = new ArrayList<Integer>();
            newSubset.addAll(prevSubset);
            newSubset.add(S[i]);
            temp.add(newSubset);
        }
        result.addAll(temp);
    }
    return result;
}

subset 2————————————-
先sort,然后往后加。重点是怎么保证不重复?比如array[] = {1, 2, 2}

  1. {}
  2. {}, {1}
  3. {}, {1}, {2}, {12}
  4. {}, {1}, {2}, {12} 这时要是还往{}和{1}里面插2就会产生重复。所以要想办法把他们skip过去。skip到哪为止呢?毕竟还是想往{2}和{12}里插的。
  5. 所以是arr[i] == arr[i + 1]的时候,不要往arr[i]之前那一层插了。要往i这一层新插的里面插。
public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
  Arrays.sort(num);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    result.add(new ArrayList<Integer>());
  int start = 0;
  for (int i = 0; i < num.length; i++) {
    int prevSize = result.size();
    //上一层的size,是数字可以用来循环,避免modification exception
    for (int j = start; j < prevSize; j++) {
      ArrayList<Integer> newSubset = new ArrayList<Integer>();
      newSubset.addAll(result.get(j));
      newSubset.add(num[i]);
      result.add(newSubset);
    }
    if (i + 1 < num.length && num[i] == num[i + 1])
      start = prevSize;
      //i + 1那层越过i - 1这层的所有subsets,因为第i层已经往i - 1层的所有subsets里插过了
    else
      start = 0;
  }
  return result;
}

这题正经做了一段时间;首先自己想的算法不好,不够数学;另外这个题的testcase很多情况,自己没想清楚,全是用oj来查出错误了。

数学的做法:每个zigzag(|/形状是n + n – 2的长度;除非n < 2, 则就是n本身的长度),这样可以直接在string上跳着取出应该append的index。这个有两种情况:

ABCDEFGHIJKL n = 4
-------------
A     G 
B   F H   L 
C E   I K  
D     J
  1. 第一行和最后一行每个zigzag段只要append一个就行了
  2. 中间那些行每次要append两个字母;

两个变量,想了半天。分别是“在当前段里的offset”和”在哪个zigzag段里“,但是要保证以”在那个段里“外层循环。

注意:想不明白边界条件的时候,不妨直接用if(边界在string range里),这样就能把所有出界全接住了。

public String convert(String s, int nRows) {
  if (s == null)
    return null;
  int len = nRows <= 1 ? nRows : (2 * nRows - 2);
  StringBuilder sb = new StringBuilder();
  for (int offset = 0; offset < nRows; offset++) {
    for (int zigIndex = 0; zigIndex * len < s.length(); zigIndex++) {
      int firstIndex = zigIndex * len + offset;
      if (firstIndex >= 0 && firstIndex < s.length())
        sb.append(s.charAt(firstIndex));
      if (offset > 0 && offset < nRows - 1) {
        int reverseIndex = (zigIndex + 1) * len - offset;
        if (reverseIndex >= 0 && reverseIndex < s.length())
          sb.append(s.charAt(reverseIndex));
      }
    }
  }
  return sb.toString();
}
Tags: , ,

example: aabc matches c*a*b.

思路:

  1. 两个指针i, j,i指regular expression,j指真的string。
  2. 观察p[i+1],
    • 如果它不是*,说明没法skip p[i],则p[i]和s[j]必须match(相等或者p[i]是’.’ which matches everything)。如果不满足,直接返回false,没法matche了。
    • 如果它是*,说明当前位置可以是0个p[i], 1个p[i], 2个p[i]..
      1. 先试试“用0个p[i]“,即把p[i]和他后面的* skip掉。若recurse (i + 2, j)成功了,直接返回true,不成功,接着做第二步。
      2. 从“用1个p[i]“开始while循环,若p[i]和s[j] match, recurse on (i + 2, j + 1)(把*用掉了所以i+2),如果返回true就直接成了,否则就while继续循环“用2个p[i]“,即recurse on (i + 2, j + 2), recurse on (i + 2, j + 3)…循环的终止条件是p[i]和s[j]不match了,直接返回false。
public boolean isMatch(String s, String p) {
  return tryMatch(p, s, 0, 0);
}
private boolean tryMatch(String p, String s, int i, int j) {
  if (i == p.length())
    return j == s.length();
  if (i == p.length() - 1 || p.charAt(i + 1) != '*') { //下一个字母不是*,当前字母必须match
    if (matchChar(p, s, i, j))
      return tryMatch(p, s, i + 1, j + 1);
    else
      return false;
  } else { // p[i + 1] is *
    boolean skip = tryMatch(p, s, i + 2, j); //把当前字母去掉能行,就直接返回
    if (skip)
      return true;
    while (matchChar(p, s, i, j)) {//*当一个p[i]开始,当两个,当三个。。
      if (tryMatch(p, s, i + 2, j + 1))
        return true;
      j++;
    }
    return false;
  }
}
private boolean matchChar(String p, String s, int i, int j) {
  if (i >= p.length() || j >= s.length())
    return false;
  return p.charAt(i) == s.charAt(j) || p.charAt(i) == '.';
}
Tags: , ,

private int findKth(int[] A, int[] B, int k) {
if (A.length == 0 && B.length == 0)
return 0;
return findKth(A, B, 0, 0, k);
}

private int findKth(int[] A, int[] B, int i, int j, int k) {
if (A.length – i > B.length – j)
return findKth(B, A, j, i, k);
if (i == A.length)
return B[j – 1 + k]; // the kth starting from j
if (k == 1) //when trying to find the first, just return the smaller head
return Math.min(A[i], B[j]);
int m1, m2; // section size
if (A.length – i < k / 2) { // A’s left over (start from A[i] to A[last]) can’t slice a size k/2 section
m1 = A.length – i;
} else {
m1 = k / 2;
}
m2 = k – m1;
int i1 = i + m1 – 1; // the pivot’s index in A
int j1 = j + m2 – 1;
if (A[i1] < B[j1]) // abandon A’s left section including A[i1]
return findKth(A, B, i1 + 1, j, k – m1);
else if (A[i1] > B[j1]) {// abandon B’s left section including B[j1],
return findKth(A, B, i, j1 + 1, k – m2);
} else {
return A[i1];
}
}

这个题好像就没一次做对过。实在是,太绕了太绕了太绕了。二维数组的上下左右index能把人活活烦死。出现的多次失误:

  1. 只转了四个角(主要在于i的物理意义没弄清)
  2. 每个边转了整个长度而不是长度-1(这样四角就会一直转来转去)
  3. 没搞清left, right, up, bottom怎么用layer和index表示。一个检查写的对不对的方法:记住
    1. upper说明i不变(depend on constant layer), j在从小到大变动(从左往右)
    2. left说明j不变(一直是最小值,因为靠左),i在从大到小的变动(从下往上)
    3. bottom说明i不变(一直是最大的),j在从大到小变动(从右往左)
    4. right说明j不变(一直是最大的),i在从大到小变动(从上往下)
public void rotate(int[][] matrix) {
  int len = matrix[0].length;
  for (int layer = 0; layer < len / 2; layer++) {
    for (int i = layer; i < len - 1 - layer; i++) {
      // save upper
      int temp = matrix[layer][i];
      // upper = left
      matrix[layer][i] = matrix[len - 1 - i][layer];
      // left = bottom
      matrix[len - 1 - i][layer] = matrix[len - 1 - layer][len - 1 - i];
      // bottom = right
      matrix[len - 1 - layer][len - 1 - i] = matrix[i][len - 1 - layer];
      // right = up
      matrix[i][len - 1 - layer] = temp;
    }
  }
}

十月份重做,还是没做出来。不知道为什么大家都觉得这个题简单,我个人认为这是CC150最难的3道题之一。别的难题都是理解了下次就做出来了,这题是理解了再做5遍还是做不出来。
和spiral matrix的区别:那道题是大大卷那种,spiral的,这个是一层一层的,上一层和这一层没关系。

思路很straight forward,就是找到两个不属于自己位置的node,把他们的值互换。

但是怎么找这两个node就非常麻烦。怎么看出一个节点出位了?比如下图,能看出来是6出位了,但是1->6是满足的,6->3才发现不对劲。但也不能说prev > next就是prev不对,比如右边的5, 2,明明是2不对,但是2这个时候是后一个。所以总结来看,应该是“第一个不对劲的prev, curr pair是prev的错(不该跑前面的跑前面去了),第二个不对劲的prev, curr pair是curr的错(不该放后面的被放在了后面)。” 这个比较难想,总之就是中序遍历一遍,keep prev指针,按照刚说的规律找出那两个不对的。

       5
      /  \
     3     8
    / \   / \
   6   4 2   9
  /
 1

但是!!跑一遍不对!然后发现又是java不能改argument pointer的问题!栽在这上面两次了!!这回一定要弄清楚,记住教训!下面是错误版本:

private void populateMistakesArray(TreeNode[] mistakes, TreeNode root, TreeNode prev) {
  if (root == null)
    return;
  populateMistakesArray(mistakes, root.left, prev);
  if (prev != null && prev.val > root.val) {
    if (mistakes[0] == null)
      mistakes[0] = prev;
    mistakes[1] = root;
  }
  prev = root;
  populateMistakesArray(mistakes, root.right, prev);
}

这样传prev进来,prev = root这一句,method 里面叫prev的variable point to root了,然后传给下一层没问题,但是没法传给上一层!因为毕竟改的是local var, 上一层prev还是以前那个prev!!以前一直这么写树的题都没问题,是因为parameter要么一路往下传,要么想往上传的话就作为return object往上传。这次坑爹的,想往上传还放paramter里,必须挂。解决方法:用一个array把prev包起来(TreeNode[] preWrapper),就能真的改para的内容了(prevWrapper[0] = root)

keep in order traversal pointer是个固定trick,见https://leetcodenotes.wordpress.com/2013/08/28/phone-%E6%A0%91populate-%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84successor-pointer/

————————————————-10月份重做——————————————————

这个题第二遍做,又栽在一个trick里——如果swap的两个数正好在中序里面连着,那只能detect出来一次Out of order(比如1235467,发现5>4,然后mistake[0]放上5了,然后4<6,正常一路下去,mistake[1]永远也没被populate出来)。为了接住这个情况,在发现mistake[0]之后立刻把下一个当作mistake[1]赋上,要是后面真有mistake[1],反正也会覆盖;要是后面没有,正好接住了上面说的特殊情况)。

Tree的test case:

 

想练习translate recursion to iteration,的确很难。。本来是这么想的:

stack.push(root);
while (!empty(stack)) {
   Node node = stack.pop();
   check if node is leaf, if so, compare curr sum to x, if not equals x, then currsum -= leaf.val
   else
      node.push(node.right);
      node.push(node.left);
}
   a
  / \
 b   c
/ \
d  e

然后就悲剧了。这样的话,比如上面的数,到e了,pop出e, 但是currSum只减去了e的值,b的值还留着,然后就pop c了,所以右边就永久的留下了b的值在currSum里面。怎么能知道“该pop parent”了呢?显然要一路pop出去的话,还得套个循环。另外别每次把左右两枝都push进去,一次push一个就好了。这样stack里面永远是一条valid的path。

while (!empty(stack)) {
    Node node = stack.peak();
    if (node.left exists)
       stack.push(node.left);
       currSum += node.left.val;
    } else if (node.right exists)
       do the same for right node
    } else {
       // this is a leaf now, you want to 
       1.看currSum是不是符合,不符合的话,这个leaf就得出去了
       2.看要不要把parent一起pop出去
       if (currSum == x)
          return true;
       Node child = stack.pop();
       currSum -= child.val;
       while (stack is not empty) {
         Node parent = stack.peek();
         if (child is parent's left && parent has no right || child is parent's right) {
            //说明这一支已经结束,parent也改闪了。
            stack.pop();
            currSum -= parent.val;
            child = parent;
         } else {
            //说明这一支还没结束,parent的右孩子还没处理,所以把右孩子push进去,path改了方向。
            stack.push(parent.right);
            currSum += parent.right.val;
            break;
         }
    }
}
          
          

example: {1, 3, 1, 4, 2, 0} => {1, 3, 2, 0, 1, 4}

这题有点类似于CC上做的“同样的0和1组成的immediate next“那道题。曾经被问过原题两次,都做出来了,但是这次居然要看答案才会!!还是不扎实啊。。

和CC那道题的区别:100110 – 从右往左找第一个”后面有1的0“,然后变成1,后面自排就行了。但是这道题是数字,难说“从右往左找第一个比谁大的呢?”——其实找到一个比右边的某个数小的就行了,这样保证找到的这位i还算比较低位(从后往前找的嘛),然后右面那个比它大的数j可以和它swap,剩下的那些数在右边排列成升序就行了。

但是这么做,发现不能不用额外空间还O(n)(最后那些数要sort,要么费时间要么费空间)。于是看别人答案,是”从右开始找第一个升序排列的紧挨着的两个数i – 1和i“,说明越过的最右边的都是降序的。然后让从第i位(这里是第二个1)开始往后找,找到j使j是i的immediate next(arr[j] > arr[i] &&arr[j] 小于其他右边的>arr[j]的数,这里是2)。然后i, j swap,  这样arr[i]就到了”他应该属于的位置(j的位置)“,此时右边这些就正好降序排列了,可以直接两两swap使O(n)的升序sort成功。

private void getNext(int[] arr) {
  int pivot = -1;
  for (int i = arr.length - 1; i > 0; i--) {
    if (arr[i] > arr[i - 1]) {
      pivot = i - 1;
      break;
    }
  }
  if (pivot < 0) {
    arrangeToIncreaseOrder(arr, 0);
    return;
  }
  // the index of the number that is immediate next of pivot
  int nextToPivot = pivot + 1;
  for (int i = nextToPivot + 1; i < arr.length; i++) {
    if (arr[i] > arr[pivot] && arr[i] <= arr[nextToPivot])
      nextToPivot = i;
  }
  swap(arr, pivot, nextToPivot);
  // arrange arr to be increase from index i
  arrangeToIncreaseOrder(arr, pivot + 1);
}
Tags: ,

这个是要算到达最后一步最少要跳几步。不用非的跳到last index上,越过去也算。

还是,用dp的话有重复,不需要算d[i]跳到每一步用的最小步数,只要算最后一步能不能跳到,最少用几步就行了。这题其实自己还不够理解,下次还得重做。

算法:在每一步i,都已知到当前这一点用的最小step数k(但是不是存在数组里的,而是local variable)。在每层小循环里,都是“走一步能到的这些点中”, 最远能到哪一点,记载为p,那么到p就能最少用k + 1步就能到了。如果p出了数组边界,直接返回k + 1,就做出来了。要是没出界,则小循环之后,继续下一层循环,但是下一层循环和当前循环不重合,因为下一层说明多走了一步,则k++, 那循环的起始部分就是上一个小循环的尾。(每层小循环的意义是:用k步能走到的这些点,都试探一下,看看从他们身上走一步最远能走到哪)。

public int jump(int[] A) {
 if (A.length == 0 || A.length == 1)
   return 0;
 int examingStart = 0;
 int currSectionCanReach = 0;
 int steps = 0;
 while (examingStart <= currSectionCanReach) {
   int examingEnd = currSectionCanReach;
   int nextSectionCanReach = examingStart;
   for (int i = examingStart; i <= examingEnd; i++) {
     nextSectionCanReach = Math.max(nextSectionCanReach, i + A[i]);
     if (nextSectionCanReach >= A.length - 1)
       return steps + 1;
   }
   examingStart = examingEnd + 1;
   currSectionCanReach = nextSectionCanReach;
   steps++;
 }
 return -1;
}

Blog Stats

  • 222,234 hits
September 2021
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
27282930