动态规划算法练习题

45. 跳跃游戏 II

中等

2K

相关企业

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i] 
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1步，然后跳 3步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

int jump(int* nums, int numsSize){
   int *dp=(int *)malloc(sizeof(int)*numsSize);
   dp[0]=0;
   for(int i = 1 ; i < numsSize ; i++ )
    {
        dp[i] =  numsSize + 1;
    }
   for(int i =1; i< numsSize; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(j + nums[j] >= i)
            {
                dp[i] = fmin(dp[i],dp[j]+1);
            }
        }
    }
   return dp[numsSize-1];

}

97. 交错字符串

相关企业

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例 1：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""
输出：true

提示：

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1、s2、和 s3 都由小写英文字母组成

bool isInterleave(char * s1, char * s2, char * s3){
    int len1=strlen(s1),len2=strlen(s2),len3=strlen(s3),dp[105][105]={0};
    if(len3!=(len1+len2)){
        return false;
    }
    dp[0][0]=1;
    for(int i=0;i<=len1;i++){
        for(int j=0;j<=len2;j++){
            int p=i+j-1;
            if(i>0){
                if(dp[i-1][j]==1&&s3[p]==s1[i-1])
                    dp[i][j]=1;
            }
            if(j>0){
                 if(dp[i][j-1]==1&&s3[p]==s2[j-1])
                    dp[i][j]=1;
            }
        }
    }
    return dp[len1][len2];
}

131. 分割回文串

中等

1.4K

相关企业

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组 
      int dp[20][20]={0};
 void dfs(char* s, int len, int begin, char*** ans, int* returnSize, int* returnColumnSizes, char** temps, int* tempsSize) {
    if(begin==len){
           char** tmp = malloc(sizeof(char*) * (*tempsSize));
        for (int j = 0; j < (*tempsSize); j++) {
            int tempsColSize = strlen(temps[j]);
            tmp[j] = malloc(sizeof(char) * (tempsColSize + 1));
            strcpy(tmp[j], temps[j]);
        }
        ans[*returnSize] = tmp;
        returnColumnSizes[(*returnSize)++] = *tempsSize;
        return;
     }
    for (int j = begin; j < len; ++j) {
        if (dp[begin][j]==1) {
            char* temp = malloc(sizeof(char) * (j - begin + 2));
                 for (int k = begin; k <= j; k++) {
                      temp[k - begin] = s[k];
                  }
            temp[j - begin + 1] = '\0';
                 temps[(*tempsSize)++]=temp;
            dfs(s, len, j + 1, ans, returnSize, returnColumnSizes, temps, tempsSize);
            --*(tempsSize);
        }
    }
}

char*** partition(char* s, int* returnSize, int** returnColumnSizes) {
     int i,j,len=strlen(s);
      int retMaxLen = len * (1 << len);
     for(i=0;i<20;i++){
         for(j=0;j<20;j++){
             dp[i][j]=0;
         }
     }
     char*** ans = malloc(sizeof(char**) * retMaxLen);
    *returnSize = 0;
    *returnColumnSizes = malloc(sizeof(int) * retMaxLen);
     for(i=len-1;i>=0;i--){
         for(j=i;j<len;j++){
             if(s[i]==s[j]){
                 if(i==j)
                    dp[i][j]=1;
                 if(j-i==1){
                     dp[i][j]=1;
                 }
                 if(j-i>1){
                     if(dp[i+1][j-1]==1){
                         dp[i][j]=1;
                     }
                 }
             }
         }
     }
      char* temps[len];
     int tempsSize=0;
    dfs(s, len, 0, ans, returnSize, *returnColumnSizes, temps, &tempsSize);
    return ans;
}

139. 单词拆分

中等

1.9K

相关企业

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅有小写英文字母组成
  • wordDict 中的所有字符串 互不相同

bool wordBreak(char * s, char ** wordDict, int wordDictSize){
   int len=strlen(s),falg=0;
   int dp[301]={0};
   dp[0]=1;
   for(int i=0;i<len;i++){
       for(int j=0;j<wordDictSize;j++){
          int n=strlen(wordDict[j]);
          if(n>(len-i)){
              continue;
          }
           falg=1;
           for(int k=0;k<n;k++){
              if(s[i+k]!=wordDict[j][k]){
                  falg=0;
                }
            }
            if(falg==1&&dp[i]==1){
                dp[i+n]=1;
            }
       }
       
   }
   if(dp[len]==1)
      return true;
   return false;
}

221. 最大正方形

中等

1.4K

相关企业

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

uploading.4e448015.gif

正在上传…重新上传取消转存失败重新上传取消

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] 为 '0' 或 '1'

暴力超时：

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
    int max=0;
    int m=matrixSize,n=matrixColSize[0];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(matrix[i][j]=='1'){
                printf(" %d %d ",i,j);
                for(int b=1;i+b<=m&&j+b<=n;b++){
                    printf(" b=%d\n",b);
                    int falg=1;
                       for(int k=i;k<b+i;k++){
                           for(int l=j;l<j+b;l++){
                                if(matrix[k][l]!='1'){
                                     falg=0;
                                     break;
                                }
                            }
                       }
                       if(falg==1){
                            if(max<b)
                            {
                                max=b;
                            }
                       }
                       if(falg==0){
                           break;
                       }
                }
                
            }
        }
    }
    return max*max;
}

动态规划：

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
    int max=0,dp[301][301]={0};
    int m=matrixSize,n=matrixColSize[0];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(matrix[i][j]=='1'){   
               dp[i+1][j+1]=fmin(fmin(dp[i][j],dp[i][j+1]),fmin(dp[i][j],dp[i+1][j]))+1;
            }
            if(dp[i+1][j+1]>max){
                max=dp[i+1][j+1];
            }
        }
    }
    return max*max;
}

279. 完全平方数

中等

1.6K

相关企业

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

  • 1 <= n <= 104
int numSquares(int n) 
{
    int dp[n +1];   //定义dp的大小
    dp[0] = 0;      //定义dp的初始状态
    int min; 
    for(int i = 1 ; i <= n ; i++)
    {
        min = INT_MAX;
        for(int j = 1 ; j*j <= i;j++)
        {
            min = fmin(min, dp[i - j * j]);
        }
        dp[i] = min + 1;
    }
    return dp[n];
}

300. 最长递增子序列

中等

3K

相关企业

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

进阶：

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
int lengthOfLIS(int* nums, int numsSize){
    int dp[numsSize],max=0;
    for(int i=0;i<numsSize;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i]=fmax(dp[i],dp[j]+1);
            }
        }
        if(dp[i]>max){
            max=dp[i];
        }
    }
    return max;
}

376. 摆动序列

中等

857

相关企业

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

  • 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
int wiggleMaxLength(int* nums, int numsSize) {
    int up[numsSize];
    memset(up,0,sizeof(int)*numsSize);
    up[0]=1;
    int down[numsSize];
    memset(down,0,sizeof(int)*numsSize);
    down[0]=1;
    int max=0;
    for(int i=0;i<numsSize;i++){
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){
                down[i]=fmax(up[j]+1,down[i]);
            }
            if(nums[i]<nums[j]){
                up[i]=fmax(down[j]+1,up[i]);
            }
            
        }
        if(up[i]>max){
            max=up[i];
        }
        if(down[i]>max){
            max=down[i];
        }
    }
    return max;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/267361.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LTE之物理信道

LTE之物理信道

信道是不同类型的信息&#xff0c;按照不同传输格式、用不同的物理资源承载的信息通道。根据信息类型的不同、处理过程的不同可将信道分为多种类型。 重点介绍LTE的逻辑信道、传输信道、物理信道等常见的信道类型&#xff0c;并和3G相应的信道类型作了比较&#xff0c;通过比较…
阅读更多...
NNDL 作业12-优化算法2D可视化 [HBU]

NNDL 作业12-优化算法2D可视化 [HBU]

老师作业原博客地址&#xff1a;【23-24 秋学期】NNDL 作业12 优化算法2D可视化-CSDN博客 目录 简要介绍图中的优化算法&#xff0c;编程实现并2D可视化 1. 被优化函数 ​编辑 深度学习中的优化算法总结 - ZingpLiu - 博客园 (cnblogs.com) SGD: Adagrad: RMSprop: Mom…
阅读更多...
基于ERC20代币协议实现的去中心化应用平台

基于ERC20代币协议实现的去中心化应用平台

文章目录 内容简介设计逻辑ERC20TokenLoanPlatform 合约事件结构体状态变量函数 Remix 运行实现部署相关智能合约存款和取款贷款和还款 源码地址 内容简介 使用 solidity 实现的基于 ERC20 代币协议的借贷款去中心化应用平台(极简版)。实现存款、取款、贷款、还款以及利息计算的…
阅读更多...
宜春万申智能装备携粉体自动化产线解决方案盛装亮相2024济南生物发酵展

宜春万申智能装备携粉体自动化产线解决方案盛装亮相2024济南生物发酵展

宜春万申智能装备股份有限公司受邀盛装亮相2024第12届济南国际生物发酵展 展位号&#xff1a;1号馆A16-2展位 2024第12届国际生物发酵产品与技术装备展览会&#xff08;济南&#xff09;于3月5-7日在山东国际会展中心盛大召开&#xff0c;全方面展示&#xff1a;生物发酵、生…
阅读更多...
分布式锁功效初探——以电商问题为例

分布式锁功效初探——以电商问题为例

文章目录 电商库存问题单机处理-Sychronized多机器处理-分布式锁入门级别&#xff0c;用redis实现&#xff0c;setnx问题1&#xff1a;逻辑可能异常&#xff0c;造成死锁问题2&#xff1a;机器宕机问题3&#xff1a;锁一直失效&#xff0c;乱套锁续命 redisson分布式丢锁问题主…
阅读更多...
数独 -- 合法数独与完全数独

数独 -- 合法数独与完全数独

一、数独的介绍 从2004年底开始&#xff0c;数独游戏在英国变得非常流行。数独(Sudoku)是一个日语单词意思是数字位置之类的单词(或短语)。谜题的理念非常简单;面对一个9 9的网格&#xff0c;被分成9个3 3的块: 在其中的一些盒子里&#xff0c;设置者放一些数字1-9:求解者的目…
阅读更多...
前端未死，顺势而生

前端未死，顺势而生

随着人工智能和低代码的崛起&#xff0c;“前端已死”的声音逐渐兴起。前端已死&#xff1f;尊嘟假嘟&#xff1f;快来发表你的看法吧&#xff01; 一、“前端已死”因何而来&#xff1f; 在开始讨论之前&#xff0c;首先要明确什么是“前端”。 所谓前端&#xff0c;主要涉及…
阅读更多...
vue使用ElementUI搭建精美页面入门

vue使用ElementUI搭建精美页面入门

ElementUI简直是css学得不好的同学的福音 ElementUI官网&#xff1a; Element - The worlds most popular Vue UI framework 安装 在vue文件下&#xff0c;用这个命令去安装Element UI。 npm i element-ui -S step1\先切换到vue的目录下去&#xff0c;注意这里面的WARN不是…
阅读更多...
每日一题：LCR 095.最长公共子序列（DP）

每日一题：LCR 095.最长公共子序列（DP）

题目描述&#xff1a; 给定两个字符串 text1 和 text2&#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 &#xff0c;返回 0 。 一个字符串的 子序列 是指这样一个新的字符串&#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些…
阅读更多...
R语言基础 | 安徽某高校《统计建模与R软件》期末复习

R语言基础 | 安徽某高校《统计建模与R软件》期末复习

第一节 数字、字符与向量 1.1 向量的赋值 c<-(1,2,3,4,5) 1.2 向量的运算 对于向量&#xff0c;我们可以直接对其作加&#xff08;&#xff09;&#xff0c;减&#xff08;-&#xff09;&#xff0c;乘&#xff08;*&#xff09;&#xff0c;除&#xff08;/&#xff09…
阅读更多...
使用Python实现发送Email电子邮件【第19篇—python发邮件】

使用Python实现发送Email电子邮件【第19篇—python发邮件】

文章目录 &#x1f47d;使用Python实现发送Email电子邮件&#x1f3b6;实现原理&#x1f3c3;Python实现发送Email电子邮件-基础版&#x1f46b;实现源码&#x1f646;源码解析 &#x1f487;Python实现发送Email电子邮件-完善版&#x1f46b;实现源码&#x1f646;源码解析&am…
阅读更多...
随机无限采集JK妹妹高清壁纸下载HTML网页源码

随机无限采集JK妹妹高清壁纸下载HTML网页源码

源码介绍 美图网站千千万&#xff0c;美图自己说了算&#xff01;本源码由宋佳乐博客 开发&#xff0c;首页图片做了浏览器窗口自适应&#xff0c;最大化占满PC浏览器和移动浏览器的窗口&#xff0c;并且防止出现滚动条。 功能介绍 首页图片设置了4个点击功能区&#xff0c;…
阅读更多...
【数据结构入门精讲 | 第十一篇】一文讲清树

【数据结构入门精讲 | 第十一篇】一文讲清树

在上一篇中我们进行了排序算法的专项练习&#xff0c;现在让我们开始树的知识点讲解。 目录 树二叉搜索树二叉排序树哈夫曼树折半查找判定树kruskal算法、prim算法、最小生成树完全二叉树 树 树是一种非线性的数据结构&#xff0c;也是一种表示一对多关系的数据结构&#xff0…
阅读更多...
Flink CDC 1.0至3.0回忆录

Flink CDC 1.0至3.0回忆录

Flink CDC 1.0至3.0回忆录 一、引言二、CDC概述三、Flink CDC 1.0&#xff1a;扬帆起航3.1 架构设计3.2 版本痛点 四、Flink CDC 2.0&#xff1a;成长突破4.1 DBlog 无锁算法4.2 FLIP-27 架构实现4.3 整体流程 五、Flink CDC 3.0&#xff1a;应运而生六、Flink CDC 的影响和价值…
阅读更多...
Python 数据分析 Matplotlib篇 plot设置线条样式（第2讲）

Python 数据分析 Matplotlib篇 plot设置线条样式（第2讲）

Python 数据分析 Matplotlib篇 plot设置线条样式（第2讲）         🍹博主 侯小啾 感谢您的支持与信赖。☀️ 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ�…
阅读更多...
算法基础之完全背包问题

算法基础之完全背包问题

完全背包问题 核心思想&#xff1a;集合表示&#xff1a; f[i][j]表示前i种物品 总容量不超过j的最大价值 求f[i][j]时 分为选0、1、2……n个第i种物品 n种情况 每种情况为 f[i][j-kv] (取k个第i种物品) 即f[i][j] max(f[i-1][j] , f[i-1][j-v]w,f[i-1][j-2v]2w….f[i-1][j-k…
阅读更多...
【自用】Ubuntu20.4从Vivado到ddr200t运行HelloWorld

【自用】Ubuntu20.4从Vivado到ddr200t运行HelloWorld

【自用】Ubuntu20.4新系统从输入法到ddr200t运行HelloWorld 一、编辑bashrc二、Vivado2022.2安装三、编译蜂鸟E203自测样例1. 环境准备2. 下载e203_hbirdv2工程文件3. 尝试编译自测案例1. 安装RISC-V GNU工具链2. 编译测试样例 4. 用vivado为FPGA生成mcs文件1.准备RTL2.生成bit…
阅读更多...
Centos 7.9安装Oracle19c步骤亲测可用有视频

Centos 7.9安装Oracle19c步骤亲测可用有视频

视频介绍了在虚拟机安装centos 7.9并安装数据库软件的全过程 视频链接&#xff1a;https://www.zhihu.com/zvideo/1721267375351996416 下面的文字描述是安装数据库的部分介绍 一.安装环境准备 链接&#xff1a;https://pan.baidu.com/s/1Ogn47UZQ2w7iiHAiVdWDSQ 提取码&am…
阅读更多...
贝叶斯球快速检验条件独立

贝叶斯球快速检验条件独立

贝叶斯球 定义几个术语&#xff0c;描述贝叶斯球在一个结点上的动作&#xff1a; 通过&#xff08;pass through&#xff09;&#xff1a;从当前结点的父结点方向过来的球&#xff0c;可以访问当前结点的任意子结点&#xff08;父->子&#xff09;。从当前节点的子结点方向…
阅读更多...
基于电商场景的高并发RocketMQ实战-NameServer内核原理剖析、Broker 主从架构与集群模式原理分析

基于电商场景的高并发RocketMQ实战-NameServer内核原理剖析、Broker 主从架构与集群模式原理分析

&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308; 【11来了】文章导读地址&#xff1a;点击查看文章导读&#xff01; &#x1f341;&#x1f341;&#x1f341;&#x1f341;&#x1f341;&#x1f341;&#x1f3…
阅读更多...
最新文章

Copyright @ 2022~2023