Problem List
1. 解密消息
1.1 题目描述
给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下：
- 使用
key中26个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。 - 将替换表与普通英文字母表对齐，形成对照表。
- 按照对照表 替换
message中的每个字母。 - 空格
' '保持不变。
- 例如，key = “happy boy”（实际的加密密钥会包含字母表中每个字母 至少一次），据此，可以得到部分对照表（
'h' -> 'a'、'a' -> 'b'、'p' -> 'c'、'y' -> 'd'、'b' -> 'e'、'o' -> 'f'）。
返回解密后的消息。
示例1：
输入： key = “the quick brown fox jumps over the lazy dog”, message = “vkbs bs t suepuv”
输出： “this is a secret”
解释： 对照表如上图所示。
提取 “the quick brown fox jumps over the lazy dog” 中每个字母的首次出现可以得到替换表。示例2：
输入： key = “eljuxhpwnyrdgtqkviszcfmabo”, message = “zwx hnfx lqantp mnoeius ycgk vcnjrdb”
输出： “the five boxing wizards jump quickly”
解释： 对照表如上图所示。
提取 “eljuxhpwnyrdgtqkviszcfmabo” 中每个字母的首次出现可以得到替换表。
1.2 思路
用哈希表存储key中字符和字母表的字符的映射，然后遍历message中的字符串，将其中的字符用前边的映射对应的字符代替即可。
class Solution {
public:
string decodeMessage(string key, string message) {
unordered_map<char, char> m;
char ch = 'a';
for(char c: key) {
if(c != ' ' && m.count(c) == 0) {
m[c] = ch;
ch++;
}
}
string res = "";
for(char c: message){
if(c != ' ') {
res += m[c];
continue;
}
res += c;
}
return res;
}
}; 2. 螺旋矩阵 IV
2.1 题目描述
给你两个整数：m 和 n ，表示矩阵的维数。
另给你一个整数链表的头节点 head 。
请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按 螺旋 顺序填充。如果还存在剩余的空格，则用 -1 填充。
返回生成的矩阵。
示例1：
输入： m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
输出： [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
解释： 上图展示了链表中的整数在矩阵中是如何排布的。
注意，矩阵中剩下的空格用 -1 填充。
示例2：
输入： m = 1, n = 4, head = [0,1,2]
输出： [[0,1,2,-1]]
解释： 上图展示了链表中的整数在矩阵中是如何从左到右排布的。
注意，矩阵中剩下的空格用 -1 填充。
2.2 思路
直接模拟即可，初始化答案为-1，当遍历完链表后直接返回结果，此时如果有空余的位置就已经是-1了。
class Solution {
public:
vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
vector<vector<int>> ret(m, vector<int>(n, -1));
ListNode* cur = head;
int r = -1, c = -1, up = 0, low = m, left = 0, right = n;
while(cur) {
for(++r, ++c; c < right; ++c) {
ret[r][c] = cur->val;
cur = cur->next;
if(!cur) return ret;
}
right--;
for(c--, r++; r < low; ++r) {
ret[r][c] = cur->val;
cur = cur->next;
if(!cur) return ret;
}
low--;
for(c--, r--; c >= left; --c) {
ret[r][c] = cur->val;
cur = cur->next;
if(!cur) return ret;
}
left++;
for(++c, --r; r > up; r--) {
ret[r][c] = cur->val;
cur = cur->next;
if(!cur) return ret;
}
up++;
}
return ret;
}
};可以把链表的移动和判断写在for里边：
class Solution { public: vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) { vector<vector<int>> ret(m, vector<int>(n, -1)); ListNode* cur = head; int r = -1, c = -1, up = -1, low = m, left = 0, right = n; while(cur) { for(++up, ++r, ++c; c < right && cur; ++c, cur = cur->next) { ret[r][c] = cur->val; } for(--right, --c, ++r; r < low && cur; ++r, cur = cur->next) { ret[r][c] = cur->val; } for(--low, --c, --r; c >= left && cur; --c, cur = cur->next) { ret[r][c] = cur->val; } for(++left, ++c, --r; r > up && cur; --r, cur = cur->next) { ret[r][c] = cur->val; } } return ret; } };另一种写法
class Solution {
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
public:
vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
vector<vector<int>> ret(m, vector<int>(n, -1));
ListNode* cur = head;
int i = 0, j = 0, D = 0;
while(cur) {
ret[i][j] = cur->val;
cur = cur->next;
while(cur) {
int ii = i + dir[D][0], jj = j + dir[D][1];
if(ii < 0 || ii >= m || jj < 0 || jj >= n || ret[ii][jj] > 0) {
D = (D+1) % 4;
}else {
i = ii;
j = jj;
break;
}
}
}
return ret;
}
};- 第三种写法：按层写
class Solution {
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
public:
vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
vector<vector<int>> ret(m, vector<int>(n, -1));
ListNode* cur = head;
int left = 0, right = n-1, top = 0, low = m-1;
while(cur) {
for(int i = left; i <= right && cur; ++i, cur = cur->next) {
ret[top][i] = cur->val;
}
for(int i = top+1; i <= low && cur; ++i, cur = cur->next) {
ret[i][right] = cur->val;
}
//if(left < right && top < low) {
for(int i = right - 1; i >= left && cur; --i, cur = cur->next) {
ret[low][i] = cur->val;
}
for(int i = low-1; i > top && cur; --i, cur = cur->next) {
ret[i][left] = cur->val;
}
// }
//if(top < low) {
//}
left++;
right--;
top++;
low--;
}
return ret;
}
}; 3. 知道秘密的人数
3.1 题目描述
在第 1 天，有一个人发现了一个秘密。
给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。
给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 1e9 + 7 取余 后返回。
示例1：
输入： n = 6, delay = 2, forget = 4
输出： 5
解释： 第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）
示例2：
输入： n = 4, delay = 1, forget = 3
输出： 6
解释： 第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）
3.2 思路
跟之前在牛客上刷到的兔子数量思路一致，只是这道题加了个边界条件，就是当索引(从1开始计算)超过forget之后的数量就不算在结果中。那么，我们可以创建一个数组，大小为forget，下标为i表征知道了秘密i天的人数，然后进入下一天的时候就把数组中的前一位赋给其后边的那一位，知道秘密天数大于delay的人可以告诉新的人，即delay~forget范围内的加和就是当天刚知道秘密的人数；而超过forget的人，由于数组大小只有forget，那么超过forget的人已经被滤除了。最后返回整个数组的加和即可。
class Solution {
int mod = 1e9 + 7;
void handle(vector<int>& f, int n, int delay, int size) {
if(n == 0) return;
int sum = 0;
for(int i = size-1; i > 0; --i) {
f[i] = f[i-1];
if(i > delay -1) sum += f[i], sum %= mod;
}
f[0] = sum;
handle(f, n-1, delay, size);
}
public:
int peopleAwareOfSecret(int n, int delay, int forget) {
vector<int> f(forget, 0);
f[0] = 1;
handle(f, n-1, delay, forget);
int ans = 0;
for(int i = 0; i < forget; ++i) ans += f[i], ans %= mod;
return ans;
}
};
