170场周赛

5304. 子数组异或查询

有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。

对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

示例 1:

输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8]
解释：
数组中元素的二进制表示形式是：
1 = 0001
3 = 0011
4 = 0100
8 = 1000
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8

示例 2：

输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出：[8,0,4,4]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
func xorQueries(_ arr: [Int], _ queries: [[Int]]) -> [Int] {
    var preXor = [Int](repeating: 0, count: arr.count+1)
    for i in 0..<arr.count {
        preXor[i+1] = arr[i] ^ preXor[i]
    }

    var ans = [Int]()
    for q in queries {
        let l = q[0], r = q[1]+1
        ans.append(preXor[l]^preXor[r])
    }
    return ans
}

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

有 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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func watchedVideosByFriends(_ watchedVideos: [[String]], _ friends: [[Int]], _ id: Int, _ level: Int) -> [String] {
    var seen = Set<Int>([id])
    var queue = [(id, 0)]
    var dstFriends = Set<Int>()
    while !queue.isEmpty {
        let (node, d) = queue.removeFirst()
        if d > level { break }
        if d == level {dstFriends.insert(node) }
        for nei in friends[node] where !seen.contains(nei) {
            seen.insert(nei)
            queue.append((nei, d+1))
        }
    }

    var dic = [String: Int]()
    for node in dstFriends {
        for video in watchedVideos[node] {
            dic[video, default: 0] += 1
        }
    }
    let videos = Array(dic.keys)
    return videos.sorted {
        if dic[$0]! == dic[$1]! {
            return $0 < $1
        }
        return dic[$0]! < dic[$1]!
    }
}