Skip to content

Latest commit

 

History

History
167 lines (121 loc) · 6.48 KB

1311.md

File metadata and controls

167 lines (121 loc) · 6.48 KB
Raw

1311. 获取你好友已观看的视频

Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。

这里是第 170 期的第 3 题，也是题目列表中的第 1311 题 -- 『获取你好友已观看的视频』

题目描述

有 n 个人，每个人都有一个 0 到 n-1 的唯一 id。

给你数组 watchedVideos 和 friends，其中 watchedVideos[i] 和 friends[i] 分别表示 id = i 的人观看过的视频列表和他的好友列表。

Level 1 的视频包含所有你好友观看过的视频，level 2 的视频包含所有你好友的好友观看过的视频，以此类推。一般的，Level 为 k 的视频包含所有从你出发，最短距离为 k 的好友观看过的视频。

给定你的 id 和一个 level 值，请你找出所有指定 level 的视频，并将它们按观看频率升序返回。如果有频率相同的视频，请将它们按名字字典序从小到大排列。

示例 1：

1311-1

输入：watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1
输出：["B","C"]
解释：
你的 id 为 0 ，你的朋友包括：
id 为 1 -> watchedVideos = ["C"]
id 为 2 -> watchedVideos = ["B","C"]
你朋友观看过视频的频率为：
B -> 1
C -> 2

示例 2：

1311-2

输入：watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2
输出：["D"]
解释：
你的 id 为 0 ，你朋友的朋友只有一个人，他的 id 为 3 。

提示：

  • n == watchedVideos.length == friends.length
  • 2 <= n <= 100
  • 1 <= watchedVideos[i].length <= 100
  • 1 <= watchedVideos[i][j].length <= 8
  • 0 <= friends[i].length < n
  • 0 <= friends[i][j] < n
  • 0 <= id < n
  • 1 <= level < n
  • 如果 friends[i] 包含 j ，那么 friends[j] 包含 i

官方难度

MEDIUM

解决思路

这道题一眼看上去还挺吓人，一堆参数，很长的限制条件，连例子都好长。然而仔细想一下就会发现，其实都是纸脑抚，哼，小猪才不会被你骗到呢，略略略 >.<

题目的意思就是根据给定的初始 id，去寻找他第 level 轮的朋友们，从而得到朋友们看过的视频列表。最终把这个列表进行排序返回。那么总的来说就分为两部分，第一部分就是找到最终的目标朋友列表，第二部分就是把视频列表按要求进行排序返回。

找到目标朋友列表

我们先看第一部分，这里的流程其实非常清晰：

  1. 根据初始 id 寻找到朋友列表。
  2. 根据当前的朋友列表继续扩展开寻找下一轮的朋友列表。
  3. 直到满足第 level 轮即可终止。

看到这个流程，结合我们前几期的题解，相信小伙们应该很容易能想到一个思路，那就是广度优先遍历。要是没想到的话，哼，罚你关注我的公众号，略略略 >.<

关于广度优先遍历，我后续关于算法和数据结构的新坑会详细说明。这里可以先结合思路和下面的代码，或者翻翻我之前的题解，应该就能明白。不过这里有个小坑小伙伴们需要注意，那就是第 level 轮的好友指的是最短距离为 level 的好友。例如你的好友是 A、B、C，而 A 的好友是 C、D，B 的好友是 E，C 的好友是 A、F。那么这里得到的你的第一轮好友列表是 A、B、C，而第二轮好友列表是 D、E、F，并没有 A、C，因为他们已经在第一轮中出现了，在第二轮中并不是最短距离了。

这里给出一个比较容易理解的模板化的代码，当然我们为了处理最短距离问题，加入一个 visited 用以进行标识。

const visited = new Uint8Array(friends.length);
let queue = [id];
visited[id] = 1;
while (level--) {
  const next = [];
  for (const id of queue) {
    for (const newId of friends[id]) {
      if (visited[newId] === 0) { next.push(newId); visited[newId] = 1; }
    }
  }
  queue = next;
}

排序视频列表

题目中对于这个排序规则做了几点要求：

  • 根据视频被观看次数，进行升序排列。
  • 对于观看次数相同的视频，按照名称字母序进行排列。

那么我们这里的处理流程就比较明晰了：

  1. 基于目标好友列表统计出各个视频观看的次数。
  2. 基于次数和字母序进行排序。

前者可以基于 Map 很容易的实现，后者由于 JS 的数组 sort 可以支持自定义的排序函数，所以也很容易实现。具体代码如下：

// 统计观看次数
const freq = new Map();
for (const id of queue) {
  for (const video of watchedVideos[id]) {
    freq.set(video, freq.has(video) ? freq.get(video) + 1 : 1);
  }
}

// 自定义排序函数
(a, b) => a[1] === b[1] ? (a[0] > b[0] ? 1 : -1) : a[1] - b[1];

最终代码

结合上述两部分内容，我们很容易能得到类似下面的最终代码：

const watchedVideosByFriends = (watchedVideos, friends, id, level) => {
  const visited = new Uint8Array(friends.length);
  let queue = [id];
  visited[id] = 1;
  while (level--) {
    const next = [];
    for (const id of queue) {
      for (const newId of friends[id]) {
        if (visited[newId] === 0) { next.push(newId); visited[newId] = 1; }
      }
    }
    queue = next;
  }

  const freq = new Map();
  for (const id of queue) {
    for (const video of watchedVideos[id]) {
      freq.set(video, freq.has(video) ? freq.get(video) + 1 : 1);
    }
  }

  return Array.from(freq.entries()).sort((a, b) => {
    return a[1] === b[1] ? (a[0] > b[0] ? 1 : -1) : a[1] - b[1]
  }).map(item => item[0]);
};

这段代码跑出了 128ms，暂时 beats 100%。

总结

这道题目整体比较直白，没有太多可以分析的部分。不过由于它的流程其实比较明显的可以拆分成独立的两部分分别进行实现，这样每一部分的逻辑和实现都会更加清晰和容易。对应的，我们在实际工作开发中，其实把 feature 和 function 进行合理的拆分也是会很有利于整理和维护的。

相关链接

我的微信公众号：张小猪粉鼻子