1309. 解碼字母到整數(shù)映射
給你一個(gè)字符串 s，它由數(shù)字（'0' - '9'）和 '#' 組成渣慕。我們希望按下述規(guī)則將 s 映射為一些小寫英文字符：
字符（'a' - 'i'）分別用（'1' - '9'）表示冀膝。
字符（'j' - 'z'）分別用（'10#' - '26#'）表示逮走。
返回映射之后形成的新字符串去扣。
題目數(shù)據(jù)保證映射始終唯一。
直接hash解析對(duì)應(yīng)關(guān)系(水題)
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. 子數(shù)組異或查詢
有一個(gè)正整數(shù)數(shù)組 arr堪唐，現(xiàn)給你一個(gè)對(duì)應(yīng)的查詢數(shù)組 queries，其中 queries[i] = [Li, Ri]翎蹈。
對(duì)于每個(gè)查詢 i淮菠，請(qǐng)你計(jì)算從 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作為本次查詢的結(jié)果。
并返回一個(gè)包含給定查詢 queries 所有結(jié)果的數(shù)組荤堪。
前綴異或和.
下標(biāo)L,R之間的異或和
下標(biāo)0,R之間的異或和 ^ 下標(biāo)0,L-1之間的異或和 = 下標(biāo)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 個(gè)人合陵，每個(gè)人都有一個(gè) 0 到 n-1 的唯一 id 枢赔。
給你數(shù)組 watchedVideos 和 friends ，其中 watchedVideos[i] 和 friends[i] 分別表示 id = i 的人觀看過(guò)的視頻列表和他的好友列表拥知。
Level 1 的視頻包含所有你好友觀看過(guò)的視頻踏拜，level 2 的視頻包含所有你好友的好友觀看過(guò)的視頻，以此類推低剔。一般的速梗，Level 為 k 的視頻包含所有從你出發(fā)，最短距離為 k 的好友觀看過(guò)的視頻襟齿。
給定你的 id 和一個(gè) level 值姻锁，請(qǐng)你找出所有指定 level 的視頻，并將它們按觀看頻率升序返回猜欺。如果有頻率相同的視頻位隶，請(qǐng)將它們按名字字典序從小到大排列。
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. 讓字符串成為回文串的最少插入次數(shù)
給你一個(gè)字符串 s 替梨，每一次操作你都可以在字符串的任意位置插入任意字符钓试。
請(qǐng)你返回讓 s 成為回文串的 最少操作次數(shù) 。
「回文串」是正讀和反讀都相同的字符串副瀑。
這個(gè)地方等于求字符串長(zhǎng)度-最長(zhǎng)非連續(xù)回文子串
即求可利用的最多字符個(gè)數(shù),其他的不可利用字符等于插入個(gè)數(shù)
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)
