讨论/题目交流/🏆 第 179 场力扣周赛/
🏆 第 179 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 生成每种字符都是奇数个的字符串
4 分 - 灯泡开关 III
5 分 - 通知所有员工所需的时间
6 分 - T 秒后青蛙的位置

展开讨论

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

思路

  1. 没有规定是啥字母
  2. 奇数就全是 1 种字母
  3. 偶数就补一个其他字母

答题

string generateTheString(int n) 
{
    string ans = (n % 2 == 0) ? "a" : "";
    n -= (n % 2 == 0);
    for (int i = 0; i < n; i++)
    {
        ans += "b";
    }
    return ans;
}

灯泡开关 III

思路

  1. 只有其左侧所有灯都亮,这个灯才会变蓝
  2. 求的是所有灯全都变蓝的情况
  3. 那么就是说,这个情况应该是从头开始的灯,全部连续的亮着
  4. 因为灯是一个一个打开的
  5. 那么当一个灯打开的时候,我们知道最右边的灯是哪个,也知道开的是第几个灯
  6. 只需要判断相等即可

答题

int numTimesAllBlue(vector<int>& light) 
{
    int ans = 0;
    int cnt = 0;
    int mx = 0;
    for (auto& n : light)
    {
        mx = max(mx, n);
        cnt++;
        ans += (mx == cnt);
    }
    return ans;
}

通知所有员工所需的时间

思路

  1. 需要先将“我的领导是谁”这张数据表转换成“我是领导,我手下有谁谁谁”这样的表
  2. 这样就可以一层一层往下找了
  3. 那么用 bfs 还是 dfs
  4. 考虑到一种情况,0 手下 1 和 2 , 1 的时间是 1s ,而 2 的时间是 2s 。从此之后再下级的时间就不一样了。
  5. 使用 bfs 处理上会更麻烦一点
  6. 所以使用 dfs

答题

void dfs(vector<vector<int>>& mana, vector<int>& informTime, int id, int time, int& ans)
{
    time += informTime[id];
    if (mana[id].empty())
    {
        ans = max(ans, time);
        return;
    }
    for (auto& next : mana[id])
    {
        dfs(mana, informTime, next, time, ans);
    }
}

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

    int ans = 0;
    dfs(mana, informTime, headID, 0, ans);
    return ans;
}

T 秒后青蛙的位置

// TODO:

致谢

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

我的leetcode

3
展开全部 25 讨论