Lexi's Leetcode solutions

Archive for October 12th, 2013

比如abcdefg, defmnabs,最长公共subtring是def。

又是二维DP求String的最优解。居然还是算法课作业做过,真是一点印象也木有了。

  • d[i][j] : A[0…i]和B[0…j]的最长公共后缀的长度
  • d[i][j] =
    1. A[i] == B[j] : d[i][j] = d[i – 1][j – 1] + 1 //公共后缀多了当前这个char
    2. A[i] != B[j] : d[i][j] = 0//断开了,无公共后缀了

总结一下二维DP解String题的做法:

  • 一个String, d[i][j]表示A[i…j]的某个最优解
  • 两个String, d[i][j]表示A[0…i], B[0…j]的某个比较方式的最优解

这是好难好难的二维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];
}

Point:

  • randN() 表示能生成0~N-1这N个数。
  • 一般除呀余呀之类的都是从0开始最好,如果题中不是从0开始,自己-1最后再+1。
  • a % b就是(0, 1, …, b – 1),一共b个。

Example 1: 用randK()来实现randN() (K < N,用小的生产大的)

  1. 比如rand5() -> rand7()
  2. 想要生成0 – 20 evenly distributed
  3. int a = 5 * rand5() + rand5() = 5 * (0 … 4) + (0…4) = (0, 5, 10, 15, 20) + (0…4) = (0..24)
  4. 然后如果a < 3 * 7,, return a % 7
  5. if a >= 3 * 7, do it again

Example 2:  用randN()来实现randK()(用大的生成小的)

  1. 用rand10() -> rand4()
  2. 已经有(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
  3. 想生成(0, 1, 2, 3)
  4. 10 % 4 = 2, 说明%1, %2的几率由于最后两个数的出现比%别的的几率都大了。所以要想办法除掉最后两个数
  5. 所以rand10结果是8, 9的时候,扔掉重算
  6. rand10结果<8的时候,就可以用这个数%K,就是结果了。
Tags:

Blog Stats

  • 221,510 hits
October 2013
M T W T F S S
 123456
78910111213
14151617181920
21222324252627
28293031