当前位置: 首页 > news >正文

交互设计网站推荐关键词研究工具

交互设计网站推荐,关键词研究工具,群晖 wordpress 端口,城市联盟网站怎么做题目 给定一个二维数组matrix[][],一个人必须从左上角出发,最终到达右下角,沿途只可以向下或者向右走,沿途的数字都累加就是距离累加和。返回最小距离累加和。 这道题中会采用压缩数组的算法来进行优化 暴力递归 暴力递归方法的整…

题目
给定一个二维数组matrix[][],一个人必须从左上角出发,最终到达右下角,沿途只可以向下或者向右走,沿途的数字都累加就是距离累加和。返回最小距离累加和。
这道题中会采用压缩数组的算法来进行优化

暴力递归
暴力递归方法的整体思路是根据小人所在的位置(当前值),通过向下传递(向左走向右走)来获取最终选择路径的最小值。
所以base case可以确定:

  1. 如果小人走到了最后一行,那么接下来就只能向下走。
  2. 如果小人走到了最后一列,那么接下来就只能向左走。
  3. 如果小人走到了matrix[][]的最后一个格子,返回当前值给上层做处理,取最小值。
  4. 否则,既可以向左也走可以向右走,并获取最小值。

所以暴力递归的方法就出来了。

public static int minPathSum1(int[][] matrix) {if (null == matrix || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {return -1;}int row = matrix.length;int col = matrix[0].length;return process(row - 1, col - 1, 0, 0, matrix);}//返回 matrix[i...][j....] 位置的最小值。public static int process(int row, int col, int curRow, int curCol, int[][] matrix) {//当走到最后一个位置,返回matrix中最后一个位置的值if (curRow == row && curCol == col) {return matrix[row][col];}//走到最后一行,只能往右走,只能向右累加if (curRow == row) {return matrix[curRow][curCol] + process(row, col, curRow, curCol + 1, matrix);}//走到最后一列,只能向下走if (curCol == col) {return matrix[curRow][curCol] + process(row, col, curRow + 1, curCol, matrix);}//否则,可以向右走,可以向下走,进行累加。int curValue = matrix[curRow][curCol];int p1 = curValue + process(row, col, curRow + 1, curCol, matrix);int p2 = curValue + process(row, col, curRow, curCol + 1, matrix);return Math.min(p1, p2);}

动态规划
这道题的动态规划也不难,给定的是一个二维数组matrix[][],每次行和列会进行变化(可变参数),所以可以创建一个和matrix大小相等的dp[][]来存放每一步计算的值。
因为只可以向下走或向右走,所以dp中任选一个格子的依赖是依赖自己的左侧的值和上面的值。其中dp中第一行的值只会依赖同行左侧的值,dp中第一列的值只会依赖同一列上面的值
所以先将dp中第一行和第一列的值填充好后,其余的按照依赖关系填充,即可完善dp表。

代码

 public static int dp(int[][] matrix) {if (null == matrix || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {return -1;}int row = matrix.length;int col = matrix[0].length;int[][] dp = new int[row][col];dp[0][0] = matrix[0][0];for (int i = 1; i < col; i++) {dp[0][i] = dp[0][i - 1] + matrix[0][i];}for (int j = 1; j < row; j++) {dp[j][0] = dp[j - 1][0] + matrix[j][0];}for (int i = 1; i < row; i++) {for (int j = 1; j < col; j++) {dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];}}return dp[row - 1][col - 1];}

优化
动态规划方法中是创建了一个和matrix[][]大小相等的dp表,通过填充dp表来完善的代码。

如果给定的matrix[][]太大了,是不是我的dp表也要跟着很大,并且,在填充dp表时,第三行依赖第二行的值,第四行依赖第三行的值,此时。第二行的值就已经没有用了,不再需要它了,所以是不是只需要一个跟matrix[][]中列的长度相等的一维数组arr[]就够了。

先根据matrix[][]中第0行的值填充arr[],下面的两层循环中,最外层循环会让arr[0]每次加matrix中当行行的第一个值(因为只依赖上面)。内层循环,会找需要依赖的上面值(arr[j])和左边值(arr[j - 1])来取最小值,后加上matrix中当前位置上的值。

代码

 public static int minPathSum2(int[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {return 0;}int row = matrix.length;int col = matrix[0].length;int[] arr = new int[col];arr[0] = matrix[0][0];//根据matrix第一行的值填充arrfor (int i = 1; i < col; i++) {arr[i] = arr[i - 1] + matrix[0][i];}for (int i = 1; i < row; i++) {arr[0] += matrix[i][0];for (int j = 1; j < col; j++) {//arr[j - 1] : 相当于我依赖的左边//arr[j]  : 因为此时arr[j]的值还没修改,还是上一行的值,相当于自己的上面。 arr[j] = Math.min(arr[j - 1], arr[j]) + matrix[i][j];}}return arr[col - 1];}
http://www.shuangfujiaoyu.com/news/53257.html

相关文章:

  • wordpress小说自动采集外链seo招聘
  • 什么是移动端网站适配seo整站优化技术培训
  • 我想做个网站找谁做市场营销毕业论文
  • 网站规划具体内容企业邮箱
  • 做盗版视频网站成本多少钱国家高新技术企业查询
  • 网站信息真实性核验单行业关键词一览表
  • 网络公司给别人做网站的cms是买的授权么百度2020新版下载
  • 织梦网站首页是哪个文件百度快照替代
  • 网站维护的工作内容步骤河南企业网站建设
  • .net商城网站开发软文代写接单平台
  • 网站报价书seo什么意思
  • wordpress检索插件重庆seo小潘大神
  • 怎么给自己的网站做排名b2b外链代发
  • 怎么做一个设计师网站模板建站网页
  • 班级建设网站设计方案2023新闻大事件摘抄
  • win7不能运行wordpress新网站应该怎么做seo
  • 成都创新互联做网站推广代运营公司
  • 行业网站建设百度经验实用生活指南
  • 新加坡网站建设公司建立网站一般要多少钱
  • 网站模板文件不存在2022新闻大事件摘抄
  • asp.net手机网站开发教程凡科建站官网免费注册
  • 个人业务网站创建网站优化外包多少钱
  • 济南城乡建设委员会网站郑州黑帽seo培训
  • 建设网站开发网站推广名词解释
  • 莱芜网站建设价格低今日头条十大新闻最新
  • 什么是营销型手机网站建设搜狗指数
  • 上海专业网站建站品黄页网络的推广网站有哪些
  • 网站做伪静态优化大师客服
  • 江苏付费网络推广培训seo关键字优化技巧
  • 急招一对夫妻门卫6500元seo教程seo教程