# 2021-09-29:单词缩写，数字交换得到最大值，滚动字符串归类，插入结点，接雨水，距离为K的点

1617-卿同学

## 热门标签

class Solution:
def validWordAbbreviation(self, word: str, abbr: str) -> bool:
index = 0
m = len(abbr)
n = len(word)
num = 0
for i in range(m):

if abbr[i].isdigit():
if num==0 and int(abbr[i]) == 0:
return False
num = num*10 +int(abbr[i])
if num > n-index:
return False
else:
print(abbr[i])
index += num
if index >= n:
return False
if abbr[i] != word[index]:
return False
index +=1
num =0
index += num
if index < n:
return False
return True



maximum swap:

class Solution:
def maximumSwap(self, num: int) -> int:
numstring = list(str(num))
numstring = list(map(int,numstring))
print(numstring)
n = len(numstring)
if n == 1:
return num
maxval = [[numstring[-1],n-1]]
prev = [numstring[-1],n-1]
ans = ""
for i in range(n-2,-1,-1):
if numstring[i] > maxval[-1][0]:
maxval.append([numstring[i],i])
prev = [numstring[i],i]
else:
maxval.append(prev)
print(maxval)
maxval = maxval[::-1]
print(maxval)
for i in range(n):
if numstring[i] != maxval[i][0]:
print (i)
numstring[i],numstring[maxval[i][1]] = numstring[maxval[i][1]],numstring[i]
break
for i in range(n):
ans += str(numstring[i])
return int(ans)


class Solution:
def groupStrings(self, strings: List[str]) -> List[List[str]]:
ans = []
groupdict = defaultdict(list)
for word in strings:
n = len(word)
if n == 1:
groupdict["a"] += [word]
else:
index = ""
for i in range(1,n):
diff = ord(word[i])-ord(word[i-1])
diff = diff % 26
index += " " +str(diff)
print(index,word)
groupdict[index] += [word]
for key,val in groupdict.items():
ans += [val]
return ans



1:中间点， 升序中间

2:开始结束点中间，唯一降序，如果比这些都大或者都小就插入

3:所有点值都一样，遍历一遍到开头结尾判断头尾是不是一样的

"""
# Definition for a Node.
class Node:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
"""

class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
newNode = Node(insertVal,None)
newNode.next = newNode
return newNode
while True:
if prev.val <= insertVal <= cur.val:
prev.next = Node(insertVal,cur)
break
elif prev.val > cur.val:
if insertVal > prev.val or insertVal < cur.val:
prev.next = Node(insertVal,cur)
break
prev,cur = cur,cur.next
if prev == head and prev.val == cur.val:
prev.next = Node(insertVal,cur)
break



class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
maxleft = [0]*n
maxleftval = 0
for i in range(1,n):
if height[i-1] > maxleftval:
maxleft[i] = height[i-1]
maxleftval = height[i-1]
else:
maxleft[i] = maxleftval
maxright = [0]*n
maxrightval = 0
print(maxleft)
for i in range(n-2,-1,-1):
if height[i+1] > maxrightval:
maxright[i] = height[i+1]
maxrightval = height[i+1]
else:
maxright[i] = maxrightval
print(maxright)
trapwater = 0
for i in range(n):
val = min(maxright[i],maxleft[i])
print(val - height[i])
if (val - height[i])>0:
trapwater += val - height[i]
return trapwater

先建立一个parent节点，

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
def dfs(node,par):
if node:
node.par = par
dfs(node.left,node)
dfs(node.right,node)

dfs(root,None)
queue = [[target,0]]
seen = [target]
ll = []
while queue:
ll =[]
if queue[0][1] == k:
return [node.val for node,d in queue]
for curnode,d in queue:
if curnode.par and curnode.par not in seen:
ll.append([curnode.par,d+1])
seen.append(curnode.par)
if curnode.left and curnode.left not in seen:
ll.append([curnode.left,d+1])
seen.append(curnode.left)
if curnode.right and curnode.right not in seen:
ll.append([curnode.right,d+1])
seen.append(curnode.right)
queue = ll
return []



Vieu3.3主题

Q Q 登 录