LEETCODE 第170场周赛

第四题感觉来不及直接放弃了🤢🤢

Contents

1 第一题：解码字母到整数映射
2 第二题：子数组异或查询
3 第三题：获取你好友已观看的视频
4 第四题：让字符串成为回文串的最少插入次数

第一题：解码字母到整数映射

　　给你一个字符串 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”

思路：先判断’ab#’的形式，再判断0-9的形式，否则会有歧义。

class Solution {
public:
    string freqAlphabets(string s) {
        string ans = "";
        for (int i=0;i<s.size();i++){
            if ((i+2) < s.size() &&  s[i+2]=='#'){
                ans += (char)((s[i]-'0')*10+ s[i+1]-'0'+'a'-1);
                i += 2;
            }else if (s[i]!='#'){
                ans += (char)(s[i]-'0'+'a'-1); 
            }
        }
        return ans;
    }
};

class Solution {

public:

string freqAlphabets(string s) {

string ans = "";

for (int i=0;i<s.size();i++){

if ((i+2) < s.size() && s[i+2]=='#'){

ans += (char)((s[i]-'0')*10+ s[i+1]-'0'+'a'-1);

i += 2;

}else if (s[i]!='#'){

ans += (char)(s[i]-'0'+'a'-1);

}

return ans;

}

};

第二题：子数组异或查询

　　有一个正整数数组 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]

思路: 查询[l, r]的之间的异或，相当于[0, r]之间的异或，再异或[0, l-1]的异或。先逐个异或一遍，把[0, i]的异或结果记录下来，然后 ans[l, r]= ans[0, r] ^ [0, l-1] 即可。

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> ans;
        vector<int> x(arr.size());
        x[0] = arr[0];
        for(int i=1;i<arr.size();i++){
            x[i] = arr[i] ^ x[i-1];
        }
        for(int i=0;i<queries.size();i++){
            int a = 0;
            if (queries[i][0]>0){
                a = x[queries[i][0]-1];
            }
            ans.push_back(x[queries[i][1]] ^ a);
        }

        return ans;
    }
};

class Solution {

public:

vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {

vector<int> ans;

vector<int> x(arr.size());

x[0] = arr[0];

for(int i=1;i<arr.size();i++){

x[i] = arr[i] ^ x[i-1];

}

for(int i=0;i<queries.size();i++){

int a = 0;

if (queries[i][0]>0){

a = x[queries[i][0]-1];

}

ans.push_back(x[queries[i][1]] ^ a);

}

return ans;

}

};

第三题：获取你好友已观看的视频

　　有 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

思路：用bfs。或者用dfs，注意一个人如果既是朋友也是朋友的朋友level为1，所以要先把朋友都标记一遍再继续向下一个level搜索。

class Solution:
    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
        vis = [0 for i in range(len(watchedVideos))]
        watchlist = dict()
        levels = dict()

        def dfs(who):
            if vis[who]:
                return
            if who in levels and levels[who] > level:
                return
            vis[who] = 1
            if levels[who] == level:
                # print(watchedVideos[who])
                for i in watchedVideos[who]:
                    if i in watchlist:
                        watchlist[i] += 1
                    else:
                        watchlist[i] = 1
                return
            for i in friends[who]:
                if i in levels:
                    levels[i] = min(levels[i], levels[who] + 1)  # 如果已经是朋友了，也是朋友的朋友，取关系较近的
                else:
                    levels[i] = levels[who] + 1

            for i in friends[who]:
                dfs(i)

        levels[id] = 0
        dfs(id)

        results = sorted(watchlist.items(), key=lambda kv: (kv[1], kv[0]))
        # return results
        return [i[0] for i in results]

class Solution:

def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:

vis = [0 for i in range(len(watchedVideos))]

watchlist = dict()

levels = dict()

def dfs(who):

if vis[who]:

return

if who in levels and levels[who] > level:

return

vis[who] = 1

if levels[who] == level:

# print(watchedVideos[who])

for i in watchedVideos[who]:

if i in watchlist:

watchlist[i] += 1

else:

watchlist[i] = 1

return

for i in friends[who]:

if i in levels:

levels[i] = min(levels[i], levels[who] + 1) # 如果已经是朋友了，也是朋友的朋友，取关系较近的

else:

levels[i] = levels[who] + 1

for i in friends[who]:

dfs(i)

levels[id] = 0

dfs(id)

results = sorted(watchlist.items(), key=lambda kv: (kv[1], kv[0]))

# return results

return [i[0] for i in results]

第四题：让字符串成为回文串的最少插入次数

　　给你一个字符串 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

思路：dp，令dp[a][b]为字符串s[a..b-1]得到回文字符串的最小添加数，那么有dp方程： $dp[a][b]=min(dp[a+1][b]+1, dp[a][b-1]+1, dp[a+1][b-1](s[a]==s[b]))$
意思即为在一下三种情况中找一个最小的：
　　1.在最后添加一个和第一个字符相同的字符(需添加1个字符)，去除第一个字符和最后一个字符，然后继续递归。
　　2.在一个个字符前添加一个和最后一个字符相同的字符(需添加1个字符)，去除第一个字符和最后一个字符，然后继续递归。
　　3.去除第一个字符和最后一个字符(如果第一个字符和最后一个字符一样)，然后继续递归。

　　使用一个数组来记录已经计算过的结果来减少重复计算的次数。

class Solution:
    def minInsertions(self, s: str) -> int:
        ans = [[-1 for i in range(len(s)+1)] for i in range(len(s)+1)]
        def dp(a, b):
            if a >= b:
                return 0

            if ans[a][b] != -1:
                return ans[a][b]

            c = dp(a+1, b-1) if s[a] == s[b-1] else 9999999
            ret = min(dp(a+1, b) + 1, dp(a, b-1) + 1, c)
            ans[a][b] = ret
            return ret

        return dp(0, len(s))

class Solution:

def minInsertions(self, s: str) -> int:

ans = [[-1 for i in range(len(s)+1)] for i in range(len(s)+1)]

def dp(a, b):

if a >= b:

return 0

if ans[a][b] != -1:

return ans[a][b]

c = dp(a+1, b-1) if s[a] == s[b-1] else 9999999

ret = min(dp(a+1, b) + 1, dp(a, b-1) + 1, c)

ans[a][b] = ret

return ret

return dp(0, len(s))