# @lc code=start
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
mid=0
n=len(matrix)
for i in range(n):
for j in range(i):
mid = matrix[i][j]
matrix[i][j] = matrix[j][i]
matrix[j][i] = mid
for i in range(n):
for j in range(n//2):
mid=matrix[i][j]
matrix[i][j]=matrix[i][n-j-1]
matrix[i][n-j-1] = mid
# @lc code=end
# [46] 全排列
#
# @lc code=start
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
import copy
def subpermute(nums,index):
if index==0:
return [[nums[0]]]
else:
rev=subpermute(nums,index-1)
res=list()
for i in range(len(rev)):
#print(rev[i])
for j in range(len(rev[i])+1):
if j==len(rev[i]) or rev[i][j]!=nums[index]:
mid=copy.deepcopy(rev[i])
#print(mid)
mid.insert(j,nums[index])
if mid not in res:
res.append(mid)
return res
index=len(nums)-1
return subpermute(nums,index)
# @lc code=start
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
lens=len(nums)
maxs=nums[0]
for i in range(lens):
for j in range(0,i+1):
maxs=max(maxs,sum(nums[j:i+1]))
return maxs
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
lens=len(nums)
maxs=nums[0]
n=0
for i in range(lens):
n=max(n+nums[i],nums[i])
maxs=max(maxs,n)
return maxs
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
maxPos, end, step = 0, 0, 0
for i in range(n - 1):
if maxPos >= i:
maxPos = max(maxPos, i + nums[i])
if i == end:
end = maxPos
step += 1
return step
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
示例 3:
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输出: false
思路：回溯算法（N叉树）
# @lc code=start
class Solution:
def isMatch(self,s: str, p: str) -> bool:
if s=="" and p=="":
return True
if p=="":
return False
len1=len(s)
n1=0
m1=""
len2=len(p)
for i in range(1,len2):
if p[i]=="*" and p[i-1]=="*":
continue
else :
m1=m1+p[i-1]
n1=1+n1
p=m1+p[-1]
len2=len(p)
def submacth(i,j):
if i==len1 and j==len2:
return True
if j==len2:
return False
if i==len1 and (p[j:]!="*"*len(p[j:])):
#print(False)
return False
if p[j]!="*" :
if p[j]=="?"or p[j]==s[i]:
i=i+1
j=j+1
return submacth(i,j)
else:
#print(False)
return False
if p[j]=="*" and j==len2-1:
#print("3333")
l=len1
h=len2
return submacth(l,h)
if p[j]=="*" and j<len2-1:
for m in range(i,len1):
if s[m]==p[j+1] or p[j+1]=="?":
#print(m,j+1,"hh")
l=m+1
h=j+2
if submacth(l,h):
return True
return False
return submacth(0,0)
需改进：
动态规划步骤：
确定dp[i][j]状态含义
确定 状态转移方程
确定dp初始值
参考官方题解：动态规划问题dp[i][j]表示s的前i个字符和 p的前j个字符是否匹配。在进行状态转移时，我们可以考虑模式 p 的第 j 个字符 pj，与之对应的是字符串 s 中的第 i 个字符si：
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, n + 1):
if p[i - 1] == '*':
dp[0][i] = True
else:
break
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i][j - 1] | dp[i - 1][j]
elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2:
return s
max_len = 1
begin = 0
# dp[i][j] 表示 s[i..j] 是否是回文串
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True
# 递推开始
# 先枚举子串长度
for L in range(2, n + 1):
# 枚举左边界，左边界的上限设置可以宽松一些
for i in range(n):
# 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
j = L + i - 1
# 如果右边界越界，就可以退出当前循环
if j >= n:
break
if s[i] != s[j]:
dp[i][j] = False
else:
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
# 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if dp[i][j] and j - i + 1 > max_len:
max_len = j - i + 1
begin = i
return s[begin:begin + max_len]
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
这份模板很重要，后面做回溯法的题目都靠它了！
实例： 解数独 （回溯法）
#回溯法
"""
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，
按选优条件向前搜索，以达到目标。但当探索到某一步时，
发现原先选择并不优或达不到目标，就退回一步重新选择，
这种走不通就退回再走的技术为回溯法，
而满足回溯条件的某个状态的点称为“回溯点”。
"""
# @lc code=start
class Solution:
def solveSudoku(self, board)->None:
"""
Do not return anything, modify board in-place instead.
"""
#判断改行、列、3*3小格子是否满足数独规则：
def isRowSafe(row,value):
for i in range(9):
if board[row][i]==value:
return False
return True
def isColSafe(col,value):
for i in range(9):
if board[i][col]==value:
return False
return True
def isSmallboxSafe(row,col,value):
inirow=row//3*3
inicol=col//3*3
for i in range(3):
for j in range(3):
if board[i+inirow][j+inicol]==value:
return False
return True
#判断该位置是否可行
def isSafe(row,col,value):
return isRowSafe(row,value) and isColSafe(col,value) and isSmallboxSafe(row,col,value)
#解数独，结束条件（回溯法，递归调用）
def solve(row,col):
if row==8 and col ==9:
return True
if col ==9:
col=0
row+=1
if board[row][col]!=".":
return solve(row,col+1)
for i in range(1,10):
if isSafe(row,col,str(i)):
i=str(i)
board[row][col] = i
if solve(row, col+1):
return board
board[row][col]="."
return False
solve(0,0)
print(board)
