leetcode 2. 两数相加
class Solution:
def addTwoNumbers(self
, l1
: ListNode
, l2
: ListNode
) -> ListNode
:
carry_bit
= 0
result
= None
result_point
= result
p
,q
= l1
,l2
while p
or q
:
x
= p
.val
if p
else 0
y
= q
.val
if q
else 0
if result
:
result_point
.next = ListNode
((x
+y
+carry_bit
)%10)
result_point
= result_point
.next
else:
result
= ListNode
((x
+y
+carry_bit
)%10)
result_point
= result
carry_bit
= (x
+y
+carry_bit
)//10
p
= p
.next if p
else p
q
= q
.next if q
else q
if carry_bit
!=0:
result_point
.next=ListNode
(carry_bit
)
return result
529. 扫雷游戏
原来数字出现的条件是空白块周围八个角的范围，以为是上下左右呢。
class Solution(object):
def updateBoard(self
, board
, click
):
def dfs(board
,row
,col
):
if board
[row
][col
]=="M":
board
[row
][col
]="X"
return True
if board
[row
][col
]=="E":
bomb_count
=0
for i
in [-1,0,1]:
for j
in [-1,0,1]:
if i
+row
>=0 and i
+row
<len(board
) and j
+col
>=0 and j
+col
<len(board
[0]):
if board
[i
+row
][j
+col
]=="M":
bomb_count
+=1
if bomb_count
!=0:
board
[row
][col
]=str(bomb_count
)
else:
board
[row
][col
]="B"
for i
,j
in [[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]:
if i
+row
>=0 and i
+row
<len(board
) and j
+col
>=0 and j
+col
<len(board
[0]):
dfs
(board
,row
+i
,col
+j
)
return False
for i
in range(0,len(click
),2):
if dfs
(board
,click
[i
],click
[i
+1]):
break
return board
1578. 避免重复字母的最小删除成本
class Solution:
def minCost(self
, s
: str, cost
: List
[int]) -> int:
if len(s
)==1:
return 0
start
=0
result
= 0
dupmax
,dupsum
=cost
[0],cost
[0]
for i
in range(1,len(s
)):
if s
[i
]==s
[start
]:
dupsum
+=cost
[i
]
dupmax
=max(dupmax
,cost
[i
])
continue
else:
result
+= dupsum
-dupmax
dupmax
,dupsum
=cost
[i
],cost
[i
]
start
= i
result
+= sum(cost
[start
:len(s
)+1])-max(cost
[start
:len(s
)+1])
return result
1177. 构建回文串检测
超时
class Solution:
def canMakePaliQueries(self
, s
: str, queries
: List
[List
[int]]) -> List
[bool]:
result
=[]
for left
,right
,k
in queries
:
Alpha
=[0]*26
count
= 0
while left
<=right
:
Alpha
[ord(s
[left
])-97]+=1
left
+=1
result
+=[sum([alpha
%2 for alpha
in Alpha
])//2<=k
]
return result
优化
统计字母频率，没必要重复加，可以求个总的，做减法。
class Solution:
def canMakePaliQueries(self
, s
: str, queries
: List
[List
[int]]) -> List
[bool]:
result
=[None]*len(s
)
res
= []
Alpha
=[0]*26
for i
,c
in enumerate(s
):
Alpha
[ord(c
)-97]+=1
result
[i
]=Alpha
.copy
()
for left
,right
,k
in queries
:
left_result
= result
[left
-1] if left
>=1 else [0]*26
res
+=[sum([alpha
%2 for alpha
in list(map(lambda x
,y
:x
-y
,result
[right
],left_result
))])//2<=k
]
return res
