Leetcode Weekly Contest 147
1. 题目列表
- 第 N 个泰波那契数（简单）
- 字母板上的路径（模拟行走）
- 单字符重复子串的最大长度
- 子数组种占绝大多数的元素（求第k小问题）
2. 第 N 个泰波那契数
题目描述：
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
代码：
class Solution {
public:
int tribonacci(int n) {
int a = 0, b = 1, c = 1, d;
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
while (n - 3 >= 0){
d = a + b + c;
a = b;
b = c;
c = d;
n--;
}
return d;
}
};
3. 字母板上的路径
题目描述：
我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。
在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"].
我们可以按下面的指令规则行动：
如果方格存在，'U' 意味着将我们的位置上移一行；
如果方格存在，'D' 意味着将我们的位置下移一行；
如果方格存在，'L' 意味着将我们的位置左移一列；
如果方格存在，'R' 意味着将我们的位置右移一列；
'!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。
返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。
示例 1：输入：target = "leet"
输出："DDR!UURRR!!DDD!"
示例 2：输入：target = "code"
输出："RR!DDRR!UUL!R!"提示：
1 <= target.length <= 100
target 仅含有小写英文字母。
解决思路：
正解：根据字母的字典大小判断在二维字典中的相对位置行走，注意到'z'时，需要回头。此处，我使用的是BFS+路径记录（复习）。
代码：
class Solution {
public:
struct Node{
int x, y, id, pre;
char op;
}nodes[50]; // 创建node数组，为了记录BFS路径
int X[4] = {-1, 1, 0, 0};
int Y[4] = {0, 0, -1, 1};
char cs[7][6] = {{'a', 'b', 'c', 'd', 'e'},{'f', 'g', 'h', 'i', 'j'},
{'k', 'l', 'm', 'n', 'o'}, {'p', 'q', 'r', 's', 't'}, {'u', 'v', 'w', 'x', 'y'}, {'z'}};
bool visited[7][6];
string res;
Node create(int x, int y, int id, int pre, char op){
nodes[id].id = id, nodes[id].x = x, nodes[id].y = y, nodes[id].pre = pre, nodes[id].op = op;
return nodes[id];
}
int BFS(int sx, int sy, char dest){
queue<Node> q;
while (!q.empty()) q.pop();
memset(visited, false, sizeof(visited));
memset(nodes, NULL, sizeof(nodes));
int index = 0;
q.push(create(sx, sy, index++, -1, ' '));
visited[sx][sy] = true;
while (!q.empty()){
Node node = q.front();
q.pop();
// printf("当前访问c(%d, %d)=%c,节点ID=%d\n",node.x, node.y, cs[node.x][node.y], node.id);
if (cs[node.x][node.y] == dest){
// nodes[node.id].op = '!';
return node.id;
}
for (int i = 0; i < 4; i++){
int newX = node.x + X[i];
int newY = node.y + Y[i];
if (newX < 0 || newX > 5 || newY < 0 || newY > 4 || visited[newX][newY] || (newX == 5 && newY > 0))
continue;
if (i == 0){
q.push(create(newX, newY, index++, node.id, 'U'));
}else if (i == 1){
q.push(create(newX, newY, index++, node.id, 'D'));
}else if (i == 2){
q.push(create(newX, newY, index++, node.id, 'L'));
}else{
q.push(create(newX, newY, index++, node.id, 'R'));
}
visited[newX][newY] = true;
}
}
return -1;
}
void printPath(int id){
if (id == -1) return;
printPath(nodes[id].pre); // 深度优先访问前驱节点
if (nodes[id].pre != -1)
res = res + nodes[id].op;
}
string alphabetBoardPath(string target) {
int x = 0, y = 0;
for (int i = 0; i < target.length(); i++){
int targetId = BFS(x, y, target[i]);
// printf("targetId= %d\n", targetId);
printPath(targetId);
res = res + '!';
// printf("suc2\n");
x = nodes[targetId].x;
y = nodes[targetId].y;
}
return res;
}
};
4. 最大的以 1 为边界的正方形
题目描述：
给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
示例 1：
输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9
示例 2：输入：grid = [[1,1,0,0]]
输出：1
解决思路：
穷举正方形边长判断即可。
代码：
class Solution {
public:
int largest1BorderedSquare(vector< vector<int> >& grid) {
int m = grid.size(), n = grid[0].size();
int MAX = 0;
for (int l = 1; l <= min(m, n); l++){
for (int i = 0; i < m - l + 1; i++){
for (int j = 0; j < n - l + 1; j++){
bool flag = true;
for (int k = i; k < i + l; k++){
if (grid[k][j] == 0){
flag = false;
break;
}
if (grid[k][j + l - 1] == 0){
flag = false;
break;
}
}
if (flag){
for (int k = j; k < j + l; k++){
if (grid[i][k] == 0){
flag = false;
break;
}
if (grid[i + l - 1][k] == 0){
flag = false;
break;
}
}
}
if (flag){
if (l * l > MAX) MAX = l * l;
}
}
}
}
return MAX;
}
};
4. 石子游戏 II
题目描述：
亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正>整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。
在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
游戏一直持续到所有石子都被拿走。
假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。
示例：
输入：piles = [2,7,9,4,4]
输出：10
解释：
如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。
如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。提示：
1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4
思路：
思路：
博弈题，动态规划求解，定义dp数组为当前玩家最优的拿石头策略。
因此，定义dp[i][j]表示从第i堆石头拿到第n堆石头、M=j时的最大拿石数量，
则当我从第i到第n堆石头堆里拿取k堆石头后，那么对手将在第i+k到n堆石头堆
里拿到最大的数量且j = max(j, k)，所以穷举k= 1, 2, ..., 2j，找出dp[i][j]的最大值。
状态转移方程为：
dp[i][j] = max(dp[i][j], sum[i~n] - dp[i + k][max(k, j)]), k = 1, 2, ..., 2j
逆序穷举i和j即可
代码：
class Solution {
public:
int sum(vector<int>& piles, int l, int r){
int s = 0;
for (int i = l; i <= r; i++)
s += piles[i];
return s;
}
int stoneGameII(vector<int>& piles) {
int dp[300][300];
memset(dp, 0, sizeof(dp));
int n = piles.size();
for (int i = n - 1; i >= 0; i--){
for (int j = n; j >= 1; j--){
for (int k = 1; k <= 2 * j; k++)
dp[i][j] = max(dp[i][j], sum(piles, i, n - 1) - dp[i + k][max(k, j)]);
}
}
return dp[0][1];
}
};
