ARTS

Algorithm 本周的算法题为 1014. 最佳观光组合 给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。 一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。 返回一对观光景点能取得的最高分。 示例 1： 输入：values = [8,1,5,2,6] 输出：11 解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11 实现代码如下： const maxScoreSightseeingPair = function (values) { let maxValue = 0 let maxPrev = values[0] // 记录前面位置能够得到的最大得分 for (let i = 1; i < values.length; i++) { maxValue = Math.max(maxValue, maxPrev + values[i] - i) // 计算当前位置的得分 maxPrev = Math.max(maxPrev, values[i] + i) // 更新前面位置能够得到的最大得分 } return maxValue } 解题思路： 一开始我以为使用两个for循环然后通过Math.max()比较一下取最大值就解出来，然后提交到力扣后，提示超出时间限制。 为了解决这个问题，可以使用动态规划来优化算法以避免重复计算，通过调整计算公式为values[i] + i + (values[j] - j)，可以将当前位置的值加上索引值，再加上下一个位置的值减去索引值，然后取最大值。因此，可以将values[i] + i和values[j] - j分别都取最大值，然后再比较两者的和，从而得到观光景点能取得的最高分。 Review Human speech is 8 times older than we thought - Breaking News English Lesson ...

Algorithm 本周的算法题为 665. 非递减数列 给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。 我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。 示例 1: 输入: nums = [4,2,3] 输出: true 解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。 示例 2: 输入: nums = [4,2,1] 输出: false 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。 实现代码如下： const checkPossibility = function (nums) { // 如果数组只有一个元素，则直接返回true if (nums.length === 1) { return true } let index = -1 for (let i = 0; i < nums.length; i++) { // 只要有一个不满足的元素，就拿到元素的下标，然后跳出循环。 if (nums[i] > nums[i + 1]) { index = i break } } // 如果出现元素A的下一个值A+1大于等于上一个值A-1，则将A赋值为A+1。 if (index === 0 || nums[index + 1] >= nums[index - 1]) { nums[index] = nums[index + 1] } else { // 否则 nums[index + 1] = nums[index] } // 再次遍历,如果修改某个元素后，不满足 nums[i] <= nums[i + 1]，则结果为false for (let i = 0; i < nums.length; i++) { if (nums[i] > nums[i + 1]) { return false } } return true }; 解题思路： ...

Algorithm 本周的算法题为 565. 数组嵌套 索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。 假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。 示例 1: 输入: A = [5,4,0,3,1,6,2] 输出: 4 解释: A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2. 其中一种最长的 S[K]: S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0} 实现代码如下： const arrayNesting = function (nums) { // 使用visited数组来记录访问过的元素 let visited = new Array(nums.length).fill(false); function getNumValue(index, nums) { // 设置count，用于记录最大集合长度 let count = 0; // 直到为false,也就是已访问过，出现重复元素，则跳出循环，返回最大集合长度count while (!visited[index]) { visited[index] = true; index = nums[index]; count++; } return count; } let longestSubArray = 0; for (let i = 0; i < nums.length; i++) { // 因为前面如果已经访问过，那么后面再次访问时，获取数组长度值一定是比之前的小的。比如当i=0时，触发了后面i=3的递归遍历，当真的执行到i=3时，又重复进行，所以没有意义。 if (!visited[i]) { let subArrayLength = getNumValue(i, nums); // 每次遍历，比较大小，获取最大值，赋值给到longestSubArray longestSubArray = Math.max(longestSubArray, subArrayLength); } } return longestSubArray; } 解题思路： 我一开始的思路是使用递归，依次将nums各个元素都执行一遍，虽然也解出来了，但是无法满足力扣的解题需求，毕竟是暴力解法，不够优雅。然后使用ChatGPT，让它诊断了下代码，提出特别好的解法，就是上面的代码。最核心的一点就是，使用visited数组来记录访问过的元素，因为如果前面已经访问过，那么后面再次访问时，获取集合长度值一定是比之前的小。比如上面的示例1，当i=0时，其值为5，触发了后面i=5的递归遍历，当真的执行到i=5时，又重复进行，所以没有意义。 Review It once rained for two million years, say scientists 农民在干旱时期祈求降雨。我们大多数人都有过这样的经历，即希望上天为我们的花园降雨以便浇灌植物。然而，我们谁也无法想象一场持续200万年的长时间降雨。英国地质学家和法医科学家阿拉斯泰尔·鲁菲尔发现，在2亿至3亿年前，在盘古大陆分离成大陆之前，地球确实经历了一个长达200万年不间断降雨的时代。鲁菲尔博士说，这有助于促进全球动植物的发展。他认为，降雨可能是由一系列大规模火山喷发后湿度的大幅上升引发的。 鲁费尔博士及其团队是基于在欧洲东阿尔卑斯山脉进行的研究，该研究于20世纪70年代和80年代展开。数据显示，在可追溯到2亿多年前的古老岩石中沉积了不寻常的地层。鲁菲尔说，这导致越来越多的证据表明，雨季可能是“使恐龙和可能是我们现代陆地动物群其他成员多样化并占领陆地”的触发因素。他补充说：“这可能是生命史上最重要的事件之一，因为它不仅在允许恐龙时代的同时，也促成了大多数构成现代动物群的关键类群的起源，包括龟类、鳄鱼、蜥蜴和哺乳动物。” Tip Flutter国内环境配置 ...

Algorithm 本周的算法题为 1222. 可以攻击国王的皇后 在一个 下标从 0 开始 的 8 x 8 棋盘上，可能有多个黑皇后和一个白国王。 给你一个二维整数数组 queens，其中 queens[i] = [xQueeni, yQueeni] 表示第 i 个黑皇后在棋盘上的位置。还给你一个长度为 2 的整数数组 king，其中 king = [xKing, yKing] 表示白国王的位置。 返回 能够直接攻击国王的黑皇后的坐标。你可以以 任何顺序 返回答案。 示例 1： 输入：queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0] 输出：[[0,1],[1,0],[3,3]] 解释：上面的图示显示了三个可以直接攻击国王的皇后和三个不能攻击国王的皇后（用红色虚线标记）。 实现代码如下： var queensAttacktheKing = function(queens, king) { // 初始化棋盘 const board = Array.from({ length: 8 }, () => Array.from({ length: 8 }, () => null)); // 将皇后的位置标记在棋盘上 queens.forEach((queen) => { board[queen[0]][queen[1]] = 'Q'; }); const res = []; // 顺时针方向遍历棋盘 const directions = [ [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1] ]; for (const element of directions) { const [dx, dy] = element; let x = king[0] + dx; let y = king[1] + dy; while (x >= 0 && x < 8 && y >= 0 && y < 8) { if (board[x][y] === 'Q') { res.push([x, y]); break; } x += dx; y += dy; } } return res; }; 解题思路： ...

Algorithm 本周的算法题为 661. 图片平滑器 图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。 每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。 如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。 给你一个表示图像灰度的 m x n 整数矩阵 img ，返回对图像的每个单元格平滑处理后的图像 。 示例 1: 输入:img = [[1,1,1],[1,0,1],[1,1,1]] 输出:[[0, 0, 0],[0, 0, 0], [0, 0, 0]] 解释: 对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0 对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0 对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0 实现代码如下： var imageSmoother = function (img) { const m = img.length; const n = img[0].length; const result = new Array(m).fill(0).map(() => new Array(n).fill(0)); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { result[i][j] = calculate(i, j); } } return result; function calculate(i, j) { let totalValue = 0; let count = 0; for (let x = Math.max(0, i - 1); x <= Math.min(i + 1, m - 1); x++) { for (let y = Math.max(0, j - 1); y <= Math.min(j + 1, n - 1); y++) { totalValue += img[x][y]; count++; } } return totalValue / count >> 0; } } 解题思路： 首先，代码初始化了两个变量 m 和 n，分别表示输入二维数组 img 的行数和列数。然后，创建了一个与 img 相同大小的二维数组 result，用于存储平滑后的图像。 ...