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

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

image.png

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

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

周赛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
展开全部 25 讨论