LeetCode2020第170场周赛

发表于 更新于 分类于 阅读次数： Disqus：

5303. 解码字母到整数映射

题目描述

给你一个字符串 s，它由数字（’0’ - ‘9’）和 ‘#’ 组成。我们希望按下述规则将 s 映射为一些小写英文字符： 字符（’a’ - ‘i’）分别用（’1’ - ‘9’）表示。 字符（’j’ - ‘z’）分别用（’10#’ - ‘26#’）表示。 返回映射之后形成的新字符串。 题目数据保证映射始终唯一。 示例 1： 输入：s = “10#11#12” 输出：”jkab” 解释：”j” -> “10#” , “k” -> “11#” , “a” -> “1” , “b” -> “2”. 示例 2： 输入：s = “1326#” 输出：”acz” 示例 3： 输入：s = “25#” 输出：”y” 示例 4： 输入：s = “12345678910#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#” 输出：”abcdefghijklmnopqrstuvwxyz” 提示： 1 <= s.length <= 1000 s[i] 只包含数字（’0’-‘9’）和 ‘#’ 字符。 s 是映射始终存在的有效字符串。

题解1

a-i对应的是1-9，即一个字母对应一个字符；j-z对应的是10#-26#即一个字母对应三个字符，且以#结尾。现在我们反向遍历字符串，遇到#，找到其前面2个数字字符对应的字母，否则，直接将对应的字符转成字母即可。最后再将字符串反转即可。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string freqAlphabets(string s) {
        int len = s.size(), num;
        string res;
        for(int i = len - 1; i >= 0; --i){
            if(s[i] == '#'){//遇到#，找到其前面的2个字符对应的字母
                num = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
                i = i - 2;
            }
            else{
                num = s[i] - '0';
            }
            res.push_back('a' + num - 1);
        }
        reverse(res.begin(), res.end());//反转
        return res;
    }
};

1310. 子数组异或查询

题目描述

有一个正整数数组 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] 提示： 1 <= arr.length <= 3 * 10^4 1 <= arr[i] <= 10^9 1 <= queries.length <= 3 * 10^4 queries[i].length == 2 0 <= queries[i][0] <= queries[i][1] < arr.length

题解1

思路类似求任意区间的数字和，首先用vec[i]存储从arr[0]到arr[i]这些元素的异或，然后对于区间[a, b]的所有元素异或值为$vec[b] \oplus vec [a - 1]$

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int>res, vec;
        int len = arr.size();
        for(int i = 0; i < len; ++i){
            if(i == 0){
                vec.push_back(arr[0]);
            }
            else{
                vec.push_back(vec[i - 1] ^ arr[i]);
            }
        }
        for(auto que:queries){
            if(que[0] == 0){
                res.push_back(vec[que[1]]);
            }
            else{
                res.push_back(vec[que[1]] ^ vec[que[0] - 1]);
            }
        }
        return res;
    }
};

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

题解1

BFS。首先利用BFS找到和起始id距离为level的所有朋友，然后统计这些朋友的观影情况，按观看频率升率返回，相同的，按字典序从小到大排列。

代码1

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
struct Node{
    int id;
    int level;
    Node(int id, int level):id(id), level(level){}
};
class Solution {
public:
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        vector<int>ids;
        vector<string>res;
        map<string, int>myMap;
        queue<Node>que;
        vector<int>mark(watchedVideos.size(), 0);
        set<pair<int, string>>tmp;

        /*
        BFS寻找距离为level的朋友们的id
        */
        que.push(Node(id, 0));
        mark[id] = 1;
        Node frt(0, 0), next(0, 0);
        while(!que.empty()){
            frt = que.front();
            que.pop();
            if(frt.level > level){
                break;
            }
            else if(frt.level == level){
                ids.push_back(frt.id);
            }
            for(int i = 0; i < friends[frt.id].size(); ++i){
                next.id =friends[frt.id][i];
                next.level = frt.level + 1;
                if(!mark[next.id]){
                    mark[next.id] = 1;
                    que.push(next);
                }
            }
        }
        //统计朋友们的观影频率
        for(auto id:ids){
            for(auto video:watchedVideos[id]){
                if(myMap.find(video) == myMap.end()){
                    myMap[video] = 1;
                }
                else{
                    myMap[video] = myMap[video]+ 1;
                }
            }
        }

        //放入set中自动排序
        for(auto iter:myMap){
            tmp.insert(make_pair(iter.second, iter.first));
        }
        for(auto iter:tmp){
            res.push_back(iter.second);
        }
        return res;
    }
};

1312. 让字符串成为回文串的最少插入次数

题目描述

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。 请你返回让 s 成为回文串的 最少操作次数 。 「回文串」是正读和反读都相同的字符串。 示例 1： 输入：s = “zzazz” 输出：0 解释：字符串 “zzazz” 已经是回文串了，所以不需要做任何插入操作。 示例 2： 输入：s = “mbadm” 输出：2 解释：字符串可变为 “mbdadbm” 或者 “mdbabdm” 。 示例 3： 输入：s = “leetcode” 输出：5 解释：插入 5 个字符后字符串变为 “leetcodocteel” 。 示例 4： 输入：s = “g” 输出：0 示例 5： 输入：s = “no” 输出：1 提示： 1 <= s.length <= 500 s 中所有字符都是小写字母。

题解1

动态规划。 题目实际上是最长回文子序列的变形。求出最长回文子序列的长度，再用原长度len - 回文子序列的长度即可。

代码1

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
/*
找出s中最长回文子序列len1
题目中要求的是len - len1
*/
class Solution {
public:
    int minInsertions(string s) {
        int len = s.size();
        vector<vector<int>>dp(len + 1, vector<int>(len + 1, 0));
        for(int i = 0; i < len; ++i){//长度为1的串，最长回文序列就是它本身即长度为1
            dp[i][i] = 1;
        }
        for(int i = 1; i < len; ++i){
            for(int j = 0; j < len; ++j){
                if(j + i < len){
                    if(s[j] == s[j + i]){
                        dp[j][j + i] = dp[j + 1][j + i - 1] + 2;
                    }
                    else{
                        dp[j][j + i] = max(dp[j + 1][j + i], dp[j][j + i - 1]);
                    }
                }
            }
        }
        return len - dp[0][len - 1];
    }
};