Leetcode——链表和数组（5）

地下城游戏

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

说明:

• 骑士的健康点数没有上限。


• 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

建立一个二维数组 dp，其中 dp[i][j] 用来表示当前位置 (i, j) 出发的起始血量，

最先处理的是公主所在的房间的起始生命值，然后慢慢向第一个房间扩散，不断的得到各个位置的最优的生命值。

如果从起始位置开始遍历，我们并不知道初始时应该初始化的血量，但是到达公主房间后，我们知道血量至少不能小于1，如果公主房间还需要掉血的话，那么掉血后剩1才能保证起始位置的血量最小。

那么下面来推导状态转移方程，首先考虑每个位置的血量是由什么决定的，骑士会挂主要是因为去了下一个房间时，掉血量大于本身的血值，而能去的房间只有右边和下边，所以当前位置的血量是由右边和下边房间的可生存血量决定的，

进一步来说，应该是由较小的可生存血量决定的，因为较我们需要起始血量尽可能的少，因为我们是逆着往回推，骑士逆向进入房间后 PK 后所剩的血量就是骑士正向进入房间时 pk 前的起始血量。

用当前房间的右边和下边房间中骑士的较小血量减去当前房间的数字，

如果是负数或着0，说明当前房间是正数，这样骑士进入当前房间后的生命值是1就行了，因为不会减血。

如果差是正数的话，当前房间的血量可能是正数也可能是负数，但是骑士进入当前房间后的生命值就一定要是这个差值。

状态转移方程是 dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])。

为了更好的处理边界情况，我们的二维 dp 数组比原数组的行数列数均多1个，先都初始化为整型数最大值 INT_MAX，由于我们知道到达公主房间后，骑士火拼完的血量至少为1，那么此时公主房间的右边和下边房间里的数字我们就都设置为1，这样到达公主房间的生存血量就是1减去公主房间的数字和1相比较，取较大值

二维动态规划

dungeon

dp

m = 3 n = 3

C++

class Solution {
public:
int calculateMinimumHP(vector>& dungeon) {
int m = dungeon.size(), n = dungeon[0].size();
vector> dp(m + 1, vector(n + 1, INT_MAX));
dp[m][n - 1] = 1; dp[m - 1][n] = 1;
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
}
}
return dp[0][0];
}
};


一维动态规划

我们可以对空间进行优化，使用一个一维的 dp 数组，并且不停的覆盖原有的值，参见代码如下：

class Solution {
public:
int calculateMinimumHP(vector>& dungeon) {
int m = dungeon.size(), n = dungeon[0].size();
vector dp(n + 1, INT_MAX);
dp[n - 1] = 1;
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
dp[j] = max(1, min(dp[j], dp[j + 1]) - dungeon[i][j]);
}
}
return dp[0];
}
};


摘樱桃

一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：

• 0 表示这个格子是空的，所以你可以穿过它。


• 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。


• -1 表示这个格子里有荆棘，挡着你的路。

你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：

• 从位置 (0, 0) 出发，最后到达 (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为0或者1的格子）；


• 当到达 (N-1, N-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；


• 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为0）；


• 如果在 (0, 0) 和 (N-1, N-1) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。

示例 1:

输入: grid =
[[0, 1, -1],
[1, 0, -1],
[1, 1, 1]]
输出: 5
解释：
玩家从（0,0）点出发，经过了向下走，向下走，向右走，向右走，到达了点(2, 2)。
在这趟单程中，总共摘到了4颗樱桃，矩阵变成了[[0,1,-1],[0,0,-1],[0,0,0]]。
接着，这名玩家向左走，向上走，向上走，向左走，返回了起始点，又摘到了1颗樱桃。
在旅程中，总共摘到了5颗樱桃，这是可以摘到的最大值了。


说明:

• grid 是一个 N * N 的二维数组，N的取值范围是1 <= N <= 50。

  
  



• 每一个 grid[i][j] 都是集合 {-1, 0, 1}其中的一个数。

  
  



• 可以保证起点 grid[0][0] 和终点 grid[N-1][N-1] 的值都不会是 -1。

  
  

动态规划

最开始时定义的dp[i][j]为单程的，即到达(i, j)位置能捡到的最大樱桃数，即：

T(i, j) = grid[i][j] + max{ T(i-1, j), T(i, j-1) }


但是定义单程就得改变grid的值，再进行一次dp计算时，就会陷入之前例子中的陷阱。所以我们的dp[i][j]还是需要定义为round trip的，即到达(i, j)位置并返回起点时能捡到的最大樱桃数，但是新的问题就来了，樱桃只有一个，只能捡一次，去程捡了，返程就不能再捡了，如何才能避免重复计算呢？我们只有i和j是不够的，其只能定义去程的位置，我们还需要pg，来定义返程的位置，那么重现关系Recurrence Relations就变成了 T(i, j, p, g)，我们有分别两种方式离开(i, j)和(p, g)，我们suppose时从终点往起点遍历，那么就有4种情况：

Case 1: (0, 0) ==> (i-1, j) ==> (i, j); (p, q) ==> (p-1, q) ==> (0, 0)
Case 2: (0, 0) ==> (i-1, j) ==> (i, j); (p, q) ==> (p, q-1) ==> (0, 0)
Case 3: (0, 0) ==> (i, j-1) ==> (i, j); (p, q) ==> (p-1, q) ==> (0, 0)
Case 4: (0, 0) ==> (i, j-1) ==> (i, j); (p, q) ==> (p, q-1) ==> (0, 0)


根据定义，我们有：

Case 1 is equivalent to T(i-1, j, p-1, q) + grid[i][j] + grid[p][q];
Case 2 is equivalent to T(i-1, j, p, q-1) + grid[i][j] + grid[p][q];
Case 3 is equivalent to T(i, j-1, p-1, q) + grid[i][j] + grid[p][q];
Case 4 is equivalent to T(i, j-1, p, q-1) + grid[i][j] + grid[p][q];


因此，我们的重现关系可以写作：

T(i, j, p, q) = grid[i][j] + grid[p][q] +
max{T(i-1, j, p-1, q), T(i-1, j, p, q-1),
T(i, j-1, p-1, q), T(i, j-1, p, q-1)}


为了避免重复计算，我们希望 grid[i][j] 和 grid[p][g] 不出现在T(i-1, j, p-1, q), T(i-1, j, p, q-1), T(i, j-1, p-1, q) 和 T(i, j-1, p, q-1)中的任意一个上。

显而易见的是(i, j)不会出现在(0, 0) ==> (i-1, j) 或 (0, 0) ==> (i, j-1) 的路径上，同理，(p, g) 也不会出现在 (p-1, q) ==> (0, 0) 或 (p, q-1) ==> (0, 0) 的路径上。

因此，我们需要保证(i, j) 不会出现在 (p-1, q) ==> (0, 0) 或 (p, q-1) ==> (0, 0) 的路径上，同时 (p, g)不会出现在(0, 0) ==> (i-1, j) 或 (0, 0) ==> (i, j-1) 的路径上，怎么做呢？

我们观察到(0, 0) ==> (i-1, j) 和 (0, 0) ==> (i, j-1) 的所有点都在矩形 [0, 0, i, j] 中（除了右下角点(i, j)点），所以只要 (p, g) 不在矩形 [0, 0, i, j] 中就行了，注意(p, g) 和 (i, j) 是有可能重合了，这种情况特殊处理一下就行了。同理， (i, j) 也不能在矩形 [0, 0, p, g] 中，那么以下三个条件中需要满足一个：

i

q
i == p && j == q
i > p && j

为了满足上述条件，我们希望当 i 或 p 增加的时候，j 或 q 减小，那么我们可以有这个等式:

k = i + j = p + q


其中k为从起点开始走的步数，所以我们可以用 T(k, i, p) 来代替 T(i, j, p, g)，那么我们的重现关系式就变成了：

T(k, i, p) = grid[i][k-i] + grid[p][k-p] +
max{T(k-1, i-1, p-1), T(k-1, i-1, p), T(k-1, i, p-1), T(k-1, i, p)}.


当 i == p 时，grid[i][k-i] 和 grid[p][k-p] 就相等了，此时只能加一个。我们注意到 i, j, p, q 的范围是 [0, n)， 意味着k只能在范围 [0, 2n - 1) 中， 初始化时 T(0, 0, 0) = grid[0][0]。

我们这里的重现关系T虽然是三维的，但是我们可以用二维dp数组来实现，因为第k步的值只依赖于第k-1步的情况

class Solution {
public:
int cherryPickup(vector>& grid) {
int n = grid.size(), mx = 2 * n - 1;
vector> dp(n, vector(n, -1));
dp[0][0] = grid[0][0];
for (int k = 1; k for (int i = n - 1; i >= 0; --i) {
for (int p = n - 1; p >= 0; --p) {
int j = k - i, q = k - p;
if (j <0 || j >= n || q <0 || q >= n || grid[i][j] <0 || grid[p][q] <0) {
dp[i][p] = -1;
continue;
}
if (i > 0) dp[i][p] = max(dp[i][p], dp[i - 1][p]);
if (p > 0) dp[i][p] = max(dp[i][p], dp[i][p - 1]);
if (i > 0 && p > 0) dp[i][p] = max(dp[i][p], dp[i - 1][p - 1]);
if (dp[i][p] >= 0) dp[i][p] += grid[i][j] + (i != p ? grid[p][q] : 0);
}
}
}
return max(dp[n - 1][n - 1], 0);
}
};


子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]


非递归

由于题目要求子集合中数字的顺序是非降序排列的，所有我们需要预处理，先给输入数组排序，然后再进一步处理，最开始我在想的时候，是想按照子集的长度由少到多全部写出来，比如子集长度为0的就是空集，空集是任何集合的子集，满足条件，直接加入。

下面长度为1的子集，直接一个循环加入所有数字，子集长度为2的话可以用两个循环，但是这种想法到后面就行不通了，因为循环的个数不能无限的增长，所以我们必须换一种思路。

我们可以一位一位的网上叠加，比如对于题目中给的例子 [1,2,3] 来说，

最开始是空集，那么我们现在要处理1，就在空集上加1，为 [1]，现在我们有两个自己 [] 和 [1]，

下面我们来处理2，我们在之前的子集基础上，每个都加个2，可以分别得到 [2]，[1, 2]，那么现在所有的子集合为 [], [1], [2], [1, 2]，

同理处理3的情况可得 [3], [1, 3], [2, 3], [1, 2, 3], 再加上之前的子集就是所有的子集合了

class Solution {
public:
vector > subsets(vector &S) {
vector > res(1);
sort(S.begin(), S.end());
for (int i = 0; i int size = res.size();
for (int j = 0; j res.push_back(res[j]);
res.back().push_back(S[i]);
}
}
return res;
}
};


递归

相当于一种深度优先搜索，由于原集合每一个数字只有两种状态，要么存在，要么不存在，那么在构造子集时就有选择和不选择两种情况，所以可以构造一棵二叉树，左子树表示选择该层处理的节点，右子树表示不选择，最终的叶节点就是所有子集合，树的结构如下：

[]
/ \
/ \
/ \
[1] []
/ \ / \
/ \ / \
[1 2] [1] [2] []
/ \ / \ / \ / \
[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []


class Solution {
public:
vector > subsets(vector &S) {
vector > res;
vector out;
sort(S.begin(), S.end());
getSubsets(S, 0, out, res);
return res;
}
void getSubsets(vector &S, int pos, vector &out, vector > &res) {
res.push_back(out);
for (int i = pos; i out.push_back(S[i]);
getSubsets(S, i + 1, out, res);
out.pop_back();
}
}
};


二进制

把数组中所有的数分配一个状态，true 表示这个数在子集中出现，false 表示在子集中不出现，那么对于一个长度为n的数组，每个数字都有出现与不出现两种情况，所以共有 2^n 中情况，那么我们把每种情况都转换出来就是子集了，

用题目中的例子, [1 2 3] 这个数组共有8个子集，每个子集的序号的二进制表示，把是1的位对应原数组中的数字取出来就是一个子集，八种情况都取出来就是所有的子集了，参见代码如下：

class Solution {
public:
vector > subsets(vector &S) {
vector > res;
sort(S.begin(), S.end());
int max = 1 < for (int k = 0; k vector out = convertIntToSet(S, k);
res.push_back(out);
}
return res;
}
vector convertIntToSet(vector &S, int k) {
vector sub;
int idx = 0;
for (int i = k; i > 0; i >>= 1) {
if ((i & 1) == 1) {
sub.push_back(S[idx]);
}
++idx;
}
return sub;
}
};


子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]


非递归解法

拿题目中的例子 [1 2 2] 来分析，当处理到第一个2时，此时的子集合为 [], [1], [2], [1, 2]，而这时再处理第二个2时，

如果在 [] 和 [1] 后直接加2会产生重复，所以只能在上一个循环生成的后两个子集合后面加2，发现了这一点，题目就可以做了，

我们用 last 来记录上一个处理的数字，然后判定当前的数字和上面的是否相同，

若不同，则循环还是从0到当前子集的个数，

若相同，则新子集个数减去之前循环时子集的个数当做起点来循环，这样就不会产生重复了

class Solution {
public:
vector> subsetsWithDup(vector &S) {
if (S.empty()) return {};
vector> res(1);
sort(S.begin(), S.end());
int size = 1, last = S[0];
for (int i = 0; i if (last != S[i]) {
last = S[i];
size = res.size();
}
int newSize = res.size();
for (int j = newSize - size; j res.push_back(res[j]);
res.back().push_back(S[i]);
}
}
return res;
}
};


递归

在处理到第二个2时，由于前面已经处理了一次2，这次我们只在添加过2的 [2] 和 [1 2] 后面添加2，其他的都不添加，那么这样构成的二叉树如下图所示：

[]
/ \
/ \
/ \
[1] []
/ \ / \
/ \ / \
[1 2] [1] [2] []
/ \ / \ / \ / \
[1 2 2] [1 2] X [1] [2 2] [2] X []


while (S[i] == S[i + 1]) ++i; 这句话的作用是跳过树中为X的叶节点，因为它们是重复的子集，应被抛弃

class Solution {
public:
vector> subsetsWithDup(vector &S) {
if (S.empty()) return {};
vector> res;
vector out;
sort(S.begin(), S.end());
getSubsets(S, 0, out, res);
return res;
}
void getSubsets(vector &S, int pos, vector &out, vector> &res) {
res.push_back(out);
for (int i = pos; i out.push_back(S[i]);
getSubsets(S, i + 1, out, res);
out.pop_back();
while (i + 1 }
}
};


字母大小写全排列

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例:
输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
输入: S = "3z4"
输出: ["3z4", "3Z4"]
输入: S = "12345"
输出: ["12345"]


注意：

• S 的长度不超过12。


• S 仅由数字和字母组成。

非递归

我们关心的是字母，数字的处理很简单，直接加上就可以了。

比如说S = "abc"，那么先让 res = [""]，

然后res中的每个字符串分别加上第一个字符a和A，得到 ["a", "A"]，

然后res中的每个字符串分别加上第二个字符b和B，得到 ["ab", "Ab", "aB", "AB"]，

然后res中的每个字符串分别加上第三个字符c和C，得到 ["abc", "Abc", "aBc", "ABc", "abC", "AbC", "aBC", "ABC"]

class Solution {
public:
vector letterCasePermutation(string S) {
vector res{""};
for (char c : S) {
int len = res.size();
if (c >= '0' && c <= '9') {
for (string &str : res) str.push_back(c);
} else {
for (int i = 0; i res.push_back(res[i]);
res[i].push_back(tolower(c));
res[len + i].push_back(toupper(c));
}
}
}
return res;
}
};


递归

一种回溯的思路，比如说S = "abc"，用一个pos指向当前处理的位置，初始化带入0，然后再递归函数中，

如果pos等于s的长度了，那么将s存入结果res再返回；

否则调用递归函数，此时带入pos+1，那么递归函数就会一直深入，直到pos等于s的长度了，那么此时就把"abc"存入结果res了，返回后此时pos=2，发现s[pos]是字母，则用上面解法中的flip方法来翻转字母，

并且调用递归函数，这样"abC"就会存入结果res中，然后回溯到pos=1的位置，s[pos]是字符，可以flip，

并且调用递归函数，这样"aBC"就会存入结果res中，然后pos继续往后遍历，这样"aBc"就会存入结果res中，然后回溯到pos=0的位置，s[pos]是字符，可以flip，

并且调用递归函数，这样"ABc"就会存入结果res中，然后继续回溯，这样"ABC"就会存入结果res中，pos又回溯到1的位置，s[pos]是字符，可以flip，

并且调用递归函数，这样"AbC"就会存入结果res中，然后pos继续往后遍历，这样"Abc"就会存入结果res中，整个的顺序为：[abc abC aBC aBc ABc ABC AbC Abc]

class Solution {
public:
vector letterCasePermutation(string S) {
vector res;
helper(S, 0, res);
return res;
}
void helper(string& s, int pos, vector& res) {
if (pos == s.size()) {
res.push_back(s);
return;
}
helper(s, pos + 1, res);
if (s[pos] > '9') {
s[pos] ^= 32;
helper(s, pos + 1, res);
}
}
};


二进制

000 -> ABC
001 -> ABc
010 -> AbC
011 -> Abc
100 -> aBC
101 -> aBc
110 -> abC
111 -> abc


统计出S中字母的个数cnt，然后遍历 [0, 2^cnt) 中的每个数字，对于每个数字，再遍历S中的每个字符，

如果是字母，那么如果当前位是1，则加入小写字母，反之加入大写字母；

如果是数字，则直接加入即可。

我们用j指向位，每次处理完一位后j自增1，表示对下一位进行处理

class Solution {
public:
vector letterCasePermutation(string S) {
vector res;
int cnt = 0;
for (char c : S) {
if (c > '9') ++cnt;
}
for (int i = 0; i <(1 < int j = 0;
string word = "";
for (char c : S) {
if (c > '9') {
if (((i >> j++) & 1) == 1) {
word.push_back(tolower(c));
} else {
word.push_back(toupper(c));
}
} else {
word.push_back(c);
}
}
res.push_back(word);
}
return res;
}
};


列举单词的全部缩写

题目描述:

请你写出一个能够举单词全部缩写的函数。

注意：输出的顺序并不重要。

示例:

输入: "word"
输出:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]


二进制

0000 word
0001 wor1
0010 wo1d
0011 wo2
0100 w1rd
0101 w1r1
0110 w2d
0111 w3
1000 1ord
1001 1or1
1010 1o1d
1011 1o2
1100 2rd
1101 2r1
1110 3d
1111 4


观察出规律，凡是0的地方都是原来的字母，单独的1还是1，

如果是若干个1连在一起的话，就要求出1的个数，用这个数字来替换对应的字母

class Solution {
public:
vector generateAbbreviations(string word) {
vector res;
for (int i = 0; i string out = "";
int cnt = 0, t = i;
for (int j = 0; j if (t & 1 == 1) {
++cnt;
if (j == word.size() - 1) out += to_string(cnt);
} else {
if (cnt != 0) {
out += to_string(cnt);
cnt = 0;
}
out += word[j];
}
t >>= 1;
}
res.push_back(out);
}
return res;
}
};


递归

class Solution {
public:
vector generateAbbreviations(string word) {
vector res{word};
helper(word, 0, res);
return res;
}
void helper(string word, int pos, vector &res) {
for (int i = pos; i for (int j = 1; i + j <= word.size(); ++j) {
string t = word.substr(0, i);
t += to_string(j) + word.substr(i + j);
res.push_back(t);
helper(t, i + 1 + to_string(j).size(), res);
}
}
}
};


class Solution {
public:
vector generateAbbreviations(string word) {
vector res;
helper(word, 0, 0, "", res);
return res;
}
void helper(string word, int pos, int cnt, string out, vector &res) {
if (pos == word.size()) {
if (cnt > 0) out += to_string(cnt);
res.push_back(out);
} else {
helper(word, pos + 1, cnt + 1, out, res);
helper(word, pos + 1, 0, out + (cnt > 0 ? to_string(cnt) : "") + word[pos], res);
}
}
};


class Solution {
public:
vector generateAbbreviations(string word) {
vector res;
res.push_back(word.size() == 0 ? "" : to_string(word.size()));
for (int i = 0; i for (auto a : generateAbbreviations(word.substr(i + 1))) {
string left = i > 0 ? to_string(i) : "";
res.push_back(left + word.substr(i, 1) + a);
}
}
return res;
}
};