Skip to content

Instantly share code, notes, and snippets.

@cmychina

cmychina/leetcode_二分查找_搜索旋转排序数组.py Secret

Created July 14, 2020 09:08
Show Gist options
  • Save cmychina/0fb110976fa38635d94d7a24e0053efd to your computer and use it in GitHub Desktop.
Save cmychina/0fb110976fa38635d94d7a24e0053efd to your computer and use it in GitHub Desktop.
Download ZIP
leetcode
Raw
leetcode_二分查找_搜索旋转排序数组.py
class Solution:
def search(self, nums, target):
def find_rotateindex(l, r):
if (nums[l] < nums[r]):
return 0
while (l <= r):
rotate = (l + r) // 2
if (nums[rotate] < nums[rotate - 1]):
return rotate
if (nums[rotate] > nums[r]):
l = rotate + 1
else:
r = rotate - 1
# print(find_rotateindex(0,len(nums)-1))
def find(l, r):
while (l <= r):
mid = (l + r) // 2
if (nums[mid] == target):
return mid
if (nums[mid] > target):
r = mid - 1
else:
l = mid + 1
return -1
n = len(nums)
if (n == 0):
return -1
if (n == 1):
return 0 if (nums[0] == target) else -1
rotateindex = find_rotateindex(0, n - 1)
if (rotateindex == 0):
return find(0, n - 1)
if (target >= nums[0]):
return find(0, rotateindex)
else:
return find(rotateindex, n - 1)
class Solution:
def search(self, nums, target):
if len(nums) == 0:
return -1
left, right = 0, len(nums) - 1
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] < nums[mid]:
if nums[left] <= target and target <= nums[mid]:
right = mid
else:
left = mid
else:
if nums[mid] <= target and target <= nums[right]:
left = mid
else:
right = mid
if nums[left] == target:
return left
if nums[right] == target:
return right
return -1
Raw
leetcode_动态规划_不同路径.py
def uniquePathsWithObstacles(obstacleGrid):
m=len(obstacleGrid)
n=len(obstacleGrid[0])
#起点与终点的限制
if obstacleGrid[0][0] == 1:
return 0
if obstacleGrid[m-1][n-1] == 1:
return 0
#初始点无障碍，则初始化为1
obstacleGrid[0][0] = 1
#初始化行列
#对于每行的第一个点，只要当前为0且上一行的点为1则设置为1,表示可以走到，否则设置0。
for i in range(1,m):
obstacleGrid[i][0]=int(obstacleGrid[i][0]==0 and obstacleGrid[i-1][0]==1)
for j in range(1, n):
obstacleGrid[0][j]=int(obstacleGrid[0][j]==0 and obstacleGrid[0][j-1]==1)
#从(1,1)点开始遍历
for i in range(1,m):
for j in range(1,n):
#0表示无障碍
if obstacleGrid[i][j] == 0:
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
#有障碍设置为0，表示无路径通过
else:
obstacleGrid[i][j] = 0
return obstacleGrid[m-1][n-1]
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [1] + [0] * n
for i in range(0, m):
for j in range(0, n):
dp[j] = 0 if obstacleGrid[i][j] else dp[j] + dp[j - 1]
return dp[-2]
Raw
leetcode_动态规划_不同路径3.py
class Solution:
def uniquePathsIII(self, grid):
def dfs(v,left):
visited[v//C][v%C] = True
left -= 1
if left == 0 and v == end:
visited[v//C][v%C] = False
return 1
res = 0
for i,j in d:
tmp_x = v//C + i
tmp_y = v%C + j
if 0 <= tmp_x < R and 0 <= tmp_y < C and grid[tmp_x][tmp_y] == 0 and not visited[tmp_x][tmp_y]:
res += dfs(tmp_x * C + tmp_y,left)
visited[v//C][v%C] = False
return res
R = len(grid)
C = len(grid[0])
visited = [[False for _ in range(C)] for _ in range(R)]
start = 0
end = 0
left = R * C
d = [(-1, 0), (0, -1), (1, 0), (0, 1)]
for i in range(R):
for j in range(C):
if grid[i][j] == 1:
start = i * C + j
grid[i][j] = 0
elif grid[i][j] == 2:
end = i * C + j
grid[i][j] = 0
elif grid[i][j] == -1:
left -= 1
return dfs(start,left)
if __name__=="__main__":
s=Solution()
n=[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
print(s.uniquePathsIII(n))
Raw
leetcode_动态规划_买卖股票最佳时间.py
"""
1.所在天数
2.剩余交易次数
3.持有状态
dp[i][k][0 or 1]
买进算一次交易
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
"""
#1.不限定交易次数
def maxProfit(prices):
if not prices:
return 0
n=len(prices)
dp=[[0]*2]*n
dp[0][1]=-prices[0]
for i in range(1,n):
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
dp[i][1]=max(dp[i-1][1],-prices[i])
return dp[n-1][0]
#2.限定k=2次交易
def maxProfit(prices):
if not prices:
return 0
n=len(prices)
dp=[[[0]*2 for _ in range(3)] for _ in range(n)]
for k in range(3):
dp[0][k][1]=-float('inf')
for i in range(n):
dp[i][0][1]=-float('inf')
dp[0][1][1]=-prices[0]
for i in range(1,n):
for k in range(1,3):
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
return max(dp[n-1][1][0],dp[n-1][2][0])
#3.含冷冻期
def maxProfit(prices):
if not prices:
return 0
n=len(prices)
dp=[[0]*2 for _ in range(n)]
dp[0][0]=0
dp[0][1]=-prices[0]
for i in range(1,n):
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
#i-2天卖出,i-1冷冻,i购入
dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i])
return dp[n-1][0]
#4.手续费
def maxProfit(prices,fee):
if not prices:
return 0
n = len(prices)
dp = [[0] * 2] * n
dp[0][1] = -prices[0] - fee ##初始持有股票的收益
dp[0][0] = 0
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee) ##buy
return dp[n - 1][0]
Raw
leetcode_动态规划_分割回文串.py
class Solution:
def partition(self, s: str):
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(i + 1):
if (s[i] == s[j]) and (i - j <= 2 or dp[j + 1][i - 1]):
dp[j][i] = True
res = []
def helper(i, tmp):
if i == n:
res.append(tmp)
for j in range(i, n):
if dp[i][j]:
helper(j + 1, tmp + [s[i: j + 1]])
helper(0, [])
return res
Raw
leetcode_动态规划_动态规划.py
class Solution:
def calculateMinimumHP(self, dungeon) -> int:
n, m = len(dungeon), len(dungeon[0])
BIG = 10**9
dp = [[BIG] * (m + 1) for _ in range(n + 1)]
dp[n][m - 1] = dp[n - 1][m] = 1
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j], 1)
return dp[0][0]
def Mudane(self,dungeon):
M=len(dungeon)
N=len(dungeon[0])
#dp[i][j]表示达到(i,j)需要的最低健康点数
dp=[[0]*N for _ in range(M)]
dp[-1][-1]=max(1,1-dungeon[-1][-1])
for i in range(N-2,-1,-1):
dp[-1][i]=max(1,dp[-1][i+1]-dungeon[-1][i])
for i in range(M-2,-1,-1):
dp[i][-1]=max(1,dp[i+1][-1]-dungeon[i][-1])
for i in range(M-2,-1,-1):
for j in range(N-2,-1,-1):
dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])-dungeon[i][j],1)
print(dp)
return dp[0][0]
if __name__=="__main__":
S=Solution()
m= [[-2,-3,3],[-5,-10,1],[10,30,-5]]
print(S.calculateMinimumHP(m))
Raw
leetcode_动态规划_单词拆分.py
class Solution:
def wordBreak(self, s: str, wordDict) -> bool:
n=len(s)
dp=[False]*(n+1)
dp[0]=True
for i in range(n):
for j in range(i+1,n+1):
if(dp[i] and (s[i:j] in wordDict)):
dp[j]=True
return dp
def Mundane(self,s,wordDict):
n = len(s)
if not wordDict: return not s
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i - 1, -1, -1):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
return dp[-1]
if __name__=="__main__":
S=Solution()
s = "catsandog"
wordDict = ["cats", "and", "og"]
print(S.wordBreak(s,wordDict))
Raw
leetcode_动态规划_可被3整除的最大和.py
"""
给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
"""
Raw
leetcode_动态规划_恢复空格.py
class Solution:
def respace(self, dictionary, sentence):
d = {}.fromkeys(dictionary)
n = len(sentence)
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i - 1] + 1
for j in range(i):
if sentence[j:i] in dictionary:
dp[i] = min(dp[i], dp[j])
return dp[-1]
Raw
leetcode_动态规划_打家劫舍.py
class Solution:
def rob(self, nums) -> int:
##怎么让收尾不相连？？？？
n = len(nums)
if n == 0:
return 0
elif 1 <= n <= 3:
return max(nums)
else:
##不考虑最后一个
dp1 = [0] * n
dp1[0] = nums[0]
dp1[1] = max(nums[0], nums[1])
for i in range(2, n - 1):
dp1[i] = max(nums[i] + dp1[i - 2], dp1[i - 1])
# 不考虑第一个
dp2 = [0] * n
dp2[1] = nums[1]
dp2[2] = max(nums[1], nums[2])
for i in range(3, n):
dp2[i] = max(nums[i] + dp2[i - 2], dp2[i - 1])
return max(max(dp1), max(dp2))
Raw
leetcode_动态规划_最大子序和.py
def maxSum(nums):
n=len(nums)
if not nums:
return 0
#dp[i]表示以i结尾的最大连续子数组的和
dp=[0]*n
dp[0]=nums[0]
for i in range(1,n):
#有一种情况是dp[i-1]<0,因此对dp[i]没有增益，所以直接取nums[i]
dp[i]=max(nums[i],dp[i-1]+nums[i])
return max(dp)
Raw
leetcode_动态规划_最大正方形.py
"""
理解为什么是dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
可以从木桶短板理论角度，最小的那个边决定新正方形的边长
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
dp(i, j) 是以 matrix(i - 1, j - 1) 为 右下角 的正方形的最大边长
"""
class Solution:
def maximalSquare(self, matrix) -> int:
if(not matrix):
return 0
m=len(matrix)
n=len(matrix[0])
res=0
dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if(matrix[i-1][j-1]=="1"):
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
res=max(dp[i][j],res)
return res*res
Raw
leetcode_动态规划_最大矩形.py
"""
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
"""
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
row = len(matrix)
col = len(matrix[0])
height = [0] * (col + 2)
res = 0
for i in range(row):
stack = []
for j in range(col + 2):
if 1<=j<=col:
if matrix[i][j-1] == "1":
height[j] += 1
else:
height[j] = 0
while stack and height[stack[-1]] > height[j]:
cur = stack.pop()
res = max(res, (j - stack[-1] - 1)* height[cur])
stack.append(j)
return res
Raw
leetcode_动态规划_最长公共子序列.py
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
if not text1 or not text2:
return 0
n = len(text1)
m = len(text2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]
if __name__=="__main__":
s=Solution()
text1 = "abcde"
text2 = "ace"
print(s.longestCommonSubsequence(text1,text2))
Raw
leetcode_动态规划_最长回文子串.py
class Solution:
#def longestPalindrome(self,s):
#dp[i][j]表示s[i][j]是否为回文子串?
def dp(self,s):
n=len(s)
res=""
max_len=float("-inf")
dp=[[0]*n for _ in range(n)]
#任何一个单字母都是回文串
for i in range(n):
dp[i][i]=1
for i in range(1,n):
for j in range(i,-1,-1):
if s[i]==s[j] and (i-j<2 or dp[j+1][i-1]):
dp[j][i]=1
if dp[j][i] and max_len<i-j+1:
res=s[j:i+1]
max_len=i+1-j
return res
def centerSpread(self,s):
n=len(s)
self.res = 0
self.ans=""
def helper(i,j):
while i>=0 and j<n and s[i]==s[j]:
i-=1
j+=1
#self.res=max(self.res,j-i-1)
if j-i-1>self.res:
self.res=j-i-1
self.ans=s[i+1:j]
for i in range(n-1):
helper(i,i)
helper(i,i+1)
print(self.res)
return self.ans
def Mundane(self,s):
n=len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(i,-1,-1):
if s[i]==s[j] or (i-j<=2 or dp[j+1][i-1]==True):
dp[j][i]=True
if __name__=="__main__":
s=Solution()
st="abababa"
print(s.centerSpread(st))
Raw
leetcode_动态规划_最长回文子序列.py
def maxPalindrome(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
for i in range(n):
dp[i][i] = 1
for j in range(i - 1, -1, -1):
if s[j] == s[i]:
dp[j][i] = 2 + dp[j + 1][i - 1]
else:
dp[j][i] = max(dp[j + 1][i], dp[j][i - 1])
return dp[0][n - 1]
Raw
leetcode_动态规划_最长有效括号.py
"""
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
"""
class Solution:
def longestValidParentheses(self, s):
stack=[-1]
max_len=float("-inf")
for i in range(len(s)):
if s[i]=="(":
stack.append(i)
else:
stack.pop()
#此时空栈说明是第一个右括号
if not stack:
stack.append(i)
max_len=max(max_len,i-stack[-1])
return max_len
def Mundane(self,s):
if not s:
return 0
n = len(s)
dp = [0] * n
res = 0
for i in range(n):
if i > 0 and s[i] == ")":
if s[i - 1] == "(":
dp[i] = dp[i - 2] + 2
# i-dp[i-1]-1表示与i处右括号匹配的左括号的位置
elif s[i - 1] == ")" and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
return dp
if __name__ == "__main__":
s = Solution()
w1="()()))"
#print(s.longestValidParentheses(w1))
print(s.Mundane(w1))
Raw
leetcode_动态规划_最长重复子串.py
class Solution:
def findLength(self, A, B) :
dp=[[0]*(len(B)+1) for _ in range(len(A)+1)]
res=0
ans=''
for i in range(len(A)):
for j in range(len(B)):
if A[i]==B[j]:
dp[i+1][j+1]=dp[i][j]+1
if dp[i+1][j+1]>res:
res=dp[i+1][j+1]
flag=i+1
return A[flag-res:flag]
def Mundane(self, A, B) :
dp = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
res = 0
for i in range(len(A)):
for j in range(len(B)):
if A[i] == B[j]:
dp[i + 1][j + 1] = dp[i][j] + 1
res = max(dp[i + 1][j + 1], res)
return res
if __name__=="__main__":
s=Solution()
A=[1, 2, 3, 2, 1]
B=[3, 2, 1, 4, 7]
print(s.Mundane(A,B))
Raw
leetcode_动态规划_最长重复子数组.py
class Solution:
def findLength(self, A,B):
n=len(A)
m=len(B)
dp=[[0]*(m+1) for _ in range(n+1)]
res=0
for i in range(1,n+1):
for j in range(1,m+1):
if A[i-1]==B[j-1]:
dp[i][j]=dp[i-1][j-1]+1
res=max(dp[i][j],res)
return res
if __name__=="__main__":
s=Solution()
A=[0, 1, 1, 1, 1]
B=[1, 0, 1, 0, 1]
print(s.findLength(A,B))
Raw
leetcode_动态规划_正则表达式匹配.py
def isMatchdp(s,p):
S=len(s)
P=len(p)
dp = [[False] * (P + 1) for _ in range(S + 1)]
dp[0][0]=True
#初始化
for i in range(P):
if p[i]=="*" and dp[0][i-1]:
dp[0][i+1]=True
for i in range(S):
for j in range(P):
if p[j]==s[i] or p[j] in {s[i],"."}:
dp[i+1][j+1]=dp[i][j]
elif p[j]=="*":
if p[j-1]!=s[i]:
dp[i+1][j+1]=dp[i+1][j-1]
if p[i-1]==s[i] or p[j-1]==".":
dp[i+1][j+1]=(dp[i][j+1] or dp[i+1][j] or dp[i+1][j-1])
return dp[-1][-1]
def isMatch(s, p):
S = len(s)
P = len(p)
memo = {}
def dp(i, j):
if ((i, j) in memo):
return memo[(i, j)]
if (j == P):
return i == S
#当前是否匹配
pre = i < S and p[j] in {s[i], "."}
if (j <= P - 2 and p[j + 1] == "*"):
#dp(i,j+2)表示*匹配前面0个，dp(1+1,j)表示匹配1个或多个
tmp = dp(i, j + 2) or pre and dp(i + 1, j)
# else:
# tmp = pre and dp(i + 1, j + 1)
memo[(i, j)] = tmp
return tmp
return dp(0, 0)
s = "aa"
p = "a*"
print(isMatchdp(s,p))
print(isMatch(s,p))
Raw
leetcode_动态规划_编辑距离.py
"""
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
dp[i][j]表示word1[:i]到word2[:j]之间操作需要的次数
插入一个字符 dp[i][j - 1] 插入一个和j相同的
删除一个字符 dp[i - 1][j] 把i的词删除掉
替换一个字符 dp[i - 1][j - 1] 即把i j 替换成相等的
"""
class Solution:
def minDist(self,word1,word2):
n = len(word1)
m = len(word2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for j in range(1, m + 1):
dp[0][j] = dp[0][j - 1] + 1
for i in range(1, n + 1):
dp[i][0] = dp[i - 1][0] + 1
for i in range(1, n + 1):
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
return dp[-1][-1]
if __name__ == "__main__":
s = Solution()
w1="distance"
w2="springbok"
print(s.minDist(w1,w2))
Raw
leetcode_动态规划_解码方法.py
class Solution:
def numDecodings(self, s: str) -> int:
n=len(s)
if(not s or s[0]=="0"):
return 0
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(1,n):
if(s[i]=="0"):
if(s[i-1]=="1" or s[i-1]=="2"):
dp[i+1]=dp[i-1]
else:
return 0
else:#s[i]!=0
if(s[i-1]=="1" or (s[i-1]=="2" and "1"<=s[i]<="6")):
dp[i+1]=dp[i]+dp[i-1]
else:
dp[i+1]=dp[i]
return dp[-1]
Raw
leetcode_回溯_不用路径III.py
class Solution:
def uniquePathsIII(self, grid):
ans = [0]
step = 0
M, N = len(grid), len(grid[0])
def dfs(x, y, M, N, step):
if (x < 0 or x >= M or y < 0 or y >= N or grid[x][y] == -1):
return
if (grid[x][y] == 2) and (step==0):
ans[0] += 1
return
grid[x][y] = -1
dfs(x + 1, y, M, N, step - 1)
dfs(x - 1, y, M, N, step - 1)
dfs(x, y + 1, M, N, step - 1)
dfs(x, y - 1, M, N, step - 1)
grid[x][y] = 0
for i in range(M):
for j in range(N):
if (grid[i][j] == 1):
x, y = i, j
if (grid[i][j] == 0):
step += 1
dfs(x, y, M, N, step + 1)
return ans[0]
class Solution:
def uniquePathsIII(self, grid) -> int:
cnt = 0
start_x = start_y = 0
self.end_x = self.end_y = 0
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
cnt += 1
elif grid[i][j] == 1:
start_x = i
start_y = j
cnt += 1
elif grid[i][j] == 2:
self.end_x = i
self.end_y = j
cnt += 1
self.res = 0
grid[start_x][start_y] = -1
self.dfs(grid, m, n, start_x, start_y, cnt, 0)
return self.res
def dfs(self, grid, m, n, x, y, cnt, step):
# 终止条件
if x == self.end_x and y == self.end_y and step == cnt - 1:
self.res += 1
return
for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != -1:
tmp = grid[nx][ny]
grid[nx][ny] = -1
self.dfs(grid, m, n, nx, ny, cnt, step + 1)
grid[nx][ny] = tmp
Raw
leetcode_回溯_全排列.py
class Solution:
"""
不包含重复数字的
"""
def permute(self, nums):
n=len(nums)
res=[]
visited=set()
def dfs(tmp):
if len(tmp)==n:
res.append(tmp)
return
for i in range(len(nums)):
if nums[i] not in visited:
visited.add(nums[i])
dfs(tmp+[nums[i]])
visited.remove(nums[i])
dfs([])
return res
if __name__ == "__main__":
s = Solution()
nums=[1,2,3]
print(s.permute(nums))
Raw
leetcode_回溯_全排列II.py
class Solution:
"""
包含重复数字的，返回所有不重复的排列
"""
def permuteUnique(self, nums):
n = len(nums)
res = []
visited = set()
def dfs(tmp):
if len(tmp) == n:
res.append(tmp)
return
for i in range(len(nums)):
if i in visited or (i>0 and i-1 not in visited and nums[i]==nums[i-1]):
continue
visited.add(i)
dfs(tmp + [nums[i]])
visited.remove(i)
dfs([])
return res
if __name__ == "__main__":
s = Solution()
nums = [1, 1, 2]
print(s.permuteUnique(nums))
Raw
leetcode_回溯_单词搜索.py
class Solution:
def exist(self,board, word):
m = len(board)
n = len(board[0])
self.visited=set()
self.path=[]
def dfs(i, j, k):
if not 0 <= i < m or not 0 <= j < n or board[i][j] != word[k] or (i, j) in self.visited:
return False
if board[i][j] == word[k] and k == len(word) - 1:
self.path.append((i, j))
return True
self.visited.add((i,j))
self.path.append((i, j))
return dfs(i + 1, j, k + 1) or \
dfs(i - 1, j, k + 1) or \
dfs(i, j + 1, k + 1) or \
dfs(i, j - 1, k + 1)
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
if dfs(i, j,0):
print(self.path)
return True
class Solution:
def exist(self, board, word: str) -> bool:
row = len(board)
col = len(board[0])
def helper(i, j, k, visited):
if k == len(word):
return True
for x, y in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
tmp_i = x + i
tmp_j = y + j
if 0 <= tmp_i < row and 0 <= tmp_j < col and (tmp_i, tmp_j) not in visited and board[tmp_i][tmp_j] == word[k]:
visited.add((tmp_i, tmp_j))
if helper(tmp_i, tmp_j, k + 1, visited):
return True
visited.remove((tmp_i, tmp_j)) # 回溯
return False
for i in range(row):
for j in range(col):
if board[i][j] == word[0] and helper(i, j, 1, {(i, j)}):
return True
return False
class Solution:
def exist(self, board, word: str) -> bool:
self.m,self.n=len(board),len(board[0])
def dfs(i,j,s):
if not s:
return True
if not (0<=i<self.m and 0 <=j<self.n and board[i][j]==s[0]):
return False
tmp=board[i][j]
board[i][j]=''
res=dfs(i-1,j,s[1:]) or dfs(i+1,j,s[1:]) or dfs(i,j-1,s[1:]) or dfs(i,j+1,s[1:])
board[i][j]=tmp
return res
for i in range(self.m):
for j in range(self.n):
if board[i][j]==word[0]:
if dfs(i,j,word):
return True
return False
if __name__=="__main__":
s=Solution()
board =[
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']
]
word='ABFCEE'
print(s.exist(board,word))
Raw
leetcode_回溯_子集.py
"""
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
"""
class Solution:
def subsets(self, nums):
res=[]
n=len(nums)
def backtrack(i,tmp):
res.append(tmp)
for j in range(i,n):
backtrack(j+1,tmp+[nums[j]])
backtrack(0,[])
return res
if __name__ == "__main__":
s = Solution()
nums=[1,2,3]
print(s.subsets(nums))
Raw
leetcode_回溯_子集II.py
"""
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
"""
class Solution:
def subsets(self, nums):
res=[]
n=len(nums)
nums.sort()
def backtrack(i,tmp):
res.append(tmp)
for j in range(i,n):
if j>i and nums[j]==nums[j-1]:
continue
backtrack(j+1,tmp+[nums[j]])
backtrack(0,[])
return res
if __name__ == "__main__":
s = Solution()
nums=[4,4,4,1,4]
print(s.subsets(nums))
Raw
leetcode_回溯_幂集.py
class Solution:
def subsets(self, nums):
n=len(nums)
res=[]
def backtrack(i,tmp):
res.append(tmp)
for j in range(i,n):
backtrack(j+1,tmp+[nums[j]])
backtrack(0,[])
return res
Raw
leetcode_回溯_有重复字符串的排列组合.py
"""
S = "qqe"
["eqq","qeq","qqe"]
"""
class Solution:
def permutation(self, S: str):
S = sorted(S)
n=len(S)
res = []
seen = [0] * len(S)
def back(tmp):
if len(tmp) == n:
res.append(tmp)
return
for j in range(n):
if seen[j]:
continue
#注意此处约束
if j > 0 and S[j] == S[j-1] and not seen[j-1]:
continue
seen[j] = 1
back(tmp+S[j])
seen[j] = 0
back("")
return res
Raw
leetcode_回溯_第k个排列.py
class Solution:
def getPermutation(self, n: int, k: int) -> str:
import math
num = [str(i) for i in range(1, n+1)]
res = ""
n -= 1
while n > -1:
t = math.factorial(n)
loc = math.ceil( k / t) - 1
res += num[loc]
num.pop(loc)
k %= t
n -= 1
return res
if __name__ == "__main__":
s = Solution()
n = 4
k = 9
print(s.getPermutation(n,k))
Raw
leetcode_回溯_组合.py
"""
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
"""
class Solution:
def combine(self, n, k):
res = []
def backtrack(i, tmp):
if len(tmp) == k:
res.append(tmp)
return
for j in range(i, n + 1):
backtrack(j + 1, tmp + [j])
backtrack(1, [])
return res
if __name__ == "__main__":
s = Solution()
n=4
k=2
print(s.combine(n,k))
Raw
leetcode_回溯_组合总和.py
"""
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
"""
class Solution:
def combinationSum(self, candidates,target):
candidates.sort()
n=len(candidates)
res=[]
def backtrack(i,tmp):
if sum(tmp)==target:
res.append(tmp)
return
for j in range(i,n):
if candidates[j]+sum(tmp)>target:
break
backtrack(j,tmp+[candidates[j]])
backtrack(0,[])
return res
if __name__ == "__main__":
s = Solution()
nums = [2,3,6,7]
target=7
print(s.combinationSum(nums,target))
Raw
leetcode_回溯_组合总和II.py
"""
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
"""
class Solution:
def combinationSum(self, candidates,target):
candidates.sort()
n=len(candidates)
res=[]
def backtrack(i,tmp):
if sum(tmp)==target:
res.append(tmp)
return
for j in range(i,n):
if candidates[j]+sum(tmp)>target:
break
if j>i and candidates[j]==candidates[j-1]:
print(j)
continue
backtrack(j+1,tmp+[candidates[j]])
backtrack(0,[])
return res
if __name__ == "__main__":
s = Solution()
candidates = [10,1,2,7,6,1,5]
target=8
print(s.combinationSum(candidates,target))
Raw
leetcode_回溯_给表达式添加运算符.py
class Solution:
def addOperators(self, num: str, target: int):
if not num:
return []
result = []
make = ['', '+', '-', '*']
def trackback(nums, i, item):
if i == len(nums) - 1:
if eval(item) == target:
result.append(item)
return
if i == 0:
item = nums[0]
for m in make:
if item[-1] == '0' and m == '':
continue
trackback(nums, i+1, item+ m + nums[i+1])
trackback(num, 0, '')
return result
Raw
leetcode_回溯_黄金矿工.py
class Solution:
def getMaximumGold(self, grid):
m,n=len(grid),len(grid[0])
def dfs(x,y):
ans=0
path=set()
tmp=grid[x][y]
grid[x][y]=0
for i,j in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
if 0<=i<m and 0<=j<n and grid[i][j]>0:
cur,p=dfs(i,j)
if cur>ans:
ans=cur
path=p
grid[x][y]=tmp
path.add((x,y))
return ans+tmp,path
sean=set()
ans=0
for i in range(m):
for j in range(n):
if grid[i][j]!=0 and (i,j) not in sean:
cur,path=dfs(i,j)
if cur>ans:
ans=cur
sean=path
return ans
def Mundane(self,grid):
direction = [(0, 1), (0, -1), (-1, 0), (1, 0)]
n = len(grid)
m = len(grid[0])
self.profit = 0
def dfs(x, y, cur, visited):
cur += grid[x][y]
self.profit = max(cur, self.profit)
for dx, dy in direction:
x_n = x + dx
y_n = y + dy
if 0 <= x_n < n and 0 <= y_n < m and grid[x_n][y_n] > 0 and (x_n, y_n) not in visited:
visited.append((x_n, y_n))
dfs(x_n, y_n, cur, visited)
visited.pop()
for i in range(n):
for j in range(m):
if grid[i][j] > 0:
dfs(i, j, 0, [(i, j)])
return self.profit
def getMaximumGold(self, grid):
self.profit = 0
L1 = len(grid)
L2 = len(grid[0])
def backtrack(i, j, cur):
if i < 0 or j < 0 or i > L1 - 1 or j > L2 - 1 or grid[i][j] == 0:
if cur >= self.profit:
self.profit = cur
return
tmp = grid[i][j]
grid[i][j] = 0
backtrack(i + 1, j, cur + tmp)
backtrack(i - 1, j, cur + tmp)
backtrack(i, j + 1, cur + tmp)
backtrack(i, j - 1, cur + tmp)
grid[i][j] = tmp
for i in range(L1):
for j in range(L2):
backtrack(i, j, 0)
return self.profit
Raw
leetcode_排序_归并排序.py
class solution:
def mergesort(self,nums):
if len(nums)<=1:
return nums
mid=len(nums)//2
left=self.mergesort(nums[:mid])
right=self.mergesort(nums[mid:])
return self.merge(left,right)
def merge(self,left,right):
res=[]
i,j=0,0
while i<len(left) and j<len(right):
if left[i]<right[j]:
res.append(left[i])
i+=1
else:
res.append(right[j])
j+=1
if i<len(left):
res.extend(left[i:])
if j<len(right):
res.extend(right[j:])
return res
if __name__ == "__main__":
s = solution()
nums=[2,1,3,4,9,8,5,6]
print(s.mergesort(nums))
Raw
leetcode_排序_快排.py
class solution:
def quicksort(self,nums,left,right):
if left<right:
mid=self.partition(nums,left,right)
left=self.quicksort(nums,left,mid-1)
right=self.quicksort(nums,mid+1,right)
return nums
def partition(self,nums,left,right):
tmp=nums[left]
while left<right:
#只要右边right都大于tmp,就移动right指针
while left<right and nums[right]>tmp:
right-=1
#找到第一个小于tmp的值
nums[left]=nums[right]
while left<right and nums[left]<tmp:
left+=1
nums[right]=nums[left]
nums[left]=tmp
return left
if __name__ == "__main__":
s = solution()
nums=[2,1,3,4,9,8,5,6]
print(s.quicksort(nums,0,len(nums)-1))
Raw
leetcode_排序_计算右侧小于当前元素的个数.py
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
arr = []
res = [0] * len(nums)
for idx, num in enumerate(nums):
arr.append((idx, num))
print(arr)
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
tmp = []
i = 0
j = 0
while i < len(left) or j < len(right):
if j == len(right) or i < len(left) and left[i][1] <= right[j][1]:
tmp.append(left[i])
res[left[i][0]] += j
i += 1
else:
tmp.append(right[j])
j += 1
return tmp
merge_sort(arr)
return res
Raw
leetcode_数学_Pow(x,n).py
"""
快速幂
"""
class Solution:
def myPow(self, x: float, n: int) -> float:
judge = True
if n < 0:
n = -n
judge = False
final = 1
while n>0:
if n%2 == 0:
x *=x
n //= 2
final *= x
n -= 1
return final if judge else 1/final
class Solution:
def myPow(self, x,n):
if n < 0 :
return self.myPow(1 / x, -n)
if n == 0:
return 1
if n % 2 == 0:
return self.myPow(x*x, n//2)
else:
return x * self.myPow(x*x, n//2)
Raw
leetcode_数学_整数拆分.py
"""
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
可用数学证明，当切分成3等分的时候，乘积最大
"""
import math
class Solution:
def integerBreak(self, n: int) -> int:
if n <= 3:
return n - 1
a, b = n // 3, n % 3
if b == 0:
return int(math.pow(3, a))
if b == 1:
return int(math.pow(3, a - 1) * 4)
return int(math.pow(3, a) * 2)
Raw
leetcode_数学_杨辉三角.py
class Solution:
def generate(self, numRows):
res=[]
for i in range(numRows):
res.append([])
for j in range(i+1):
res[i].append(1)
for i in range(2,numRows):
for j in range(1,i):
res[i][j]=res[i-1][j-1]+res[i-1][j]
return res
Raw
leetcode_数学_生成螺旋矩阵.py
class Solution:
def generateMatrix(self, n):
# 螺旋矩阵
nums = [i + 1 for i in range(n ** 2)]
dx = 0
dy = 1
i = 0
j = 0
matrix = [[0] * n for _ in range(n)]
for z in range(n ** 2):
matrix[i][j] = nums[z]
if matrix[(i + dx) % n][(j + dy) % n] != 0:
dx, dy = dy, -dx
i += dx
j += dy
return matrix
Raw
leetcode_数学_角矩形.py
class Solution:
def countCornerRectangles(self, grid):
row = len(grid)
col = len(grid[0])
res = 0
for i in range(row - 1):
one = []
for k in range(col):
if grid[i][k] == 1:
one.append(k)
#print(one)
#算每行一的个数，然后将1的列值记录，再从之后的行中判断是否存在这样的1
#最后使用公式计算矩形个数
for j in range(i+1, row):
tmp = 0
for t in one:
if grid[j][t] == 1:
tmp += 1
res += tmp * (tmp - 1) // 2
return res
Raw
leetcode_数组_三数之和.py
class Solution:
def threeSum(self,nums,target=0):
nums.sort()
print(nums)
res=[]
for i in range(len(nums)-2):
if nums[i]>target:
return res
if i>0 and nums[i]==nums[i-1]:
continue
if nums[i]>target:
break
elif nums[i]+nums[i+1]+nums[i+2]>target:
break
elif nums[i]+nums[-1]+nums[-2]<target:
continue
else:
l=i+1
r=len(nums)-1
while l<r:
tmp=nums[i]+nums[l]+nums[r]
if tmp==target:
res.append([nums[i],nums[l],nums[r]])
while l<r and nums[l]==nums[l+1]:
l+=1
while l<r and nums[r]==nums[r-1]:
r-=1
l+=1
r-=1
elif tmp<target:
l+=1
else:
r-=1
return res
if __name__=="__main__":
s=Solution()
nums =[-2,0,0,2,2]
print(s.threeSum(nums,0))
Raw
leetcode_数组_二维网格迁移.py
class Solution:
def shiftGrid(self, grid, k: int):
line = []
for i in range(len(grid)):
for j in range(len(grid[0])):
line.append(grid[i][j])
idx = k % len(line)
line[:] = line[len(line) - idx:] + line[:len(line) - idx]
for i in range(len(grid)):
for j in range(len(grid[0])):
grid[i][j] = line.pop(0)
return grid
#找到首字符，然后依次填补
def Mundane(self,grid,k):
n, m = len(grid), len(grid[0])
sx, sy = (k // m) % n, k % m
g = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
g[sx][sy] = grid[i][j]
sy += 1
if sy == m:
sy = 0
sx += 1
if sx == n:
sx = 0
return g
Raw
leetcode_数组_交集.py
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
i,j=0,0
res=[]
while i <len(nums1) and j<len(nums2):
if nums1[i]==nums2[j]:
res.append(nums1[i])
i+=1
j+=1
elif nums1[i]<nums2[j]:
i+=1
else:
j+=1
return res
Raw
leetcode_数组_出现次数最多的K个单词.py
class Solution:
def topKFrequent(self, words, k: int):
from collections import defaultdict
cnt = defaultdict(int)
for i in words:
cnt.setdefault(i, 0)
cnt[i] += 1
sort_cnt = sorted(cnt.items(), key=lambda x: (-x[1], x[0]))
res = []
for i in range(k):
res.append(sort_cnt[i][0])
return res
Raw
leetcode_数组_删除排序数组中的重复项.py
"""
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
"""
class Solution:
def removeDuplicates(self, nums):
for i in range(len(nums)-1,0,-1):
if nums[i]==nums[i-1]:
nums.pop(i)
return nums
def remove2(self,nums):
pre, cur = 0, 1
while cur < len(nums):
if nums[pre] == nums[cur]:
nums.pop(cur)
else:
pre, cur = pre + 1, cur + 1
return nums
if __name__=="__main__":
s=Solution()
nums=[0,0,1,1,1,2,2,3,3,4]
print(s.remove2(nums))
Raw
leetcode_数组_对角线遍历.py
class Solution:
def findDiagonalOrder(self,matrix):
from collections import defaultdict
lookup=defaultdict(list)
n=len(matrix)
m=len(matrix[0])
for i in range(n):
for j in range(m):
lookup[i+j].append(matrix[i][j])
#print(lookup)
res=[]
flag=True
for k,v in sorted(lookup.items()):
if flag:
res.extend(v[::-1])
else:
res.extend(v)
flag=not flag
return res
if __name__=="__main__":
s=Solution()
matrix=[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
print(s.findDiagonalOrder(matrix))
Raw
leetcode_数组_插入区间.py
class Solution:
def insert(self,intervals,newInterval):
intervals.append(newInterval)
intervals = sorted(intervals)
res = []
n = len(intervals)
i = 0
while (i < n):
left = intervals[i][0]
right = intervals[i][1]
while (i < n - 1 and intervals[i + 1][0] <= right):
i = i + 1
right = max(intervals[i][1], right)
res.append([left, right])
i = i + 1
return res
def insert2(self, intervals, newInterval):
i = 0
n = len(intervals)
res = []
# 找左边重合区域
while i < n and newInterval[0] > intervals[i][1]:
res.append(intervals[i])
i += 1
tmp = [newInterval[0], newInterval[1]]
# 找右边重合区域
while i < n and newInterval[1] >= intervals[i][0]:
tmp[0] = min(tmp[0], intervals[i][0])
tmp[1] = max(tmp[1], intervals[i][1])
i += 1
res.append(tmp)
while i < n:
res.append(intervals[i])
i += 1
return res
Raw
leetcode_数组_旋转数组.py
"""
先转置 再按行翻转
"""
class Solution:
def rotate(self,matrix):
n=len(matrix)
m=len(matrix[0])
for i in range(n):
for j in range(i,m):
matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
for i in range(n):
matrix[i].reverse()
return matrix
if __name__=="__main__":
s=Solution()
matrix =[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
print(s.rotate(matrix))
Raw
leetcode_数组_最接近的三数之和.py
"""
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
找出 nums 中的三个整数，使得它们的和与 target 最接近。
返回这三个数的和。假定每组输入只存在唯一答案。
"""
class Solution:
def threeSumClosest(self,nums,target):
res=float("inf")
nums.sort()
n=len(nums)
cur=0
for i in range(n-2):
l=i+1
r=n-1
while l<r:
tmp=nums[i]+nums[l]+nums[r]
if abs(tmp-target)<res:
res=abs(tmp-target)
cur=tmp
print(cur)
if tmp>target:
r-=1
else:
l+=1
return cur
if __name__=="__main__":
s=Solution()
nums=[-1,2,1,-4]
target=1
print(s.threeSumClosest(nums,target))
Raw
leetcode_数组_矩阵置零.py
"""
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为0。请使用原地算法。
"""
class Solution:
def setZero(self,matrix):
n=len(matrix)
m=len(matrix[0])
zero=[]
for i in range(n):
for j in range(m):
if matrix[i][j]==0:
zero.append((i,j))
def set2Zero(matrix,point):
x = point[0]
y = point[1]
for j in range(m):
matrix[x][j] = 0
for i in range(n):
matrix[i][y] = 0
return matrix
for point in zero:
matrix=set2Zero(matrix,point)
return matrix
if __name__=="__main__":
s=Solution()
matrix=[[0,1,2,0],
[3,4,5,2],
[1,3,1,5]]
print(s.setZero(matrix))
Raw
leetcode_数组_移除元素.py
class Solution:
def removeElement(self, nums, val: int) -> int:
i = 0
for j in range(len(nums)):
if nums[j] != val:
nums[i] = nums[j]
i += 1
return i
Raw
leetcode_数组_螺旋数组.py
"""
顺时针打印数组
"""
def funx():
r, i, j, di, dj = [], 0, 0, 0, 1
if matrix != []:
for _ in range(len(matrix) * len(matrix[0])):
r.append(matrix[i][j])
matrix[i][j] = 0
if matrix[(i + di) % len(matrix)][(j + dj) % len(matrix[0])] == 0:
di, dj = dj, -di
i += di
j += dj
return r
class solution:
def printMatrix(self,matrix):
if not matrix:
return []
n=len(matrix)
m=len(matrix[0])
left,right=0,m-1
bottom,top=n-1, 0
res=[]
while True:
for i in range(left,right+1):
res.append(matrix[left][i])
top+=1
if top>bottom:
break
for i in range(top,bottom+1):
res.append(matrix[i][right])
right-=1
if right<left:
break
for i in range(right,left-1,-1):
res.append(matrix[bottom][i])
bottom-=1
if top > bottom:
break
for i in range(bottom,top-1,-1):
res.append(matrix[i][left])
left+=1
if right < left:
break
return res
if __name__=="__main__":
s=solution()
matrix=[[1,2,3],[4,5,6],[7,8,9]]
print(s.printMatrix(matrix))
Raw
leetcode_数组_较小的三数之和.py
class Solution:
def threeSumSmaller(self, nums, target):
nums.sort()
n=len(nums)
count=0
for i in range(n-2):
j=i+1
k=n-1
while j<k:
cur=nums[i]+nums[j]+nums[k]
if cur>=target:
k=k-1
if cur<target:
count+=k-j
j+=1
return count
Raw
leetcode_杂七杂八_132模式.py
class Solution:
def find132pattern(self, nums):
stack = []
m = float('-inf')
for i in range(len(nums) - 1, -1, -1):
if nums[i] < m:
return True
while stack and nums[i] > stack[-1]:
m = stack.pop()
print("m",m)
stack.append(nums[i])
print(stack)
return False
if __name__ == "__main__":
s = Solution()
nums=[1,2,3,2,0]
print(s.find132pattern(nums))
Raw
leetcode_杂七杂八_下一个排列.py
class Solution:
def nextPermutation(self, nums):
firstIndex = -1
n = len(nums)
def reverse(nums, i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
for i in range(n - 2, -1, -1):
if nums[i] < nums[i + 1]:
firstIndex = i
break
if firstIndex == -1:
reverse(nums, 0, n - 1)
return
secondIndex = -1
for i in range(n - 1, firstIndex, -1):
if nums[i] > nums[firstIndex]:
secondIndex = i
break
nums[firstIndex], nums[secondIndex] = nums[secondIndex], nums[firstIndex]
reverse(nums, firstIndex + 1, n - 1)
return nums
if __name__ == "__main__":
s = Solution()
nums=[1,2,4,3]
print(s.nextPermutation(nums))
Raw
leetcode_杂七杂八_分割回文串.py
class Solution:
def partition(self, s):
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(i + 1):
if (s[i] == s[j]) and (i - j <= 2 or dp[j + 1][i - 1]):
dp[j][i] = True
res = []
def helper(i, tmp):
if i == n:
res.append(tmp)
for j in range(i, n):
if dp[i][j]:
helper(j + 1, tmp + [s[i: j + 1]])
helper(0, [])
return res
if __name__=="__main__":
s=Solution()
str="aaba"
print(s.partition(str))
Raw
leetcode_杂七杂八_去除重复字母.py
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
counts = {}
for c in s: # 字符计数
counts[c] = counts.get(c, 0) + 1
stack, stacked = [], set()
for c in s:
if c not in stacked:
while stack and c < stack[-1] and counts[stack[-1]]: # 当栈顶在后面还有且大于当前字符时弹出
stacked.remove(stack.pop())
stack.append(c)
print(stack)
stacked.add(c)
counts[c] -= 1
return ''.join(stack)
if __name__=="__main__":
s=Solution()
string="dbcabc"
print(s.removeDuplicateLetters(string))
Raw
leetcode_杂七杂八_双行道.py
n=input()
matrix=[[0]*int(n) for _ in range(2)]
first=input()
second=input()
for i in range(int(n)):
matrix[0][i]=first[i]
matrix[1][i] = second[i]
def getpath(matrix):
if not matrix:
return 0
if matrix[0][0]=="X":
return 0
if matrix[-1][-1]=="X":
return 0
col=len(matrix[0])
dp = [[0] * col for _ in range(4)]
dp[1][0] = 1
for j in range(1, col):
for i in range(2):
if matrix[i][j] != "X":
dp[i+1][j] = dp[i+1][j - 1] + dp[i + 2][j - 1] + dp[i][j - 1]
print(dp)
return dp[2][-1]
if __name__=="__main__":
import sys
#print(matrix)
ans=getpath(matrix)
sys.stdout.write(str(ans))
"""
5
..X.X
XX...
"""
Raw
leetcode_杂七杂八_基本计算器.py
class Solution:
def calculate(self, s: str) -> int:
res = 0
stack = []
sign = 1
i = 0
n = len(s)
while i < n:
if s[i] == " ":
i += 1
elif s[i] == "-":
sign = -1
i += 1
elif s[i] == "+":
sign = 1
i += 1
elif s[i] == "(":
stack.append(res)
stack.append(sign)
res = 0
sign = 1
i += 1
elif s[i] == ")":
res = res * stack.pop() + stack.pop()
i += 1
elif s[i].isdigit():
tmp = int(s[i])
i += 1
while i < n and s[i].isdigit():
tmp = tmp * 10 + int(s[i])
i += 1
res += tmp * sign
return res
if __name__ == "__main__":
s = Solution()
string ="(1+(4+5+2)-3)+(6+8)"
print(s.calculate(string))
Raw
leetcode_杂七杂八_字符串解码.py
class Solution:
def decodeString(self, s: str) -> str:
def dfs(s, i):
res, multi = "", 0
while i < len(s):
if s[i].isdigit():#如果是数字
multi = multi * 10 + int(s[i])
elif s[i] == '[':
i, tmp = dfs(s, i + 1)
res += multi * tmp
multi = 0
elif s[i] == ']':
return i, res
else:
res += s[i]
i += 1
return res
return dfs(s,0)
if __name__ == "__main__":
s = Solution()
string ="3[a2[c]]"
print(3*"abc")
print(s.decodeString(string))
Raw
leetcode_杂七杂八_快手笔试.py
import sys
import collections
import torch
def genSeq(values):
count = collections.defaultdict(int)
s, a, b, p = values[0], values[1], values[2], values[3]
arr = []
arr.append(s)
count[s] = 1
i = 1
while 1:
x = (arr[i - 1] * a + b) % p
if count[x] == 2:
arr = arr[:i]
break
else:
arr.append(x)
count[x] += 1
i += 1
del count
return arr
def getMaxlen(arr1, arr2):
##求最大公共子序列长度
n = len(arr1)
m = len(arr2)
##dp[i][j]表示arr1[0]~arr1[i]与arr2[0]~arr2[j]之间的最长公共子序列长度
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(m):
if arr1[i] == arr2[j]:
dp[i + 1][j + 1] = dp[i][j] + 1
else:
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
return dp[-1][-1]
if __name__ == "__main__":
T = int(sys.stdin.readline().strip())
seq = []
for i in range(2 * T):
line = sys.stdin.readline().strip()
values = list(map(int, line.split()))
seq.append(values)
for i in range(0,2*T,2):
seq1=seq[i]
seq2=seq[i+1]
if seq1==seq2:
print(len(genSeq(seq1)))
else:
print(getMaxlen(genSeq(seq1),genSeq(seq2)))
'''
class Solution:
def find_best_path_cost(self , A ):
n=len(A)
m=len(A[0])
for i in range(1,n):
A[i][0]=A[i-1][0]+A[i][0]
for j in range(1,m):
A[0][j]=A[0][j-1]+A[0][j]
for i in range(1,n):
for j in range(1,m):
A[i][j]=min(A[i-1][j],A[i][j-1])+A[i][j]
print(A[-1][-1])
if __name__=='__main__':
s=Solution()
A=[[1,2,3],[4,5,6],[7,8,9]]
print(s.find_best_path_cost(A))
import sys
line=sys.stdin.readline().strip().split()
K=int(line[0])
N=int(line[1])
res=1
while K:
div=N//K
res*=div
N-=div
K-=1
print(res)
'''
Raw
leetcode_杂七杂八_扔鸡蛋.py
"""
dp[k][m]=n 表示k个鸡蛋，最多允许扔m次，最坏情况下最多可以度量n层
dp[k][m]=dp[k][m-1]+dp[k-1][m-1]+1
"""
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
dp=[[0]*(N+1) for _ in range(K+1)]
m=0
while dp[K][m] < N:
m+=1
for k in range(K,0,-1):
dp[k][m]=dp[k-1][m-1]+dp[k][m-1]+1
return m
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
memo = dict()
def dp(N, K):
if N == 0:
return 0
# 只有一个鸡蛋，只能线性扫描
if K == 1:
return N
if (N, K) in memo:
return memo[(N, K)]
res = float('inf')
for i in range(1, N + 1):
res = min(res, max(dp(i - 1, K - 1), dp(N - i, K)) + 1)
memo[(N, K)] = res
return res
return dp(N, K)
if __name__ == "__main__":
s = Solution()
T = "ABC"
Raw
leetcode_杂七杂八_整数拆分.py
class Solution:
def integerBreak(self, n: int) -> int:
dp = [-1]*(n+1)
dp[1] = 1
dp[2] = 1
for i in range(3,n+1):
for j in range(1,i):
#j*(i-j)表示拆分成两个数的乘积
#j*dp[i-j]表示拆分成多个数的乘积
dp[i] = max(dp[i],j*(i-j),j*dp[i-j])
return dp[n]
if __name__=="__main__":
s=Solution()
n=10
print(s.integerBreak(n))
Raw
leetcode_杂七杂八_栈的最小值.py
class Minstack:
def __init__(self):
self.stack1=[]
self.stack2=[]
def push(self,e):
self.stack1.append(e)
if len(self.stack2)==0 or e<self.stack2[-1]:
self.stack2.append(e)
else:
self.stack2.append(self.stack2[-1])
def pop(self):
e=self.stack1.pop()
self.stack2.pop()
return e
def getMin(self):
return self.stack2[-1]
def top(self):
return self.stack1[-1]
if __name__=="__main__":
minStack=Minstack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
print(minStack.getMin())
print(minStack.pop())
print(minStack.top())
print(minStack.getMin())
Raw
leetcode_杂七杂八_每日温度.py
class Solution:
def dailyTemperatures(self, T):
n=len(T)
res=[0]*n
stack=[]
for i in range(n):
while stack and T[i]>T[stack[-1]]:
res[stack.pop()]=i-stack[-1]
stack.append(i)
return res
if __name__ == "__main__":
s = Solution()
T=[73, 74, 75, 71, 69, 72, 76, 73]
print(s.dailyTemperatures(T))
Raw
leetcode_杂七杂八_移除k位数字.py
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
if len(num)==k:
return "0"
stack=[]
n=len(num)
for i in range(n):
while stack and k and stack[-1]>num[i]:#开始出现逆序
stack.pop()
k-=1
stack.append(num[i])
#print(stack)
while k:
stack.pop()
k -=1
res=""
for i in range(len(stack)):
if stack[i]=="0" and res=="":
continue
res+=stack[i]
return "0" if res=="" else res
if __name__ == "__main__":
s = Solution()
#string='1432219'
#k=3
string="99641436378815361153471302158193420182863684789411484994976484827114595334610042544056442370530816060833617030976813134098793056155103202008549344446519354408307307071055065112738442020228471569394796174150323080161225901964338837341524253243218509500254619223683091799365677720582389568156585225666197123093377871100002481402486219837255411382162499321193416524972275273471969155848742457476556433737281147710021781210134765321761285612276511917324552585569882156635094670362653567596144728653795007023230933817566104488637696450166087905100823699425798763598444326069357052842379918535855296915760054459317433521878778171811081076593166663090948029793113626852462712388116483774713426183911481230884393594249331828165503798269634244430773693033882708000249632850148799859322024693146577635543114657662418998860517525989192973250701631765598465053097616804817344343895016724561947860836117504915797011185132674255278236597746042138768473723059825948301565719437610732907662545499042953499866813741157301003371005200992314265077531029437948931255617153417148822355928318598517533241719641002712204874161001604269216566928220767474713135516717997491363360204764154264989004671363541097433484822118483642107547658581450616821769964767032521138851570822729134762460014265433227201724724004338494552397280090568164786109721571436206198382814849033856987338787473335772666933218810822482848994610491705665155516384799459418594559136827941106387689501641851101743298582575466303864906673788496628288920867422193950180810131396612913851112593807649152972068279299934113463669714575613645929365652921808836725682390026075559320995704880149764583379697505303474550029059828116836469203370428449330442281563135568935742669243344218603994417955703485059862132359688776290378210392955310785874528205203788559715493852405991380290274268143557970398441851157977520689440430265144029789788511042795879174567381358510694749512938934687979305099149575464220629804942550564164786808856897809863824121659548034395539735407069279457678613909222371848892294754933299091164656871086269084324529512544747434123547189729993758337622038098699448815701644934651292719067683227727438808955969543542319197883567369733867364250353136697865107182282929655918362211832327827571354787535611501731943856155003853732339819594939524719169561110698571676562329360803282215467534058504728127731515598941143637827010955579092451405821352126706550438315176049692316210490899702613078702535716735901806171522853021035597316703390478571485677998207922773938829371460838611214446417528913575284776737837046439695408523434414916342979688820197836458637694991540998291690345194205452439239827382953039810367712244590155940394387554911786652478111954297185544106384174592451680875083737874735810068767866214924634885513828808880161930987276602570872860752119813042414550396358433893592777541756673206882876746731707766966268096104320061937913505893028833592137540396064375155513979764728180927083060481127522118240026140625647313783901073938419240249929000962722034273952683635919540169732220854978101308126446671885186032295490845060116567165945677975672981321362161949418405852378788584602802612398876874288293756055559457538271197205867506313677160755990736347314715042607243878693780144368083800080967842966193539823770427967091132770230485036143223363387876244958899577538069175123004651952588711287008791159682042581943812962882375293348462523257081140457567348612069746943329842264291823570671268374580651696311114624358304235261945894627668267192756606441264485628097480920062857007640396910214970556623416565940789636657349735150043836194242061994234044262604284350296258397208287158735477739515615890093167555389262170576609082365199242352356197706754361085079177223144662701424848070607319078068303190442737202186364818021792860690571733432439513976759807778513151206801184300729685910765785586373831699595178352610150383283823456881293647763022411686252640648120690251120902631370825525354213297549430441989419362406888242180413640397005462289002837178086683143441254722528075315187910994986929463063282350677644105312484770818851268755183086729904524488901102287310169865855725358976453628171038414004415469635124255044890245890050115901243603489384920067923087045070616429510114587493955384903357111302068595548921504222171096098548413208088831560744996899783844118318185694142620796984004522106434428513215881883542758888862576036415421097762413907290417004936441609238204617100586876487061497586106631983740139555573272626681186969272113315348553052708453716313010811194726904231406455432865684477036960953564406390115786323388585604716504384778912812410729908949581143722120318954849846535676912868526526501078193502393524062471534154104899815734648650035608611113327222040864146091286020205304970098510045582130989981665393076480660907742469107193219475618455618115516353495211289597815564506193368287178714208989206470099207227171770619580227427772058576958549342547850566371060314330889132466260972915500785842700966615103949831075688522846389635990078358138687466663099265099431775674237640711466272609872329090894406587154198409486434056948991642623725868520261081714501891452704954562834244485695899485150794033902595303371632597184940525684558272222395813587950566598836575728711404672894869851301199508345442816914540274231773573695049117433232750564343477296571911336451338765122801905492189124021699698020217831160061375249740348841211772476455089061870953510480256335713228323198782026742817220321247980121667780800877801219532811542139900480803615083739957513418528009253849655053312995534574307148952727627870318872325094411860749809155407484065987101730385346571248798467212335910821152286411077915790397497756477613051365987943518909759211252763081626026136209474490841118337332773116122063152414208776801671614382203998310801791046109980464795153775904284579208046765170299376571712696359391195309011046580945099118345329164807866461624513459858969478261348365746242842254100449074846018162381649508771205692387943049083877156128753239386498305599949138477358461424273464036997642435352074743094695564535693378173888280633866732018710701060752702258884562187458492514181027419045608607139753797741693225900923436163273291784047946102859573341135995351940672974945745062320931107916232460722010886651827074516009065280667168017782964663521168472263155891094369134584611694802620433621767214124173962636180142978128638945692419270222518432363382128100260544917455244318162619360808797214154001396840051520865249909119773623276044783996235484958441702533661095335337458603732924068113476544273220040621287278168707393471504842692312354782265568742305367773635557008065688109790648713350572351799924638273829816187626279342407486758617884199669669286080608957640162096427744397522103026413782698158732581790000716751490076906346484023835702438474105176931779065689980130347837155056303467742499515965713045957954225592059807462917282749105358673064716135765849677591608061323905019687616579401117839719269327243007586938365568212311638431283680946079388989080798521721770825311237382299640977231722390040018733060008726711369177955792504805871660952275133036361448257222162174106121886956846208577175900217031085260775753651365765038925717954695019720235653672968689019573262654460436772900765775615489257834882352941349073672575670561593061387879337673233294306479935031268311515186416299622966578517978675818927585118344348361158710756313053131716293124192982037977789379782122120656399498488608931743952536041546453299501041577456229618221253519224906611827751220393777623642577532653929191439603183004880021982807536023221789599010502125687724004685177438516674638976736887749480118357141229355178588718777866510629202733751110559334924038607709059709853979249569510212755627954315025008066453716096825677236680969921750877126730256949811077056975031686370565845816981036167892330455103497165407984322792515265566483796338273488042877728447328933645773410093062365682687268013318931065552717013674172822704288279197461978805944285413220284999303849740540429893025407810120053701999064303195562726870079068213843151094378846458471168159763363401468459072474435300433314015701363633705309153196187013664717617975618648227816754951474354742056233896619815305871556180590934191775446450232435064334173434855333465262160341517250209548644211312373841441024747539900101488865742679168673356769004244781832745045012713439497231232255815861738982590755401780194874615548229070120796893835181030047378827641086164272219294123942746140207443292075817414598536256892540490923602419336928186124051416665048479530882042184097629985897052425322145715174649893481917612568426372077919256931921063600255204010662044398922537796993713110889134889921360833579323314386803074533058134342770923839546994120322442157750203621967931319597649960815556196358566683782572730174920215034531104191490057838260392829741446722127017532444082857280503217574522928285094747407153894570747792487061998260753833304433675066923630595212677695003060727653119915126939127827754432456052655283764591328484359469704894122366077507922825301623961196207923544095047285011474898262448957681893278273601046641810135121516552187096005252171171905022763076761687166299014789581539855448453229411352775826042558462563147630238335355859149814380543807473386539264830261256996173935860136236427622918234260408201158550118527706241993700526213016072648406003487895118011337828945314863348154387066988573131543747121745028364818130265528614742576976975564213718421245904443000581698214695522541683926528961160986876871840844632069685227319014872180179370554032205521013345746425253133686231659075343389374580200717637698542920298315739628019867736462368334051114029380922339886663078026309916370486909128253195100898377068612057592121356555290537815049586626181680384845905180029133497372417653664436161971980137048236053329456957495141918670077299206755740534997886723627476115663811233372206043170460623060506091246306386543951687123557178508806912199010111871"
k=1000
print(s.removeKdigits(string,k))
Raw
leetcode_杂七杂八_路径总数.py
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1]*n] + [[1]+[0] * (n-1) for _ in range(m-1)]
#print(dp)
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]
class Solution1:
def uniquePaths(self, m: int, n: int) -> int:
cur = [1] * n
for i in range(1, m):
for j in range(1, n):
cur[j] += cur[j-1]
print(cur)
return cur[-1]
if __name__=="__main__":
s=Solution1()
print(s.uniquePaths(5,4))
Raw
leetcode_杂七杂八_阿里3月25日笔试.py
class Solution:
def minpath(self, matrix):
n = len(matrix)
m = len(matrix[0])
# dp[i][j]表示到(i,j)的的最短路径值
dp = [[0] * m for _ in range(3)]
for j in range(1, m):
for i in range(3):
last_min=float("inf")
for k in range(3):
last_min=min(last_min,(abs(matrix[i][j]-matrix[k][j-1])+dp[k][j-1]))
dp[i][j] = last_min
min_num = min(dp[0][-1], dp[1][-1], dp[2][-1])
print(dp)
print(min_num)
if __name__=="__main__":
s=Solution()
import sys
n = int(sys.stdin.readline().strip())
matrix=[]
for i in range(3):
line = sys.stdin.readline().strip()
values = list(map(int, line.split()))
matrix.append(values)
s.minpath(matrix)
"""
6
5 9 5 4 4 7
4 7 4 10 3 6
2 10 9 2 3 4
"""
Raw
leetcode_杂七杂八_阿里笔试一.py
path=[]
def dfs(state):
if tuple(state) in memo:
return memo[tuple(state)]
if sum(state) == 0:
return 0
else:
res = float('inf')
for i in range(10):
# 出三连对子
if i < 8 and state[i] > 1 and state[i + 1] > 1 and state[i + 2] > 1:
state[i] -= 2
state[i + 1] -= 2
state[i + 2] -= 2
res = min(res, dfs(state) + 1)
state[i] += 2
state[i + 1] += 2
state[i + 2] += 2
memo[tuple(state)] = res
# 出顺子
if i < 6 and state[i] > 0 and state[i + 1] > 0 and state[i + 2] > 0 and state[i + 3] > 0 and state[
i + 4] > 0:
state[i] -= 1
state[i + 1] -= 1
state[i + 2] -= 1
state[i + 3] -= 1
state[i + 4] -= 1
res = min(res, dfs(state) + 1)
state[i] += 1
state[i + 1] += 1
state[i + 2] += 1
state[i + 3] += 1
state[i + 4] += 1
memo[tuple(state)] = res
# 出2张对子
if res == float('inf') and state[i] > 1:
state[i] -= 2
res = min(res, dfs(state) + 1)
state[i] += 2
memo[tuple(state)] = res
# 单出一张
if res == float('inf') and state[i] > 0:
state[i] -= 1
res = min(res, dfs(state)+1)
state[i] += 1
memo[tuple(state)] = res
return res
memo = {}
state = [2,3,3,1,1,1,3,2,2,1]
import time
t=time.time()
print(dfs(state))
print(memo)
print(time.time()-t)
Raw
leetcode_杂七杂八_阿里笔试三.py
class Solution:
def minPath(self,matrix):
n=len(matrix)
m=len(matrix[0])
self.fly = 5
self.min_path=float("inf")
visited=set()
def dfs(i,j,path):
if i<0 or i>=n or j<0 or j>=n or matrix[i][j]=="#" or (i,j) in visited:#跨界和障碍
return
if matrix[i][j]=="E":
self.min_path=min(self.min_path,path)
visited.add((i,j))
if self.fly:
dfs(n-i-1,m-1-j,path+1)
self.fly-=1
dfs(i-1,j,path+1)
dfs(i+1,j,path+1)
dfs(i,j-1,path+1)
dfs(i,j+1,path+1)
visited.remove((i, j))
for i in range(n):
for j in range(m):
if matrix[i][j]=="S":
dfs(i,j,0)
return self.min_path
if __name__=="__main__":
s=Solution()
matrix = [["#", "S", ".", "."], [".", "#", ".", "E"], ["#", ".", ".", "."], [".", ".", ".", "."]]
print(s.minPath(matrix))
Raw
leetcode_杂七杂八_阿里笔试二.py
import sys
seq=[]
while 1:
line=sys.stdin.readline().strip()
if line=='':
break
seq.append(line)
num=seq[1:]
n=len(num)
#dp[i][j]表示两个字母之间的最大长度，dp[0][1]为以字符a为开头，字符b为结尾的最大长度，dp[0][25]表示以字符a为开头，字符z为结尾的最大长度
dp=[[0 for _ in range(26)] for _ in range(26)]
for i in range(n):
tmp=num[i]
for j in range(ord(tmp[0])-97+1):#ord('a')=97
for k in range(25,ord(tmp[-1])-97-1,-1):
dp[j][k]=max(dp[j][k],dp[j][ord(tmp[0])-97]+dp[ord(tmp[-1])-97][k]+len(tmp))
print(dp)
import sys
seq=[]
while 1:
line=sys.stdin.readline().strip()
if line=='':
break
seq.append(line)
nums=seq[1:]
n=len(nums)
nums.sort(key=lambda x:(x[-1],x[0]))
print(nums)
#dp[j]表示 a~'j'之间的最大长度
dp=[0]*26
for i in range(n):
tmp=nums[i]
tmp_length=len(tmp)
left=ord(tmp[0])-ord('a')
right=ord(tmp[-1])-ord('a')
left_max=0
for j in range(left+1):
left_max=max(dp[j],left_max)
dp[right]=max(dp[right],left_max+tmp_length)
print(dp)
Raw
leetcode_栈_最小栈.py
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.mystack=[]
self.minstack=[]
def push(self, x: int) -> None:
self.mystack.append(x)
if not self.minstack:
self.minstack.append(x)
elif self.minstack[-1]<x:
self.minstack.append(self.minstack[-1])
else:
self.minstack.append(x)
def pop(self) -> None:
self.mystack=self.mystack[:-1]
self.minstack=self.minstack[:-1]
def top(self) -> int:
if self.mystack:
return self.mystack[-1]
def getMin(self) -> int:
return self.minstack[-1]
if __name__=="__main__":
minStack=MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
minStack.getMin()
minStack.pop()
minStack.top()
minStack.getMin()
Raw
leetcode_树_Morris.py
class Morris:
def preorder(root):
if not root:
return
p = root;
prenode = None
while p:
if p.left:
#前驱结点的最右子节点--->自身
prenode = p.left
while prenode.right and prenode.right != p:
prenode = prenode.right
if not prenode.right: #建立链接方便回溯
print(p.val) #打印
prenode.right = p
p = p.left
continue
if prenode.right == p:
prenode.right = None #回溯完成删除多余链接
if not p.left:
print(p.val) #打印
p = p.right
def inorder(root):
if not root: return
p = root;
prenode = None
while p:
if p.left:
prenode = p.left
while prenode.right and prenode.right != p:
prenode = prenode.right
if not prenode.right: # 建立链接方便回溯
prenode.right = p
p = p.left
continue
#之前建立过连接，即先前结点要回溯到的父节点，打印
if prenode.right == p:
print(p.val) # 打印
prenode.right = None # 回溯完成删除多余链接
#到达最左结点，中学遍历开始打印该节点
if not p.left:
print(p.val) # 打印
p = p.right
def Morris_preorder(self,root):
if not root:
return []
p=root
prenode=None
res=[]
while p:
if p.left:
prenode=p.left
while prenode.right and prenode.right!=p:#还没有建立连接
prenode=prenode.right
if prenode.right!=p:
res.append(p.val)
prenode.right=p
p=p.left
continue
if prenode.right==p:
prenode.right=None
if not p.left:
res.append(p.val)
p=p.right
return res
Raw
leetcode_树_二叉搜索树的最近公共祖先.py
"""
二叉搜索树的 左子树值都小于右子树
"""
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
parent_val = root.val
p_val = p.val
q_val = q.val
if p_val > parent_val and q_val > parent_val:
return self.lowestCommonAncestor(root.right, p, q)
elif p_val < parent_val and q_val < parent_val:
return self.lowestCommonAncestor(root.left, p, q)
else:
return root
# if p.val >q.val:
# p,q =q,p
# while True:
# #说明p q都在左子树
# if root.val>q.val:
# root = root.left
# elif root.val < p.val:
# root = root.right
# else:
# return root
Raw
leetcode_树_二叉树右视图.py
"""
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
"""
#len(self.res) == depth关键点
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def rightSideView(self, root: TreeNode) :
def dfs(node, depth):
if not node:
return
if len(self.res) == depth:
self.res.append(node.val)
dfs(node.right,depth + 1)
dfs(node.left,depth + 1)
self.res=[]
dfs(root, 0)
return self.res
import collections
#BFS
class Solution:
def rightSideView(self, root: TreeNode):
if not root:
return []
res = []
def bfs(root):
queue = [root]
while queue:
nxt = []
res.append(queue[-1].val)
for node in queue:
if node.left:
nxt.append(node.left)
if node.right:
nxt.append(node.right)
queue = nxt
bfs(root)
return res
Raw
leetcode_树_二叉树展开为链表.py
class Solution:
def flatten(self, root):
"""
Do not return anything, modify root in-place instead.
"""
if not root:
return
#打平左右子树
self.flatten(root.left)
self.flatten(root.right)
tmp = root.right
root.right = root.left
root.left = None
while root.right:
root = root.right
root.right = tmp
def flatten(self, root) -> None:
"""
Do not return anything, modify root in-place instead.
"""
cur = root
while cur:
if cur.left:
p = cur.left
while p.right:
p = p.right
p.right = cur.right
cur.right = cur.left
cur.left = None
cur = cur.right
Raw
leetcode_树_二叉树序列化与反序列化.py
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Codec:
def serialize(self, root):
res = []
def preorder(root):
if not root:
res.append("#")
return
res.append(str(root.val))
preorder(root.left)
preorder(root.right)
preorder(root)
return ",".join(res)
def deserialize(self, data):
d = iter(data.split(","))
def helper():
tmp = next(d)
if tmp == "#":
return
node = TreeNode(int(tmp))
node.left = helper()
node.right = helper()
return node
return helper()
Raw
leetcode_树_二叉树最大路径和.py
class Solution:
def maxPathSum(self, root) -> int:
self.ans=float("-inf")
def dfs(root):
if not root:
return 0
left=dfs(root.left)
right=dfs(root.right)
#经过经前节点，加上左右
self.ans=max(self.ans,left+right+root.val)
#每个父节点返回，左右子树中最大的加上该父节点
return max(0,max(left,right)+root.val)
dfs(root)
return self.ans
Raw
leetcode_树_二叉树最近公共祖先.py
class Solution:
def lowestCommonAncestor(self, root, p, q):
if not root or p == root or q == root:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if not left:
return right
if not right:
return left
return root
Raw
leetcode_树_二叉树深度.py
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
def minDepth(self, root):
if not root:
return 0
left = self.minDepth(root.left)
right = self.minDepth(root.right)
return left + right + 1 if (left==0 or right==0) else min(left, right) + 1
def maxDepth(root):
from collections import deque
if not root:
return 0
queue = deque()
queue.appendleft(root)
res = 0
while queue:
res += 1
n = len(queue)
for _ in range(n):
tmp = queue.pop()
if tmp.left:
queue.appendleft(tmp.left)
if tmp.right:
queue.appendleft(tmp.right)
return res
Raw
leetcode_树_二叉树的中序遍历.py
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# def __init__(self,res=[]):
# self.res=[]
#
# def inorderTraversal(self, root):
# if not root:
# return
# self.inorderTraversal(root.left)
# self.res.append(root.val)
# self.inorderTraversal(root.right)
#
# return self.res
def inorderTraversal(root):
stack = []
cur = root
res = []
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
def inorderTraversal(root):
res = []
def helper(root):
if not root:
return
helper(root.left)
res.append(root.val)
helper(root.right)
helper(root)
return res
# if __name__=='main':
# s=Solution()
# nums=[1,None,2,3]
# print(s.inorderTraversal(nums))
Raw
leetcode_树_二叉树的前序遍历.py
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
#迭代
def preorderTraversal(root):
if not root:
return []
stack = [root]
res = []
while stack:
cur = stack.pop()
res.append(cur.val)
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
return res
def preorderTraversal(root):
res = []
cur = root
stack = []
while cur or stack:
while cur:
res.append(cur.val)
stack.append(cur)
cur = cur.left
tmp = stack.pop()
cur = tmp.right
#递归
def preorderTraversal(root):
res = []
def helper(root):
if not root:
return
res.append(root.val)
helper(root.left)
helper(root.right)
helper(root)
return res
Raw
leetcode_树_二叉树的后续遍历.py
"""
left-right-root
"""
class Solution:
#迭代
def postorderTraversal(root):
res = []
cur = root
stack = []
while cur or stack:
while cur:
res.append(cur.val)
stack.append(cur)
cur = cur.right
tmp = stack.pop()
cur = tmp.left
return res[::-1]
#递归
def postorderTraversal(root):
res = []
def helper(root):
if not root:
return
helper(root.left)
helper(root.right)
res.append(root.val)
helper(root)
return res
Raw
leetcode_树_二叉树的层次遍历.py
class Solution:
def levelOrder(root):
res = []
if not root:
return res
level = [root]
while level:
res.append([node.val for node in level])
next_level = []
for node in level:
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
level = next_level
return res
def levelOrder(root):
res = []
def helper(root, depth):
if not root:
return
if len(res) == depth:
res.append([])
res[depth].append(root.val)
helper(root.left, depth + 1)
helper(root.right, depth + 1)
helper(root, 0)
return res
Raw
leetcode_树_二叉树的层次遍历逆序.py
"""
给定一个二叉树，返回其节点值自底向上的层次遍历。
（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
"""
class Solution:
def levelOrderBottom(root):
res = []
def helper(root, depth):
if not root:
return
if len(res) == depth:
res.insert(0, [])
res[-(depth + 1)].append(root.val)
helper(root.left, depth + 1)
helper(root.right, depth + 1)
helper(root, 0)
return res
def levelOrderBottom(root):
from collections import deque
if not root:
return []
queue = deque()
queue.appendleft(root)
res = []
while queue:
tmp = []
n = len(queue)
for _ in range(n):
node = queue.pop()
tmp.append(node.val)
if node.left:
queue.appendleft(node.left)
if node.right:
queue.appendleft(node.right)
res.insert(0, tmp)
return res
Raw
leetcode_树_二叉树的所有路径.py
class Solution:
def binaryTreePaths(self, root):
if not root:
return []
ans=[]
def dfs(root, tmp):
if not root:
return
if not root.left and not root.right:
tmp+=[str(root.val)]
ans.append(tmp)
dfs(root.left, tmp+[str(root.val)])
dfs(root.right, tmp+[str(root.val)])
return ans
ans=dfs(root,[])
return ["->".join(x) for x in ans]
Raw
leetcode_树_二叉树锯齿形层次遍历.py
class Solution:
def zigzagLevelOrder(root):
res = []
def helper(root, depth):
if not root:
return
if len(res) == depth:
res.append([])
#偶数从左到右，奇数从右到左
if depth % 2 == 0:
res[depth].append(root.val)
else:
res[depth].insert(0, root.val)
helper(root.left, depth + 1)
helper(root.right, depth + 1)
helper(root, 0)
return res
Raw
leetcode_树_从中序与后序遍历序列构造二叉树.py
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def buildTree(self,inorder, postorder):
if len(inorder)==0:
return None
root=TreeNode(postorder[-1])
mid=inorder.index(postorder[-1])
root.left=self.buildTree(inorder[:mid],postorder[:mid])
root.right=self.buildTree(inorder[mid+1:],postorder[mid:-1])
return root
Raw
leetcode_树_从前序与中序遍历序列构造二叉树.py
"""
前序遍历 root-left-right
中序遍历 left-root-right
"""
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def buildTree(self,preorder, inorder) -> TreeNode:
if len(inorder) == 0:
return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
return root
Raw
leetcode_树_分裂二叉树最大乘积.py
class Solution:
def maxProduct(self,root):
ans=[]
def dfs(root):
if not root:
return 0
sum=dfs(root.left)+dfs(root.right)+root.val
ans.append(sum)
return sum
total=dfs(root)
max_num=float("-inf")
for sum in ans:
max_num=max(max_num,(total-sum)*sum)
return max_num
Raw
leetcode_树_对称二叉树.py
def isSymmetric(root):
if not root:
return True
def dfs(left, right):
if left == right:
return True
if not (left and right):
return False
if left.val!=right.val:
return False
return dfs(left.left, right.right) and dfs(left.right, right.left)
return dfs(root.left, root.right)
Raw
leetcode_树_平衡二叉树.py
class solution:
def isBalanced(self,root):
self.res = True
def helper(root):
if not root:
return 0
left = helper(root.left)
right = helper(root.right)
if abs(right - left) > 1:
self.res = False
return max(left, right) + 1
helper(root)
return self.res
Raw
leetcode_树_恢复二叉搜索树.py
"""
二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下，恢复这棵树。
"""
Raw
leetcode_树_最接近的二叉搜索树值 II.py
class Solution:
def closestValue(self, root, target, k):
self.res=float("inf")
self.ans=[]
def dfs(root):
if not root:
return
if abs(root.val-target)<=self.res:
self.res=abs(root.val-target)
self.ans.insert(0,root.val)
if root.val<target:
dfs(root.right)
else:
dfs(root.left)
dfs(root)
return self.ans[:k]
Raw
leetcode_树_最接近的二叉搜索树值.py
class Solution:
def closestValue(self, root, target):
self.res=float("inf")
self.ans=0
def dfs(root):
if not root:
return
if abs(root.val-target)<=self.res:
self.res=abs(root.val-target)
self.ans=root.val
if root.val<target:
dfs(root.right)
else:
dfs(root.left)
dfs(root)
return self.ans
Raw
leetcode_树_树的子结构.py
class Solution:
def isSubStructure(self, A, B) -> bool:
def isSameTree(t1,t2):
if not t2:
return True
if not t1 or t1.val!=t2.val:
return False
return isSameTree(t1.left, t2.left) and isSameTree(t1.right, t2.right)
if not A:
return False
if not B:
return False
return isSameTree(A,B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)
Raw
leetcode_树_根据前序和后序遍历构造二叉树.py
"""
前序遍历为 (根结点) (前序遍历左分支) (前序遍历右分支)
后序遍历为 (后序遍历左分支) (后序遍历右分支) (根结点)
"""
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def constructFromPrePost(self, pre, post):
if not pre:
return None
node = TreeNode(pre[0])
if len(pre) == 1:
return node
i = post.index(pre[1])+1
node.left = self.constructFromPrePost(pre[1:i + 1], post[:i ])
node.right = self.constructFromPrePost(pre[i + 1:], post[i:-1])
return node
Raw
leetcode_树_求根到叶子节点数字之和.py
class Solution:
def sumNumbers(self, root) -> int:
if not root:
return 0
self.res = 0
def helper(root, tmp):
if not root:
return
if not root.left and not root.right:
self.res += int(tmp + str(root.val))
return
helper(root.left, tmp + str(root.val))
helper(root.right, tmp + str(root.val))
helper(root, "")
return self.res
Raw
leetcode_树_相同的树.py
#递归
def isSameTree(p, q):
if p==q:
return True
if not q or not p:
return False
if p.val != q.val:
return False
return isSameTree(p.right, q.right) and isSameTree(p.left, q.left)
#迭代
def isSameTree(p, q):
stack = [(q, p)]
while stack:
a, b = stack.pop()
if not a and not b:
continue
if a and b and a.val == b.val:
stack.append((a.left, b.left))
stack.append((a.right, b.right))
else:
return False
return True
Raw
leetcode_树_翻转二叉树.py
class Solution:
def invertTree(self, root) :
if not root:
return root
root.left,root.right=root.right,root.left
root.left=self.invertTree(root.left)
root.right=self.invertTree(root.right)
return root
def invertTree(self, root):
if not root:
return root
stack = [root]
while stack:
node = stack.pop()
node.left, node.right = node.right, node.left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return root
Raw
leetcode_树_路径和.py
class Solution:
def hasPathSum(self,root,target):
if not root:
return False
self.res=False
def dfs(root,target):
if not root:
return
if root.val==target and not root.left and not root.right:
self.res=True
dfs(root.left,target-root.val)
dfs(root.right,target-root.val)
dfs(root,target)
return self.res
def pathSumII(self,root,target):
if not root:
return False
res=[]
def dfs(root, target,tmp):
if not root:
return
if root.val == target and not root.left and not root.right:
tmp.append(root.val)
res.append(tmp)
dfs(root.left, target - root.val,tmp+[root.val])
dfs(root.right, target - root.val,tmp+[root.val])
dfs(root, target,[])
return res
def pathSumIII(self,root,target):
if not root:
return
self.cnt=0
def dfs(root,target):
if not root:
return
if root.val == target:
self.cnt+=1
dfs(root.left, target - root.val)
dfs(root.right, target - root.val)
queue=[root]
while queue:
next=[]
for node in queue:
dfs(node,target)
if node.left:
next.append(node.left)
if node.right:
next.append(node.right)
queue=next
return self.cnt
Raw
leetcode_树_输出二叉树.py
class Solution:
def printTree(self, root):
def depth(root):
if not root:
return 0
left = depth(root.left)
right = depth(root.right)
return 1 + max(left, right)
m = depth(root)
n = 2 ** m - 1
res = [[""] * n for _ in range(m)]
def dfs(root, depth, start, end):
if not root:
return
mid = start + (end - start) // 2
res[depth][mid] = str(root.val)
dfs(root.left, depth + 1, start, mid - 1)
dfs(root.right, depth + 1, mid + 1, end)
dfs(root, 0, 0, n)
return res
Raw
leetcode_树_验证二叉搜索树.py
class Solutin:
def isValidBST(root):
pre=None
stack=[]
res=[]
cur=root
while cur or stack:
while cur:
stack.append(cur)
cur=cur.left
cur=stack.pop()
#pre用来表示上一个值
if pre and pre.val>=cur.val:
return False
else:
pre=cur
cur=cur.right
return True
def Mundane(self, root) -> bool:
res = []
def helper(root):
if not root:
return
helper(root.left)
res.append(root.val)
helper(root.right)
helper(root)
return res == sorted(res) and len(set(res)) == len(res)
Raw
leetcode_深度广度优先遍历_01矩阵and地图分析.py
"""
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
"""
import collections
class Solution:
def updateMatrix(self,matrix):
n = len(matrix)
m = len(matrix[0])
#记录结果
res = [[None for _ in range(m)] for _ in range(n)]
q = collections.deque()
for i in range(n):
for j in range(m):
if matrix[i][j] == 0:
res[i][j] = 0
q.append([i, j])
while q:
x, y = q.popleft()
for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < m and res[nx][ny] == None:
res[nx][ny] = res[x][y] + 1
q.append([nx, ny])
return res
def maxDistance(self, grid):
n = len(grid)
m = len(grid[0])
# res = [[None for _ in range(m)] for _ in range(n)]
q = collections.deque()
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
q.append([i, j])
steps = -1
if len(q) == 0 or len(q) == n ** 2:
return steps
move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while q:
# 从陆地向四周扩展，扩展后原地修改为-1
for _ in range(len(q)):
x, y = q.popleft()
for dx, dy in move:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 0:
q.append((nx, ny))
grid[nx][ny] = -1
steps += 1
return steps
Raw
leetcode_深度广度优先遍历_删除无效的括号.py
class Solution:
def removeInvalidParentheses(self, s: str) :
def isvalid(string): # 判断括号串是否合法
l_minus_r = 0
for c in string:
if c == '(':
l_minus_r += 1
elif c == ')':
l_minus_r -= 1
if l_minus_r < 0:
return False
return l_minus_r == 0
level = {s}
while True: # BFS
valid = list(filter(isvalid, level))
if valid:
return valid
level = {s[:i] + s[i + 1:] for s in level for i in range(len(s)) if s[i] in '()'}
def isvalid(string):
l_minus_r = 0
for c in string:
if c == '(':
l_minus_r += 1
elif c == ')':
l_minus_r -= 1
if l_minus_r < 0:
return False
return l_minus_r == 0
print(list(filter(isvalid, {"()()()"})))
Raw
leetcode_深度广度优先遍历_岛屿数量.py
class Solution:
def numIslands(self, grid):
if not grid:
return 0
m=len(grid)
n=len(grid[0])
visited=set()
def dfs(i,j):
if 0<=i<m and 0<=j<n and grid[i][j]=='1' and (i,j) not in visited:
#等于1标记为0
visited.add((i,j))
dfs( i + 1, j)
dfs(i, j + 1)
dfs( i - 1, j)
dfs(i, j - 1)
count=0
for i in range(m):
for j in range(n):
if grid[i][j]=='1'and (i,j) not in visited:
dfs(i,j)
count+=1
return count
if __name__ == "__main__":
# import sys
# seq = []
# res=[]
# while 1:
# line = sys.stdin.readline().strip()
# if line == '':
# break
# seq.append(line.split())
#
# print(seq)
grid=[["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"]]
s=Solution()
print(s.numIslands(grid))
Raw
leetcode_深度广度优先遍历_岛屿最大面积.py
class Solution:
def maxAreaOfIsland(self, grid):
if not grid:
return 0
m=len(grid)
n=len(grid[0])
visited=set()
def dfs(i,j):
if 0<=i<m and 0<=j<n and grid[i][j]==1 and (i,j) not in visited:
#等于1标记为0
visited.add((i,j))
k=1
k+=dfs(i + 1, j)
k+=dfs(i, j + 1)
k+=dfs( i - 1, j)
k+=dfs(i, j - 1)
#visited.remove((i,j))
return k
else:
return 0
aera=0
for i in range(m):
for j in range(n):
if grid[i][j]==1 and (i,j) not in visited:
tmp=dfs(i,j)
aera=max(tmp,aera)
return aera
if __name__ == "__main__":
s = Solution()
grid=[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
print(s.maxAreaOfIsland(grid))
Raw
leetcode_深度广度优先遍历_岛屿的周长.py
#上下左右几个0边长就加几
class Solution:
def islandPerimeter(self, grid):
if not grid:
return 0
m=len(grid)
n=len(grid[0])
visited=set()
def dfs(i,j,s):
if s>1:
return 0
# 边界或者取值为0，则返回1
if not 0<=i<m or not 0<=j<n or grid[i][j]==0:
return 1
k = 0
k+=dfs(i + 1, j,s+1)
k+=dfs(i, j + 1,s+1)
k+=dfs(i - 1, j,s+1)
k+=dfs(i, j - 1,s+1)
return k
aera = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
tmp = dfs(i, j,0)
aera+=tmp
return aera
if __name__ == "__main__":
s = Solution()
grid=[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
print(s.islandPerimeter(grid))
Raw
leetcode_深度广度优先遍历_水域大小.py
class Solution:
def pondSizes(self, land):
M=len(land)
N=len(land[0])
res=[]
def dfs(i,j):
if not (0<=i<M and 0<=j<N and land[i][j]==0):
return 0
land[i][j]=1
k=1
#上下左右
k+=dfs(i+1,j)
k+=dfs(i-1,j)
k+=dfs(i,j+1)
k+=dfs(i,j-1)
#对角线
k+=dfs(i-1,j-1)
k+=dfs(i+1,j+1)
k+=dfs(i-1,j+1)
k+=dfs(i+1,j-1)
return k
for i in range(M):
for j in range(N):
if land[i][j]==0:
k=dfs(i,j)
res.append(k)
return sorted(res)
def Mundane(self,land):
M = len(land)
N = len(land[0])
res = []
direction=[(1,0),(-1,0),(0,1),(0,-1),(1,-1),(1,-1),(-1,1),(-1,-1)]
def dfs(x,y):
k=1
for dx,dy in direction:
x_n=x+dx
y_n=y+dy
if 0<=x_n<M and 0<=y_n<N and land[x_n][y_n]==0:
land[x_n][y_n]=1
k+=dfs(x_n,y_n)
return k
for i in range(M):
for j in range(N):
if land[i][j]==0:
k=dfs(i,j)
res.append(k)
return sorted(res)
Raw
leetcode_深度广度优先遍历_被围绕的区域.py
class Solution:
def solve(self, board):
m=len(board)
n=len(board[0])
def dfs(i,j):
if not 0<i<m or not 0<j<n or board[i][j] !="O":
return
#标记O
board[i][j]="#"
dfs(i, j-1)
dfs(i, j-1)
dfs(i+1, j)
dfs(i-1, j)
#与边界联通的所有O都标记为#
for i in range(m):
dfs(i, 0)
dfs(i, n - 1)
for i in range(n):
dfs(0, i)
dfs(m - 1, i)
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
if board[i][j] == '#':
board[i][j] = 'O'
return board
if __name__ == "__main__":
s = Solution()
board=[["X","X","X","X"],["X","O","O","X"],
["X","X","O", "X"],["X","O","X","X"]]
print(s.solve(board))
Raw
leetcode_滑动窗口_最小覆盖子串.py
class solution:
def Mundane(self,s,t):
from collections import defaultdict
lookup=defaultdict(int)
#先计算t中的字符个数
for c in t:
lookup[c]+=1
start=0
end=0
min_len=float("inf")
counter=len(t)
res=""
while end<len(s):
#该字母在t中
if lookup[s[end]]>0:
counter-=1
lookup[s[end]]-=1
end+=1
#说明当前start-end包含了t
while counter==0:
if min_len>end-start:
min_len=end-start
res=s[start:end]
#最左边的数字
if lookup[s[start]]==0:
counter+=1
lookup[s[start]]+=1
start+=1
return res
if __name__ == "__main__":
s = solution()
S = "ADOBECODEBANC"
T = "ABC"
print(s.Mundane(S,T))
Raw
leetcode_滑动窗口_最长不含重复字符的子字符串.py
"""
滑动窗口
"""
class solution:
def lengthOfLongestSubstring(self,s):
from collections import defaultdict
lookup = defaultdict(int)
start = 0
end = 0
max_len = 0
counter = 0
while end < len(s):
#end表示当前遍历的指针
if lookup[s[end]] > 0:#表示该字母在前面出现过
counter += 1
lookup[s[end]] += 1
end += 1
#出现重复数字，开始移动窗口
while counter > 0:
#找重复的数字
if lookup[s[start]] > 1:
counter -= 1
lookup[s[start]] -= 1
start += 1
max_len = max(max_len, end - start)
return max_len
def Qili(self,s):
from collections import defaultdict
if not s:
return 0
left=0
end=0
n=len(s)
lookup=defaultdict(int)
max_len=0
counter=0
while end<n:
#出现重复
if lookup[s[end]]>0:
counter+=1
lookup[s[end]]+=1
end+=1
while counter>0:
#找到重复
if lookup[s[left]]>1:
counter-=1
lookup[s[left]]-=1
left+=1
max_len=max(max_len,end-left)
return max_len
def Mundane(self,s):
if not s:
return 0
left=0
n=len(s)
lookup=set()
max_len=0
cur_len=0
for i in range(n):
cur_len+=1
while s[i] in lookup:
lookup.remove(s[left])
left+=1
cur_len-=1
max_len=max(max_len,cur_len)
lookup.add(s[i])
return max_len
if __name__ == "__main__":
s = solution()
str="abcabcbb"
print(s.Qili(str))
Raw
leetcode_滑动窗口_至多包含两个不同字符的最长子串.py
"""
至多包含两个不同字符的最长子串
"""
class solution:
def Mundane(self,s):
from collections import defaultdict
start=0
end=0
lookup=defaultdict(int)
max_len=0
n=len(s)
counter=0
while end<n:
#之前没出现过，说明是新字母
if lookup[s[end]]==0:
counter+=1
lookup[s[end]]+=1
end+=1
while counter>2:
#只剩1个字母了，此次迭代就可以减少一个字母
if lookup[s[start]]==1:
counter-=1
lookup[s[start]]-=1
start+=1
max_len=max(max_len,end-start)
return max_len
if __name__ == "__main__":
s = solution()
str="ccaabbb"
print(s.Mundane(str))
Raw
leetcode_背包问题_零钱兑换.py
class Solution:
def coinChange(self, coins, amount):
#背包问题
#dp[i]表示组成金额i所需要的最小硬币数
N=len(coins)
dp=[float("inf")]*(amount+1)
dp[0]=0
for i in range(1,amount+1):
for coin in coins:
if i-coin >=0:
dp[i]=min(dp[i],dp[i-coin]+1)
return dp[-1] if(dp[-1]!=float("inf")) else -1
Raw
leetcode_设计_设计推特.py
from collections import defaultdict
class Twitter:
def __init__(self):
self.cnt=0
self.user_post=defaultdict(list)
self.user_follow=defaultdict(set)
def postTweet(self,userID,tweetID):
self.user_post[userID].append([self.cnt,tweetID])
self.cnt+=1
def getNewsFeed(self,userID):
persons=self.user_follow[userID]
res=[]
res.extend(self.user_post[userID])
for person in persons:
res.extend(self.user_post[person])
res.sort(key=lambda x:x[0],reverse=True)
ans=[]
for p in res[:10]:
ans.append(p[1])
return ans
def follow(self,followID,followeeID):
if followID!=followeeID:
self.user_follow[followID].add(followeeID)
def unfollow(self, followID, followeeID):
if followeeID in self.user_follow[followID]:
self.user_follow[followID].remove(followeeID)
Raw
leetcode_链表_1.两数相加.py
"""
给出两个非空的链表用来表示两个非负的整数。
其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
"""
from linklist import ListNode
class Solution:
def addTwoNum(self,l1,l2):
ans=ListNode(-1)
cur=ans
#表示进位
flag=0
while l1 or l2:
x=l1.val if l1 else 0
y=l2.val if l2 else 0
s=flag+x+y
flag=s//10
#余数
cur.next=ListNode(s%10)
cur=cur.next
if l1:
l1=l1.next
if l2:
l2=l2.next
if flag>0:
cur.next=ListNode(1)
return ans.next
class Solution2:
def addTwoNum(self,l1,l2):
ans=ListNode(0)
if not l1:
return l2
if not l2:
return l1
val=l1.val+l2.val
ans=ListNode(val%10)
ans.next=self.addTwoNum(l1.next,l2.next)
if val>=10:
ans.next=self.addTwoNum(ListNode(1),ans.next)
return ans
def Mundane(self,l1,l2):
if not l1:
return l2
if not l2:
return l1
val=l1.val+l2.val
ans=ListNode(val%10)
ans.next=self.addTwoNum(l1.next,l2.next)
if val>=10:
ans.next=self.addTwoNum(ListNode(1),ans.next)
return ans
#两数相加II
class Solution:
"""
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
"""
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
s1=""
s2=""
p=l1
q=l2
while p:
s1+=str(p.val)
p=p.next
while q:
s2+=str(q.val)
q=q.next
res=str(int(s1)+int(s2))
ans=ListNode(-1)
pre=ans
for i in res:
pre.next=ListNode(i)
pre=pre.next
return ans.next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
stack1 = []
stack2 = []
while l1:
stack1.append(l1.val)
l1 = l1.next
while l2:
stack2.append(l2.val)
l2 = l2.next
node = None
carry = 0
while stack1 or stack2:
x = stack1.pop() if stack1 else 0
y = stack2.pop() if stack2 else 0
val= x + y + carry
carry = val // 10
n = val % 10
cur = ListNode(n)
cur.next = node#!!!!!!!!!!!!!!!!!!尾插法
node = cur
# 判断最高位是否有进位
if carry != 0:
res = ListNode(carry)
res.next = cur
return res
return cur
def list2link(li):
n=len(li)
ans=ListNode(-1)
cur=ans
for i in range(n):
cur.next=ListNode(li[i])
cur=cur.next
return ans.next
def link2list(li):
ans=[]
while li:
ans.append(li.val)
li=li.next
return ans
if __name__=="__main__":
a=[4,4,4]
b=[4,6,4]
l1=list2link(a)
l2=list2link(b)
s=Solution()
out=s.addTwoNum(l1,l2)
print(link2list(out))
Raw
leetcode_链表_10.分隔链表.py
"""
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
思路：双链表分别记录大于x和小于x的
"""
from linklist import *
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
d1=ListNode(-1)
d2=ListNode(-1)
p1=d1
p2=d2
while head:
if head.val<x:
p1.next=head
p1=p1.next
head=head.next
else:
p2.next=head
p2=p2.next
head=head.next
p1.next=d2.next
p2.next=None
return d1.next
if __name__=="__main__":
a=[1,4,3,2,5,2]
x=3
l1=convert.list2link(a)
s=Solution()
out=s.partition(l1,x)
print(convert.link2list(out))
Raw
leetcode_链表_11.翻转链表II.py
"""
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
"""
from linklist import *
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
slow,fast=head,head
for i in range(m):
slow=slow.next
Raw
leetcode_链表_12.有序链表转二叉搜索树.py
"""
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
思路:快慢指针找到中点，递归的处理左右子树。
"""
from linklist import *
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
def findmid(head, tail):
slow = head
fast = head
while fast != tail and fast.next != tail:
slow = slow.next
fast = fast.next.next
return slow
def helper(head, tail):
if head == tail:
return
node = findmid(head, tail)
root = TreeNode(node.val)
root.left = helper(head, node)
root.right = helper(node.next, tail)
return root
return helper(head, None)
if __name__=="__main__":
a=[-10, -3, 0, 5, 9]
l1=convert.list2link(a)
s=Solution()
out=s.sortedListToBST(l1)
print(convert.tree2list(out))
Raw
leetcode_链表_13.复制带随机指针的链表.py
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
lookup = {}
def dfs(head):
if not head:
return None
if head in lookup:
return lookup[head]
clone = Node(head.val, None, None)
lookup[head] = clone
clone.next, clone.random = dfs(head.next), dfs(head.random)
return clone
return dfs(head)
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return
#复制节点
cur=head
while cur:
tmp=cur.next
cur.next=Node(cur.val,None,None)
cur.next.next=tmp
cur=tmp
#复制随机节点
cur=head
while cur:
if cur.random:
cur.next.random=cur.random.next
cur=cur.next.next
#拆分
cur=head
copy_head=head.next
copy_cur=copy_head
while copy_cur.next:
cur.next=cur.next.next
cur=cur.next
copy_cur.next=copy_cur.next.next
copy_cur=copy_cur.next
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
# 复制节点
cur = head
while cur:
# 保存下一个节点
tmp = cur.next
# 后面跟着同样的节点
cur.next = Node(cur.val, None, None)
# 拼接
cur.next.next = tmp
cur = tmp
# 复制random指针
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# 拆分
cur = head
copy_head = head.next
copy_cur = copy_head
while copy_cur.next:
# 组head
cur.next = cur.next.next
cur = cur.next
# 组 copy_head
copy_cur.next = copy_cur.next.next
copy_cur = copy_cur.next
# 把链表结束置空
cur.next = copy_cur.next
copy_cur.next = None
return copy_head
Raw
leetcode_链表_14.环形链表.py
"""
给定一个链表，判断链表中是否有环。为了表示给定链表中的环，
我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。
输入：head = [3,2,0,-4], pos = 1
输出：true
"""
from linklist import *
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head:
return False
slow,fast=head,head.next
while fast and fast.next:
slow=slow.next
fast=fast.next.next
if slow==fast:
return True
return False
Raw
leetcode_链表_15.环形链表II.py
"""
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
"""
from linklist import *
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow,fast=head,head
while slow!=fast:
slow=slow.next
fast=fast.next.next
#第一次相遇的时候，快指针比慢指针多走了一个环的距离
cur=head
while cur!=slow:
cur=cur.next
slow=slow.next
return slow
Raw
leetcode_链表_16.重排链表.py
"""
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
思路：快慢指针找到中点Lm，然后将Lm后面的翻转得 Ln,Ln-1,Ln-2
然后得到两个序列L0,L1,...Lm和Ln,Ln-1,Ln-2，然后交替连接即可
#交替连接，首先保存左右的next，然后将左指针连接到右指针，把右指针和左next连接
然后更新左右指针
"""
from linklist import *
class Solution:
def reorderList(self, head: ListNode) -> None:
if head==None or head.next==None:
return head
#快慢指针找中点
slow,fast=head,head
while fast.next and fast.next.next:
slow=slow.next
fast=fast.next.next
right_reverse=slow.next
slow.next=None
right_reverse=self.reverse(right_reverse)##4->3
#指针
left_cur=head
right_cur=right_reverse
while left_cur and right_cur:
#保存右侧指针
right_next=right_cur.next
left_next=left_cur.next
#连接
right_cur.next=left_cur.next
left_cur.next=right_cur
#更新指针
left_cur=left_next
right_cur=right_next
return head
def reverse(self, head: ListNode):
if head == None or head.next == None:
return head
tmp = head.next
cur = self.reverse(tmp)
tmp.next = head
head.next = None
return cur
if __name__=="__main__":
a=[1,2,3,4,5,6]
l1=convert.list2link(a)
s=Solution()
out=s.reorderList(l1)
print(convert.link2list(out))
Raw
leetcode_链表_17.对链表进行插入排序.py
"""
"""
from linklist import *
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
ans=ListNode(-1)
ans.next=head
while head and head.next:
if head.val<=head.next.val:
head=head.next
else:
#pre用来排序
pre=ans
while pre.next.val<head.next.val:
pre=pre.next
cur=head.next
head.next=cur.next
cur.next=pre.next
pre.next=cur
return ans.next
if __name__=="__main__":
a=[4,5,3,6,1,7,8,2]
l1=convert.list2link(a)
s=Solution()
out=s.insertionSortList(l1)
print(convert.link2list(out))
Raw
leetcode_链表_18.排序链表(快排+归并).py
"""
链表的快排与归并排序
"""
from linklist import *
class Solution:
def sortList(self, head: ListNode) -> ListNode:
"""
归并排序，要找中点，链表中点用快慢指针
:param head:
:return:
"""
if not head or not head.next:
return head
slow,fast=head,head
while fast.next and fast.next.next:
slow=slow.next
fast=fast.next.next
right=self.sortList(slow.next)
slow.next=None#切断
left=self.sortList(head)
return self.mergesort(left,right)
def mergesort(self,head1,head2):
ans=ListNode(-1)
pre=ans
while head1 and head2:
if head1.val<=head2.val:
pre.next=head1
head1=head1.next
pre=pre.next
else:
pre.next=head2
head2=head2.next
pre=pre.next
if head1:
pre.next=head1
if head2:
pre.next=head2
return ans.next
class Solution:
def sortList(self, head: ListNode) -> ListNode:
"""
快排
:param head:
:return:
"""
if not head or not head.next:
return head
ans = ListNode(-1)
ans.next = head
return self.quicksort(ans, None)
def quicksort(self, head, end):
if head == end or head.next == end or head.next.next == end:
return head
tmp = ListNode(-1)
partition = head.next
p = partition
#用来记录排序结果？
t = tmp
while p.next!=end:
if p.next.val < partition.val:
t.next = p.next
t = t.next
p.next = p.next.next
#大于partitio的val，不操作
else:
p = p.next
t.next = head.next#head.next 是未排序前
head.next = tmp.next
self.quicksort(head, partition)
self.quicksort(partition, end)
return head.next
if __name__=="__main__":
a=[4,5,3,6,1,7,8,2]
l1=convert.list2link(a)
s=Solution()
out=s.sortList(l1)
print(convert.link2list(out))
Raw
leetcode_链表_2.删除链表的倒数第N个节点.py
"""
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
进阶：
你能尝试使用一趟扫描实现吗？
思路：快慢指针
"""
from linklist import ListNode
class Solution:
def removeNthFromEnd(self, head, n):
if not head or not head.next:
return head
fast,slow=head,head
for i in range(n):
fast=fast.next
while fast.next:
fast=fast.next
slow=slow.next
#slow此时定位的下一个节点就是要删除的节点
slow.next=slow.next.next
return head
def list2link(li):
n=len(li)
ans=ListNode(-1)
cur=ans
for i in range(n):
cur.next=ListNode(li[i])
cur=cur.next
return ans.next
def link2list(li):
ans=[]
while li:
ans.append(li.val)
li=li.next
return ans
if __name__=="__main__":
a=[1,2,3,4,5]
n=2
head=list2link(a)
s=Solution()
out=s.removeNthFromEnd(head,n)
print(link2list(out))
Raw
leetcode_链表_21.反转链表.py
"""
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
"""
from linklist import *
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre=None
cur=head
while cur:
tmp=cur.next
cur.next=pre
pre=cur
cur=tmp
return pre
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
tmp=head.next
cur=self.reverseList(tmp)
tmp.next=head
head.next=None
return cur
#翻转链表2
class Solution:
"""
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转
"""
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
tmpHead = ListNode(0)
tmpHead.next = head
node = tmpHead
for i in range(1, m):
node = node.next
# node.next就是反转前的起点
cur = node.next
pre = None
for i in range(m, n + 1):
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
print(cur)
#这里的顺序不能搞错！！！！！！！
node.next.next = tmp
node.next = pre
return tmpHead.next
if __name__=="__main__":
a=[1,2,3,4,5]
l1=convert.list2link(a)
s=Solution()
out=s.reverseList(l1)
print(convert.link2list(out))
Raw
leetcode_链表_3.合并两个有序链表.py
from linklist import ListNode
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
ans=ListNode(-1)
cur=ans
while l1 and l2:
if l1.val<=l2.val:
cur.next=l1
l1=l1.next
else:
cur.next=l2
l2=l2.next
cur=cur.next
if l1:
cur.next=l1
if l2:
cur.next=l2
return ans.next
def list2link(li):
n=len(li)
ans=ListNode(-1)
cur=ans
for i in range(n):
cur.next=ListNode(li[i])
cur=cur.next
return ans.next
def link2list(li):
ans=[]
while li:
ans.append(li.val)
li=li.next
return ans
if __name__=="__main__":
a=[1,2,4]
b=[1,3,4]
l1=list2link(a)
l2=list2link(b)
s=Solution()
out=s.mergeTwoLists(l1,l2)
print(link2list(out))
Raw
leetcode_链表_4.合并K个排序链表.py
from linklist import ListNode
class Solution:
def mergeKLists(self, lists):
if not lists:
return
n=len(lists)
return self.merge(lists,0,n-1)
def merge(self,lists,left,right):
if left==right:
return lists[left]
mid=left+(right-left)//2
l1=self.merge(lists,left,mid)
l2=self.merge(lists,mid+1,right)
return self.mergeTwoLists(l1,l2)
def mergeTwoLists(self, l1,l2):
if not l1:
return l2
if not l2:
return l1
if l1.val<l2.val:
l1.next=self.mergeTwoLists(l1.next,l2)
return l1
else:
l2.next=self.mergeTwoLists(l1,l2.next)
return l2
#O(knlog(k))
Raw
leetcode_链表_5.两两交换链表中的节点.py
"""
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
给定 1->2->3->4, 你应该返回 2->1->4->3.
"""
from linklist import ListNode,convert
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
cur=head.next
head.next=self.swapPairs(cur.next)
cur.next=head
return cur
def Mundane(self,head):
ans = ListNode(-1)
ans.next = head
pre = ans
cur = ans.next
while cur and cur.next:
tmp = cur.next
pre.next = tmp
cur.next = tmp.next
tmp.next = cur
pre = cur
cur = cur.next
return ans.next
if __name__=="__main__":
a=[1,2,3,4,5,6]
l1=convert.list2link(a)
s=Solution()
out=s.swapPairs(l1)
print(convert.link2list(out))
Raw
leetcode_链表_6.K个一组链表翻转.py
"""
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
"""
from linklist import *
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if not head or not head.next:
return head
#标记当前头结点 去判断翻转节点,若长度不够，则不翻转
#head=[1,2,3,4,5,6,7]
#tail=[4,5,6,7]
tail=head
for i in range(k):
if tail==None:
return head
tail=tail.next
#[3,2,1]
newhead=self.reverse(head,tail)
head.next=self.reverseKGroup(tail,k)
return newhead
#翻转head到tail之间的部分
def reverse(self,head,tail):
pre=None
while head!=tail:
tmp=head.next
head.next=pre
pre=head
head=tmp
return pre
if __name__=="__main__":
a=[1,2,3,4,5,6,7]
k=3
l1=convert.list2link(a)
s=Solution()
out=s.reverseKGroup(l1,k)
print(convert.link2list(out))
Raw
leetcode_链表_7.旋转链表.py
"""
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
"""
from linklist import *
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
ans=ListNode(-1)
fast,slow=head,head
#判断链表长度与k之间的关系
cur=head
n=0
while cur:
cur=cur.next
n+=1
if n==0 or k%n==0:
return head
n=k%n
for i in range(n):
fast=fast.next
while fast.next:
fast=fast.next
slow=slow.next
tmp=slow.next
fast.next=head
ans.next=tmp
slow.next=None
return ans.next
if __name__=="__main__":
a=[1,2,3,4,5]
k=2
l1=convert.list2link(a)
s=Solution()
out=s.rotateRight(l1,k)
print(convert.link2list(out))
a=[0,1,2]
k=4
l1=convert.list2link(a)
s=Solution()
out=s.rotateRight(l1,k)
print(convert.link2list(out))
Raw
leetcode_链表_8.删除排序链表中的重复元素I.py
"""
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
输入: 1->2->3->3->4->4->5
输出: 1->2->5
输入: 1->1->1->2->3
输出: 2->3
"""
from linklist import *
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
ans=ListNode(-1)
ans.next=head
pre=ans
while pre.next and pre.next.next:
if pre.next.val==pre.next.next.val:
tmp=pre.next.val
cur=pre.next
while cur and cur.val==tmp:
cur=cur.next
pre.next=cur
else:
pre=pre.next
return ans.next
if __name__=="__main__":
a=[1,2,3,3,4,4,5,5]
l1=convert.list2link(a)
s=Solution()
out=s.deleteDuplicates(l1)
print(convert.link2list(out))
Raw
leetcode_链表_9.删除排序链表中的重复元素II.py
"""
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
输入: 1->1->2
输出: 1->2
输入: 1->1->2->3->3
输出: 1->2->3
"""
from linklist import *
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
ans=ListNode(-1)
ans.next=head
while head and head.next:
if head.val==head.next.val:
head.next=head.next.next
else:
head=head.next
return ans.next
if __name__=="__main__":
a=[1,1,2,3,3]
l1=convert.list2link(a)
s=Solution()
out=s.deleteDuplicates(l1)
print(convert.link2list(out))
Raw
leetcode_链表_linklist.py
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class convert:
def list2link(li):
n=len(li)
ans=ListNode(-1)
cur=ans
for i in range(n):
cur.next=ListNode(li[i])
cur=cur.next
return ans.next
def link2list(li):
ans=[]
while li:
ans.append(li.val)
li=li.next
return ans
def tree2list(node):
res=[]
def dfs(node):
if not node:
return
res.append(node.val)
dfs(node.left)
dfs(node.right)
return res
Raw
leetcode_链表_二叉树中的列表.py
class Solution:
"""
类似于A是B的子树
"""
def isSubPath(self, head, root) -> bool:
if not root:
return False
return self.helper(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
def helper(self, head, root):
if not head:
return True
if root and root.val != head.val or not root:
return False
return self.helper(head.next, root.left) or self.helper(head.next, root.right)
class Solution:
def isSubPath(self, head, root) -> bool:
if not head or not root:
return False
stack = [root]
while stack:
node = stack.pop()
if node.val == head.val:
res = self.find(head, node)
if res:
return res
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return False
def find(self, head, root):
if head.val != root.val:
return False
if not head.next:
return True
if root.left and root.right:
return self.find(head.next, root.left) or self.find(head.next, root.right)
elif root.left:
return self.find(head.next, root.left)
elif root.right:
return self.find(head.next, root.right)
else:
return False
Raw
leetcode_链表_从链表中删去总和值为零的连续节点.py
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
"""
关键点：
如果i-j之间的和为0
那么0-i和0-j之间的和是相等的
[1,2,3,-3,4]
[0,1,2,3,4] 0-1的和为3，0-3的和为3，所以2-3的和是0.
"""
def removeZeroSumSublists(self, head):
l = ListNode(0)
l.next = head
d = {0:l}
s = 0
while head:
s+=head.val
if s in d:
d[s].next = head.next
return self.removeZeroSumSublists(l.next)
else:
d[s] = head
head = head.next
return l.next
def Mundane(self,head):
l = ListNode(0)
l.next = head
d={0:l}
node, s = head, 0
while node:
s += node.val
if s not in d:
d[s] = node
else:
node = d[s].next
tmp = node.val + s
# 同前缀和的两点之间的节点删掉
while tmp != s:
del d[tmp]
node = node.next
tmp += node.val
# 删掉两点之间的后，接上不重复的段
d[s].next = node.next
node = node.next
return l.next
Raw
leetcode_链表_删除链表 M 个节点之后的 N 个节点.py
class Solution:
def deleteNodes(self, head, m: int, n: int):
p = head
while p and p.next:
for i in range(m - 1):
if p.next:
p = p.next
else:
break
cur = p
for j in range(n):
if cur and cur.next:
cur = cur.next
else:
break
p.next = cur.next
p = p.next
return head
Raw
leetcode_链表_删除链表中的节点.py
class Solution:
def deleteNode(self,node):
"""
原地删除 秀
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next
Raw
leetcode_链表_回文链表.py
"""
编写一个函数，检查输入的链表是否是回文的。
思路：快慢指针找中点，然后将后面的链表翻转，然后比较翻转后的链表和头结点的值。
"""
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if head == None or head.next == None:
return True
p = ListNode(-1)
p.next = head
slow, fast = p, p
while fast and fast.next:
fast = fast.next.next
slow = slow.next
#找到中点，将后面翻转
tmp = self.reverse(slow.next)
while tmp:
if head.val != tmp.val:
return False
head = head.next
tmp = tmp.next
return True
def reverse(self, node: ListNode) -> ListNode:
if node == None or node.next == None:
return node
tmp = node.next
ans = self.reverse(tmp)
tmp.next = node
node.next = None
return ans
Raw
leetcode_链表_奇偶链表.py
class Solution:
def oddEvenList(self, head):
if not head:
return head
p=head
tmpHead=q=p.next
while q and q.next:
p.next=p.next.next
q.next=q.next.next
p,q=p.next,q.next
p.next=tmpHead
return head
Raw
leetcode_链表_循环有序列表的插入.py
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':
if not head:
newNode = Node(insertVal,head)
newNode.next = newNode
return newNode
p = head
while p.next:
if p.val <= insertVal <= p.next.val:
break
# 就一个值
if p.next == head:
break
if p.val > p.next.val and (p.val <= insertVal or insertVal <= p.next.val):
break
p = p.next
node = Node(insertVal)
next = p.next
p.next = node
node.next = next
return head
Raw
leetcode_链表_环路检测.py
class Solution:
def detectCycle(self, head):
slow, fast = head, head
while fast and fast.next: #开始走位
slow = slow.next
fast = fast.next.next
if slow == fast: # 相遇
break
if not fast or not fast.next:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
Raw
leetcode_链表_给单链表加1.py
"""
先翻转链表，然后借助两数相加的原理加(考虑进位)，最后再翻转
"""
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def plusOne(self, head: ListNode) -> ListNode:
def reverseList(head):
if not head or not head.next:
return head
cur = reverseList(head.next)
tmp = head.next
tmp.next = head
head.next = None
return cur
head = reverseList(head)
p = head
carry = 1
while p:
carry, b = divmod(p.val + carry, 10)
p.val = b
if carry == 0:
break
if not p.next and carry:
p.next = ListNode(0)
p = p.next
return reverseList(head)
Raw
leetcode_链表_返回倒数第 k 个节点.py
class Solution:
def kthToLast(self, head, k: int) -> int:
slow,fast=head,head
for _ in range(k):
fast=fast.next
if not fast:
return head.val
while fast.next:
slow=slow.next
fast=fast.next
return slow.next.val
Raw
leetcode_链表_链表求和.py
"""
同two_sum
"""
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
ans=ListNode(-1)
cur=ans
#表示进位
flag=0
while l1 or l2:
x=l1.val if l1 else 0
y=l2.val if l2 else 0
s=flag+x+y
flag=s//10
#余数
cur.next=ListNode(s%10)
cur=cur.next
if l1:
l1=l1.next
if l2:
l2=l2.next
if flag>0:
cur.next=ListNode(1)
return ans.next
Raw
leetcode_链表_链表相交.py
class Solution:
def getIntersectionNode(self, headA,headB):
node1, node2 = headA, headB
while node1 != node2:
node1 = node1.next if node1 else headB
node2 = node2.next if node2 else headA
return node1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment