周赛 – 179

1. 生成每种字符都是奇数个的字符串

给你一个整数 n,请你返回一个含 n 个字符的字符串,其中每种字符在该字符串中都恰好出现 奇数次
返回的字符串必须只含小写英文字母。如果存在多个满足题目要求的字符串,则返回其中任意一个即可。

样例

示例 1:

输入:n = 4
输出:”pppz”
解释:”pppz” 是一个满足题目要求的字符串,因为 ‘p’ 出现 3 次,且 ‘z’ 出现 1 次。当然,还有很多其他字符串也满足题目要求,比如:”ohhh” 和 “love”。

示例 2:

输入:n = 2
输出:”xy”
解释:”xy” 是一个满足题目要求的字符串,因为 ‘x’ 和 ‘y’ 各出现 1 次。当然,还有很多其他字符串也满足题目要求,比如:”ag” 和 “ur”。

示例 3:

输入:n = 7
输出:”holasss”

提示

  • 1 <= n <= 500

代码

viv丑陋版

我一开始居然还想着用26个字母,我是猪。
如果字母数$n$是奇数,则用一个字母从头写到尾;否则,输出一次一个字母,其余的都输出另一个字母。

class Solution {
public:
    string generateTheString(int n) {
        string ans = "";
        if(n & 1) {
            for(int i=0; i<n; i++) ans += 'a';
        }
        else {
            ans += 'a';
            for(int i=1; i<n; i++) ans += 'b';
        }
        return ans;
    }
};

zz美丽版

zz写的稍微比我简单一些吧……但是我有理由怀疑他在秀恩爱……

class Solution {
public:
    string generateTheString(int n) {
        string ret = "";
        if (n % 2 == 0) ret = 'z', --n;
        for (int i = 0; i < n; i++) ret += 'w';
        return ret;
    }
};

2. 灯泡开关 III

房间中有 n 枚灯泡,编号从 1 到 n,自左向右排成一排。最初,所有的灯都是关着的。
k 时刻( k 的取值范围是 0 到 n – 1),我们打开 light[k] 这个灯。
灯的颜色要想 变成蓝色 就必须同时满足下面两个条件:

  • 灯处于打开状态。
  • 排在它之前(左侧)的所有灯也都处于打开状态。
    请返回能够让 所有开着的 灯都 变成蓝色 的时刻 数目

样例

示例 1:

输入:light = [2,1,3,5,4]
输出:3
解释:所有开着的灯都变蓝的时刻分别是 1,2 和 4 。

示例 2:

输入:light = [3,2,4,1,5]
输出:2
解释:所有开着的灯都变蓝的时刻分别是 3 和 4(index-0)。

示例 3:

输入:light = [4,1,2,3]
输出:1
解释:所有开着的灯都变蓝的时刻是 3(index-0)。
第 4 个灯在时刻 3 变蓝。

示例 4:

输入:light = [2,1,4,3,6,5]
输出:3

示例 5:

输入:light = [1,2,3,4,5,6]
输出:6

代码

viv丑陋版

当前打开的灯的编号最大值等于已经打开灯的数目,则是满足条件的一次变蓝。
直接用优先队列实现,每一次比当前编号是否等于已经打开灯的数量。

class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        priority_queue<int> que;
        int n = light.size(), ans = 0;
        for(int i=0; i<n; i++) {
            que.push(light[i]);
            if(que.top() == i+1) ans++;
        }
        return ans;
    }
};

zz美丽版

嗯,我觉得最近真的可以把个别题改成viv美丽版和zz丑陋版了。
zz用的并查集
每次打开一盏灯,将其与左边开着的灯和右边开着的灯连起来。判断1号灯是否开着且1号灯的父节点是否为当前节点,记录答案。

const int MAXN = 5e4 + 50;
int fa[MAXN], op[MAXN];
int getFather(int x){
    return fa[x] = (fa[x] == x ? x : getFather(fa[x]));
}

class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int n = light.size();
        
        int cur = 0, ans = 0;
        for (int i = 1; i <= n; i++) fa[i] = i, op[i] = 0;
        
        for (int i = 0; i < n; i++){
            int k = light[i];
            op[k] = 1;
            if (k > 1 && op[k - 1] == 1) fa[k - 1] = k;
            if (k + 1 <= n && op[k + 1] == 1) fa[k] = k + 1;
            
            cur += 1;
            
            if (op[1] == 1 && getFather(1) == cur) ++ans;
        }
        
        return ans;
    }
};

3. 通知所有员工所需的时间

公司里有 n 名员工,每个员工的 ID 都是独一无二的,编号从 0 到 n – 1。公司的总负责人通过 headID 进行标识。
在 manager 数组中,每个员工都有一个直属负责人,其中 manager[i] 是第 i 名员工的直属负责人。对于总负责人,manager[headID] = -1。题目保证从属关系可以用树结构显示。
公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们,然后由这些下属通知他们的下属,直到所有的员工都得知这条紧急消息。
第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属(也就是说在 informTime[i] 分钟后,他的所有直属下属都可以开始传播这一消息)。
返回通知所有员工这一紧急消息所需要的 分钟数

样例

示例 1:

输入:n = 1, headID = 0, manager = [-1], informTime = [0]
输出:0
解释:公司总负责人是该公司的唯一一名员工。

示例 2:

输入:n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
输出:1
解释:id = 2 的员工是公司的总负责人,也是其他所有员工的直属负责人,他需要 1 分钟来通知所有员工。
上图显示了公司员工的树结构。

示例 3:

输入:n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]
输出:21
解释:总负责人 id = 6。他将在 1 分钟内通知 id = 5 的员工。
id = 5 的员工将在 2 分钟内通知 id = 4 的员工。
id = 4 的员工将在 3 分钟内通知 id = 3 的员工。
id = 3 的员工将在 4 分钟内通知 id = 2 的员工。
id = 2 的员工将在 5 分钟内通知 id = 1 的员工。
id = 1 的员工将在 6 分钟内通知 id = 0 的员工。
所需时间 = 1 + 2 + 3 + 4 + 5 + 6 = 21 。

示例 4:

输入:n = 15, headID = 0, manager = [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6], informTime = [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0]
输出:3
解释:第一分钟总负责人通知员工 1 和 2 。
第二分钟他们将会通知员工 3, 4, 5 和 6 。
第三分钟他们将会通知剩下的员工。

示例 5:

输入:n = 4, headID = 2, manager = [3,3,-1,2], informTime = [0,0,162,914]
输出:1076

提示

  • 1 <= n <= 10^5
  • 0 <= headID < n
  • manager.length == n
  • 0 <= manager[i] < n
  • manager[headID] == -1
  • informTime.length == n
  • 0 <= informTime[i] <= 1000
  • 如果员工 i 没有下属,informTime[i] == 0 。
  • 题目 保证 所有员工都可以收到通知。

代码

viv丑陋版

我感觉我这题写的巨烦,但是大抵还是有一些进步的,至少写暴力也能把题写出来qwq(自恋ING…)。
根据题目要求用链式前向星建一张有向图,并记录一下根节点。
然后从根节点开始dfs,dfs过程中记录当前路径长度,然后用一个全局变量$ans$获取路径长度的最大值。

const int MAXN = 1e5 + 5;
struct Edge {
    int to, w, nxt;
} edge[MAXN];
int head[MAXN], cnt, ans;

class Solution {
public:
    void init() {
        memset(head, -1, sizeof(head));
        cnt = 0; ans = 0;
    }
    void add(int u, int v, int w) {
        edge[cnt].to = v;
        edge[cnt].w = w;
        edge[cnt].nxt = head[u];
        head[u] = cnt++;
    }
    void dfs(int root, int now) {
        for(int i=head[root]; i!=-1; i=edge[i].nxt) {
            dfs(edge[i].to, now+edge[i].w);
        }
        ans = max(ans, now);
    }
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        init();
        int root;
        for(int i=0; i<n; i++) {
            if(manager[i] == -1) root = i;
            else add(manager[i], i, informTime[manager[i]]);
        }
        dfs(root, 0);
        return ans;
    }
};

zz美丽版

思路也是一样的,不过zz是从根节点开始BFS,而我是dfs。

const int MAXN = 1e5 + 50;
int dist[MAXN];
vector<int> edge[MAXN];

class Solution {
public:
    int ans = 0;
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        ans = 0;
        for (int i = 0; i < n; i++) dist[i] = 0, edge[i].clear();
        for (int i = 0; i < n; i++)
            if (manager[i] != -1) edge[manager[i]].push_back(i);
        queue<int> que;
        que.push(headID); dist[headID] = 0;
        
        while(!que.empty()){
            int x = que.front(); que.pop();
            ans = max(ans, dist[x]);
            
            for (auto v: edge[x]){
                dist[v] = dist[x] + informTime[x];
                que.push(v);
            }
        }
        
        return ans;
    }
};

4. T 秒后青蛙的位置

给你一棵由 n 个顶点组成的无向树,顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规则如下:
在一秒内,青蛙从它所在的当前顶点跳到另一个 未访问 过的顶点(如果它们直接相连)。
青蛙无法跳回已经访问过的顶点。
如果青蛙可以跳到多个不同顶点,那么它跳到其中任意一个顶点上的机率都相同。
如果青蛙不能跳到任何未访问过的顶点上,那么它每次跳跃都会停留在原地。
无向树的边用数组 edges 描述,其中 edges[i] = [from_i, to_i] 意味着存在一条直接连通 from_i 和 to_i 两个顶点的边。
返回青蛙在 t 秒后位于目标顶点 target 上的概率。

样例

示例 1:

输入:n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
输出:0.16666666666666666
解释:上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳,第 1 秒 有 1/3 的概率跳到顶点 2 ,然后第 2 秒 有 1/2 的概率跳到顶点 4,因此青蛙在 2 秒后位于顶点 4 的概率是 1/3 * 1/2 = 1/6 = 0.16666666666666666 。

示例 2:

输入:n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
输出:0.3333333333333333
解释:上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳,有 1/3 = 0.3333333333333333 的概率能够 1 秒 后跳到顶点 7 。

示例 3:

输入:n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
输出:0.16666666666666666

提示

  • 1 <= n <= 100
  • edges.length == n-1
  • edges[i].length == 2
  • 1 <= edgesi, edgesi <= n
  • 1 <= t <= 50
  • 1 <= target <= n
  • 与准确值误差在 10^-5 之内的结果将被判定为正确。

代码

viv丑陋版

看到题我以为是概率DP,然后发现这题我写的和上一题一样,把树遍历一遍就差不多了qwq。
首先建图,然后从点1开始遍历。统计每个节点的下一步有几个选择,就将当前概率除以几继续dfs下去。
如果t已经为0并还没有到达target,则无法到达;否则,如果能到达target且没有多余的时间或者有多余的时间但没有下一步可以走,记录答案。

const int MAXN = 1e5 + 5;
struct Edge {
    int to, nxt;
} edge[MAXN];
int head[MAXN], cnt;
double ans;

class Solution {
public:
    void init() {
        memset(head, -1, sizeof(head));
        cnt = 0; ans = 0.0;
    }
    void add(int u, int v) {
        edge[cnt].to = v;
        edge[cnt].nxt = head[u];
        head[u] = cnt++;
    }
    void dfs(int root, double now, int target, int t, int fa) {
        if(root == target) {
            int cnt0 = 0;
            for(int i=head[root]; i!=-1; i=edge[i].nxt) if(fa != edge[i].to) cnt0++;
            if(cnt0 > 0 && t > 0) ans = 0;
            else ans = now;
            return;
        }
        if(t == 0 && root != target) return;
     
        int cnt = 0;
        for(int i=head[root]; i!=-1; i=edge[i].nxt) if(fa != edge[i].to) cnt++;
        for(int i=head[root]; i!=-1; i=edge[i].nxt) {
            if(fa == edge[i].to) continue;
            dfs(edge[i].to, now / cnt, target, t-1, root);
        }
    }
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        init();
        for(auto e: edges) {
            add(e[0], e[1]);
            add(e[1], e[0]);
        }
        dfs(1, 1.0, target, t, -1);
        return ans;
    }
};

zz美丽版

好吧这道题可以理解为DP,只不过过于简单了……
其实就是有根树上父节点向子节点传播概率。$dp[i][j]$表示青蛙在$j$时间在第$i$个顶点上停留的概率。

const int MAXN = 100 + 50;
double dp[MAXN][55];
vector<int> edge[MAXN];

class Solution {
public:
    
    void dfs(int x, int f, int T){
        int cnt = 0;
        for (auto v: edge[x]){
            if (f == v) continue;
            ++cnt;
        }
        
        if (cnt == 0)
            dp[x][T] += dp[x][T - 1];
        
        for (auto v: edge[x]){
            if (f == v) continue;
            // printf("%d - %d\n", x, v);
            dp[v][T] += 1. * dp[x][T - 1] / cnt;
            // printf("%d %d = %f\n", v, T, dp[v][T]);
            dfs(v, x, T);
        }
        
    }
    
    double frogPosition(int n, vector<vector<int>>& edges, int T, int target) {
        for (int i = 1; i <= n; i++)
            for (int k = 0; k <= T; k++)
                dp[i][k] = 0;
        dp[1][0] = 1.0;
        
        for (int i = 1; i <= n; i++) edge[i].clear();
        for (auto e: edges){
            edge[e[0]].push_back(e[1]);
            edge[e[1]].push_back(e[0]);
        }
        
        for (int i = 1; i <= T; i++)
            dfs(1, 0, i);
        
        return dp[target][T];
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇