Leetcode

使用状态机思路解决一个并行问题。 题目可以描述为：进程A每轮循环产生一个 H，进程 B 每轮循环产生一个 O，需要保证每产生 3 个元素时都由 2 个 H 和 1 个 O 组成。 ...

记忆化搜索，刚好卡过去 执行用时：1964 ms, 在所有 C++ 提交中击败了 5.08% 的用户 int mem[100][100][100][100]; class Solution { public: // 0 unknow // 1 true // 2 false bool dfs(const vector<vector<char>>& grid, int x1, int y1, int x2, int y2) { if (x1 >= grid.size() || x2 >= grid.size() || y1>=grid[0].size() || y2 < 0 || x2 < 0 || x1 > x2 || y1 > y2) return false; if ((x2 - x1 + y2 - y1)%2==0) return false; if (mem[x1][y1][x2][y2] != 0) { return mem[x1][y1][x2][y2] == 1; } if ( x2 - x1 + y2 - y1 == 1 && grid[x1][y1] == '(' && grid[x2][y2] == ')') { mem[x1][y1][x2][y2] = 1; return true; } if (grid[x1][y1] == '(' && grid[x2][y2] == ')'){ bool tmp = dfs(grid, x1+1, y1, x2-1, y2) || dfs(grid, x1+1, y1, x2, y2-1) || dfs(grid, x1, y1+1, x2-1, y2) || dfs(grid, x1, y1+1, x2, y2-1); if (tmp) { mem[x1][y1][x2][y2] = 1; return true; } for (int i=x1; i<=x2; ++i) for (int j=y1; j<=y2; ++j) { if (i == x1 && j==y1) continue; if (i == x2 && j==y2) continue; if ((dfs(grid, x1, y1, i, j) && dfs(grid, i, j+1, x2, y2))) { mem[x1][y1][x2][y2] = 1; return true; } if (dfs(grid, x1, y1, i, j) && dfs(grid, i+1, j, x2, y2)) { mem[x1][y1][x2][y2] = 1; return true; } } mem[x1][y1][x2][y2] = 2; return false; } else { mem[x1][y1][x2][y2] = 2; return false; } } bool hasValidPath(vector<vector<char>>& grid) { int row = grid.size(); int col = grid[0].size(); if ((row + col)%2==0) return false; if ( grid[0][0] == ')' || grid[row - 1][col - 1] == '(') return false; memset(mem, 0, sizeof mem); return dfs(grid, 0, 0, row-1, col -1); } }; 题解里面有一个写法很好，可以学习一下 ...

爬楼梯的加强版本，分别提前生成三个字母和四个字母的 fib 数组，然后分组统计后相乘。代码如下： class Solution { public: int countTexts(string pressedKeys) { int f1[100005]; int f2[100005]; memset(f1, 0, sizeof f1); memset(f2, 0, sizeof f2); f1[0] = 1; f1[1] = 2; f1[2] = 4; f2[0] = 1; f2[1] = 2; f2[2] = 4; f2[3] = 8; for (int i=3; i<100005; ++i) f1[i] = (0LL + f1[i-1] + f1[i-2] + f1[i-3])%int(1e9+7); for (int i=4; i<100005; ++i) f2[i] = (0LL + f2[i-1] + f2[i-2] + f2[i-3] + f2[i-4])%int(1e9+7); int ans = 1; int cur_ch = pressedKeys[0]; int cur_cnt = 1; for (int i=1; i<pressedKeys.size(); ++i) { if (pressedKeys[i] != cur_ch) { if (cur_ch == '7' || cur_ch == '9') ans = 1LL *ans * f2[cur_cnt - 1] % int(1e9+7); else ans = 1LL *ans * f1[cur_cnt - 1] % int(1e9+7); cur_ch = pressedKeys[i]; cur_cnt = 1; } else { ++ cur_cnt; } } if (cur_ch == '7' || cur_ch == '9') ans = 1LL * ans * f2[cur_cnt - 1] % int(1e9+7); else ans = 1LL * ans * f1[cur_cnt - 1] % int(1e9+7); return ans; } };