题目与解答

未分类

题目

1. 恶魔抓到了公主，把她囚禁在地牢的右下角，勇敢的骑士从地牢左上角出发，一次走一格。每个格子里可能有恶魔守卫（扣血），血瓶（加血），或什么事都不发生。包括左上角和右下角的格子。骑士的起始血量为正整数，如果骑士的血量<=0，他就会立即死亡。为了尽快赶到公主那里，骑士决定每步只会向右走或向下走。输入地牢的结构（整数二维数组），求骑士起始血量至少为多少，才能成功赶到公主那里？
   例如：如下的地牢，骑士最少需要7点生命，路线为右->右->下->下。
   -2 -3 3
   -5 -10 1
   10 30 -5

java:public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {     
    }
}

2.对于任意一个字符串，你可以在它之前添加字符，使得它构成回文序列。现在输入一个字符串，请输出以这种方式，能够得到的最短回文序列。
例如：
输入："aacecaaa" 输出："aaacecaaa"
输入："abcd" 输出："dcbabcd"

java:public class Solution {
    public String shortestPalindrome(String s) {
    }
}

解答

地牢游戏(leetcode 174)

假设输入的二维数组为dungeon[m][n]，注意两点：
1. 使用额外的O(m*n)空间存储中间结果。这样复杂度降低为O(m*n)。否则复杂度为O(2^(m+n))。
2. 利用一个特点，即对于方格(i,j)，勇者该格子中扣除的血量，无法通过之后得到的血瓶进行补偿。
解：
设置二维数组x[m][n]，其中x[i][j]记录为了到达终点，勇者在格子(i,j)上的最小血量。
从终点出发，反向遍历矩阵的所有格子，直到回到起点。

在终点处:

if(dungeon[m-1,n-1]>=0)
    x[m-1,n-1] = 1
else
    x[m-1,n-1] = 1 - dungeon[m-1,n-1]

状态转移方程为:

    temp = min(x[i+1,j],x[i,j+1])
    if (dungeon[i,j]>=temp)
        x[i,j]=1
    else
        x[i,j] = temp-dungeon[i,j]

最短回文串(leetcode 214)

1. 使用一个分界点将字符串分为两部分，分界点起始在字符串中央。
2. 对分界点两侧等长的字符串进行hash，由hash值相等判断两个字符串是否全等。
3. 不断将分界点左移，最多比较n次可以得到结果。
4. 只要对字符串的hash复杂度为O(1)。该解法的总时间复杂度为O(n)

一般对一个长度为n的字符串，取hash的复杂度为O(n)。要做到O(1)内hash，可以利用一个特点，即分界点每移动一次，点两侧的字符串仅变化一个字符。
相应的方法是：多项式插值取模哈希，参考：http://www.cnblogs.com/ka200812/archive/2012/08/30/2663997.html
该方法本质上利用了这样一个规律
1. x*37%H = x%H*37%H
2. (x*37+y)%H = (x%H*37+y)%H