解密消息
题目
思路
- 模拟，打标记即可。
代码
class Solution { public: string decodeMessage(string key, string message) { string res = ""; int n = key.size(); bool st[26] = {0}; map<char, int> mp; int now = 0; for (int i = 0; i < n; i++) { if(key[i] == ' ') continue; if(!st[key[i] - 'a']) { st[key[i] - 'a'] = true; mp[key[i]] = now; now ++; } } for (int i = 0; i < message.size(); i++) { if(message[i] == ' ') res += ' '; else { res += mp[message[i]] + 'a'; } } return res; } };
螺旋矩阵 IV
题目
思路
设定当前方向 n o w ，（0、1、2、3）对应方向数组 w a l k 。
设定上下左右（lx、rx、ly、ry）四个边界，在转向方向的时候进行调整。
代码
class Solution { public: vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) { vector<vector<int>> res(m, vector<int>(n, -1)); ListNode *p = head; if(p == nullptr) return res; vector<int> v; while(p) { v.push_back(p->val); p = p->next; } int x = 0, y = -1; int walk[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; int now = 0; int lx = 0, rx = m - 1, ly = 0, ry = n - 1; for (int i = 0; i < v.size(); i++) { int dx = x + walk[now][0], dy = y + walk[now][1]; if(dx > rx || dx < lx || dy > ry || dy < ly) { if(now == 0) lx += 1; if(now == 1) ry -= 1; if(now == 2) rx -= 1; if(now == 3) ly += 1; now = (now + 1) % 4; dx = x + walk[now][0], dy = y + walk[now][1]; } res[dx][dy] = v[i]; x = dx, y = dy; } return res; } };
知道秘密的人数
题目
思路
代码
class Solution { public: constexpr static int mod = 1e9 + 7; int peopleAwareOfSecret(int n, int delay, int forget) { map<int, int> mp; int res = 0; mp[1] = 1; for (int i = 2; i <= n; i++) { int cnt = 0; for (auto &x: mp) { int a = x.first, b = x.second; if(i >= a + forget) { mp.erase(a); continue; } if (i >= a + delay) cnt = (cnt + b) % mod; } mp.insert({i, cnt}); } for (auto &x: mp) res = (res + x.second) % mod; return res % mod; } };
网格图中递增路径的数目
题目
思路
记忆化搜素
考虑样例图解
3->4：1
1->3、1->3->4： 2
相邻能抵达，状态转移 dp[i][j]=dp[x][y]+1。
代码
class Solution { public: constexpr static int mod = 1e9 + 7; int n, m; int walk[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; int dfs(int x, int y, vector<vector<int>>& grid, vector<vector<int>>& dp) { int s = 0; for (int i = 0; i < 4; i++) { int dx = x + walk[i][0]; int dy = y + walk[i][1]; if(dx >= n || dx < 0 || dy >= m || dy < 0) continue; if(grid[x][y] >= grid[dx][dy]) continue; if(dp[dx][dy]) { s += dp[dx][dy] + 1; continue; } s += dfs(dx, dy, grid, dp) + 1; s %= mod; } dp[x][y] = (s + dp[x][y]) % mod; return dp[x][y]; } int countPaths(vector<vector<int>>& grid) { n = grid.size(), m = grid[0].size(); vector<vector<int>> dp(n, vector<int>(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if(!dp[i][j]) { dfs(i, j, grid, dp); } } } int res = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) res = (res + dp[i][j] + 1) % mod; return res; } };
