动态规划,回溯法,广度优先搜索(DFS)
目录:
1,Leetcode-416
2,Leetcode-17
3,Leetcode-64
4,Leetcode-70
5,Leetcode-279
6,Leetcode-695
7,Leetcode-343
8,Leetcode-583
9,Leetcode-303
10,Leetcode-300
11,Leetcode-309
1,Leetcode-416:
# leetcode-416:动态规划, beats 56.04%
class Solution:
def canPartition(self, nums: List[int]) -> bool:
c = sum(nums)
if c % 2 != 0:
return False
c = c//2 # 取整
w = [False] * (c+1)
w[0] = True
for num in nums:
for i in range(c, num-1, -1):
w[i] = w[i] or w[i-num]
return w[c]
2,Leetcode-17:
# leetcode-17:回溯法,beats 83.25%
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
self.keys = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
combinations, prefix = [], ''
if not digits:
return combinations
self.doCombinations(prefix, combinations, digits)
return combinations
def doCombinations(self, prefix:str, combinations: List[str], digits: str):
if len(prefix) == len(digits):
combinations.append(prefix)
return
for i in self.keys[int(digits[len(prefix)])]:
prefix += i
self.doCombinations(prefix, combinations, digits)
prefix = prefix[:-1]
3,Leetcode-64:
# leetcode-64:最小路径和,beats 68.36%
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
r = len(grid) # 行数
c = len(grid[0]) # 列数
dp = [0] * c
for i in range(r):
for j in range(c):
if j == 0:
dp[j] = dp[j]
elif i == 0:
dp[j] = dp[j-1]
else:
dp[j] = min(dp[j-1], dp[j])
dp[j] += grid[i][j]
return dp[c-1]
4,Leetcode-70:
# leetcode-70:斐波那契数列
class Solution: # beats 17.26%
def climbStairs(self, n: int) -> int:
if n < 3:
return n
pre2, pre1 = 1, 2
for i in range(2, n):
pre1, pre2 = pre1+pre2, pre1
return pre1
5,Leetcode-279:
# leetcode-279:广度优先搜索(DFS),beats 51.82%
class Solution:
def numSquares(self, n: int) -> int:
squares = []
square, interval = 1, 3
while square <= n:
squares.append(square)
square += interval
interval += 2
list.reverse(squares)
q = [(0, n)]
used = [False for i in range(n+1)]
while q:
temp = q.pop(0)
if temp[1] == 0:
return temp[0]
for s in squares:
if temp[1] - s >= 0 and not used[temp[1] - s]:
q.append((temp[0] + 1, temp[1] - s))
used[temp[1] - s] = True
return -1
6,Leetcode-695:
# leetcode-695:广度优先搜索(DFS),beats 44.88%
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid:
return 0
self.r, self.c, max_area = len(grid), len(grid[0]), 0
for i in range(self.r):
for j in range(self.c):
max_area = max(max_area, self.dfs(grid, i, j))
return max_area
def dfs(self, grid: List[List[int]], n: int, m: int) -> int:
if n < 0 or n >= self.r or m<0 or m>=self.c or grid[n][m] == 0:
return 0
area, grid[n][m] = 1, 0
area += self.dfs(grid, n-1, m)
area += self.dfs(grid, n+1, m)
area += self.dfs(grid, n, m+1)
area += self.dfs(grid, n, m-1)
return area
7,Leetcode-343:
# leetcode-343:动态规划,beats 57.79%
class Solution:
def integerBreak(self, n: int) -> int:
sums = [0, 1]
for i in range(2, n+1):
tmp = 0
for j in range(1, i):
tmp = max(tmp, j*sums[i-j], j*(i-j))
sums.append(tmp)
return sums[n]
8,Leetcode-583:
# leetcode-583:动态规划,beats 87.48%
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
dp = [[0] * (n+1) for i in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
return m+n- 2 * dp[m][n]
9,Leetcode-303:
# leetcode-303:
class NumArray: # 动态规划, beats 83.14%
def __init__(self, nums: List[int]):
self.nums = nums
self.sums = [-1] * (len(self.nums) + 1)
for i in range(1, len(self.nums) + 1):
self.sums[i] = self.sums[i-1] + self.nums[i-1]
def sumRange(self, i: int, j: int) -> int:
return self.sums[j+1] - self.sums[i]
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)
class NumArray: # 记忆性搜索法,beats 7.05%
def __init__(self, nums: List[int]):
self.nums = nums
self.sums = [-1] * (len(self.nums) + 1)
def sumRange(self, i: int, j: int) -> int:
if self.sums[i] == -1:
self.sums[i] = self.sum_x(i)
if self.sums[j+1] == -1:
self.sums[j+1] = self.sum_x(j+1)
return self.sums[j+1] - self.sums[i]
def sum_x(self, x):
sum = 0
for i in range(x):
sum += self.nums[i]
return sum
10,Leetcode-300:
# leetcode-300:动态规划,beats 53.08%
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
LIS = [1] * len(nums)
for i in range(1, len(nums)):
LIS[i] = max([1+LIS[j] for j in range(i) if nums[j] < nums[i]] + [1])
return max(LIS)
11,Leetcode-309:
# leetcode-309:动态规划,beats 95.44%
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1:
return 0
buy, pre_buy, sell, pre_sell = -max(prices), 0, 0, 0
for p in prices:
pre_buy = buy
buy = max(pre_sell - p, pre_buy)
pre_sell = sell
sell = max(pre_buy + p, pre_sell)
return sell
本文分享自 MiningAlgorithms 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!