# 【每日算法Day 63】LeetCode 第 179 场周赛题解

## LeetCode 5352. 生成每种字符都是奇数个的字符串

### 题目链接

https://leetcode-cn.com/problems/generate-a-string-with-characters-that-have-odd-counts/

### 代码（python）

```class Solution:
def generateTheString(self, n: int) -> str:
if n % 2 == 0:
return "a"+"b"*(n-1)
return "a"*n```

## LeetCode 5353. 灯泡开关 III

### 题目链接

https://leetcode-cn.com/problems/bulb-switcher-iii/

### 代码（c++）

```class Solution {
public:
int numTimesAllBlue(vector<int>& light) {
int res = 0, maxx = 0;
for (int i = 0, sz = light.size(); i < sz; ++i) {
maxx = max(maxx, light[i]);
if (maxx == i + 1) res++;
}
return res;
}
};```

```class Solution {
public:
static const int MAXN = 50010;
int bit[MAXN];

int numTimesAllBlue(vector<int>& light) {
memset(bit, 0, sizeof bit);
int maxx = 0, res = 0;
for (int i = 0, sz = light.size(); i < sz; ++i) {
maxx = max(maxx, light[i]);
if (sum(maxx) == maxx) res++;
}
return res;
}

int lowbit(int x) {
return x&(-x);
}

void add(int i, int x) {
while (i < MAXN) {
bit[i] += x;
i += lowbit(i);
}
}

void sub(int i, int x) {
while (i < MAXN) {
bit[i] -= x;
i += lowbit(i);
}
}

int sum(int i) {
int s = 0;
while (i > 0) {
s += bit[i];
i -= lowbit(i);
}
return s;
}
};```

## LeetCode 5354. 通知所有员工所需的时间

### 题目链接

https://leetcode-cn.com/problems/time-needed-to-inform-all-employees/

### 代码（c++）

```class Solution {
public:
static const int N = 100010;
vector<int> G[N];

int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
for (int i = 0; i < n; ++i) {
if (manager[i] != -1) {
G[manager[i]].push_back(i);
}
}
}

int f(int headID, vector<int>& informTime) {
int maxx = 0;
for (int i = 0, sz = G[headID].size(); i < sz; ++i) {
}
}
};```

## LeetCode 5355. T 秒后青蛙的位置

### 题目链接

https://leetcode-cn.com/problems/frog-position-after-t-seconds/

### 代码（c++）

```class Solution {
public:
double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
if (n == 1) return 1.0;
vector<vector<int>> G(110);
for (int i = 0; i < n-1; ++i) {
int u = edges[i][0], v = edges[i][1];
G[u].push_back(v);
G[v].push_back(u);
}
return dfs(1, 0, t, target, G);
}

double dfs(int u, int fa, int t, int target, vector<vector<int>>& G) {
int sz = G[u].size();
if (!t || (fa && sz == 1)) {
if (u == target) return 1;
else return 0;
}
double p = 1.0 / (fa ? sz-1 : sz), maxx = 0;
for (int i = 0, sz = G[u].size(); i < sz; ++i) {
int v = G[u][i];
if (v == fa) continue;
maxx = max(maxx, dfs(v, u, t-1, target, G));
}
return p*maxx;
}
};```

0 条评论

• ### 每日算法系列【EOJ 3031】二进制倒置

给定一个整数 、将 的 334 位二进制表示形式（不包括开头可能的值为 0 的位， 表示为 1 位 0）前后倒置，输出倒置后的二进制数对应的整数。

• ### 【每日算法Day 94】经典面试题：机器人的运动范围

地上有一个 m 行 n 列的方格，从坐标 [0, 0] 到坐标 [m-1, n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、...

• ### 【每日算法Day 77】LeetCode 第 181 场周赛题解

https://leetcode-cn.com/contest/weekly-contest-181

• ### 一遍记住Java常用的八种排序算法与代码实现

对Java技术，架构技术感兴趣的同学，欢迎加QQ群668041364，一起学习，相互讨论。 群内已经有小伙伴将知识体系整理好（源码，笔记，PPT，学习视频），欢...

• ### 一遍记住Java常用的八种排序算法

(如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序。)

• ### ICPC Asia Shenyang 2019 Dudu's maze

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

• ### LeetCode 第 210 场周赛 解题报告

那么在遍历过程中，栈中元素数量的最大值即为答案。栈中的(可以理解为还没遍历到匹配的)，即那些嵌套的(。

• ### LeetCode 164. Maximum Gap (排序)

题解：首先，当然我们可以用快排，排完序之后，遍历一遍数组，就能得到答案了。但是快速排序的效率是O(n* logn)，不是题目要求的线性效率，也就是O(n)的效率...

• ### 图论--拓扑排序--判断一个图能否被拓扑排序

拓扑排序的实现条件，以及结合应用场景，我们都能得到拓扑排序适用于DAG图（Directed Acyclic Graph简称DAG）有向无环图， 根据关系我们能得...

• ### Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心，构造，线段树，树的子树

Educational Codeforces Round 67 (Rated for Div. 2)