1贪心算法：跳跃游戏2：
class Solution:
def jump(self, nums: List[int]) -> int:
n=len(nums)
if n<=1:
return 0
step=1
left,right=1,nums[0]
while right<n-1:
for i in range(left,right+1):
if i+nums[i]>right:
right=i+nums[i]
lef=i+1
step+=1
return step
2两数之和：map的使用：
nums=[1,4,6,7]
tagert=5
def add_two():
record={}
for index,val in enumerate(nums):
if tagert-val not in record:
record[val]=index
else:
print([record[tagert - val], index])
add_two()
两数之和for循环：
nums=[1,4,6,7]
tagert=10
n=len(nums)
for i in range(0,n-1):
for j in range(1,n):
if nums[i]+nums[j]==tagert and i!=j and i<j:
print([i,j])
用正则切割字符：
s="babdlkl"
import re
print(re.findall(r".{1}",s))
3最长回文字符串：切片法
class Solution:
def longestPalindrome(self, s: str) -> str:
n=len(s)
res=""
if n<1:
return 0
if n==1:
return s
for i in range(n):
start=max(0,i-len(res)-1)
temp=s[start:i+1]
if temp==temp[::-1]:
res=temp
else:
temp=temp[1:]
if temp==temp[::-1]:
res=temp
return res
#temp==temp[::-1]
4反转没对括号间的子串：栈的应用：
s="(ed(et(oc))el)"
open_group = []
cur_group = []
for ch in s:
if ch=="(":
#收起来
open_group.append(cur_group)
cur_group=[]
elif ch==")":
#出栈
prev_group=open_group.pop()
cur_group.reverse()
prev_group.extend(cur_group)
cur_group=prev_group
else:
cur_group.append(ch)
print(''.join(cur_group))
5岛屿数量：二维数组，深度优先
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(grid, i, j):
if 0<=i and i<row and 0<=j and j<col and grid[i][j]=="1" :
grid[i][j]="0"
dfs(grid,i+1,j)
dfs(grid,i-1,j)
dfs(grid,i,j+1)
dfs(grid,i,j-1)
row=len(grid)
col=len(grid[0])
count=0
if not grid:
return 0
for i in range(row):
for j in range(col):
if grid[i][j]=="1":
dfs(grid,i,j)
count+=1
return count
6每日温度：单调栈的使用
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n=len(temperatures)
if n==0:
return 0
ret=[0]*n
stack=[]
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
#新值大 则旧值弹出
index=stack.pop()
ret[index]=i-index
stack.append(i)
return ret
7字符串解码394
class Solution:
def decodeString(self, s: str) -> str:
n=len(s)
if n<1:
return "0"
if n==1:
return s
x=0
stack=[]
res,num="",0
for i in s :
if i.isdigit():
num=num*10+int(i)
elif i=="[":
stack.append((res,num))
res,num="",0
elif i=="]":
pop=stack.pop()
res=pop[0]+res*pop[1]
else:
res+=i
return res
8两数相加2--链表：
# Definition for singly-linked list.
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
re=temp=ListNode(None)
add=0
while l1 or l2 or add:
add+=(l1.val if l1 else 0)+(l2.val if l2 else 0)
temp.next=ListNode(add%10)
add//=10
temp=temp.next
l1=l1.next if l1 else None
l2=l2.next if l2 else None
return re.next
9无重复字符的最长子串? leetcode3：
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n=len(s)
usedSet=set()
l,r=0,0
result=0
for r in range(n):
while s[r] in usedSet:
usedSet.remove(s[l])
l+=1
usedSet.add(s[r])
result=max(result,len(usedSet))
return result
10.有效的括号leetcode20
class Solution:
def isValid(self, s: str) -> bool:
while '{}' in s or '()' in s or '[]' in s:
s = s.replace('{}', '')
s = s.replace('[]', '')
s = s.replace('()', '')
return s == ''
11.森林中的兔子：
import collections
from typing import List
class Solution:
def numRabbits(self, answers: List[int]) -> int:
sum=0
count=collections.defaultdict(int)
for i in answers:
count[i]+=1
for key,value in count.items():
sum+=(key+1)*((key+value)//(key+1))
return sum
12.最大正方形：
from typing import List
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
dp=[[0 for _ in range(len(matrix))]for _ in range(len(matrix[0]))]
maxedge=0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j]=="1":
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
maxedge=max(dp[i][j],maxedge)
return maxedge ** 2
13.单词的压缩编码：leetcode820
from typing import List
class Solution:
def minimumLengthEncoding(self, words: List[str]) -> int:
s = ""
words = sorted(words, key = lambda i: len(i), reverse=True)
for i in words:
if i+"#" in s:
continue
s += i+"#"
return len(s)
14整数反转：leetcode7
class Solution:
def reverse(self, x: int) -> int:
str_x=str(x)
if len(str_x)==1:
return x
x=''
if str_x[0]=="-":
x+="-"
x+=str_x[::-1].lstrip("0").rstrip("-")
x=int(x)
if -2**31<x<2**31-1:
return x
else:
return 0
整数反转2方法：
class Solution:
def reverse(self, x: int) -> int:
str_x=str(x)
if x < 0:
x = int('-' + str_x[1:][::-1])
elif x>0:
x=int(str_x[::-1])
if x==0:
return 0
if -2**31<x<2**31-1:
return x
return 0
15.两数相乘：
def multiply(self, num1, num2):
res = 0
for i in range(1,len(num1)+1):
for j in range(1, len(num2)+1):
res += int(num1[-i]) * int(num2[-j]) *10**(i+j-2)
return str(res)
class Solution:
def multiply(self, num1: str, num2: str) -> str:
res=[0]*(len(num1)+len(num2))
for i in range(len(num1))[::-1]:
carry=0
for j in range(len(num2))[::-1]:
tmp=int(num1[i])*int(num2[j])+carry
carry,res[i+j+1]=divmod((res[i+j+1]+tmp),10)
res[i]+=carry
res="".join(map(str,res))
res=res.lstrip("0")
return 0 if not res else res
16.穿砖头、方法一，顺口溜
class Solution:
def leastBricks(self, wall: List[List[int]]) -> int:
res = {0: 0}
for lvl in wall:
pos = 0
for brick in lvl[:-1]:
pos += brick
res[pos] = res.get(pos, 0) +1
return len(wall)-max(res.values())
?方法二：
import collections
from typing import List
class Solution:
def leastBricks(self, wall: List[List[int]]) -> int:
row=len(wall)
col=len(wall[0])
sum_wall=[]
for i in range(row):
for j in range(col-1):
if j==0:
sum_wall.append(wall[i][j])
else:
sum_wall.append(wall[i][j]+sum_wall[-1])
counter=collections.Counter(sum_wall)
if not counter:
return len(wall)
return len(wall)-max([k[1] for k in counter.items()])
17.跳跃游戏1：
from typing import List
class Solution:
def jump(self, nums: List[int]) -> int:
max_num=0
n=len(nums)
for i in range(n):
if max_num<i:
return False
else:
max_num=max(max_num,i+nums[i])
return True
18.有效的括号---leetcode20
class Solution:
def isValid(self, s: str) -> bool:
stack=[]
for i in s:
if i=="(":
stack.append(")")
elif i=="[":
stack.append("]")
elif i=="{":
stack.append("}")
elif not stack or stack[-1]!=i:
return False
else:
stack.pop()
return True if not stack else False
19.供暖器，好说歹说leetcode475
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()
maxr = 0
i = 0
for house in houses:
while True:
if heaters[i]>house or i==len(heaters)-1:
break
i += 1
if i == 0 or house>=heaters[i]:
minr = abs(heaters[i]-house)
else: minr = min(house-heaters[i-1], heaters[i] - house)
if minr > maxr:
maxr = minr
return maxr
20.根据身高重建队列：
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key=lambda x:(-x[0],x[1]))
que=[]
for p in people:
que.insert(p[1],p)
return que
21.全排列leetcode46
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res=[]
def backtrack(nums,tmp):
if not nums:
res.append(tmp)
return res
for i in range(len(nums)):
backtrack(nums[:i]+nums[i+1:],tmp+[nums[i]])
backtrack(nums,[])
return res
|