devbox
小桥流水78
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

leetcode刷题（javaScript）——数组相关场景题总结_给定一个由正整数数组,请按以下规则处理,使得数组有序(递增或者递减,不一定要严格

作者：小桥流水78 | 2024-07-08 18:03:07

赞

踩

给定一个由正整数数组,请按以下规则处理,使得数组有序(递增或者递减,不一定要严格

数组只是一种数据结构，通常结合其他算法场景出现。这里总结几类在LeetCode刷题时，针对数组相关的场景题，可以使用以下技巧和方法：

  1. 双指针法：

    • 快慢指针用于解决数组中的有序问题，如移除重复项、找出唯一元素等。
    • 左右指针用于解决数组中的对撞问题，如两数之和、接雨水等。

  2. 排序：对数组进行排序可以简化很多问题，如对数组进行排序后，可以更容易地解决部分排序问题。

  3. 哈希表：使用对象字面量或Map结构存储键值对，可以快速查找数组中的元素，常用于解决两数之和、最长连续序列等问题。

  4. 滑动窗口：对于找出连续子数组的问题，如连续子数组的最大和、最小覆盖子串等，滑动窗口是一个有效的技巧。

  5. 动态规划：对于需要考虑历史状态的问题，如最大子序和、最长递增子序列等，动态规划可以提供解决方案。

  6. 分治法：将大问题分解为小问题，分别解决后再合并结果，适用于如归并排序等场景。

  7. 贪心算法：在每一步选择中都采取在当前看来最好的选择，例如买卖股票的最佳时机等问题。

哈希表相关参考我的博客：leetcode刷题（javaScript）——字典哈希表相关场景题总结-CSDN博客

动态规划相关参考我的博客

leetcode刷题（javaScript）——动态规划相关场景题总结

递归相关参考我的博客

leetcode刷题（javaScript）——回溯、递归、dfs相关场景题总结-CSDN博客

双指针：快慢指针/左右指针

双指针法在LeetCode刷题中经常被用到，特别是在数组和字符串相关的问题中。双指针法在解决数组和字符串相关问题时，通常用于处理两个方向的遍历、查找、移动等操作。根据问题的特点，选择合适的双指针策略，可以有效地提高问题的解决效率。以下是一些常见的应用场景：

  1. 快慢指针：

    • 移除数组中的重复元素，保留唯一元素。
    • 寻找数组中的某个特定值或范围。

  2. 左右指针：

    • 在有序数组中查找两数之和、三数之和等。
    • 滑动窗口问题，如最小覆盖子串、最长无重复字符的子串等

26. 删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

 思路：用快慢指针，慢指针pre在数组左侧，记录非重复值的index，快指针是循环遍历的i变量。快指针正常遍历，每走一个位置都和pre进行比较，如果快指针的元素和pre相同，pre不变；如果快指针和pre不同，pre向右走一个，通时保存快指针的值。一次循环结束，慢指针pre及之前的元素都是唯一的了。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var removeDuplicates = function(nums) {
  6.     let pre=0;//左指针
  7.     for(let i=1;i<nums.length;i++){//循环充当右指针
  8.         if(nums[i]!=nums[pre]){//当右指针i找到唯一值，左指针向后移动，并记录右指针的值
  9.             pre++;
  10.             nums[pre]=nums[i];
  11.         }
  12.     }
  13.     return pre+1;//pre最终的index+1是数组长度
  14. };

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

 思路：用快慢指针，慢指针记录非0的最后一个index，快指针为i循环数组。当快指针走完时，如果快慢指针中间还有元素，将其置为0即可。如果快指针指向的元素为0，慢指针不更新，否则慢指针更新为快指针指向的值。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {void} Do not return anything, modify nums in-place instead.
  4.  */
  5. var moveZeroes = function (nums) {
  6.     //快慢指针，慢指针指向非0值，快指针遍历数组。最后快指针停止的时候，将快慢指针部分填充0
  7.     let slow = 0;
  8.     for (let i = 0; i < nums.length; i++) {
  9.         if (nums[i] != 0) {
  10.             nums[slow++] = nums[i];
  11.         }
  12.     }
  13.     //如果没有0元素，slow应该等于nums.length。因为slow每次执行完都加1
  14.     if (slow <= nums.length - 1) {
  15.         for (let j = slow; j < nums.length; j++) {
  16.             nums[j] = 0;
  17.         }
  18.     }
  19. };

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

进阶：

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

思路：这是一道双指针的技巧题了，不容易想出来。因为数组中还有负数，负数的平方和有可能大于正数的平方和，所以直接用平方和是无法排序的。

这里假设结果数组是从大到小获取的，也就是数组从头插法建立结果数组。那么每次从剩余数组中取出较大的元素，可以使用双指针来完成，根据左右指针的平方和取一个较大值，然后取值的指针走一步。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[]}
  4.  */
  5. var sortedSquares = function (nums) {
  6.     let result = [];
  7.     let left = 0,
  8.         right = nums.length - 1;
  9.     while (left <= right) {
  10.         const leftSquare = nums[left] * nums[left];
  11.         const rightSquare = nums[right] * nums[right];
  12.         if (leftSquare > rightSquare) {//左右指针选一个较大值
  13.             result.unshift(leftSquare);
  14.             left++;
  15.         } else {
  16.             result.unshift(rightSquare);
  17.             right--;
  18.         }
  19.     }
  20.     return result;
  21. };

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

思路：利用左右双指针，向中间靠拢计算水容量。如何得到过程中较大值，每次移动的时候移动那个高度较小的指针，这样指针就会去尝试找大的高度，而让较高的高度保留。计算过程中水容量的较大值max。最后返回max

  1. /**
  2.  * @param {number[]} height
  3.  * @return {number}
  4.  */
  5. var maxArea = function (height) {
  6.     let left = 0, right = height.length - 1;
  7.     let cur, max = 0;
  8.     while (left < right) {//左右指针，每次移动两者高度的最小值，保证获得较大的容量
  9.         let leftVal = height[left];
  10.         let rightVal = height[right];
  11.         cur = Math.min(leftVal, rightVal) * (right - left);
  12.         max = Math.max(cur, max);
  13.         if (leftVal < rightVal) {//如果左侧高度小，移动左指针
  14.             left++;
  15.         } else {//如果相等或右侧高度小移动右指针
  16.             right--;
  17.         }
  18.     }//遍历结束
  19.     return max;
  20. };

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

 思路：这题老难了。看了解析才做出来。主体思路是先排序。然后对这个有序数组求解。

将三数之和拆成x+y+z。由于三数之和为0，那么必然有一个是非正数，即负数或0。遍历x，然后利用双指针从x后面的元素找y和z，这里不找两数之后，还是判断x+y+z是否为0，y从x后面第一个元素开始，z从数组最后一项开始。如果sum>0，说明z大了，z向左移，如果sum<0，说明y小了，y向右移。

那么难点来了，如何去重，这里x可能有重，y和z也有可能重复。面对这样一个数组，你如何跳过重复的x,y,z？

nums =[-2,0,0,2,2]

答案就是，移动y和z的时候，要移动下一个不相等的。

那x重复呢？

那你就跳过x，找不重复的。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[][]}
  4.  */
  5. var threeSum = function (nums) {
  6.     //将三数之和拆成x+y+z,假设x是负数，那么y+z一定是正数；相同的x只遍历一次
  7.     nums = nums.sort((a, b) => a - b);//从小到大排序
  8.     let res = [];//存放最终的数组
  9.     let xIndex = 0, yIndex, zIndex;
  10.     while (nums[xIndex] <= 0) {//只遍历负数和0，每次固定x，找y和z
  11.         if (xIndex > 0 && nums[xIndex] === nums[xIndex - 1]) {//x去重，不要重复处理相同的x
  12.             xIndex++;
  13.             continue;
  14.         }
  15.         yIndex = xIndex + 1;
  16.         zIndex = nums.length - 1;
  17.         while (yIndex < zIndex) {
  18.             let sum = nums[xIndex] + nums[yIndex] + nums[zIndex];//
  19.             if (sum > 0) {
  20.                 zIndex--;
  21.             } else if (sum < 0) {
  22.                 yIndex++;
  23.             } else {//找到了目标x,y,z
  24.                 res.push([nums[xIndex], nums[yIndex], nums[zIndex]]);
  25.                 while (nums[yIndex] == nums[yIndex + 1]) {//y和z去重，否则nums =[-2,0,0,2,2]过不了
  26.                     yIndex++;
  27.                 }
  28.                 while (nums[zIndex] === nums[zIndex - 1]) {
  29.                     zIndex--;
  30.                 }
  31.                 yIndex++; 
  32.                 zIndex--;
  33.             }
  34.         }
  35.         xIndex++;
  36.     }
  37.     return res;
  38. };

滑动窗口

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

思路：这是个困难题。但是诈一块思路很简单，就是用一个队列先进先出，每次求队列的最大值。但是题目没说，从无序队列求最大值会导致超时，n*k的时间复杂度。所以思路就变成了维护一个相对有序的队列。

怎么维护呢，首先，滑动窗口右侧的要加入的元素无论大小都要加入队列里，此时如果队列没有元素直接加入。如果队列有元素，当前加入的如果比队尾大，循环删除队尾，整个队列保持降序的状态。如果此时队头还有老的元素，判断队头的存放的数组下标是否不在当前的窗口中，如果不在，删除队头。每次队头最少删一个，最多删k-1个。在窗口移动的过程中将更新后的队头最大值存入结果数组中

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @return {number[]}
  5.  */
  6. var maxSlidingWindow = function (nums, k) {
  7.     let queue = [];//队头维护最大值，nums[i]推进去的时候如果比队尾大，循环删除小的队尾，推入后。判断队头是否需要移除
  8.     let res = [];
  9.     for (let i = 0; i < nums.length; i++) {
  10.         while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
  11.             queue.pop();//当前入队的元素比队列尾部的大，删除队尾
  12.         }
  13.         queue.push(i);//当前下标入队
  14.         if (queue[0] <= i - k) {//处理队头，如果队头不在窗口里，删除
  15.             queue.shift();
  16.         }
  17.         if (i >= k - 1) {
  18.             res.push(nums[queue[0]])
  19.         }
  20.     }
  21.     return res;
  22. };

 模拟过程

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

思路：有多种方法可以实现数组向右旋转 k 个位置，下面列举其中两种常见的方法：

  1. 使用额外数组：

    • 创建一个额外的数组，将原数组中从倒数第 k 个元素到最后一个元素复制到额外数组的开头。
    • 将原数组中前 len-k 个元素复制到额外数组的剩余位置。
    • 将额外数组复制回原数组。
    • 时间复杂度为 O(n)，空间复杂度为 O(n)。

  2. 使用翻转：

    • 翻转整个数组。
    • 翻转从索引 0 到 k-1 的子数组。
    • 翻转从索引 k 到末尾的子数组。
    • 时间复杂度为 O(n)，空间复杂度为 O(1)。

这两种方法都可以实现数组向右旋转 k 个位置，但使用翻转的方法空间复杂度更低。因此，推荐使用翻转的方法来实现数组旋转。

 这里注意k的值可能超过nums数组的长度，因此，需要对k进行nums取模。避免翻转多次。为了O(1)的空间复杂度，使用三次翻转，使得数组原地被修改，不引入额外空间。在js中我们可以使用数组方式，交换两个元素值。

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @return {void} Do not return anything, modify nums in-place instead.
  5.  */
  6. var rotate = function (nums, k) {
  7.     // 获取数组的长度。
  8.     let len = nums.length;
  9.     // 如果 k 大于数组长度，使用取模运算调整 k 的值。处理 k 大于数组元素数量时的情形。
  10.     k = k % len;
  11.     // 翻转整个数组，从索引 0 到 len-1。
  12.     reverse(nums, 0, len - 1);
  13.     reverse(nums, 0, k - 1);// 翻转数组的前 k 个元素。    
  14.     reverse(nums, k, len - 1);// 翻转从 k 到数组末尾的元素。
  15. };
  16. // 定义一个翻转函数，接收一个数组、一个开始索引和一个结束索引。
  17. function reverse(nums, start, end) {
  18.     // 从 start 索引遍历到 start 和 end 索引中间的位置。
  19.     // 中间位置使用 floor 函数计算，以正确处理奇数长度的数组。
  20.     for (let i = start; i <= Math.floor((end + start) / 2); i++) {
  21.         // 交换当前元素与从 end 索引开始对应的元素。这在原地有效地翻转了数组。
  22.         [nums[i], nums[end - i + start]] = [nums[end - i + start], nums[i]];
  23.     }
  24. }

59. 螺旋矩阵 II 

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

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

示例 2：

输入：n = 1
输出：[[1]]

提示：

  • 1 <= n <= 20

思路：生成一个按顺时针顺序螺旋排列的n x n正方形矩阵，我们可以模拟顺时针填充矩阵的过程。具体步骤如下：

  1. 初始化一个空的n x n矩阵matrix，并定义四个变量top、bottom、left、``right`分别表示当前填充区域的上、下、左、右边界。

  2. 定义一个变量num表示当前要填充的数字，初始值为1。

  3. 不断循环填充矩阵，直到num达到n*n为止。在每一轮循环中，按照顺时针的顺序填充矩阵的上、右、下、左边界，同时更新边界值和num的值。

  4. 最终返回填充完成的矩阵matrix。

  1. /**
  2.  * @param {number} n
  3.  * @return {number[][]}
  4.  */
  5. function generateMatrix(n) {
  6.     const matrix = Array.from(Array(n), () => Array(n).fill(0));
  7.     let top = 0,
  8.         bottom = n - 1,
  9.         left = 0,
  10.         right = n - 1;//表示当前填充区域的上、下、左、右边界。
  11.     let num = 1;
  12.     while (num <= n * n) {
  13.         for (let i = left; i <= right; i++) {
  14.             matrix[top][i] = num++;
  15.         }
  16.         top++;
  17.         for (let i = top; i <= bottom; i++) {
  18.             matrix[i][right] = num++;
  19.         }
  20.         right--;
  21.         for (let i = right; i >= left; i--) {
  22.             matrix[bottom][i] = num++;
  23.         }
  24.         bottom--;
  25.         for (let i = bottom; i >= top; i--) {
  26.             matrix[i][left]=num++;
  27.         }
  28.         left++;
  29.     }
  30.     return matrix;
  31. }

动态规划

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

思路：通常我们在看到这种跳跃的题目，很容易想到动态规划，动态规划适用于爬楼梯这种，根据当前状态，有几种走法，根据走法从前面已有的信息推导当前状态。在这道题里，可以定义一个dp数组，dp[i]表示从0到i的任意节点能够跳到的最大数组下标。用dp数组记录一个最大值是不是大材小用？我们是不是可以直接使用一个max变量，每个index都重新计算一下。如果第i个元素是0，并且这个max没有超过i，是不是没法避免这个0值。后续的元素都到达不了。当然，如果这个0是数组最后一项就不用考虑。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {boolean}
  4.  */
  5. var canJump = function (nums) {
  6.     let maxToIndex = 0;//maxToIndex表示0-i之间的下标能到达最远的下标
  7.     for (let i = 0; i < nums.length; i++) {
  8.         if (nums[i] == 0 && maxToIndex <= i && i<nums.length-1) {//如果nums[i]是0，并且当前max没有超过i，并且不是最后一项
  9.             return false;//返回false，结束
  10.         } else {
  11.             maxToIndex = Math.max(maxToIndex, i + nums[i]);//否则，更新max
  12.         }
  13.     }
  14.     return true;
  15. };

 45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i] 
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

思路：我们看到，后一个的求解和前面的跳转是有关系的。考虑用动态规划做。动态规划的难点在于你怎么抽离一个公共的描述dp[i]的行为。在这个题里可以看出来，我们需要记录到达下标i能够跳跃的最少步数，那么dp[i]就描述为从节点0到达节点i经过的最少跳跃次数。那么难点来了，我们更新哪个节点呢？

假设除了节点0，后面的节点dp都初始化无限大。

每次访问节点i的时候，是不是可以更新节点i到i+nums[i]之间的跳转次数。

取dp[i]+1和节点本身的dp[j]值的最小值。因为dp[j]可能被计算过。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var jump = function (nums) {
  6.     let dp = Array(nums.length).fill(Infinity);//使用动态规划dp[i]定义为从0跳到i最少跳跃步数
  7.     dp[0] = 0;//初始化dp
  8.     for (let i = 0; i < nums.length; i++) {//外循环i
  9.         let jumpIndex = i + nums[i];//拿到覆盖范围
  10.         for (let j = i + 1; j <= jumpIndex; j++) {//对覆盖范围内所有点重新计算dp
  11.             dp[j] = Math.min(dp[i] + 1, dp[j]);//取新计算的最小值赋给当前dp[j]
  12.         }
  13.     }
  14.     return dp[nums.length - 1];//返回最后一个元素，即为目标
  15. };

哈希表结合数组

380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

  • RandomizedSet() 初始化 RandomizedSet 对象
  • bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
  • bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
  • int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

思路:看到插入和删除时间复杂度为 O(1) 时，立马联想到使用哈希表，但哈希表无法在随机获取值的时候达到O(1) ，需要使用数组配合。因此同时使用哈希表和数组结构

在插入时，哈希表记录对应值所在的下标，并将值从数组队尾插入；

在删除时，获取值对应的数组下标，并用队尾元素覆盖写入对应下标，且重新给哈希表对应的记录更新下标；

在查找时，只要随机一个下标值访问数组即可

  1.  
  2. var RandomizedSet = function () {
  3.     this.map = new Map();//存储val和index
  4.     this.arr = [];
  5. };
  6.  
  7. /** 
  8.  * @param {number} val
  9.  * @return {boolean}
  10.  */
  11. RandomizedSet.prototype.insert = function (val) {
  12.     if (this.map.has(val)) {
  13.         return false;
  14.     } else {
  15.         this.map.set(val, this.arr.length);
  16.         this.arr.push(val);
  17.         return true;
  18.     }
  19. };
  20.  
  21. /** 
  22.  * @param {number} val
  23.  * @return {boolean}
  24.  */
  25. RandomizedSet.prototype.remove = function (val) {
  26.     if (this.map.has(val)) {
  27.         const index = this.map.get(val);
  28.         this.arr[index] = this.arr[this.arr.length - 1];
  29.         this.map.set(this.arr[index], index);
  30.         this.arr.pop();
  31.         this.map.delete(val);
  32.         return true;
  33.     } else {
  34.         return false;
  35.     }
  36. };
  37.  
  38. /**
  39.  * @return {number}
  40.  */
  41. RandomizedSet.prototype.getRandom = function () {
  42.     let randomIndex = Math.floor(Math.random() * this.arr.length);
  43.     return this.arr[randomIndex];
  44. };
  45.  
  46. /**
  47.  * Your RandomizedSet object will be instantiated and called as such:
  48.  * var obj = new RandomizedSet()
  49.  * var param_1 = obj.insert(val)
  50.  * var param_2 = obj.remove(val)
  51.  * var param_3 = obj.getRandom()
  52.  */

80. 删除有序数组中的重复项 II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

思路：题目的数组还是有序，增加了一个限制，可以允许重复次数2。在上一题的基础上，增加一个计数器，统计重复的个数。pre和i不相等的时候正常给pre赋值。当两者相等的时候，如果计数器没有超过2，正常赋值。超过了就不移动pre了。相等的时候count++，不等的时候count=1

  1. var removeDuplicates = function (nums) {
  2.     let pre = 0;//左指针
  3.     let count = 1;//增加一个计算重复的count
  4.     for (let i = 1; i < nums.length; i++) {
  5.         if (nums[pre] != nums[i]) {//左右指针不相等
  6.             pre++;
  7.             nums[pre] = nums[i];
  8.             count = 1;//不相等的时候count为1
  9.         } else {//左右指针相等
  10.             count++;
  11.             if (count <= 2) {//count没有超过2
  12.                 pre++;//正常记录
  13.                 nums[pre] = nums[i];
  14.             }//超过了，不处理
  15.         }
  16.     }
  17.     return pre + 1;
  18. };

12. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

思路：用哈希表存储键值对+使用相减法获取每步加入的字符。这里使用map构建哈希表，因为map对象会维护键值对的插入顺序 。为什么要考虑顺序呢？因为相减法会尝试用最大值做减法，用被减数减它，每次相减可获得减数对应的val值。比如3200这个数，3200-1000，得到一个1000，用M表示，剩余2200，是不是还可以用1000减，得到MM，还有1200，在用1000减，得到MMM，剩余200，在尝试从剩余的数值中找比200小的第一个，100。用100减得到MMMC，最后MMMCC

  1. /**
  2.  * @param {number} num
  3.  * @return {string}
  4.  */
  5. var intToRoman = function (num) {
  6.     let map = new Map();
  7.     let carry = 1;
  8.     let str = '';
  9.     //map存储键值对，在遍历的时候顺序和插入的顺序保持一致，大的值放前面
  10.     map.set(1000, 'M');
  11.     map.set(900, 'CM');
  12.     map.set(500, 'D');
  13.     map.set(400, 'CD');
  14.     map.set(100, 'C');
  15.     map.set(90, 'XC');
  16.     map.set(50, 'L');
  17.     map.set(40, 'XL');
  18.     map.set(10, 'X');
  19.     map.set(9, 'IX');
  20.     map.set(5, 'V');
  21.     map.set(4, 'IV');
  22.     map.set(1, 'I');
  23.     //用相减比取余简单一点。一直尝试用map中较高的值做减数
  24.     map.forEach((val, key) => {
  25.         while (num >= key) {//对每个key值如果可以作为减数，一直减，直到不符合，在尝试下一个key
  26.             str += val;
  27.             num -= key;
  28.         }
  29.     })
  30.     return str;
  31. };

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

思路：如果不考虑空间复杂度

求最小正整数，可以初始化最小正整数为1。只处理正数，不用管负数。那么用哈希表存储已遍历的元素。去哈希表里找是否有min，如果有，min+1，同时删除哈希表里的min，防止哈希过长。遍历nums结束，min值返回

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var firstMissingPositive = function (nums) {
  6.     let set = new Set();//用map存储已存在的值
  7.     let min = 1;
  8.     for (let i = 0; i < nums.length; i++) {
  9.         if (nums[i] > 0) {//set只处理正数
  10.             set.add(nums[i]);//先将结果入set
  11.             while (set.has(min)) {//如果set里有min，说明min已经存在
  12.                 set.delete(min);//删除min，min+1，继续查找
  13.                 min++;
  14.             }
  15.         }
  16.     }
  17.     return min;
  18. };

思路：题目要求空间复杂度为O(1)。怎么构建哈希表呢？

可以采用一种“原地哈希”的方法。

基本思想是：利用数组本身的索引来标记数字是否出现过。具体步骤如下：

  1. 首先遍历数组，将所有负数和0的数置为n+1。

  2. 然后再次遍历数组，将出现过的数字对应的索引位置的数置为负数。

  3. 最后再次遍历数组，找到第一个正数的索引加1即为未出现的最小正整数。

在第二次遍历设置最小整数的时候用的是Math.abs(nums[i])，既不能更改负数的状态，同时还要使用当前nums[i]的正数值作为索引去更新其他值。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var firstMissingPositive = function (nums) {
  6.     let n = nums.length;
  7.     //原地hash
  8.     for (let i = 0; i < nums.length; i++) {
  9.         if (nums[i] <= 0) {
  10.             nums[i] = n + 1;//设置负数都比n大
  11.         }
  12.     }
  13.     //处理小于等于n的正数
  14.     for (let i = 0; i < nums.length; i++) {
  15.         let num = Math.abs(nums[i]);
  16.         if (num <= n) {
  17.             const index = num - 1;//用数组下标表示正数是否出现
  18.             nums[index] = -Math.abs(nums[index]);//将已经出现的设为自身的负数，同时正数的值还可能后序遍历用到
  19.         }
  20.     }
  21.     for (let i = 0; i < nums.length; i++) {
  22.         if (nums[i] > 0) {
  23.             return i + 1;
  24.         }
  25.     }
  26.     return n + 1;
  27. };

前缀后缀和/积

238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

 

思路：这个题明确给出了不能用乘法，而且时间复杂度限制在o(n)，然后还有提示前缀元素和后缀元素。如何利用前缀和后缀呢

对于要返回的数组arr，数组每一项arr[i]可以拆为两个部分的乘积，[0,i)的元素乘积，(i,len-1]的元素乘积。因此，先让arr[i]记录数组前缀积，一次遍历数组nums，所有的下标都能更新前缀积。之后计算后缀积，因为此时arr已经有前缀积了，所有后缀积需要用一个变量suf存储。从后往前所有元素都共享这个suf，arr[i]*这个前缀就可以了

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[]}
  4.  */
  5. var productExceptSelf = function (nums) {
  6.     let arr = [];//返回的数组arr[i]表示除i以外元素的乘积，按照下标i将arr[i]=i之前的元素乘积*i之后的元素乘积
  7.     // 两次for循环
  8.     //第一次for循环求前缀积
  9.     arr[0] = 1;
  10.     let suf = 1;//后缀
  11.     for (let i = 1; i < nums.length; i++) {
  12.         arr[i] = arr[i - 1] * nums[i - 1];
  13.     }
  14.  
  15.     //第二次for循环求后缀积
  16.     for (let i = nums.length - 1; i >= 0; i--) {
  17.         arr[i] = arr[i] * suf;
  18.         suf *= nums[i];
  19.     }
  20.     return arr;
  21. };
  22.

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

思路：这个题一定要看题解。自己想很复杂。这道题目要求统计一个整数数组中和为特定值k的连续非空子数组的个数。解决这个问题的一个有效方法是使用前缀和与哈希表。

对于nums数组：

  1. nums = [1, 0, 1, 0, 1]
  2. k = 2

前缀和数组如下：

prefixSum = [0, 1, 1, 2, 2, 3]

加上第j个元素的前缀和为prefixSum[j]，我现在想找以i为结束的子串数量有多少个。如何有i，prefixSum[i]表示0-i之间的和。那么有prefixSum[j]-prefixSum[i]=k;那我在节点j的时候怎么取找有多少个起始点i呢？假设我已经用map字典存放了前缀和，和出现的次数。那么我在找prefixSum[j]-k在map中有没有出现过，以及出现了几次，是不是就是i出现了几次。

  1. 前缀和：首先，我们可以计算数组的一个前缀和数组，这样我们就可以快速得到任意一个子数组的和。前缀和数组prefixSum的第i个元素表示原数组从第一个元素到第i个元素的和。

  2. 哈希表：我们使用一个哈希表（用map对象）来存储前缀和的出现次数。键是前缀和，值是该前缀和出现的次数。

  3. 遍历数组：我们遍历数组，计算前缀和，并更新哈希表。对于每个前缀和，我们检查prefixSum[i] - k是否在哈希表中。如果存在，这意味着我们找到了一个子数组，其和为k。

  4. 统计子数组个数：如果prefixSum[i] - k在哈希表中，我们就增加结果计数。哈希表中prefixSum[i] - k的值表示有多少个前缀和等于prefixSum[i] - k，也就是有多少个子数组的和为k。

  5. 更新哈希表：每次计算新的前缀和时，我们更新哈希表，增加当前前缀和的计数。

  6. 边界条件：在开始遍历之前，我们先将prefixSum[0]设置为1，因为一个空的子数组的和为0。

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @return {number}
  5.  */
  6. var subarraySum = function (nums, k) {
  7.     //用map计算前缀和
  8.     let map = new Map();
  9.     map.set(0, 1);//表示前缀和为0的有一个
  10.     let prefixSum = 0;
  11.     let count = 0;
  12.     for (let i = 0; i < nums.length; i++) {
  13.         prefixSum += nums[i];//统计当前前缀和
  14.         if (map.has(prefixSum - k)) {
  15.             count += map.get(prefixSum - k);
  16.         }
  17.         map.set(prefixSum, map.has(prefixSum) ? map.get(prefixSum) + 1 : 1);//当前前缀和出现的次数
  18.     }
  19.     return count;
  20. };

贪心算法

134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

思路：这个问题可以使用贪心算法来解决。具体步骤如下：

  1. 遍历每个加油站，计算每个加油站的净剩余汽油量（gas[i] - cost[i]）。

  2. 定义两个变量：rest用于记录总的净剩余汽油量，curr用于记录当前的净剩余汽油量。

  3. 从第一个加油站开始遍历，如果当前净剩余汽油量小于0，则说明无法从当前加油站出发到达下一个加油站，需要将起始加油站设置为下一个加油站。

  4. 最后，如果总的净剩余汽油量大于等于0，则返回起始加油站的索引，否则返回-1。

  1. /**
  2.  * @param {number[]} gas
  3.  * @param {number[]} cost
  4.  * @return {number}
  5.  */
  6. var canCompleteCircuit = function (gas, cost) {
  7.     let currGas = 0;
  8.     let rest = 0;    //记录总剩余，如果总的油量小于总消耗，一定没解
  9.     let start = 0;
  10.     for (let i = 0; i < gas.length; i++) {
  11.         rest += gas[i] - cost[i];//记录此时总剩余
  12.         currGas += gas[i] - cost[i];//记录当前汽油量
  13.         if (currGas < 0) {//如果当前汽油是负数，更换起始点
  14.             start = i + 1;
  15.             currGas = 0;
  16.         }
  17.     }
  18.     return rest >= 0 ? start : -1;//如果总剩余是负数，一定找不到，否则返回最后一次更新的起始点
  19. };

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

 思路：用一个数组存储第i个节点应该获取的糖果数量。默认最少有一个。

题目要求每个节点i，既要考虑它左侧的节点i-1，又要考虑右侧的节点i+1。这个时候不能同时考虑左右两个，因为会顾此失彼。这题的求解应该先考虑左边大或者右边大，在进行右边大或左边大的考虑。

假设我们先考虑右边比左边大的情况：

从左到右遍历，如果评分ratings[i]大于ratings[i-1]，那么arr[i]=arr[i-1]+1，即在前一个糖果的基础上加1。否则arr[i]=1，不变。

遍历结束后，所有节点的右边比左边大的情况考虑结束。

接着考虑左边比右边大的情况：

这个时候我们需要以右侧为基准，不断找左侧孩子，因此，循环从右向左，如果当前评分ratings[i]大于ratings[i+1]，第i个孩子的糖果数量arr[i]=arr[i+1]+1，但是如果这个值可能小于arr[i]，为了两个都满足，取最大值。

arr[i]求解结束，第i个孩子的糖果数量固定了，更新sum值

  1. /**
  2.  * @param {number[]} ratings
  3.  * @return {number}
  4.  */
  5. var candy = function (ratings) {
  6.     let sum = 0;
  7.     let arr = Array(ratings.length).fill(1);//初始化糖果数组
  8.     for (let i = 1; i < ratings.length; i++) {//从前遍历，右侧比左侧大，右侧+1
  9.         if (ratings[i] > ratings[i - 1]) {
  10.             arr[i] = arr[i - 1] + 1;//右边比左边大的话，对应糖果数组比左边+1
  11.         }
  12.     }
  13.     sum = arr[ratings.length - 1];
  14.     for (let i = ratings.length - 2; i >= 0; i--) {//如果左边比右边大
  15.         if (ratings[i] > ratings[i + 1]) {
  16.             arr[i] = Math.max(arr[i + 1] + 1, arr[i]);
  17.         }
  18.         //二次遍历arr[i]存放的是最终糖果数量
  19.         sum += arr[i];
  20.     }
  21.     return sum;
  22. };

单调栈

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路：使用单调递增栈，一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了。然后计算横向的雨水量。凹槽内部的雨水通过横向计算累加得到。

凹槽的底部：取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部

凹槽的高度：min(凹槽左边高度, 凹槽右边高度) - 凹槽自身高度

凹槽的宽度：凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度）

在求解时，先考虑凹槽时处理栈的情况要简单一下。同时在while循环求栈的时候，如果栈内没有元素可提前结束。

  1. /**
  2.  * @param {number[]} height
  3.  * @return {number}
  4.  */
  5.  
  6. var trap = function (height) {
  7.     let stack = [];
  8.     let total = 0; // 记录雨水量
  9.  
  10.     for (let i = 0; i < height.length; i++) {
  11.         while (stack.length && height[i] > height[stack[stack.length - 1]]) {//出现凹槽循环求解栈内元素
  12.             let curIndex = stack.pop();
  13.             if (stack.length === 0) {//如果栈里没有数据，当前curIndex没有降水量
  14.                 break;
  15.             }
  16.             let leftIndex = stack[stack.length - 1];//拿到左边的高度
  17.             let h = Math.min(height[leftIndex], height[i]) - height[curIndex];//和最右边取一个最小值，并减去自身的高度
  18.             let w = i - leftIndex - 1;//计算宽度
  19.             total += h * w;//累加当前的体积
  20.         }
  21.         stack.push(i);//处理结束，当前元素入栈
  22.     }
  23.  
  24.     return total;
  25. };

数组合并

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

 解题思路：从两个数组的最后两个元素进行比较，取最大值放第一个数组后面。考虑边界值，n=0时不用处理，m=0时将nums2数组值填充第一个

  1.   /**
  2.    * @param {number[]} nums1
  3.    * @param {number} m
  4.    * @param {number[]} nums2
  5.    * @param {number} n
  6.    * @return {void} Do not return anything, modify nums1 in-place instead.
  7.    */
  8.   var merge = function (nums1, m, nums2, n) {
  9.     if (n == 0) return;
  10.     //比较数据中最后一个元素，每次取最大值
  11.     let i = m - 1,
  12.       j = n - 1,
  13.       k = m + n - 1;
  14.     while (i >= 0 && j >= 0) {
  15.       if (nums1[i] > nums2[j]) {
  16.         nums1[k--] = nums1[i--];
  17.       } else {
  18.         nums1[k--] = nums2[j--];
  19.       }
  20.     }
  21.     while (j >= 0) {
  22.       nums1[k--] = nums2[j--];
  23.     }
  24.   };

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路：没有技巧，纯手撕，根据测试用例看出bug在哪。注意这个用例

intervals =[[1,4],[2,3]]。输出是1,4。思路是将intervals按照首元素递增排列，可以借用sort实现。其次是合并逻辑，记录一个start和end。end是不确定的，只要end小与下一个start的时候，才将start，end存起来。整个思路如下

  1. 对输入的区间数组intervals按照区间的起始位置进行排序。
  2. 初始化start和end为排序后第一个区间的起始和结束位置。
  3. 遍历排序后的区间数组，从第二个区间开始，判断当前区间是否与前一个区间重叠。
  4. 如果重叠，更新end为当前区间和前一个区间结束位置的最大值。
  5. 如果不重叠，将前一个区间添加到结果数组res，并更新start和end为当前区间的起始和结束位置。
  6. 遍历结束后，将最后一个区间添加到结果数组。
  1. var merge = function (intervals) {
  2.     let res = []; // 存储最终合并后的区间
  3.     intervals.sort((a, b) => a[0] - b[0]); // 对区间数组按区间的起始位置进行升序排序
  4.     let [start, end] = intervals[0]; // 初始化start和end为第一个区间的起始和结束位置
  5.  
  6.     // 从第二个区间开始遍历
  7.     for (let i = 1; i < intervals.length; i++) {
  8.         const [curStart, curEnd] = intervals[i]; // 获取当前区间的起始和结束位置
  9.         if (end >= curStart) { // 如果当前区间的起始位置小于等于上一个区间的结束位置，说明存在重叠
  10.             end = Math.max(end, curEnd); // 更新结束位置为两个区间结束位置的最大值
  11.         } else { // 如果没有重叠，将上一个区间添加到结果数组
  12.             res.push([start, end]);
  13.             start = curStart; // 更新start和end为当前区间的起始和结束位置
  14.             end = curEnd;
  15.         }
  16.     }
  17.  
  18.     // 添加最后一个区间到结果数组
  19.     res.push([start, end]);
  20.     return res;
  21. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/799646
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号