力扣题51~70
题51（困难）：
分析：
递归金典题：N皇后问题，搞过扫雷游戏就很简单了
python代码：
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
#n 皇后问题--》非线性--》选递归，
res=[]
queue_count=n
#设置皇后，递归函数，传当前可行位置+放置第几个
def set_queue(free_queue,queue_board,n):
if n<=0 or n>queue_count:
return
if n==queue_count:#放置第九个皇后
if 1 not in free_queue[n-1]:
return
else:
for i in range(queue_count):
if free_queue[n-1][i]==1:
queue_board[n-1][i]='Q'
res.append([''.join(i.copy()) for i in queue_board])
queue_board[n-1][i]='.'
return
else:
for i in range(queue_count):
if free_queue[n-1][i]==1:
free_queue_new = [i.copy() for i in free_queue]
queue_board_new = [i.copy() for i in queue_board]
queue_board_new[n-1][i]='Q'
for m in range(queue_count-n):
#设置纵列为0
free_queue_new[n+m][i]=0
#设置横列为0（要不要无所谓）
if i+m+1<queue_count:
free_queue_new[n-1][i+m+1]=0
#设置斜率为1的列为0
if n+m<queue_count and i+m+1<queue_count:
free_queue_new[n+m][i+m+1]=0
#设置斜率为-1的列为0
if n+m<queue_count and i-m-1>=0:
free_queue_new[n+m][i-m-1]=0
set_queue(free_queue_new,queue_board_new,n+1)
return
free_queue=[[1 for i in range(queue_count)] for j in range(queue_count)]
queue_board=[['.' for i in range(queue_count)] for j in range(queue_count)]
set_queue(free_queue,queue_board,1)
return res题52（困难）：
分析：
解决了上一题，这题就是送啊
python代码：
class Solution:
def totalNQueens(self, n: int) -> int:
#n 皇后问题--》非线性--》选递归，
res=[]
queue_count=n
#设置皇后，递归函数，传当前可行位置+放置第几个
def set_queue(free_queue,queue_board,n):
if n<=0 or n>queue_count:
return
if n==queue_count:#放置第九个皇后
if 1 not in free_queue[n-1]:
return
else:
for i in range(queue_count):
if free_queue[n-1][i]==1:
queue_board[n-1][i]='Q'
res.append([''.join(i.copy()) for i in queue_board])
queue_board[n-1][i]='.'
return
else:
for i in range(queue_count):
if free_queue[n-1][i]==1:
free_queue_new = [i.copy() for i in free_queue]
queue_board_new = [i.copy() for i in queue_board]
queue_board_new[n-1][i]='Q'
for m in range(queue_count-n):
#设置纵列为0
free_queue_new[n+m][i]=0
#设置横列为0（要不要无所谓）
if i+m+1<queue_count:
free_queue_new[n-1][i+m+1]=0
#设置斜率为1的列为0
if n+m<queue_count and i+m+1<queue_count:
free_queue_new[n+m][i+m+1]=0
#设置斜率为-1的列为0
if n+m<queue_count and i-m-1>=0:
free_queue_new[n+m][i-m-1]=0
set_queue(free_queue_new,queue_board_new,n+1)
return
free_queue=[[1 for i in range(queue_count)] for j in range(queue_count)]
queue_board=[['.' for i in range(queue_count)] for j in range(queue_count)]
set_queue(free_queue,queue_board,1)
return len(res)题53（中等）：
分析：
python代码：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
#不用看也是动态规划啊，每一个现状等于之前状态加判断
res=0
n_len=len(nums)
n_list=[0 for i in range(n_len)]
for i in range(n_len):
n_list[i]=max(nums[i],n_list[i-1]+nums[i])
res=max(n_list)
return res题54（中等）：
分析：
会搞贪吃蛇小游戏的一个很清晰怎么搞
python代码：
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
row=len(matrix)
col=len(matrix[0])
cout=row*col
res=[]
#选则x，y作为当前位置
x,y=0,0
#和贪吃蛇一样选则p_x,p_y作为前进的方向
p_x,p_y=1,0
#定义终止转弯点
left,right,top,bottom=0,col-1,0,row-1
i=0
while i<cout:
res.append(matrix[y][x])
if x==right and y==top:
#到右上
if p_x==1:
top+=1
p_x,p_y=0,1
pass
if x==right and y==bottom:
#到右下
if p_y==1:
right-=1
p_x,p_y=-1,0
pass
if x==left and y==top:
#到左上
if p_y==-1:
left += 1
p_x,p_y=1,0
pass
if x==left and y==bottom:
#到左下
if p_x==-1:
bottom-=1
p_x,p_y=0,-1
pass
x+=p_x
y+=p_y
i+=1
return res题55（中等）：
分析：
之前没想到贪心，这次直接用贪心算法，（因为动态规划为n^2,时间复杂度高）
python代码：
class Solution:
def canJump(self, nums: List[int]) -> bool:
n_len=len(nums)
end,max_jump=0,0
for i in range(n_len):
if i>end:
return False
max_jump=max(max_jump,i+nums[i])
if max_jump>=n_len-1:
return True
if i==end:
end=max_jump
题56（中等）：
分析：
显然可以贪心也可以动态规划
python代码：
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
s_intervals=sorted(intervals,key=Solution.sort_rule)
res=[]
start,end=s_intervals[0][0],s_intervals[0][1]
for i in s_intervals:
#如果新区间和上一个区间没有交集，则直接将新区间加入结果集
if i[0]>end:
res.append([start,end])
start=i[0]
end=i[1]
end=max(end,i[1])
res.append([start, end])
return res
@staticmethod
def sort_rule(item):
return item[0]题57（中等）：
分析：
显然可以贪心也可以动态规划，其实就是上一题的变形
python代码：
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
new_i=intervals.copy()
new_i.append(newInterval)
s_intervals=sorted(new_i,key=Solution.sort_rule)
res=[]
start,end=s_intervals[0][0],s_intervals[0][1]
for i in s_intervals:
#如果新区间和上一个区间没有交集，则直接将新区间加入结果集
if i[0]>end:
res.append([start,end])
start=i[0]
end=i[1]
end=max(end,i[1])
res.append([start, end])
return res
@staticmethod
def sort_rule(item):
return item[0]
题58（简单）：
分析：
python代码：
class Solution:
def lengthOfLastWord(self, s: str) -> int:
word_list=s.split(' ')
word_list=[i for i in word_list if i !='']
return len(word_list[-1])题59（中等）：
分析：
这个螺旋我们做第二次了，如果会写贪吃蛇就能搞这个，如果会这个，再学一下图形界面就应该可以写一个贪吃蛇小游戏了，我之前做了纯c版贪吃蛇，还有qt的，可以看看我的其他博客内容
python代码：
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
#按顺序走要走n*n个数，
end=n*n
#设置x，y位置,p_x,p_y作为方向
x,y,p_x,p_y=0,0,1,0
#设置结果的初始值
res=[[0 for i in range(n)] for i in range(n)]
i=1
while i<=end:
res[y][x]=i
#在右上角
if p_x==1 and (x+p_x>=n or res[y+p_y][x+p_x]!=0 ):
p_x=0
p_y=1
#在右下角
if p_y==1 and (y+p_y>=n or res[y+p_y][x+p_x]!=0):
p_x=-1
p_y=0
#在左下角
if p_x==-1 and ( x+p_x<0 or res[y+p_y][x+p_x]!=0):
p_x=0
p_y=-1
#在左上角
if p_y==-1 and (y+p_y<0 or res[y+p_y][x+p_x]!=0 ):
p_x=1
p_y=0
i+=1
x+=p_x
y+=p_y
return res
题60（困难）：
分析：
这道题第一反应是暴力递归求排列再取值，其实没必要这样，主要是它要取第k个，我们想象1,2,3来说
如果k在【1,2】那么第一个数就是1，如果k在【3，4】就是2……
这个时候来判断第二个数字，有n-1种情况，每种情况之间间隔（n-2）！个，思路就来了
python代码：
class Solution:
def getPermutation(self, n: int, k: int) -> str:
if k==Solution.get_n_factorial(n):
return ''.join(str(i) for i in range(n,0,-1))
n_list=[Solution.get_n_factorial(i) for i in range(n-1,0,-1)]
res=''
num=0
leave=k
#num剩余取值
nums=[str(i) for i in range(n,0,-1)]
for index,value in enumerate(n_list):
num=math.ceil(leave/value)
leave=leave%value
res+=str(nums[len(nums)-num])
nums.remove(str(nums[len(nums)-num]))
if leave==0:
res=res+''.join(nums)
break
return res
@staticmethod
def get_n_factorial(n):
res=1
for i in range(1,n+1):
res*=i
return res题61（中等）：
分析：
python代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
#利用空间复杂度解决，将链表装进列表
node_list=[]
p=head
while p!=None:
node_list.append(p)
p=p.next
node_len=len(node_list)
if node_len==0:
return head
k_new=k%node_len
if k_new==0:
return head
node_list[-1].next=node_list[0]
head=node_list[-k_new]
node_list[-(k_new+1)].next=None
return head
题62（中等）：
分析：
python代码：
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
#思路就是动态数组嘛
auto_list=[[1 for j in range(n)] for i in range(m)]
for i in range(1,m):
for j in range(1,n):
a1,a2=0,0
if i-1>=0:
a1=auto_list[i-1][j]
if j-1>=0:
a2=auto_list[i][j-1]
auto_list[i][j]=a1+a2
return auto_list[-1][-1]题63（中等）：
分析
会这个差不多可以制作迷宫小游戏了
python代码：
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
#动态数组，和上一题差不多
#构造动态数组，obstacleGrid中有障碍为设置为0，没有设置为1
auto_list=[[0 for i in range(len(obstacleGrid[0]))] for j in range(len(obstacleGrid))]
for i in range(len(obstacleGrid)):
for j in range(len(obstacleGrid[0])):
if obstacleGrid[i][j]==0:
auto_list[i][j]=1
else:
auto_list[i][j]=0
#设置动态数组的值
for i in range(len(obstacleGrid)):
for j in range(len(obstacleGrid[0])):
#第一个位置必须是0
if i==0 and j==0:
continue
if auto_list[i][j]==0:
continue
a1,a2=0,0
if i-1>=0:
a1=auto_list[i-1][j]
if j-1>=0:
a2=auto_list[i][j-1]
auto_list[i][j]=a1+a2
return auto_list[-1][-1]题64（中等）：
分析：
python代码：
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
#动态规划，本质上和前面的题目是一样的
auto_list=grid.copy()
for i in range(len(auto_list)):
for j in range(len(auto_list[0])):
if i==0 and j==0:
#第一个就跳过就好了
continue
if i-1<0:
auto_list[i][j]+=auto_list[i][j-1]
continue
if j-1<0:
auto_list[i][j]+=auto_list[i-1][j]
continue
auto_list[i][j]+=min(auto_list[i-1][j],auto_list[i][j-1])
return auto_list[-1][-1]题65（困难）：
分析：
不得不说，这个有效数字判定规则很诡异，不过难度真不配困难
python代码：
class Solution:
def isNumber(self, s: str) -> bool:
s_stack=[]
dot_flag=0
sign_flag=0
e_flag=0
for i in s:
#如果为数字
if i in ('0','1','2','3','4','5','6','7','8','9'):
if dot_flag==1:
dot_flag=0
if e_flag==1:
e_flag=0
if sign_flag==1:
sign_flag=0
s_stack.append(i)
#如果为.
elif i=='.':
if s_stack==[] or s_stack==['+'] or s_stack==['-']:
dot_flag=1
if '.' in s_stack:
return False
if ('e' in s_stack) or ('E' in s_stack):
return False
s_stack.append('.')
#如果为+-
elif i=='+' or i=='-':
#如果不是空或者前面不是e就0
if s_stack==[]:
sign_flag=1
s_stack.append(i)
elif s_stack[-1]=='e' or s_stack[-1]=='E':
s_stack.append(i)
else:
return False
#如果为e或者E
elif i=='e' or i=='E':
print(s_stack)
e_flag=1
if 'e' in s_stack or 'E' in s_stack:
return False
if s_stack==[] or s_stack==['+'] or s_stack==['-']:
return False
if s_stack==['.'] or s_stack==['+','.'] or s_stack==['-','.']:
return False
s_stack.append(i)
else:
return False
if dot_flag==1:
return False
if e_flag==1:
return False
if sign_flag==1:
return False
return True
题66（简单）：
python代码：
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
s_str=''.join([str(i) for i in digits])
n=str(int(s_str)+1)
n_str=list(n)
res=[int(i) for i in n_str]
return res
题67（简单）：
python代码：
class Solution:
def addBinary(self, a: str, b: str) -> str:
a_to_i=int(a,2)
b_to_i=int(b,2)
res_10=a_to_i+b_to_i
res_2=bin(res_10)
res=str(res_2)[2:]
return res题68（困难）：
分析：
感觉这题也不配困难啊，思路清晰点都随便做
python代码：
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
res=[]
tmp_line=[]
now_len=0
#遍历一遍，确定每一行塞哪些单词
for index,value in enumerate(words):
#首先判断是否可以塞下这个单词
#now_len+=单词长度+1
if now_len+len(value)<=maxWidth:
#如果可以塞下这个单词，那么直接塞进去
now_len+=len(value)+1
tmp_line.append(value)
else:
#如果塞不下
kg_num=maxWidth-now_len+1
i=0
while kg_num>0:
#从第一个的后面加空格
tmp_line[i]+=' '
kg_num-=1
i+=1
if i>=len(tmp_line)-1:
i=0
line=' '.join(tmp_line)
res.append(line)
tmp_line=[value]
now_len=len(value)+1
#如果是最后一个单词
if index==len(words)-1:
line=' '.join(tmp_line)+' '*(maxWidth-now_len+1)
res.append(line)
return res
题69（简单）：
python代码：
class Solution:
def mySqrt(self, x: int) -> int:
for i in range(1,x+2):
if i*i>x:
return i-1
return 0
题70（简单）：
python代码：
class Solution:
def climbStairs(self, n: int) -> int:
#使用动态数组
auto_list=[1 for i in range(n+1)]
for i in range(1,n+1):
if i==1:
auto_list[i]=1
continue
auto_list[i]=auto_list[i-1]+auto_list[i-2]
return auto_list[-1]