LEETCODE 第170场周赛

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

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

  给你一个字符串 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的形式,否则会有歧义。

第二题:子数组异或查询

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

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

  有 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搜索。

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

  给你一个字符串 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.去除第一个字符和最后一个字符(如果第一个字符和最后一个字符一样),然后继续递归。

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