leetcode 3.01-3.07

2021-03-07

217 存在重复元素
1311 获取你好友已观看的视频

217. 存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

输入: [1,2,3,1]
输出: true
示例 2:

输入: [1,2,3,4]
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contains-duplicate
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：排序，比较。也可考虑哈希表。

AC代码：

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) < 2: return False
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i+1]: return True
        return False
      
      	# 方法二
        return len(nums) != len(set(nums))

15种方法的题解https://leetcode-cn.com/problems/contains-duplicate/solution/15chong-shu-zu-yan-zhong-fang-fa-1xing-d-jwm8/

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：

输入：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：

输入：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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/get-watched-videos-by-your-friends
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：先广度优先搜索获得用户id的level用户列表；根据这个用户列表和视频观看列表统计视频观看频率，用map保存；之后按照题目要求排序返回即可。

AC代码：

using PSI = pair<string, int>;

class Solution {
public:
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        int n = friends.size();
        vector<bool> used(n);
        queue<int> q;
        q.push(id);
        used[id] = true;
        for (int l = 1; l <= level; ++l) {
            int span = q.size();
            for (int i = 0; i < span; ++i) {
                int u = q.front();
                q.pop();
                for (int v: friends[u]) {
                    if (!used[v]) {
                        q.push(v);
                        used[v] = true;
                    }
                }
            }
        }
        
        unordered_map<string, int> freq;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (const string& watched: watchedVideos[u]) {
                ++freq[watched];
            }
        }
        
        vector<PSI> videos(freq.begin(), freq.end());
        sort(videos.begin(), videos.end(), [](const PSI& p, const PSI& q) {
            return p.second < q.second || (p.second == q.second && p.first < q.first);
        });
        
        vector<string> ans;
        for (const PSI& video: videos) {
            ans.push_back(video.first);
        }
        return ans;
    }
};

待调试代码：

class Solution(object):
    def watchedVideosByFriends(self, watchedVideos, friends, id, level):
        """
        :type watchedVideos: List[List[str]]
        :type friends: List[List[int]]
        :type id: int
        :type level: int
        :rtype: List[str]
        """
        users = []
        users.append(friends[id])
        for l in range(1, level):
            tmp = []
            for user in users[l-1]:
                tmp.extend(friends[user])
            users.append(set(tmp))
        # print(users[-1])
        dic = {}
        for user in users[-1]:
            if user == id: continue
            for video in watchedVideos[user]:
                dic[video] = dic.get(video, 0) + 1
        tmpret = sorted(dic.items(), key = lambda kv: (kv[1], kv[0]))
        # print(tmpret)
        ret = []
        for kv in tmpret:
            ret.append(kv[0])
        # print(ret)
        return ret