徐年の博客

面试题 17.21. 直方图的水量题目说明给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。 示例例112输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6 笔者理解此题是一道数组算法问题，在力扣题库中被定义为困难题。 解法当笔者阅读完此题后，发现此题是需要好好理解题目，我们统计蓄水处时，实际上需要讨论每个位置左右大于它的位置，这样需要的时间复杂度较高，所以我们可以通过双指针向中间推进的方法，左右指针只需要算对应方向的蓄水处即可，让我们来看看具体如何实现的吧。 实现1234567891011121314151617181920212223242526272829303132public int trap(int[] height) { int n = height.length; if (n == 0 ...

力扣 1006. 笨阶乘题目说明通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。 相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。 例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。 另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。 实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。 提示： 1 <= N <= 10000 -2^31 <= answer <= 2^31 - 1 （答案保证符合 32 位整数。）m == matrix.lengt ...

力扣 74. 搜索二维矩阵题目说明编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。 提示： m == matrix.length n == matrix[i].length 1 <= m, n <= 100 -104 <= matrix[i][j], target <= 104 示例例1 12输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3输出：true 例2 12输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13输出：false 笔者理解此题是一道二分查找算法问题，在力扣题库中被定义为中等题。 解法当笔者阅读完此题后，发现此题是非常经典的二分查找，只是将一维变成了二维，注意对应一二维位置的转化即可，让我们来看看具体如何实现的吧。 实现123456789101112131 ...

剑指 Offer 47. 礼物的最大价值题目说明在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 0 < grid.length <= 200 0 < grid[0].length <= 200 示例例112345678输入: [ [1,3,1], [1,5,1], [4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物 笔者理解此题是一道动态规划算法问题，在力扣题库中被定义为中等题。 解法当笔者阅读完此题后，发现此题是经典的动态规划问题，因为我们这里只能选择向上或者向右走，可以直接用一个和礼物数组大小相当的二维数组来承载各种选择的可能（此处我用了1，1~m，n，便于理解），让我们来看看具体如何实现的吧。 实现12345678910111213141516public int maxValue(int[][] grid ...

力扣 61. 旋转链表题目说明给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 返回同样按升序排列的结果链表。 链表中节点的数目在范围 [0, 500] 内 -100 <= Node.val <= 100 0 <= k <= 2 * 109 示例例1 12输入：head = [1,2,3,4,5], k = 2输出：[4,5,1,2,3] 例2 12输入：head = [0,1,2], k = 4输出：[2,0,1] 笔者理解此题是一道链表算法问题，在力扣题库中被定义为中等题。 解法当笔者阅读完此题后，发现此处将单链表变成环就会比较容易，然后通过双指针来控制开闭环即可，让我们来看看具体如何实现的吧。 实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546/** * Definition for singly-linked list. * public class ListNode { * ...

力扣 82. 删除排序链表中的重复元素 II题目说明存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。 返回同样按升序排列的结果链表。 链表中节点数目在范围 [0, 300] 内 -100 <= Node.val <= 100 题目数据保证链表已经按升序排列 示例例1 12输入：head = [1,2,3,3,4,4,5]输出：[1,2,5] 例2 12输入：head = [1,1,1,2,3]输出：[2,3] 笔者理解此题是一道链表算法问题，在力扣题库中被定义为中等题。 解法当笔者阅读完此题后，发现使用递归操作节点比较合适，让我们来看看具体如何实现的吧。 实现1234567891011121314151617181920212223242526272829303132/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNo ...

力扣 73. 矩阵置零题目说明给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用**原地算法。** 一个直接的解决方案是使用 O(m**n) 的额外空间，但这并不是一个好的解决方案。 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。 你能想出一个常数空间的解决方案吗？ 示例例1123456789101112输入: [ [1,1,1], [1,0,1], [1,1,1]]输出: [ [1,0,1], [0,0,0], [1,0,1]] 例2123456789101112输入: [ [0,1,2,0], [3,4,5,2], [1,3,1,5]]输出: [ [0,0,0,0], [0,4,5,0], [0,3,1,0]] 笔者理解此题是一道数组算法问题，在力扣题库中被定义为中等题。 解法当笔者阅读完此题后，发现此题需要我们运用原地算法，这里，我们可以用元素首行首列是否为零来表示当前行列有没有零，不过在此遍历前，我们需要两个变量预先存储首行首列存在零的情况，让我们来看 ...

力扣 150. 逆波兰表达式求值题目说明根据 逆波兰表示法，求表达式的值。 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。 1 <= tokens.length <= 10^4 tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数 示例例1123输入：tokens = ["2","1","+","3","*"]输出：9解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9 例2123输入：tokens = ["4","13","5","/","+&q ...

力扣 59. 螺旋矩阵 II题目说明给你一个正整数 n ，生成一个包含 1 到 n² 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 1 <= n <= 20 示例例1 12输入：n = 3输出：[[1,2,3],[8,9,4],[7,6,5]] 例212输入：n = 1输出：[[1]] 笔者理解此题是一道数组算法问题，在力扣题库中被定义为中等题。 解法当笔者阅读完此题后，发现此题与昨天的螺旋矩阵思路大概一致，就是像在格子上走路，我们只需要预先规划好格子，然后在即将走出边界和面对已经走过的格子时，调转方向即可。让我们来看看具体如何实现的吧。 实现1234567891011121314151617181920212223242526272829303132333435363738394041424344454647public int[][] generateMatrix(int n) { int []direX = { 0, 1, 0, -1 }; int []dir ...

力扣 54. 螺旋矩阵题目说明给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。 m == matrix.length n == matrix[i].length 1 <= m, n <= 10 -100 <= matrix[i][j] <= 100 示例例1 12输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5] 例2 12输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出：[1,2,3,4,8,12,11,10,9,5,6,7] 笔者理解此题是一道数组算法问题，在力扣题库中被定义为中等题。 解法当笔者阅读完此题后，发现此题就是像在格子上走路，我们只需要在即将走出边界和面对已经走过的格子时，调转方向即可。让我们来看看具体如何实现的吧。 实现123456789101112131415161718192021222324252627282930313233343536373839404 ...