IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> leetcode动态规划(python与c++) -> 正文阅读

[数据结构与算法]leetcode动态规划(python与c++)

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;
    }
};

?

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-31 15:42:15  更:2021-08-31 15:43:05 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 0:36:03-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码