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

drupal和wordpress专业网站推广优化

drupal和wordpress,专业网站推广优化,网站项目建设策划书,wordpress社会化插件【LetMeFly】3148.矩阵中的最大得分:每个元素与其左或上元素之差的最大值(原地修改O(1)空间) 力扣题目链接:https://leetcode.cn/problems/maximum-difference-score-in-a-grid/ 给你一个由 正整数 组成、大小为 m x n 的矩阵 g…

【LetMeFly】3148.矩阵中的最大得分:每个元素与其左或上元素之差的最大值(原地修改O(1)空间)

力扣题目链接:https://leetcode.cn/problems/maximum-difference-score-in-a-grid/

给你一个由 正整数 组成、大小为 m x n 的矩阵 grid。你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格(不必相邻)。从值为 c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1

你可以从 任一 单元格开始,并且必须至少移动一次。

返回你能得到的 最大 总得分。

 

示例 1:

输入:grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]

输出:9

解释:从单元格 (0, 1) 开始,并执行以下移动:
- 从单元格 (0, 1) 移动到 (2, 1),得分为 7 - 5 = 2
- 从单元格 (2, 1) 移动到 (2, 2),得分为 14 - 7 = 7
总得分为 2 + 7 = 9

示例 2:

输入:grid = [[4,3,2],[3,2,1]]

输出:-1

解释:从单元格 (0, 0) 开始,执行一次移动:从 (0, 0)(0, 1) 。得分为 3 - 4 = -1

 

提示:

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 105
  • 1 <= grid[i][j] <= 105

解题方法:动态规划

从a移动到b,再从b移动到c,等价于直接从a移动到c。

因此要求的,就是对所有的a到c中,c-a的最大值。

怎么求?很简单,在遍历原始数组的时候将每个值修改为这个元素、这个元素左上方(包含)所有元素的最小值

这样,对应下标为(i, j)的元素,其左上方的最小值就是min(grid[i - 1][j], grid[i][j - 1])。

使用grid[i][j]减去这个“最小值”,即为从任意一点移动到(i, j)所得的最大得分(只能往右或下移动)。

所有的最大得分中,最大的那个即为所求。

  • 时间复杂度 O ( s i z e ( g r i d ) ) O(size(grid)) O(size(grid))
  • 空间复杂度 O ( 1 ) O(1) O(1):可以直接修改grid数组的话,空间复杂度就是O(1)

AC代码

C++
class Solution {
public:int maxScore(vector<vector<int>>& grid) {int ans = grid[0][1] - grid[0][0];for (int i = 0; i < grid.size(); i++) {for (int j = 0; j < grid[0].size(); j++) {int original = grid[i][j];if (i > 0) {grid[i][j] = min(grid[i][j], grid[i - 1][j]);ans = max(ans, original - grid[i - 1][j]);}if (j > 0) {grid[i][j] = min(grid[i][j], grid[i][j - 1]);ans = max(ans, original - grid[i][j - 1]);}}}return ans;}
};

执行用时分布119ms击败99.11%;消耗内存分布55.80MB击败87.46%。

Python
from typing import Listclass Solution:def maxScore(self, grid: List[List[int]]) -> int:ans = grid[0][1] - grid[0][0]for i in range(len(grid)):for j in range(len(grid[0])):original = grid[i][j]if i > 0:grid[i][j] = min(grid[i][j], grid[i - 1][j])ans = max(ans, original - grid[i - 1][j])if j > 0:grid[i][j] = min(grid[i][j], grid[i][j - 1])ans = max(ans, original - grid[i][j - 1])return ans
Java
import java.util.List;class Solution {public int maxScore(List<List<Integer>> grid) {int ans = -100000000;for (int i = 0; i < grid.size(); i++) {for (int j = 0; j < grid.get(0).size(); j++) {int original = grid.get(i).get(j);if (i > 0) {grid.get(i).set(j, Math.min(grid.get(i).get(j), grid.get(i - 1).get(j)));ans = Math.max(ans, original - grid.get(i - 1).get(j));}if (j > 0) {grid.get(i).set(j, Math.min(grid.get(i).get(j), grid.get(i).get(j - 1)));ans = Math.max(ans, original - grid.get(i).get(j - 1));}}}return ans;}
}
Go
package mainfunc min(a int, b int) int {if a < b {return a}return b
}func max(a int, b int) int {if a > b {return a}return b
}func maxScore(grid [][]int) int {ans := -12345678for i, line := range grid {for j, item := range line {original := itemif i > 0 {grid[i][j] = min(grid[i][j], grid[i - 1][j])  // 这里修改item的值不会改变grid[i][j]的值ans = max(ans, original - grid[i - 1][j])}if j > 0 {grid[i][j] = min(grid[i][j], grid[i][j - 1])ans = max(ans, original - grid[i][j - 1])}}}return ans
}

End

44CC44Gt44GZ44Gn44Kr44OQ44Gr5b2T5pysCg==

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

Tisfy:https://letmefly.blog.csdn.net/article/details/141234633

http://www.zhongyajixie.com/news/18014.html

相关文章:

  • iis 建设网站百度sem竞价托管
  • 大连鑫农建设集团网站独立网站怎么做
  • wordpress 网站卡杭州seo推广公司
  • 丫丫影院seo专员是什么职业
  • 中山营销网站建设联系方式排名优化公司电话
  • 邢台物流网站建设电商网站公司
  • 网站底部备案号悬挂八大营销方式有哪几种
  • 昌平哪有做网站的公司最好的网站设计公司
  • 个人网站经营 合法么广东省新闻
  • java做兼职找什么网站推广app平台有哪些
  • app游戏开发公司哪家好保定百度seo排名
  • 美术教育机构网站建设方案磁力搜索引擎
  • 深圳网站建设公司简介下载优化大师并安装
  • 怎么在网上做公司网站全网推广平台有哪些
  • 制作校园网站百度软件下载中心官方网站
  • 莲塘网站建设枫树seo
  • 五莲网站建设公司引擎搜索大全
  • 国内代理ip地址重庆黄埔seo整站优化
  • 企业邮箱哪个好用和安全seo的主要工作是什么
  • 面包屑网站导航怎么做淘宝推广平台有哪些
  • 做网站怎么挣钱威海seo优化公司
  • 创意设计专业重庆seo排名电话
  • 开发网站的申请怎么写怎么去优化关键词
  • 济南企业网站搭建浙江网站建设营销
  • 电商运营是干嘛的网站推广优化外包公司哪家好
  • 怎么做关于易烊千玺的网站郑州网站seo外包公司
  • 为网站添加isapi扩展网站快速收录
  • 黑彩网站自己可以做么苹果被曝开发搜索引擎对标谷歌
  • 企业级网站建设外贸推广方式
  • 上海网站建设制作微信百度免费收录提交入口