生成每种字符都是奇数个的字符串
假设 n = 5，返回长度为 5 的字符串，保证返回的每个字符都出现奇数次，返回 5 个 a 即可或者返回 abcde 也可以
n = 4，返回 aaab
n 是奇数，返回 n 个 a
n 是偶数，返回 n - 1 个 a，1 个 b，不管是 a 还是 b 都有奇数个
class Solution {
public:
string generateTheString(int n) {
string res;
//如果 n是偶数
if(n % 2 == 0) res += 'b',n--;
// n一定是奇数
while(n--) res += 'a';
return res;
}
};二进制字符串前缀一致的次数
?
?
给出一个二进制字符串编号是 1 ~ n，最初这个字符串的所有位上都是 0
按给定的顺序 flips，从第 0 时刻 ~ 第 n - 1 时刻依次把 当前时刻下对应字符串的位置的值 变成 1
前缀一致需要满足自身的值是 1 并且它左边的所有位的值都是 1； 如果自身是1，中间某个位置出现 0，就不满足前缀一致的情况
前缀一致说明满足当前位置到左边连续的一段都是 1
flips 数组是 1 ~ n 的排列，数据为 1 ~ n 且所有数互不相同
从前往后扫描所有变成 1 的编号，判断哪些时刻变成 1 的编号是从 1 开始的连续的一段(从前往后遍历 flips 数组，如何判断数组的哪些前缀构成了从 1 开始的连续的一段)
2????????1????????3????????5????????4
2??????? ×
1??????? 2??????? √
1??????? 2??????? 3??????? √
1??????? 2??????? 3??????? 5 ?????? ×
1??????? 2??????? 3??????? 4??????? 5??????? √
从前往后遍历数组，记录当前 flips 数组中的最大值，如果最大值是 k，并且已经扫描了 k 个数(意味着有 k 个互不相同的数)，说明前 k 个数必然是 1 ~ k
当前最大值 == 扫描数组的个数 == 下标 + 1→ 满足要求的时刻
????????????????2??????? 1??????? 3??????? 5????? ? 4
最大值???? 2???????? 2?????? 3???????? 5??????? 5
扫描个数 1???????? 2?????? 3???????? 4??????? 5
因此满足要求的一共有 3 个时刻
class Solution {
public:
int numTimesAllBlue(vector<int>& flips) {
//定义答案 | 记录最大值
int res = 0,k = 0;
//从前往后扫描每一个数
for(int i = 0;i < flips.size();i++){
//让k取最大值
k = max(k,flips[i]);
//k == i + 1说明有一个满足要求的时刻
if(k == i + 1) res++;
}
return res;
}
};通知所有员工所需的时间
?
?
n 名员工的 ID 是独一无二的，编号是 0 ~ n - 1
每一个点只有唯 一 一 个父节点，树结构
把 headID 看成根节点，除了根节点之外，其他所有节点都有一个父节点
从根节点往下发通知，分发通知可以看成是并行的过程，用 informTime1 的时间通知他所有的下属，过了 informTime1 时间后同一层的所有子节点会同时收到信息，收到信息后，再有一个 informTime2 的时间通知他们的所有的下属，如果没有下属就不用考虑，问通知完整个公司的所有员工一共需要多长时间？
通知需要的总时间取决于最晚通知到的员工，问从根节点开始走到所有叶子节点的距离的最长值
所有叶子节点的 informTime 是 0
示例2：只有一个主管，其他都是下属，这个主管通知他的所有员工所需要的时间是 1 分钟，所以总时间是 1 分钟
求最长路径 DFS
求当前点走到叶子节点一共要走多远，当前点往两个孩子节点走，走到底，得到的的最大值：孩子节点走到底的最大值? + 当前点的权值，回溯到根的时候，根的最大值就是要求的答案
存储图，需要找到每一个点所有的子节点，用邻接表的方式存储图：1.数组模拟邻接表? 2.二维vector存储图，变长数组 √
数据比较大，不能用邻接矩阵存储
class Solution {
public:
//存储所有的子节点
vector<vector<int>> son;
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
son = vector<vector<int>>(n);
//遍历整个数组
for(int i = 0;i < n;i++){
//i不等于根节点
if(i != headID){
//存储从根节点走到当前点的路径
son[manager[i]].push_back(i);
}
}
return dfs(headID,informTime);
}
//当前节点
int dfs(int u,vector<int>& informTime){
int res = 0;
//遍历所有的子节点
for(auto s: son[u]) res = max(res,dfs(s,informTime));
//加上从当前点传递到子节点的时间
return res + informTime[u];
}
};T秒后青蛙的位置
