LeetCode 5352. 生成每种字符都是奇数个的字符串
题目链接
https://leetcode-cn.com/problems/generate-a-string-with-characters-that-have-odd-counts/
题解
代码（python）
classSolution: defgenerateTheString(self, n: int) ->str: ifn%2==0: return"a"+"b"*(n-1) return"a"*n
LeetCode 5353. 灯泡开关 III
题目链接
https://leetcode-cn.com/problems/bulb-switcher-iii/
题解
如果某一个时刻灯都是蓝色的，等价于所有的亮灯都连续排列在数组最左边，没有间断。所以只需要判断当前时刻亮灯的最大编号是否等于亮灯的数量就行了。
比赛的时候傻 x 了，第一个想到的竟然是树状数组，于是直接把模板套过来过了。
代码（c++）
classSolution { public: intnumTimesAllBlue(vector<int>&light) { intres=0, maxx=0; for (inti=0, sz=light.size(); i<sz; ++i) { maxx=max(maxx, light[i]); if (maxx==i+1) res++; } returnres; } };
树状数组：
classSolution { public: staticconstintMAXN=50010; intbit[MAXN]; intnumTimesAllBlue(vector<int>&light) { memset(bit, 0, sizeofbit); intmaxx=0, res=0; for (inti=0, sz=light.size(); i<sz; ++i) { add(light[i], 1); maxx=max(maxx, light[i]); if (sum(maxx) ==maxx) res++; } returnres; } intlowbit(intx) { returnx&(-x); } voidadd(inti, intx) { while (i<MAXN) { bit[i] +=x; i+=lowbit(i); } } voidsub(inti, intx) { while (i<MAXN) { bit[i] -=x; i+=lowbit(i); } } intsum(inti) { ints=0; while (i>0) { s+=bit[i]; i-=lowbit(i); } returns; } };
LeetCode 5354. 通知所有员工所需的时间
题目链接
https://leetcode-cn.com/problems/time-needed-to-inform-all-employees/
题解
代码（c++）
classSolution { public: staticconstintN=100010; vector<int>G[N]; intnumOfMinutes(intn, intheadID, vector<int>&manager, vector<int>&informTime) { for (inti=0; i<n; ++i) { if (manager[i] !=-1) { G[manager[i]].push_back(i); } } returnf(headID, informTime); } intf(intheadID, vector<int>&informTime) { if (!informTime[headID]) return0; intmaxx=0; for (inti=0, sz=G[headID].size(); i<sz; ++i) { maxx=max(maxx, f(G[headID][i], informTime)); } returnmaxx+informTime[headID]; } };
LeetCode 5355. T 秒后青蛙的位置
题目链接
https://leetcode-cn.com/problems/frog-position-after-t-seconds/
题解
代码（c++）
classSolution { public: doublefrogPosition(intn, vector<vector<int>>&edges, intt, inttarget) { if (n==1) return1.0; vector<vector<int>>G(110); for (inti=0; i<n-1; ++i) { intu=edges[i][0], v=edges[i][1]; G[u].push_back(v); G[v].push_back(u); } returndfs(1, 0, t, target, G); } doubledfs(intu, intfa, intt, inttarget, vector<vector<int>>&G) { intsz=G[u].size(); if (!t|| (fa&&sz==1)) { if (u==target) return1; elsereturn0; } doublep=1.0/ (fa?sz-1 : sz), maxx=0; for (inti=0, sz=G[u].size(); i<sz; ++i) { intv=G[u][i]; if (v==fa) continue; maxx=max(maxx, dfs(v, u, t-1, target, G)); } returnp*maxx; } };
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
