Lexi's Leetcode solutions

Archive for the ‘summery’ Category

  • d[i][j]表示从(0, 0)到(i, j)有几种走法,因为只能从上面来或从左边来,所以每次计算只需要d[i – 1][j]和d[i, j – 1],左上角的全都浪费了。
  • f[i]表示从(0,0)到(当前row, j)有几种走法,上面来的就是自己,左边来的已经算好了,所以 f[j] = f[j] + f[j – 1];
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    // one way DP, f[i] means from (0, 0) to (currRow, i) has how many ways
    int f[] = new int[n];
    f[0] = obstacleGrid[0][0] > 0 ? 0 : 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) { //comes from above or left 
            if (obstacleGrid[i][j] > 0) {
                f[j] = 0;
            } else {
                if (j == 0) //first col only from above
                    f[j] = f[j];
                else 
                    f[j] = f[j] + f[j - 1];
            }
        }
    }
    return f[n - 1];
}
Advertisements
Tags: ,

不让用*, /, %号做整数除法。基本只能bit了。但是bit操作都是跟2有关的,所以到最后还得不断缩小范围,好能贴近结果。

算法:a / b

  1. a本来是想一直-b,然后减到<0了,算counter。但是这样慢,所以类似c++ vector的思路,每次发现还没减没,那减数就翻倍(b <<= 1)
  2. 然后到了一定程度,b实在太大了,大于a剩余的部分了,那么就停止。然后剩下的a再一点点开始减,b回归成最开始的值,重做这两步。

重点是一旦超过,b应该不要一下回到原始值,而是应该一点一点/2这样做。最刁钻的地方是test case全是各种Integer.MINVALUE之类的,搞得各种溢出,然后才发现Math.abs(MIN_VALUE)其实还是-2147483648(坑爹呢吧abs还是负数),而不是2147483648。

下面的解法是能跑过的。因为测试数据出现了-2147483648,还不能把它转成正的(2147483648就溢出了),所以直接全转换成long(64位),跑一遍就过了。

public int divide(int dividend, int divisor) {
    if (dividend == 0)
        return 0;
    if (divisor == 1)
        return dividend; //纯粹是为了防止超时
    boolean positive = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0);
    long absDividend = dividend < 0 ? 0 - (long) dividend : (long) dividend;
    long absDivisor = divisor < 0 ? 0 - (long) divisor : (long) divisor;
    int result = dividePositive(absDividend, absDivisor, absDivisor);
    return positive ? result : 0 - result;
}
private int dividePositive(long p, long q, long originalDivisor) { // p / q
    if (p < q)
        return 0; //这个十分必要,否则会因为p > 0而直接下一层递归,pq永远不变,死循环了就。
    int result = 0;
    int e = 0;
    while (p >= q) { //等于应该也进去。
        result += 1 << e;
        p -= q;
        q = q << 1;
        e++;
    }
    return p > 0 ? result + dividePositive(p, originalDivisor, originalDivisor) : result;
 }
Tags: , ,

比如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]的某个比较方式的最优解

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:
Tags:
  • generic list题的test cases
    1. normal case
    2. 1个ele
    3. 整个是个loop
    4. partial loop
  • 有可能删了元素的题:
    1. 小心head是不是被删了,要不要换新的
    2. prev指针一定要有,直接用一个指针指前一个,但是想删/动下一个,相比写p, p.next != null什么的,最好再keep一个prev指针,不容易乱套。即使多了一个var,总比写不对强!!
    3. 一般是Node head, Node prev, Node i, Node j四个指针。一定要写代码之前弄明白i, j都是什么物理意义!

Tags: