1309. 解码字母到整数映射
给你一个字符串 s，它由数字（'0' - '9'）和 '#' 组成。我们希望按下述规则将 s 映射为一些小写英文字符：
字符（'a' - 'i'）分别用（'1' - '9'）表示。
字符（'j' - 'z'）分别用（'10#' - '26#'）表示。
返回映射之后形成的新字符串。
题目数据保证映射始终唯一。
直接hash解析对应关系(水题)
class Solution(object):
def freqAlphabets(self, s):
"""
:type s: str
:rtype: str
"""
map = {}
for i in range(1,28):
str = "{}".format(i) if i<10 else "{}#".format(i)
map[str] = chr(ord('a')+i-1)
def dfs(start,lim):
if lim-start>=3:
if s[start:start+3] in map.keys():
return map[s[start:start+3]] + dfs(start+3,lim)
elif lim-start>=1:
if s[start:start+1] in map.keys():
return map[s[start:start+1]] + dfs(start+1,lim)
return ""
return dfs(0,len(s))
1310. 子数组异或查询
有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。
对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作为本次查询的结果。
并返回一个包含给定查询 queries 所有结果的数组。
前缀异或和.
下标L,R之间的异或和
下标0,R之间的异或和 ^ 下标0,L-1之间的异或和 = 下标L...R的异或和
class Solution(object):
def xorQueries(self, arr, queries):
"""
:type arr: List[int]
:type queries: List[List[int]]
:rtype: List[int]
"""
xorsum = [0]*(len(arr)+1)
#
for i,v in enumerate(arr):
xorsum[i] = xorsum[i-1]^v
ans = []
for que in queries:
l,r = que
ans.append(xorsum[r]^xorsum[l-1])
return ans
1311. 获取你好友已观看的视频
有 n 个人，每个人都有一个 0 到 n-1 的唯一 id 。
给你数组 watchedVideos 和 friends ，其中 watchedVideos[i] 和 friends[i] 分别表示 id = i 的人观看过的视频列表和他的好友列表。
Level 1 的视频包含所有你好友观看过的视频，level 2 的视频包含所有你好友的好友观看过的视频，以此类推。一般的，Level 为 k 的视频包含所有从你出发，最短距离为 k 的好友观看过的视频。
给定你的 id 和一个 level 值，请你找出所有指定 level 的视频，并将它们按观看频率升序返回。如果有频率相同的视频，请将它们按名字字典序从小到大排列。
BFS广搜,深度为k的情况下记录视频.不要忘记移除自己
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]
"""
vis = [0]*len(friends)
que = []
que.append((id,0))
vis[id] = 1
mp = {}
def add(key):
for video in watchedVideos[key]:
mp[video] = mp.get(video,0)+1
while que:
now,dep = que.pop(0)
if dep == level:
add(now)
continue
friendlist = friends[now]
for f in friendlist:
if not vis[f]:
vis[f] = 1
que.append((f,dep+1))
sorted_list = sorted(mp.items(),lambda x,y: cmp(x[0],y[0]) if cmp(x[1],y[1]) == 0 else cmp(x[1],y[1]) )
return [ arr[0] for arr in sorted_list ]
1312. 让字符串成为回文串的最少插入次数
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
这个地方等于求字符串长度-最长非连续回文子串
即求可利用的最多字符个数,其他的不可利用字符等于插入个数
class Solution(object):
def minInsertions(self, s):
"""
:type s: str
:rtype: int
"""
vis = [[-1]*len(s) for i in range(len(s))]
def dfs(l,r):
if l == r:
return 1
if l > r:
return 0
if vis[l][r] !=-1:
return vis[l][r]
if s[l] == s[r]:
vis[l][r] = 2+dfs(l+1,r-1)
else:
vis[l][r] = max(dfs(l+1,r),dfs(l,r-1))
return vis[l][r]
return len(s) - dfs(0,len(s)-1)
