array reflections

·data-structure-and-algorithm
#array

704.二分查找

题目：https://leetcode.cn/problems/binary-search/description/

我的解答

这道题主要是对二分查找概念的检验，以及如何在 cpp 中实现二分查找算法，通过将基本想法转化一下可得下面的细分步骤：

  • 创建 left、right 变量用于记录数组起始和结束位置

    • left 初始为 0

    • right 初始为数组长度减一

  • 利用 while 循环，仅当 left <= right 时才进入

    • 这里考虑使用左闭右闭区间，即 [left, right]，当 left=right 时，这个区间也是合法的，且该区间内仍有一个元素，仍需要判断这个元素是否跟目标值相等

    • 所以才是 <= 而不是 < ，后面的 left 和 right 才会有对应的加和减

  • 在循环中，创建 middle 变量用于记录数组中位数位置

    • (right - left) / 2 代表的是偏移量，需要加上起始位置 left 才是数组中的正确下标

  • 通过 if 条件判断，分别比较中位数和目标数的大小和是否相等

核心思想还是在于循环的构建和 left、right 变量的移动，这一点在后面几道应用二分查找的题目中更能体现

27.移除元素

题目：https://leetcode.cn/problems/remove-element/description/

我的解答

原地：其实就是保留原数组，对原数组进行一系列的操作，而不是重新创建一个新数组

这题的暴力解法是直接用两个 for 循环，但这里我们就不讨论了（因为我自己没有尝试过），我们这里可以采用时间复杂度更优秀的双指针法 - 快慢指针解决这题，分析如下：

  • 创建一个慢指针和一个快指针（快指针在 for 循环里创建）

  • 创建一个 for 循环，利用快指针遍历数组

  • 循环中使用 if 语句，逐个判断数组中是否存在需要删除的数

    • 如果不存在，则直接将此时快指针对应数组中的值赋给慢指针对应数组中的值，并将 slow 指针右移

  • 返回 slow 指针

最后返回 slow 指针，其实就是相当于返回一个“虚假”的数组元素个数

因为这里的 slow 其实并不代表整个 nums 数组的元素个数，因为我们仅仅只是将那个需要删除的元素覆盖了，而数组原本最后一个元素其实并没有改变

977.有序数组的平方

题目：https://leetcode.cn/problems/squares-of-a-sorted-array/description/

我的解答

这题的暴力解法还是直接对每个数平方（利用 *=），平方完之后再直接用 sort 算法排序，但双指针法 - 左右指针可以优化时间复杂度，分析如下：

  • 由于数组是按照非递减顺序排序的，所以很有可能最左边的负数平方之后反而比右边最大的正数平方之后还要大，于是我们可以考虑用两个指针（一左一右）来遍历整个数组并比较

  • 我们可以使用一个新的数组来保存比较结果，从而实现新数组的排序

  • 利用一个 while 循环，将左边元素的平方和右边元素的平方进行比较，赋值，并移动指针

这道题我还是想多讲讲我是怎么错的，因为我死磕这道题磕了很久都没磕出来（不应该这样的，还是要早点看答案，不要钻牛角尖）

  • 一开始，我是想着直接平方完之后，相邻元素对比，但好像写成冒泡排序（但又不是完整的冒泡排序）之类的四不像了，这就导致想的很好，但却让int溢出了

  • 然后就很想当然地换了一种写法，但根本没有意识到数组原本顺序的前提，既让数据覆盖出现了问题，又没有排序

  • 接着又听劝尝试了重新搞个数组，但再次没有意识到数组原本顺序，导致排序错误

这道题也是折磨了很久gpt才最后做出来的哈哈哈，说白了还是，就，明明有一种更方便、更快速的方式能使用，真的没必要非要钻牛角尖，这道题实际想过之后会发现双指针法并不一定是一个快一个慢，也可以一左一右，遍历的方式有很多，要灵活运用

209. 长度最小的子数组

题目：https://leetcode.cn/problems/minimum-size-subarray-sum/description/

我的解答

这题的暴力解法是两个 for 循环嵌套，通过穷举来求子数组，但实际上我们可以使用双指针法 - 滑动窗口来解决这道题目，从而优化时间复杂度

  • 快慢指针都从初始位置开始，通过遍历整个数组来寻找子数组

  • 快指针先走，让将原数组元素一个个加到 sum 变量中

  • 再用 sum 和 target 比较，来缩短放到 sum 里元素的长度，从而形成滑动窗口

  • 在缩短窗口长度时要使用长度变量来实现每次符合条件的长度都能和之前符合条件的长度进行比较，只保留最小的

注意事项：

  • 题干已经默认和暗示这里的子数组必须是原数组中连续的元素组成的，排除了跳跃元素组成子数组的情况，所以才能用滑动窗口

  • 暴力解法的时间复杂度是 O(n^2) 是因为每个外层循环中的 i 都会让内层循环完全遍历一次数组，所以是从 i=0 开始就遍历 n 遍，一直到 i=n 一共遍历了 n 次，所以才是 n * n

  • 而滑动窗口则是，外层循环会遍历一次数组来扩大窗口，并且也只会让内层循环遍历一次数组来缩小窗口，所以其实是 n + n，时间复杂度还是 O(n)，不要看到两个循环嵌套就认为时间复杂度是 O(n^2)，要自己实际分析元素被操作的次数

59. 螺旋矩阵Ⅱ

题目：https://leetcode.cn/problems/spiral-matrix-ii/

我的解答

这题一般的解法是直接模拟，但我对其涉及到的边界判断和重复工作感到不适，所以通过 gpt 学到了另一种建模索引的方法，个人感觉写起来会更舒服一些

  • 初始化数据结构，使用 pair 和二维的 vector，比较考验对代码的掌控能力，前者主要是为了建模出右、下、左、上四个方向向量方便我们循环使用，后者是为了存储我们的螺旋矩阵

  • 用一个索引变量来轮流拿四个移动方向向量，将矩阵初始化为 0 来方便判断下一个位置是否有被填过

  • 再用 x、y 以及 nextX、nextY 变量来便于我们进行移动

  • 在循环中，当前的位置被填完之后，先计算下一步，然后再进行边界和是否已填充的判断，这里的判断是可复用的

    • 如果发现下一步越界了，就通过调整索引变量的值来自动切换方向，否则就继续往该方向走，实现了自动拐弯

    • 只要跑满了 n * n 次，矩阵就会自动被填满

注意事项：

  • 利用二维数组存储矩阵，需要捋清楚初始化逻辑

  • 利用 pair 类型初始化 vector

  • 通过 % 取余符来约束方向索引变量的值

螺旋的核心就是保持一种“优先往前走，不通就拐弯”的策略，并且“拐弯”后依然在四个固定方向之间依次切换，这样一步步走完，就会在矩阵里留下从外到内、顺时针的螺旋路径

以下为补充题，刷完代码随想录和 hot100 后会重新整理

35.搜索插入位置

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

我的解答

这道题其实是上一道题的变形，跟上一题基本完全一样，不一样的地方在于需要找到是什么代表了按顺序插入的位置，我们可以进行以下分析：

  • 在二分查找过程中，left和right代表的是查找范围的左边界和右边界，并随着查找的推进不断更新

  • 当left大于right时，二分查找自然退出，此时我们留意left停留的位置，刚好停在第一个大于target的元素的位置，否则二分查找无法退出

  • 也就是说，在一般情况下，left停留的位置刚好就是target应该插入的位置（如果target不在数组中的话）

  • 在边界情况下，比如target比数组中所有元素都大或者都小，left也会分别停留在数组的末尾或者初始位置，也仍然是target应该插入的位置

  • 如果使用right则会导致插入位置偏左

  • 如果使用right + 1也可以，因为left本身就等于right + 1，可以验证端点情况也是符合的，只是会出现负数

这道题其实不难，重点还是在如何对于按顺序插入target的位置的寻找；马后炮地说，其实在二分查找中一共就三个位置变量，left、right、middle，即使一开始没思路，也可以聚焦与这三个位置变量的变化情况，本质上考察的还是对于二分查找是否足够熟悉或深入；该算法的时间复杂度：O(log n)，空间复杂度：O(1)

需要注意的是，left和right变量要在while循环外面创建并初始化为0，而middle变量则需要在while循环里面创建并初始化，这是因为left和right变量在while中会不断被更新，所以我们不能把它们放到循环内，否则会导致重复的初始化，进而导致了无限循环，而middle变量则是循环每次开始时都会被更新的，自然也不能被放在循环外面，否则二分查找是无法正常进行的，这两个错误我在写的时候都犯了，我一开始把三个变量全放在了循环里面，然后修改了一下，结果又把三个变量全放在了循环外面🤣，写代码的时候脑子一定要清晰才行！！

34.在排序数组中查找元素的第一个和最后一个位置

题目：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

我的解答

非递减顺序：意味着数组中元素值不会递减，简单来说就是递增或持平，所以可以将它理解为递增顺序，只是可能包含相同的元素

这道题可以说是二分查找的升级版，因为现在数组中出现了重复的元素，这就导致二分查找的难度大大增加，作为初学者（相信上面那题的注意事项已经让你相信了我是一个彻底的初学者），我们可以考虑使用两个二分查找来分别找到重复元素的左边界和右边界（题目已经假设所有相同元素都是相邻的），下面是分析过程：

  • 写两个函数，分别代表两次二分查找，第一次二分查找找到左边界，第二次二分查找找到右边界

  • 再用另一个主函数来调用这两个函数，并创建两个变量来记录两个二分查找函数的返回值，最终返回一个区间

  • 查找左边界的函数（返回值应当是int类型）

    • 创建left、right、leftBoundary变量，将leftBoundary初始化为-1，方便记录如果数组中不存在目标值的情况

    • 创建一个while循环，创建middle变量，进入二分查找

    • 如果middle < target，说明目标数在更大的右半边，我们需要更新left变量

    • 如果middle >= target，说明目标数在更小的左半边，我们需要更新right变量

      • 如果middle = target，则说明找到了重复的目标值之一，于是我们将middle赋给leftBoundary

      • 但二分查找仍需要继续，继续寻找此时middle的左边是否仍有相同的元素，因为我们并不确定这个位置就是最左位置，而这将通过while循环实现，直到left大于right，循环才会退出，此时我们才找到了左边界

      • 所以，无论是小于还是等于，我们都要更新right变量，以便检查左边部分，最终leftBoundary会停留在最左边的target位置上

  • 查找右边界的函数同理，只要更改一下if判断的条件即可，不再重复叙述

  • 主函数

    • 创建左右边界变量，接收两个函数的值

    • 如果两个变量的值有一个为-1， 说明目标数不在数组中，直接返回两个-1

    • 最终返回两个边界值

这道题是中等难度类型的题目，但逻辑其实不算特别复杂，只是我们这种初学者没有见过这样的题目，容易没有思路，或者自己把自己绕进去，据说这题的代码简洁度还有很大的提升空间，但我想这并不是现阶段的我们需要留意的；该题的时间复杂度仍为O(log n)，空间复杂度仍为O(1)

其实一开始我是想写两个while循环嵌套在一起，但这样实在是太混乱了，也很容易造成逻辑错误或者赋值问题，错误代码也可以在我的解答里面找到，但非常不建议模仿，哈哈哈哈哈哈哈

感觉其实写代码就是这样，自己一开始写的可能跟实际正确的代码相差千里，但这并没有什么，真的没关系，因为我们本身就是学习者，我们现在要做的就应该是，读完题目之后大胆地按照自己的想法先写一遍，如果没有思路或者发现写出来的东西无法正确运行，当然可以先思考一下，但千万不要死磕太久，重要的是去看别人正确的代码是怎么写的（比如看题解或者问chatgpt），然后学习正确代码的逻辑和规范，这样我们才能提升效率并且走得更远

69.x的平方根

题目：给你一个非负整数 x ，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去。注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

我的解答

这题一开始很容易没有思路，而且也很难联想到要用二分查找，但其实二分查找可以帮助我们快速找到满足条件的整数，思路如下：

  • 将问题转化为寻找一个mid，使得mid * mid = x，从而求解

  • 需要注意if的条件，当mid <= x / mid时，不但需要修改left边界，也需要更新结果值，这样才能让二分查找继续下去

此题较为简单，但要注意防溢出时，由于使用了除法，可能会带来一些麻烦，比如除0问题和整除问题（这个会在下一题中看到），所以需要注意初始化的情况，或者直接使用long和long long

367.有效的完全平方数

题目：给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。完全平方数是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。不能使用任何内置的库函数，如 sqrt 。

我的解答

这题其实就是上一题的升级版，多了一个需求，但具体实现是差不多的，只是有一些细节要注意，我一开始写的时候遇到了下面几个问题（错误代码也在解答里面）：

  • num小于2时，可以直接返回真，没必要再计算一次平方根了

  • 在我的while循环中，虽然我的操作没问题，也更新了square值，但循环结束后square可能可能只是一个接近平方根的数，而不一定就是num的真正平方根（其实我这里还是受到了前面两题的影响，导致对二分查找的使用有些僵化，但实际二分查找的应用是可以根据需求灵活变化的）

  • 没有考虑到除法引入的精度误差

整体来说这题也不算很难，只是容易陷入思维陷阱，还是要学会变通才行，灵活使用if判断

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

题目：给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持一致 。然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。

我的解答，本题为简单题

这道题其实跟上一题非常像，只是修改了一下需求，上一题是要移除某个特定的元素，这一题是要找到重复的元素并将重复出现的均删掉，只保留一个；我们还是可以使用双指针法，分析如下：

  • 创建快慢指针

  • 仍然使用for循环和if语句，只是判断条件需要改成快指针对应的元素是否跟快指针对应的元素的上一个元素相同（即nums[fast] == nums[fast - 1]）

  • 同样遍历之后返回slow即可

这道题相当于是加深对双指针法的印象，用法跟上一题完全一样，这个判断条件也很容易想到，但上一题能马上想到双指针法是很难的（如果跟我一样做题前没听过双指针法而且也跟我一样恰好不是天才（bushi）的话），我也是看了别人的思路才知道怎么做的

但这题需要注意以下几点：

  1. 在for循环前加入判断数组大小是否为0的语句，增加代码完整性
  2. 由于我们的判断条件牵扯到了fast前面的位置，所以fast不能初始化为0，而应该初始化成1，这样才不会越界
  3. 而考虑到slow和fast一开始应该是同步的，只是fast先右移，所以slow也应该初始化为1，这样这题我们就相当于是从数组的第二个元素（起始索引为0）开始判断是否跟前一个元素相同
  4. 如果采用fast后面的位置，即nums[fast + 1]，那就不用修改初始化的值

我一开始没有注意到这些，导致第一次提交错误了哈哈哈，但没关系，犯错不可怕，只要别重复犯一样的错误就好啦

283.移动零

题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。

我的解答，本题为简单题

这道题一开始容易没思路（比如现在在写记录的我，哈哈哈哈哈），但只要能把双指针法和库函数里面的swap()函数想起来就会发现跟前面两题本质上也是一样滴，分析如下：

  • 同样创建快慢指针和for循环、if语句

  • 如果当前元素不为零，就将快慢指针对应的元素交换，并右移慢指针

这样的话，当fast指针遍历到第一个0时，在下一次第一个不为零的元素时，fast指针就会将0（此时由慢指针指向）跟此时的元素交换，从而达到将0后移

这题本质上还是要求我们对于双指针法的灵活运用，重点还是在于要想到将0后移的方法，我一开始完全想不到该怎么后移，看了答案才恍然大悟——其实简单的交换就可以了（别死磕太久~）