Lexi's Leetcode solutions

Posts Tagged ‘palindrome

非常非常难,用dfs完全过不了。即使把每个substring是不是palindrome全算好了放在cache里也会挂。必须dp了。

算法:

  1. 首先把每个substring是不是palindrome先二维dp的做出来,参见上一题的分析。其实这一步可以合在下一步里,但是下一步本身的logic就够难想了,所以这里分开来写。
  2. 一维dp(为神马是一维啊!!头一次看这样的一维啊!!一维dp却是两层循环啊卧槽!!!),d[i]表示str[i..n]最少切几刀能保证substring全是palindrome。
  3. 把d[i]先赋成最大值。
  4. i从后往前,然后j在每个i处从前往后。这样做就能保证在i处,i + 1…j – 1的所有两两combination(中间的小节substring)都已经算出来了,就能用了。如果str[i, j]是个palindrome,那么可以在j 和j + 1中间切一刀,这样的#就是d[j + 1] + 1([i..j], 一刀, [j + 1..本来有几刀])。这样切法可能就比之前算的d[i]小了,于是update。
public int minCut(String s) {
    int n = s.length();
    boolean[][] isPalin = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) { // i is always <= j
        for (int j = i; j < n; j++) {
            boolean isPalindrome = s.charAt(i) == s.charAt(j) 
                && (j - i < 2 || isPalin[i + 1][j - 1]);
            isPalin[i][j] = isPalindrome;
        }
    }
    int[] d = new int[n];
    // initialize as cut between every letter
    for (int i = 0; i < n; i++) {
        d[i] = n - 1 - i;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (isPalin[i][j]) {
                if (j == n - 1)
                    d[i] = 0;
                else
                    d[i] = Math.min(d[i], d[j + 1] + 1);
            }
         }
    }
    return d[0];
}
Advertisements

这题八月份做的太复杂了,中心思想还是如何render两头的digit,不过leetcode的方法最简单:

  1. 最左边的digit = x / 1000..(长度为x的长度)
  2. 最右边的digit= x % 10
  3. 然后把x两头chop掉。这个做的挺巧妙的,先是x = x % 1000…,把后几位留下,然后x / 10,把最后一位扔了。
  4. 感觉还是对除、余不熟练。记住x/10000..最长就是10000..那么长。所以%10就是显示一位。%是要后面的,/是要前面的。
public boolean isPalindrome(int x) {
    if (x < 0)
        return false;
    int len = 0, temp = x;
    while (temp > 0) {
        temp /= 10;
        len++;
    }
    int pow = (int)Math.pow(10, len - 1);
    while (x > 0) {
        int firstDigit = x / pow;
        int lastDigit = x % 10;
        if (firstDigit != lastDigit)
            return false;
        x = (x % pow) / 10; //chop first then chop last;
        pow /= 100; //two digits gone, so pow shrinks by 100 times
    }
    return true;
}

——————————————————————–八月份——————————————————————-

这题其实思路挺简单,就是不断把两头的digit(通过/10^x, %10^y)弄出来比较,若有不等的时候,就返回false。

重点是怎么render两头的digit。index什么的非常容易错位,写出来了其实也不直观make sense,所以一定要写好了算法之后,自己好好试试,跑几个case才能发现问题。

int i = 1;
while (i <= bitCount / 2) {
  int tenPowerI = (int) Math.pow(10, i); // 10^i
  int p = x % tenPowerI; //p = x % 10^i
  p = p * 10 / tenPowerI; //p = p / 10^(i - 1), render the first digit of p

  int tenPowerBitCountMinusI = (int) Math.pow(10, bitCount - i); //10^(bitCount - i)
  int q = x / tenPowerBitCountMinusI; // q = x / 10^(bitCount - i))
  q = q % 10; //render the last digit of q

  if (p != q)
    return false;
  i++;
}

题目:给一个string,找这个str里面最长的中心对称substring

这个题上来就想一维dp,然后挣扎半天做不出来(找不到一维的d[i]和d[i + 1]的直接关系)。然后上网查答案,原来用二维dp做,而且速度是O(n^2)。其实这题上来就应该先想暴力,然后知道暴力的速度是n^3,然后想办法降一维,别上来就强迫自己O(n)!

二维dp:

  1. d[i][j]是个boolean,表示(i, j)这个substring是不是中心对称。
  2. d[i][j]
    • 正常情况下,d[i][j] = true when 1.A[i]==A[j] 2. d[i + 1][j – 1] == true (中间那部分已经中心对称了)
    • 处理i+1, j-1出界和左边反而大于右边的情况:
      • 当i == j时,d[i][j] = 1(一个字母肯定是中心对称)
      • 当i == j – 1时,说明两个字符是连着的,看A[i]是否==A[j]就行
  3. 这个题的坑爹之处在于正常i从0~last, j从0~last那么循环不行。因为d[i][j]用到了d[i + 1][j – 1],说明i要从后往前,j则要从前往后。导致二层循环是这种顺序:
    for (int i = last; i >= 0; i–)
    for(int j = i; j  <= last; j++)
    因为这事想了半天,有点焦躁。

不用二维数组的算法(直接按中心对称的定义来,而不是每个pair算一遍,可以省一维空间):

  1. 以每个元素以及间隔为中心(共2 * n – 1个),以相同的速度往两侧扩张,直到两边儿的值不相等了,说明palindrome在此打破,于是输出。这样每次输出的肯定是以当前这个点为中心最长的palindrome)
  2. 这样过一遍数组,最长的就出来了。
public String longestPalindrome(String s) {
    String res = "";
    for (int i = 0; i < s.length(); i++) {
        String odd = expand(s, i, i);
        String even = expand(s, i, i + 1);
        String longer = odd.length() > even.length() ? odd : even;
        res = longer.length() > res.length() ? longer : res;
    }
    return res;
}
private String expand(String s, int i, int j) {
    while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
       i--;
       j++;
    }
    return s.substring(i + 1, j);
}