leetcode64. 最小路徑和
給定一個包含非負整數(shù)的 m x n 網(wǎng)格,請找出一條從左上角到右下角的路徑杏死,使得路徑上的數(shù)字總和為最小泵肄。
說明:每次只能向下或者向右移動一步。
技巧:不用遞歸淑翼,原地更新該位置的最小路徑和
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
if not grid:
return
num1 = len(grid)
num2 = len(grid[0])
if num1==1:
return sum(grid[0])
sum1=0
if num2==1:
for i in range(0,num2):
sum1=sum1+grid[i][0]
return sum1
for i in range(1,num2):
grid[0][i]=grid[0][i-1]+grid[0][i]
for j in range(1,num1):
grid[j][0]=grid[j-1][0]+grid[j-1][0]
for i in range(2,num1):
for j in range(2,num2):
if grid[i-1][j]<=grid[i][j-1]:
grid[i][j]=grid[i-1][j]+grid[i][j]
else:
grid[i][j]=grid[i][j-1]+grid[i][j]
return grid[num1-1][num2-1]
leetcode322. 零錢兌換
給定不同面額的硬幣 coins 和一個總金額 amount腐巢。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)。如果沒有任何一種硬幣組合能組成總金額玄括,返回 -1冯丙。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,-1);
sort(coins.begin(),coins.end());
dp[0]=0;
for(int i=1;i<=amount;i++){
for(int j=0;j<coins.size();j++){
if(coins[j]>i)
break;
if(dp[i-coins[j]]!=-1){
if(dp[i]==-1 ||dp[i]>dp[i-coins[j]]+1){
dp[i]=dp[i-coins[j]]+1;
}
}
}
}
return dp[amount];
}
};
leetcode70. 爬樓梯
假設你正在爬樓梯。需要 n 階你才能到達樓頂遭京。
每次你可以爬 1 或 2 個臺階胃惜。你有多少種不同的方法可以爬到樓頂呢?
class Solution:
def climbStairs(self, n: int) -> int:
if n==1 or n==0:
return 1
elif n==2:
return 2
else:
return self.climbStairs(n-1)+self.climbStairs(n-2)
leetcode46. 全排列
給定一個沒有重復數(shù)字的序列哪雕,返回其所有可能的全排列船殉。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
from itertools import permutations
return list(permutations(nums))