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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2020-03-08
共 25 个讨论

写了简单的爬虫,发现:

code of xiaoyu-46,san-ming-zi are same at problem 4
code of seaskylwl,chaoliu_lc are same at problem 3
code of seaskylwl,chaoliu_lc are same at problem 2
code of xiaoyu-46,san-ming-zi are same at problem 2
code of da-wu-wei-2,chong-ru-bu-liang-3 are same at problem 1
code of faris9527,zhangzhen024 are same at problem 1
code of goodfellow-2,liyaogogogo are same at problem 1
code of wiper,che820 are same at problem 1
code of wuqing-array,carter_ron are same at problem 1
code of ThomasCTR,everfight are same at problem 1
code of raolongjiang,deng-dai-38,muwen,wu-yi-41 are same at problem 1
code of jerry_nju,ewbar are same at problem 1
code of ge-zi-9,sukidayo are same at problem 1
code of zengjinrong,xiao-mei-mei-_ are same at problem 1
code of fa-kuang-de-jie-zi,icefeeder are same at problem 1
code of thegreatfirewall,antik-4,wheelBL are same at problem 1
code of da-li-wang,qi-qi-51 are same at problem 1
code of phh,wu-bian-luo-mu-2 are same at problem 1
code of Andruet,michaelanyanxin are same at problem 1
code of submitwithoutrun,user5905H,fei-fei-a-2 are same at problem 1
code of xiaoyu-46,san-ming-zi are same at problem 1
code of zzzzzwm-2,supermantou,kuai-le-shu-sheng are same at problem 1
code of jizhiyi,zbmygril are same at problem 1
code of 15892873721,sfaaa12,ray-86,ren-gui,xh5828,lkj5432,6a_dore,shi-76,yong-zhong-zhong are same at problem 1
code of Minori,noneland,kirk-karpathy,whilelivetruecoding,wyzidu are same at problem 1
code of lwy0ever,wincss,yao-bing,wang-rong-chuan,cxy7tv,xu-xu-15 are same at problem 1
code of weak-chicken,sun-man-man are same at problem 1
code of Snowe,xixiwu are same at problem 1
code of duo-15,visvli,CharlesZ,Desgard_Duan are same at problem 1
code of tommyjiang,abtemp,lxx are same at problem 1
code of fuwutu,qd452 are same at problem 1
code of lostleaf,fanzhh,lih,lovehhf are same at problem 1
code of jassy,joker-Di0G8mMZC6,ku-gua-yi-jiao-ban-sheng-gua are same at problem 1
code of 747929791,liupengmolly-2,fantding,zxm-9,Tensor,ban-xia-wei-liang-10,xing-dong-zhe-3 are same at problem 1

这是相同指完全相同,多一个空格都认为是不同的。
若是本人弄错,真诚道歉,我马上删除。

15

我在想,经常第一名和第二名那两个的是不是应该不愁衣服穿?
像我这种菜鸡!想要搞件衣服穿,都是在计划着需要几百天才能够,而且每天还在要死不活的想今天的四十积分还没拿到。。。。

5

只会做第一个,我想哭

5

建议, 以后周赛题目难度都mid+起吧, 模板题最好就别出了. 有时候扫一眼就知道怎么做了,还得写一遍,有点浪费时间.

T1: 如果奇数,全输出a;偶数就输出n-1个a和一个b
T2: 树状数组模板题, 每次更新sum[pos], 然后求1..max的和是否等于max. (其实直接扫维护一个计数器才是最优的,我煞笔了)
T3: BFS, 直接裸bfs, 统计没有出度的点的max
T4: BFS, count[pos]表示pos点还连着几个没有遍历过的点,每次走的时候计算下一次的概率即可.

5

第一次全A,开心。。。

第四题耗时太久,编码前考虑不全,导致路径寻找错误,导致返工。

4

哇!被第一道题卡了一个多小时!太蠢了
最后发现解决办法是:
如果n是奇数,输出n个'a';
如果n是偶数,输出n-1个'a'和1个'b'!!

3

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

思路

  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

周赛179

简单地写一下题解,大家有什么疑问、意见都可以直接说哈。

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

基础数学 + 贪心。可以看注释。

var generateTheString = function(n) {
  let res = '';
  if (n & 1) { // 奇,直接输出就好
    res = 'a'.repeat(n);
  } else { // 偶 = 奇 + 奇
    res = 'a' + 'b'.repeat(n - 1);
  }
  return res;
};

灯泡开关 III

线性走一遍,判断当前序列(长度为K,K <= N)是否是[1~K]的全排列。快捷的方法是求最大值,即只需要看当前的最大值是否是K,如果是K则表示满足全排列。

var numTimesAllBlue = function(lights) {
  let res = 0;
  let max = -Infinity;
  for (let i = 0; i < lights.length; ++i) {
    const light = lights[i];
    max = Math.max(max, light);
    if (max === i + 1) { // 满足排列相等
      ++res;
    }
  }
  return res;
};

通知所有员工所需的时间

有点绕,本质上是求从root到leaf的最大路径和。因为通知到leaf就意味着通知到所有人,然后是同时进行所以取最大时间。

var numOfMinutes = function(n, headID, manager, informTime) {
  // 建立正向映射
  const p2c = Array.from({ length: n }, () => []); // 父节点 => 子节点数组
  for (let i = 0; i < n; ++i) {
    const p = manager[i];
    if (p === -1) continue;
    p2c[p].push(i);
  }
  
  let res = 0;

  function dfs(i, sum) {
    if (p2c[i].length === 0) { // 叶子
      res = Math.max(res, sum);
      return;
    }

    for (const j of p2c[i]) {
      dfs(j, sum + informTime[i]);
    }
  }

  dfs(headID, 0);
  return res;
};

T 秒后青蛙的位置

我的思路是模拟BFS,因为t很小……BFS的同时算概率,最后只需要取target的概率就好。大家有更好的做法可以留言一下~

var frogPosition = function(n, edges, T, target) {
  const adj = Array.from({ length: n + 1 }, () => []); // 邻接表
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }

  const visited = Array.from({ length: n + 1 }, () => false);
  let currs = [];
  currs.push([1, 1]); // [i, prob]
  visited[1] = true;

  for (let t = 0; t < T; ++t) { // t次迭代
    const nexts = [];

    for (const [i, p] of currs) {
      const js = new Set();

      for (const j of adj[i]) {
        if (!visited[j]) {
          js.add(j);
        }
      }

      if (js.size === 0) { // 停留在原地
        nexts.push([i, p]);
      } else { // 扩展
        for (const j of js) {
          nexts.push([j, p / js.size]);
          visited[j] = true;
        }
      }
    }

    currs = nexts;
    // console.log(currs);
  }

  for (const [i, p] of currs) {
    if (i === target) return p;
  }
  return 0;
};
2

第一次正式参加周赛(还混过一个只剩20分钟的双周赛)
第一次全A
然而做的还是太慢,搞了50多分钟,一把年纪了,继续努力吧

1

灯泡开关 C++ 题解

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