Lexi's Leetcode solutions

Posts Tagged ‘hard

有点后悔,这个题当时看了就好了,T家真的就考了类似的。要是看了就不至于现场出现当天同时买卖那个bug;从后往前scan array也不会那么生疏。。G家也是,要是看了CC150那道题就不会挂在拓扑排序上。没事,记住教训就好了——题是不能越过去的,越是skip的越有考的可能。

这个题一开始是二分法做的,每次切一刀然后左边O(n)做一次右边O(n)做一次,整体是O(n^2),超时。正确方法是一维dp从左到右扫一遍,再从右到左扫一遍,然后两次加和。
两个一维数组的定义一定要搞清,onsite的时候就栽在这上面了!

  • d[i]: [0…i]这段时间的买卖一次的最大利润。所以i应该从1开始。
  • f[i]: [i…n – 1]这段时间的买卖一次的最大利润。所以i应该最大n – 2。
  • 然后就看出问题了——两个i不能同步,否则就当天买卖了。最后加和的时候要错开。
  • 因为“最多买卖两次”, 所以还要包括买卖一次的情况。用d[n-1]就是[0…n-1]可以表达这种情况。
        public int maxProfit(int[] prices) {
	    if (prices.length == 0)
	        return 0;
	    int[] d = buildMaxProfitFromStart(prices);
	    int[] f = buildMaxProfitFromEnd(prices);
	    int maxProfit = d[prices.length - 1]; 
	    for (int i = 0; i < prices.length - 1; i++) { 			
                maxProfit = Math.max(maxProfit, d[i] + f[i + 1]); 		
            } 		
            return maxProfit; 	
        } 	
        private int[] buildMaxProfitFromEnd(int[] arr) { 		
            int[] f = new int[arr.length]; 		
            f[arr.length - 1] = 0; 		
            int max = arr[arr.length - 1]; 		
            int maxProfit = 0; 		
            for (int i = arr.length - 2; i >= 0; i--) {
	        maxProfit = Math.max(maxProfit, max - arr[i]);
		max = Math.max(max, arr[i]);
		f[i] = maxProfit;
	    }
	    return f;
	}
	private int[] buildMaxProfitFromStart(int[] arr) {
	    int[] d = new int[arr.length];
	    d[0] = 0;
	    int min = arr[0];
	    int maxProfit = 0;
	    for (int i = 1; i < arr.length; i++) {
	  	maxProfit = Math.max(maxProfit, arr[i] - min);
		min = Math.min(min, arr[i]);
		d[i] = maxProfit;
	    }
	    return d;
	}
Advertisements

这个题尽管是CC150上的,理论上很简单,但是想明白(而且用好的方法)很不容易。

1. 数组没有重复

  1. 既然是断开一次的数组,说明A[p] > A[q]。我们从中间一刀划分,想出找sorted那一半,看是否包含x,包含的话就在sorted那一半找;不包含就在broken那一半找。
  2. 这个是根据A[mid]和A[p]来初步划分,平时binary search都是根据A[mid]和x来直接划分。所以一开始做复杂了。这个题按上面说的定义做最好,简单易懂。
  3. 当A[mid] == A[p]的时候,说明mid==p,就左边这一个点,既然已经判断过A[mid] != x了,所以直接找右边就好了。
public int search(int[] A, int target) {
  return find(A, 0, A.length - 1, target);
}
private int find(int[] arr, int p, int q, int x) {
  if (p > q)
    return -1;
  int mid = (p + q) / 2;
  if (arr[mid] == x)
    return mid;
  if (arr[p] < arr[mid]) { // left is ordered, right is broken
    if (arr[p] <= x && x <= arr[mid]) // x is in the left ordered part
      return find(arr, p, mid - 1, x);
    else // x doesn't belong to left ordered part
      return find(arr, mid + 1, q, x);
  } else if (arr[p] > arr[mid]) {// left is broken, so right is ordered
    if (arr[mid] <= x && x <= arr[q])
      return find(arr, mid + 1, q, x);
    else
      return find(arr, p, mid - 1, x);
  } else { // a[p] == a[mid], directly search right
      return find(arr, mid + 1, q, x);
  }
}

2. 数组有重复数字

  1. 还是从中间一刀划分,想找出sorted那一半,看是否包含x。
  2. 但是当A[p] == A[mid]的时候,不能说明左边就是长度为1的一半了。左边可以是全是repeat,也可以是包含x。
  3. 这时要和A[q]比较,如果A[mid] == A[q],总不能整个数组平了吧。这时候x可以是左边也可以是在右边,必须两边找。
  4. 如果A[mid] != A[q],说明右半部分有起伏,左边的平的这段就不能有起伏了(自己画一下吧)。所以还是找右边。
public boolean search(int[] A, int target) {
  return find(A, 0, A.length - 1, target) >= 0;
}
private int find(int[] arr, int p, int q, int x) {
  if (p > q)
    return -1;
  int mid = (p + q) / 2;
  if (arr[mid] == x)
    return mid;
 
  if (arr[p] < arr[mid]) { //left is ordered, right is broken
    if (arr[p] <= x && x <= arr[mid]) // x is in the left ordered part
      return find(arr, p, mid - 1, x);
    else //x doesn't belong to left orderd part
      return find(arr, mid + 1, q, x);
  } else if (arr[p] > arr[mid]) {//left is broken, so right is ordered
    if (arr[mid] <= x && x <= arr[q])
      return find(arr, mid + 1, q, x);
    else
      return find(arr, p, mid - 1, x);
  } else { // arr[p] = arr[mid], don't know which side is broken
    if (arr[mid] == arr[q]) {
      int leftResult = find(arr, p, mid - 1, x);
      return leftResult == -1 ? find(arr, mid + 1, q, x) : leftResult;
    } else { //mid is not equals right, so left is all repeats, search right
      return find(arr, mid + 1, q, x);
    }
  }
}

这是好难好难的二维DP题。尽管知道两个String比较很可能是二维DP,但是状态方程真是不好定义;定义了关系也特别不直观。

A: RABBBIT; B: RABBIT

  • d[i][j]: A[0…i]里面出现了几次B[0…j],比如RAB里出现了几次RA
  • d[i][j] =
    • if A[i] != B[j],比如RABC和RAB,那么C(A[i]就得被删除,d[i][j]就是RAB在RAB包含的之前算过的情况d[i – 1][j]
    • if A[i] == B[j],比如RABB和RAB,那么
      1. 可以把RABB的第二个B删除得到RAB,所以d[i][j]最少也是d[i – 1][j]
      2. 可以用RABB的第二个B直接对应RAB的那个B消掉,所以相当于A=RAB和B=RA,d[i][j] += d[i – 1][j – 1]
    • 初始值就是二维DP那么做就行了。
  • 这个是真心难想通。还得多做多练习。
public int numDistinct(String S, String T) {
  if (T.length() > S.length())
    return 0;
  char[] A = S.toCharArray();
  char[] B = T.toCharArray();
  int[][] d = new int [A.length][B.length];
  d[0][0] = A[0] == B[0] ? 1 : 0;
  int count = d[0][0];
  for (int i = 1; i < A.length; i++) {
    if (A[i] == B[0])
    count++;
    d[i][0] = count;
  }
  for (int j = 1; j < B.length; j++) {
    d[0][j] = 0;
  }
  for (int i = 1; i < A.length; i++) {
    for (int j = 1; j < B.length; j++) {
      if (A[i] == B[j]) {
        d[i][j] = d[i - 1][j] + d[i - 1][j - 1];
      } else {
        d[i][j] = d[i - 1][j];
      }
    }
  }
  return d[A.length - 1][B.length - 1];
}

比如 {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: , ,