专栏首页算法码上来【每日算法Day 63】LeetCode 第 179 场周赛题解

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

起床打开 leetcode,准备看看今天搞点啥题目水一水的,突然发现周赛还剩 1 小时整。看了眼题目也都挺简单的,就把 4 道题都做掉了。

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/

题解

如果某一个时刻灯都是蓝色的,等价于所有的亮灯都连续排列在数组最左边,没有间断。所以只需要判断当前时刻亮灯的最大编号是否等于亮灯的数量就行了。

比赛的时候傻 x 了,第一个想到的竟然是树状数组,于是直接把模板套过来过了。

代码(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) {
            add(light[i], 1);
            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/

题解

首先根据 数组来建图,边权就是父结点到子结点的通知时间。然后从根结点开始做 dfs ,求出根结点到每个叶子结点的路径长度的最大值。

代码(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);
            }
        }
        return f(headID, informTime);
    }
    
    int f(int headID, vector<int>& informTime) {
        if (!informTime[headID]) return 0;
        int maxx = 0;
        for (int i = 0, sz = G[headID].size(); i < sz; ++i) {
            maxx = max(maxx, f(G[headID][i], informTime));
        }
        return maxx+informTime[headID];
    }
};

LeetCode 5355. T 秒后青蛙的位置

题目链接

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

题解

首先建图,然后从 号结点开始,还是用 dfs 。每往下走一次,时间 减 。如果 或者到了叶子结点了,就判断结点是否为 ,是就返回 ,不是就返回 。每次概率除以当前结点的子结点个数,然后再乘上所有子结点 dfs 结果的最大值(因为结果不是 就是正确概率)。

代码(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;
    }
};

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

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

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

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

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

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

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

    java爱好者
  • 一遍记住Java常用的八种排序算法

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

    Java旅途
  • ICPC Asia Shenyang 2019 Dudu's maze

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

    用户2965768
  • LeetCode 第 210 场周赛 解题报告

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

    ACM算法日常
  • LeetCode 164. Maximum Gap (排序)

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

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

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

    风骨散人Chiam
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768

扫码关注云+社区

领取腾讯云代金券