content_views" class="markdown_views prism-atom-one-light">

class="tags" href="/SuanFa.html" title=算法>算法class="tags" href="/XueXi.html" title=学习>学习——LeetCode力扣补充篇11

c="https://img-blog.csdnimg.cn/direct/914fb34013b54ec79c53f13a549e9cb1.jpeg#pic_center" alt="在这里插入图片描述" />

64. 最小路径和

64. 最小路径和 - 力扣（LeetCode）

描述

给定一个包含非负整数的 m x n 网格 grid ࿰c;请找出一条从左上角到右下角的路径࿰c;使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例

示例 1：
c="https://img-blog.csdnimg.cn/direct/52d756cf776142f7a1f965e325ee33fb.png" alt="在这里插入图片描述" />

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

代码解析

<code class="prism language-cpp">class="token keyword">class class="token class-name">Solution class="token punctuation">{
class="token keyword">publicclass="token operator">:class="token keyword">int class="token function">minPathSumclass="token punctuation">(vectorclass="token operator"><vectorclass="token operator"><class="token keyword">intclass="token operator">>>class="token operator">& gridclass="token punctuation">) class="token punctuation">{class="token keyword">int m class="token operator">= gridclass="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">) class="token punctuation">, n class="token operator">= gridclass="token punctuation">[class="token number">0class="token punctuation">]class="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">)class="token punctuation">;vectorclass="token operator"><vectorclass="token operator"><class="token keyword">intclass="token operator">>> class="token function">dpclass="token punctuation">(m class="token punctuation">, class="token generic-function">class="token function">vectorclass="token generic class-name">class="token operator"><class="token keyword">intclass="token operator">>class="token punctuation">(n class="token punctuation">, class="token number">0class="token punctuation">) class="token punctuation">)class="token punctuation">;dpclass="token punctuation">[class="token number">0class="token punctuation">]class="token punctuation">[class="token number">0class="token punctuation">] class="token operator">= gridclass="token punctuation">[class="token number">0class="token punctuation">]class="token punctuation">[class="token number">0class="token punctuation">]class="token punctuation">;class="token keyword">forclass="token punctuation">(class="token keyword">int iclass="token operator">=class="token number">1 class="token punctuation">; iclass="token operator"><m class="token punctuation">;iclass="token operator">++class="token punctuation">)dpclass="token punctuation">[iclass="token punctuation">]class="token punctuation">[class="token number">0class="token punctuation">] class="token operator">= dpclass="token punctuation">[iclass="token operator">-class="token number">1class="token punctuation">]class="token punctuation">[class="token number">0class="token punctuation">] class="token operator">+  gridclass="token punctuation">[iclass="token punctuation">]class="token punctuation">[class="token number">0class="token punctuation">]class="token punctuation">;class="token keyword">forclass="token punctuation">(class="token keyword">int jclass="token operator">=class="token number">1 class="token punctuation">; jclass="token operator"><n class="token punctuation">;jclass="token operator">++class="token punctuation">)dpclass="token punctuation">[class="token number">0class="token punctuation">]class="token punctuation">[jclass="token punctuation">] class="token operator">=  dpclass="token punctuation">[class="token number">0class="token punctuation">]class="token punctuation">[jclass="token operator">-class="token number">1class="token punctuation">]  class="token operator">+  gridclass="token punctuation">[class="token number">0class="token punctuation">]class="token punctuation">[jclass="token punctuation">]class="token punctuation">;class="token keyword">forclass="token punctuation">(class="token keyword">int iclass="token operator">=class="token number">1 class="token punctuation">; iclass="token operator"><m class="token punctuation">;iclass="token operator">++class="token punctuation">)class="token punctuation">{class="token keyword">forclass="token punctuation">(class="token keyword">int jclass="token operator">=class="token number">1 class="token punctuation">; jclass="token operator"><n class="token punctuation">; jclass="token operator">++class="token punctuation">)class="token punctuation">{dpclass="token punctuation">[iclass="token punctuation">]class="token punctuation">[jclass="token punctuation">] class="token operator">= class="token function">minclass="token punctuation">( dpclass="token punctuation">[iclass="token operator">-class="token number">1class="token punctuation">]class="token punctuation">[jclass="token punctuation">]class="token punctuation">, dpclass="token punctuation">[iclass="token punctuation">]class="token punctuation">[jclass="token operator">-class="token number">1class="token punctuation">] class="token punctuation">) class="token operator">+ gridclass="token punctuation">[iclass="token punctuation">]class="token punctuation">[jclass="token punctuation">]class="token punctuation">;class="token punctuation">}class="token punctuation">}class="token keyword">return dpclass="token punctuation">[mclass="token operator">-class="token number">1class="token punctuation">]class="token punctuation">[nclass="token operator">-class="token number">1class="token punctuation">]class="token punctuation">;class="token punctuation">}
class="token punctuation">}class="token punctuation">;
code>

48. 旋转图像

48. 旋转图像 - 力扣（LeetCode）

描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像࿰c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例

示例 1：

c="https://img-blog.csdnimg.cn/direct/8e51f6df76ae4e9fbd49f13babb8692b.png" alt="在这里插入图片描述" />

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

示例 2：
c="https://img-blog.csdnimg.cn/direct/477b69996e214f539bbd2e5319df027c.png" alt="在这里插入图片描述" />

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

代码解析

<code class="prism language-cpp">class="token keyword">class class="token class-name">Solution class="token punctuation">{
class="token keyword">publicclass="token operator">:class="token keyword">void class="token function">rotateclass="token punctuation">(vectorclass="token operator"><vectorclass="token operator"><class="token keyword">intclass="token operator">>>class="token operator">& matrixclass="token punctuation">) class="token punctuation">{class="token keyword">int m class="token operator">= matrixclass="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">)class="token punctuation">;class="token keyword">int n class="token operator">= matrixclass="token punctuation">[class="token number">0class="token punctuation">]class="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">)class="token punctuation">;class="token keyword">forclass="token punctuation">(class="token keyword">int iclass="token operator">=class="token number">0 class="token punctuation">; iclass="token operator"><m class="token punctuation">; iclass="token operator">++class="token punctuation">)class="token punctuation">{class="token keyword">forclass="token punctuation">(class="token keyword">int jclass="token operator">=i class="token punctuation">; jclass="token operator"><n class="token punctuation">; jclass="token operator">++class="token punctuation">)class="token punctuation">{class="token function">swapclass="token punctuation">(matrixclass="token punctuation">[iclass="token punctuation">]class="token punctuation">[jclass="token punctuation">] class="token punctuation">, matrixclass="token punctuation">[jclass="token punctuation">]class="token punctuation">[iclass="token punctuation">]class="token punctuation">)class="token punctuation">;class="token punctuation">}class="token punctuation">}class="token keyword">forclass="token punctuation">(class="token keyword">int iclass="token operator">=class="token number">0 class="token punctuation">; iclass="token operator"><m class="token punctuation">; iclass="token operator">++class="token punctuation">)class="token punctuation">{class="token keyword">forclass="token punctuation">(class="token keyword">int jclass="token operator">=class="token number">0 class="token punctuation">; jclass="token operator"><nclass="token operator">/class="token number">2 class="token punctuation">; jclass="token operator">++class="token punctuation">)class="token punctuation">{class="token function">swapclass="token punctuation">(matrixclass="token punctuation">[iclass="token punctuation">]class="token punctuation">[jclass="token punctuation">] class="token punctuation">, matrixclass="token punctuation">[iclass="token punctuation">]class="token punctuation">[nclass="token operator">-jclass="token operator">-class="token number">1class="token punctuation">]class="token punctuation">)class="token punctuation">;class="token punctuation">}class="token punctuation">}class="token punctuation">}
class="token punctuation">}class="token punctuation">;code>

169. 多数元素

169. 多数元素 - 力扣（LeetCode）

描述

给定一个大小为 n 的数组 nums ࿰c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的࿰c;并且给定的数组总是存在多数元素。

示例

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

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

提示

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的class="tags" href="/SuanFa.html" title=算法>算法解决此问题。

代码解析

<code class="prism language-cpp">class="token keyword">class class="token class-name">Solution class="token punctuation">{
class="token keyword">publicclass="token operator">:class="token keyword">int class="token function">majorityElementclass="token punctuation">(vectorclass="token operator"><class="token keyword">intclass="token operator">>class="token operator">& numsclass="token punctuation">) class="token punctuation">{mapclass="token operator"><class="token keyword">intclass="token punctuation">,class="token keyword">intclass="token operator">> my_mapclass="token punctuation">;pairclass="token operator"><class="token keyword">intclass="token punctuation">,class="token keyword">intclass="token operator">> class="token function">resultclass="token punctuation">(class="token number">0class="token punctuation">,class="token number">0class="token punctuation">)class="token punctuation">;class="token keyword">forclass="token punctuation">(class="token keyword">int iclass="token operator">=class="token number">0 class="token punctuation">; iclass="token operator"><numsclass="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">) class="token punctuation">; iclass="token operator">++class="token punctuation">)class="token punctuation">{my_mapclass="token punctuation">[numsclass="token punctuation">[iclass="token punctuation">]class="token punctuation">]class="token operator">++class="token punctuation">;class="token keyword">ifclass="token punctuation">(my_mapclass="token punctuation">[numsclass="token punctuation">[iclass="token punctuation">]class="token punctuation">] class="token operator">>= numsclass="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">)class="token operator">/class="token number">2class="token punctuation">)class="token punctuation">{class="token keyword">ifclass="token punctuation">(my_mapclass="token punctuation">[numsclass="token punctuation">[iclass="token punctuation">]class="token punctuation">] class="token operator">> resultclass="token punctuation">.secondclass="token punctuation">)class="token punctuation">{resultclass="token punctuation">.first class="token operator">= numsclass="token punctuation">[iclass="token punctuation">]class="token punctuation">;resultclass="token punctuation">.second class="token operator">= my_mapclass="token punctuation">[numsclass="token punctuation">[iclass="token punctuation">]class="token punctuation">]class="token punctuation">;class="token punctuation">}class="token punctuation">}class="token punctuation">}class="token keyword">return resultclass="token punctuation">.firstclass="token punctuation">;class="token punctuation">}
class="token punctuation">}class="token punctuation">;
code>

394. 字符串解码

394. 字符串解码 - 力扣（LeetCode）

描述

给定一个经过编码的字符串࿰c;返回它解码后的字符串。

编码规则为: k[encoded_string]࿰c;表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格࿰c;且输入的方括号总是符合格式要求的。

此外࿰c;你可以认为原始数据不包含数字࿰c;所有的数字只表示重复的次数 k ࿰c;例如不会出现像 3a 或 2[4] 的输入。

示例

示例 1：

输入：s = “3[a]2[bc]”
输出：“aaabcbc”

示例 2：

输入：s = “3[a2[c]]”
输出：“accaccacc”

示例 3：

输入：s = “2[abc]3[cd]ef”
输出：“abcabccdcdcdef”

示例 4：

输入：s = “abc3[cd]xyz”
输出：“abccdcdcdxyz”

提示

1 <= s.length <= 30
s 由小写英文字母、数字和方括号 ‘[]’ 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300]

代码解析

<code class="prism language-cpp">class="token keyword">class class="token class-name">Solution class="token punctuation">{
class="token keyword">publicclass="token operator">:string class="token function">decodeStringclass="token punctuation">(string sclass="token punctuation">) class="token punctuation">{string resclass="token punctuation">;stack class="token operator"><class="token keyword">intclass="token operator">> numsclass="token punctuation">;stack class="token operator"><stringclass="token operator">> strsclass="token punctuation">;class="token keyword">int num class="token operator">= class="token number">0class="token punctuation">;class="token keyword">forclass="token punctuation">(class="token keyword">int i class="token operator">= class="token number">0class="token punctuation">; i class="token operator">< sclass="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">)class="token punctuation">; iclass="token operator">++class="token punctuation">)class="token punctuation">{class="token keyword">ifclass="token punctuation">(sclass="token punctuation">[iclass="token punctuation">] class="token operator">>= class="token char">'0' class="token operator">&& sclass="token punctuation">[iclass="token punctuation">] class="token operator"><= class="token char">'9'class="token punctuation">)class="token punctuation">{num class="token operator">= num class="token operator">* class="token number">10 class="token operator">+ sclass="token punctuation">[iclass="token punctuation">] class="token operator">- class="token char">'0'class="token punctuation">;class="token punctuation">}class="token keyword">else class="token keyword">ifclass="token punctuation">(sclass="token punctuation">[iclass="token punctuation">] class="token operator">>= class="token char">'a' class="token operator">&& sclass="token punctuation">[iclass="token punctuation">] class="token operator"><= class="token char">'z'class="token punctuation">)class="token punctuation">{res class="token operator">+= sclass="token punctuation">[iclass="token punctuation">]class="token punctuation">;class="token punctuation">}class="token keyword">else class="token keyword">ifclass="token punctuation">(sclass="token punctuation">[iclass="token punctuation">] class="token operator">== class="token char">'['class="token punctuation">) class="token comment">//将‘[’前的数字压入nums栈内࿰c; 字母字符串压入strs栈内class="token punctuation">{numsclass="token punctuation">.class="token function">pushclass="token punctuation">(numclass="token punctuation">)class="token punctuation">;num class="token operator">= class="token number">0class="token punctuation">;strsclass="token punctuation">.class="token function">pushclass="token punctuation">(resclass="token punctuation">)class="token punctuation">; resclass="token punctuation">.class="token function">clearclass="token punctuation">(class="token punctuation">)class="token punctuation">;class="token punctuation">}class="token keyword">else class="token comment">//遇到‘]’时࿰c;操作与之相配的‘[’之间的字符࿰c;使用分配律class="token punctuation">{class="token keyword">int times class="token operator">= numsclass="token punctuation">.class="token function">topclass="token punctuation">(class="token punctuation">)class="token punctuation">;numsclass="token punctuation">.class="token function">popclass="token punctuation">(class="token punctuation">)class="token punctuation">;class="token keyword">forclass="token punctuation">(class="token keyword">int j class="token operator">= class="token number">0class="token punctuation">; j class="token operator">< timesclass="token punctuation">; class="token operator">++ jclass="token punctuation">)strsclass="token punctuation">.class="token function">topclass="token punctuation">(class="token punctuation">) class="token operator">+= resclass="token punctuation">;res class="token operator">= strsclass="token punctuation">.class="token function">topclass="token punctuation">(class="token punctuation">)class="token punctuation">; class="token comment">//之后若还是字母࿰c;就会直接加到res之后࿰c;因为它们是同一级的运算class="token comment">//若是左括号࿰c;res会被压入strs栈࿰c;作为上一层的运算strsclass="token punctuation">.class="token function">popclass="token punctuation">(class="token punctuation">)class="token punctuation">;class="token punctuation">}class="token punctuation">}class="token keyword">return resclass="token punctuation">;class="token punctuation">}
class="token punctuation">}class="token punctuation">;code>

240. 搜索二维矩阵 II

240. 搜索二维矩阵 II - 力扣（LeetCode）

描述

编写一个高效的class="tags" href="/SuanFa.html" title=算法>算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例

示例 1：
c="https://img-blog.csdnimg.cn/direct/d795178348a14450a8532b3136d55cde.png" alt="在这里插入图片描述" />

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：
c="https://img-blog.csdnimg.cn/direct/f17a4ad598364e71855d8e2ec4df7731.png" alt="在这里插入图片描述" />

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

代码解析

常规

<code class="prism language-cpp">class="token keyword">class class="token class-name">Solution class="token punctuation">{
class="token keyword">publicclass="token operator">:class="token keyword">bool class="token function">searchMatrixclass="token punctuation">(vectorclass="token operator"><vectorclass="token operator"><class="token keyword">intclass="token operator">>>class="token operator">& matrixclass="token punctuation">, class="token keyword">int targetclass="token punctuation">) class="token punctuation">{class="token keyword">int m class="token operator">= matrixclass="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">) class="token punctuation">, n class="token operator">= matrixclass="token punctuation">[class="token number">0class="token punctuation">]class="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">)class="token punctuation">;class="token keyword">int max_point class="token operator">= class="token number">1class="token punctuation">;class="token keyword">forclass="token punctuation">(class="token keyword">int iclass="token operator">=class="token number">0 class="token punctuation">; iclass="token operator"><class="token function">minclass="token punctuation">(mclass="token punctuation">,nclass="token punctuation">) class="token punctuation">;iclass="token operator">++class="token punctuation">)class="token punctuation">{class="token keyword">ifclass="token punctuation">(matrixclass="token punctuation">[iclass="token punctuation">]class="token punctuation">[iclass="token punctuation">] class="token operator">> targetclass="token punctuation">) class="token keyword">breakclass="token punctuation">;max_point class="token operator">= iclass="token punctuation">;class="token punctuation">}class="token keyword">forclass="token punctuation">(class="token keyword">int iclass="token operator">=class="token number">0 class="token punctuation">; i class="token operator">< max_point class="token punctuation">; iclass="token operator">++class="token punctuation">)class="token punctuation">{class="token keyword">forclass="token punctuation">(class="token keyword">int jclass="token operator">=max_point class="token punctuation">; jclass="token operator"><n class="token punctuation">; jclass="token operator">++class="token punctuation">)class="token punctuation">{class="token keyword">ifclass="token punctuation">(matrixclass="token punctuation">[iclass="token punctuation">]class="token punctuation">[jclass="token punctuation">] class="token operator">== targetclass="token punctuation">) class="token keyword">return class="token boolean">trueclass="token punctuation">;class="token punctuation">}class="token punctuation">}class="token keyword">forclass="token punctuation">(class="token keyword">int iclass="token operator">=max_point class="token punctuation">; iclass="token operator"><m class="token punctuation">; iclass="token operator">++class="token punctuation">)class="token punctuation">{class="token keyword">forclass="token punctuation">(class="token keyword">int jclass="token operator">=class="token number">0 class="token punctuation">; jclass="token operator"><n class="token punctuation">; jclass="token operator">++class="token punctuation">)class="token punctuation">{class="token keyword">ifclass="token punctuation">(matrixclass="token punctuation">[iclass="token punctuation">]class="token punctuation">[jclass="token punctuation">] class="token operator">== targetclass="token punctuation">) class="token keyword">return class="token boolean">trueclass="token punctuation">;class="token punctuation">}class="token punctuation">}class="token keyword">return class="token boolean">falseclass="token punctuation">;class="token punctuation">}
class="token punctuation">}class="token punctuation">;
code>

路径优化

<code class="prism language-cpp">class="token keyword">class class="token class-name">Solution class="token punctuation">{
class="token keyword">publicclass="token operator">:class="token keyword">bool class="token function">searchMatrixclass="token punctuation">(vectorclass="token operator"><vectorclass="token operator"><class="token keyword">intclass="token operator">>>class="token operator">& matrixclass="token punctuation">, class="token keyword">int targetclass="token punctuation">) class="token punctuation">{class="token keyword">int m class="token operator">= matrixclass="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">) class="token punctuation">, n class="token operator">= matrixclass="token punctuation">[class="token number">0class="token punctuation">]class="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">)class="token punctuation">;class="token keyword">int x class="token operator">= class="token number">0 class="token punctuation">, y class="token operator">= nclass="token operator">-class="token number">1class="token punctuation">;class="token keyword">whileclass="token punctuation">( x class="token operator">< m class="token operator">&& y class="token operator">>= class="token number">0class="token punctuation">)class="token punctuation">{class="token comment">// cout<<matrix[x][y]<<endl;class="token keyword">ifclass="token punctuation">(matrixclass="token punctuation">[xclass="token punctuation">]class="token punctuation">[yclass="token punctuation">] class="token operator">== targetclass="token punctuation">) class="token keyword">return class="token boolean">trueclass="token punctuation">;class="token keyword">else class="token keyword">ifclass="token punctuation">(matrixclass="token punctuation">[xclass="token punctuation">]class="token punctuation">[yclass="token punctuation">] class="token operator">> targetclass="token punctuation">) yclass="token operator">--class="token punctuation">;class="token keyword">else class="token keyword">ifclass="token punctuation">(matrixclass="token punctuation">[xclass="token punctuation">]class="token punctuation">[yclass="token punctuation">] class="token operator">< targetclass="token punctuation">) xclass="token operator">++class="token punctuation">;class="token punctuation">}class="token keyword">return class="token boolean">falseclass="token punctuation">;class="token punctuation">}
class="token punctuation">}class="token punctuation">;
code>