1 .?斐波那契数??
?
class Solution:
def fib(self, n: int) -> int:
# if n==0:
# return 0
# elif n==1:
# return 1
# else:
# return self.fib(n-1)+self.fib(n-2)
a =0
b =1
for i in range(n):
a,b = b,a+b
return a
class Solution {
public:
int fib(int n) {
int a = 0, b = 1;
for(int i = 0; i < n; i++){
int temp = a;
a = a + b;
b = temp;
}
return a;
}
};
2. 第 N 个泰波那契数
class Solution:
def tribonacci(self, n: int) -> int:
if n == 0:
return 0
if n <= 2:
return 1
dp = [0]*(n+1)
dp[1] = 1
dp[2] = 1
for i in range(3, n+1):
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
return dp[-1]
class Solution {
public:
int tribonacci(int n) {
if(n == 0){
return 0;
}
if(n <= 2){
return 1;
}
vector<int> dp(n + 1, 0);
dp[1] = 1;
dp[2] = 1;
for(int i = 3; i < n+1; i++){
dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
}
return dp[n];
}
};
3. 爬楼梯
?
?
class Solution:
def climbStairs(self, n: int) -> int:
if n < 3:
return n
a = 1
b = 2
for i in range(3, n + 1):
a, b = b, a + b
return b
class Solution {
public:
int climbStairs(int n) {
if(n < 3){
return n;
}
int a = 1, b = 2;
for(int i = 3; i < n + 1; i++){
int temp = b;
b = a + b;
a = temp;
}
return b;
}
};
?4. 使用最小花费爬楼梯
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
dp = [0]*len(cost)
dp[0],dp[1] =cost[0],cost[1]
for i in range(2,len(cost)):
dp[i] = min(dp[i-1],dp[i-2])+cost[i]
return min(dp[-1],dp[-2])
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n, 0);
dp[0] = cost[0];
dp[1] = cost[1];
for(int i = 2; i < n; i++){
dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
}
return min(dp[n-2], dp[n-1]);
}
};
?5. 打家劫舍
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return max(nums)
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[1],nums[0])
for i in range(2, n):
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
return dp[-1]
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 0){
return 0;
}
if(n == 1){
return nums[0];
}
if(n == 2){
return max(nums[0],nums[1]);
}
vector<int> dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for(int i = 2; i < n; i++){
dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[n-1];
}
};
6. 打家劫舍 II
?
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return max(nums)
dp1 = [0]*n
dp2 = [0]*n
dp1[0] = 0
dp1[1] = nums[1]
dp2[0] = nums[0]
dp2[1] = max(nums[0], nums[1])
for i in range(2, n):
dp1[i] = max(dp1[i-2]+nums[i], dp1[i-1])
for i in range(2, n-1):
dp2[i] = max(dp2[i-2]+nums[i], dp2[i-1])
return max(dp1[-1], dp2[-2])
7. 删除并获得点数?
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
maxVal = max(nums)
total = [0] * (maxVal + 1)
for val in nums:
total[val] += val
# print(total)
n = len(total)
dp = [0]*n
if n <=2:
return max(total)
dp[0] = total[0]
dp[1] = max(total[0], total[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + total[i])
return dp[-1]
?8.?跳跃游戏
class Solution:
def canJump(self, nums: List[int]) -> bool:
#贪心算法
most_dis = 0
for i in range(len(nums)):
if i <= most_dis:
most_dis = max(most_dis, nums[i] + i)
if most_dis >= len(nums) - 1:
return True
return False
class Solution {
public:
bool canJump(vector<int>& nums) {
int most_length = 0;
for(int i = 0; i < nums.size(); i++){
if(i <= most_length){
most_length = max(nums[i] + i, most_length);
}
if(most_length >= nums.size() - 1){
return true;
}
}
return false;
int n = nums.size();
vector<bool> opt(n, false);
opt[0] = true;
for(int i = 1; i < n; i++){
opt[i] = opt[i - 1] && nums[i-1] >= 1;
nums[i] = max(nums[i - 1] - 1, nums[i]);
}
return opt[n-1];
}
};
9.?跳跃游戏 II
class Solution {
public:
int jump(vector<int>& nums) {
int res = 0;
int start = 0;
int end = 1;
int maxPos = 0;
while(end < nums.size()){
for(int i = start; i < end; i++){
//能跳到的最远距离
maxPos = max(maxPos, nums[i] + i);
}
start = end;//下一次起跳点范围开始的格子
end = maxPos + 1;//下一次起跳点范围结束的格子
res++;
}
return res;
}
};
10.?最大子序和
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
nums[i]+=max(nums[i-1],0)
return max(nums)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int max_num = nums[0];
for(int i = 1; i < n; i++){
nums[i] += max(nums[i-1], 0);
max_num = max(nums[i], max_num);
}
return max_num;
}
};
11.?环形子数组的最大和
题解:
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
dpmax = nums.copy()
dpmin = nums.copy()
sum_ = sum(nums)
for i in range(1, len(nums)):
dpmax[i] = max(dpmax[i-1]+nums[i], dpmax[i])
for i in range(1, len(nums)):
dpmin[i] = min(dpmin[i-1]+nums[i], dpmin[i])
# print(dpmax)
# print(dpmin)
max_value = max(dpmax)
min_value = min(dpmin)
if (sum_ - min_value) == 0:
return max_value
else:
return max(max_value, sum_ - min_value)
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int sum_ = nums[0];
vector<int>dpmax(nums);
vector<int>dpmin(nums);
for(int i=1;i<nums.size();i++){
dpmax[i]=max(dpmax[i-1]+nums[i],nums[i]);
dpmin[i]=min(dpmin[i-1]+nums[i],nums[i]);
sum_ += nums[i];
}
int maxv=*max_element(dpmax.begin(),dpmax.end());
int minv=*min_element(dpmin.begin(),dpmin.end());
if(sum_ - minv == 0 ){
return maxv;
}
else{
return max(maxv, sum_ - minv);
}
}
};
12.?最佳观光组合
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
# n = len(values)
# max_score = float('-inf')
# for i in range(n):
# for j in range(i+1, n):
# max_score = max(max_score, values[i]+values[j]+i-j)
# return max_score
n = len(values)
mx = values[0]
max_score = float('-inf')
for i in range(1, n):
max_score = max(max_score, mx + values[i] - i)
mx = max(mx, values[i] + i)
return max_score
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& values) {
int n = values.size();
int mx = values[0];
int max_score = INT_MIN;
for(int i = 1; i < n; i++){
max_score = max(max_score, mx + values[i] - i);
mx = max(mx, values[i] + i);
}
return max_score;
}
};
13.?买卖股票的最佳时机
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1:
return 0
min_price = prices[0]
max_profit = 0
for i in range(1, len(prices)):
min_price = min(prices[i], min_price)
max_profit = max(max_profit, prices[i] - min_price)
return max_profit
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1){
return 0;
}
int max_profit = 0, min_price = prices[0];
for(int i = 1; i < prices.size(); i++){
min_price = min(min_price, prices[i]);
max_profit = max(max_profit, prices[i] - min_price);
}
return max_profit;
}
};
?14.?买卖股票的最佳时机 II
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices)<=1:
return 0
res = 0
for i in range(1, len(prices)):
res += max(0, prices[i] - prices[i-1])
return res
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n <= 1){
return 0;
}
int res = 0;
for(int i = 1; i < n; i++){
res += max(0, prices[i] - prices[i-1]);
}
return res;
}
};
?
|