🔥 LeetCode 热题 HOT 100

未完善…

1. 两数之和 LeetCode1 Easy *

题目

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?

思路一

通过双重循环,暴力枚举每一种组合,再通过判断语句,如果两数满足和为target,则返回它们的数组下标。

注意

因为题目要求元素在答案里不能重复出现,且可以按任何顺序返回答案,所以部分组合已经遍历过,无需重复遍历。

思路二

利用哈希表,运用Array的some()方法进行处理,将每个元素的值和它的索引加到表中,检查每个元素所对应的目标元素(target - nums[i])是否存在于表中。

注意

判断成立的条件应为typeof lookup[target - v] ==="number",如果为lookup[target - v]在下标为0时会判断错误。

2. 两数相加 LeetCode2 Medium *

题目

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

思路一

由于输入的两个链表都是逆序存储数字的位数的,因此两个链表中同一位置的数字可以直接相加。我们同时遍历两个链表,逐位计算它们的和,并与当前位置的进位值相加。

注意

注意需要保存进位值用于下一位相加,另外当链表遍历完时,如果进位值大于0,应再加一个结点存储进位值

思路二

将输入的链表转换为逆序的字符串(字符串可以更容易的取出每一位数,无论是正序取出还是逆序取出),再将字符串转换为数(可以考虑使用BigInt,确保精度),然后将两个链表转换的数相加,再转换为字符串,然后逆序放入新的链表。

3. 无重复字符的最长子串 LeetCode3 Medium *

题目

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

思路一

初始化一个数组和最大值, 从前向后遍历字符串, 如果该字符不在数组中(使用Array的indexOf()方法进行判断),则把字符 push 到数组中,并且比较记录下当前最大值。 否则就从头部向外shift字符直到该重复字符被移除(也可以使用slice()方法直接截断数组,a.slice(a.indexOf(s[i])+1,i+1)), 如此循环直到结束。

思路二

通过for (char of s){}遍历字符串,记录当前正在遍历的不重复字串的子集 string , 在遍历过程中不断地添加不重复字符,遇到重复字符则截断 string 达到 string 内补字符不重复的条件。

4. 寻找两个正序数组的中位数 LeetCode4 Hard

题目

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n))

5. 最长回文子串 LeetCode5 Medium *

题目

给你一个字符串 s,找到 s 中最长的回文子串。

思路一

暴力解法。用三个嵌套的for循环,列举所有的子串并判断其是否为回文子串,每次判断后记录此子串并与前一次的子串进行长度比较选取较大的子串。

思路二

中心扩展。回文子串一定是对称的,所以我们可以每次选择一个中心,然后从中心向两边扩展判断左右字符是否相等。 中心点的选取有两种情况: 当长度为奇数时,以单个字符为中心; 当长度为偶数时,以两个字符之间的空隙为中心。

注意

String的slice方法,s.slice(++i,j)在执行时第一个参数为i而非i+1,应写为++i。

思路三

动态规划。动态规划算法的核心就是记住已经解决过的子问题的解。根据字符串的长度,建立一个矩阵 dp, 通过不同情况的判断条件,通过 dp[i][j]表示 s[i] 至 s[j] 所代 表的子串是否是回文子串。不同长度的子串,根据不同的条件进行判断是否为回文子串。长度为 1,一定回文 ;长度为 2 或 3,判断首尾是否相同:s[i] === s[j] ;长度 > 3, 首尾字符相同,且去掉首尾之后的子串仍为回文。

注意

使用双层for循环遍历时,注意外层表示长度,内层表示字符串的开始位置。如果外层表示开始位置,内层表示长度,则在长度>3时判断去掉首尾之后的子串是否为回文会有误。

6. 正则表达式匹配 LeetCode10 Hard

题目

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

  • ‘.’ 匹配任意单个字符
  • ‘*’ 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

7. 盛最多水的容器 LeetCode11 Medium

题目

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

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

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

说明:你不能倾斜容器。

思路一

双指针解法。开始双指针指向数组的左右边界,然后每次移动较小高度的那一边,因为移动会减小宽度,又因面积受限于较短边,如果移动较高的那一边那么只会减小宽度而高度不可能会增加。另外其实可以在每次移动后对移动后的边的高度与未移动之前的高度进行比较,如果高度减小则可以不对当前移动进行面积计算,因为移动后宽度减小,而如果移动的边高度减小,那么面积只可能减小。

思路二

双for循环,但是时间会超时,不做详解。

8. 三数之和 LeetCode15 Medium *

题目

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

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

思路一

首先对数组进行排序,便于在插入的时候去重,进行双指针遍历时,遇到重复的数就方便跳过。设两个指针指向数组首尾,每次计算两个指针所指数与每次遍历的数三数之和,因为数组已经从小到大排序了,所以如果三数之和大于0则尾指针前移,小于0则首指针后移,如果等于0则添加此组合,并进行去重。

注意

在数组中因避免这种写法:while(left<right&&r===nums[right-1]){right–;},在加粗出容易超出边界。

思路二

三重循环,但是时间会超时,不做详解。

9. 电话号码的字母组合 LeetCode17 Medium *

题目

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

思路一

利用队列的先进先出的特点,把队列中的第一个元素拿出,再与后面的挨个拼接

  1. 先在队列中插入一个空字符
  2. 取出队列中的第一个元素,与后一位数字对应的字符进行挨个拼接 。
  3. 重复第二步,直到结束。

注意

let a = [1, 2, 3];

let b = a;

let c = a;

此代码中a,b,c仍然是同一个地址

思路二

回溯。可以穷举所有的可能性,找到所有的可能性。回溯过程中维护一个字符串,表示已有的字母排列。 如果有数字需要被输入,就遍历数字对应的字母进行组合 。 当发现没有数字输入时,说明已经走完了,得到结果。

10. 删除链表的倒数第 N 个结点 LeetCode19 Medium *

题目

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

进阶:你能尝试使用一趟扫描实现吗?

思路一

双指针法。先设first和second指向head,让first 指针前进 n,如果 first为空,说明要删除的节点正是 head 节点,那么直接返回 head 的下一个节点。如果不为空,则让让 second 从 head 开始和 first 一起前进,直到 first 到了最后,此时 second 的下一个节点就是要删除的节点,做出 second.next = second.next.next处理。

注意

注意first为空时的处理,还有second.next = second.next.next这一步,而不是second.next=first,这仅适用于n为2时。

思路二

单向链表成为双向链表。先遍历,让单向链表成为双向链表,先找到其尾节点,从这个节点向前查找,n–,直到n=1时,此时的节点就是我们要找的节点,然后直接删除。

11 有效的括号 LeetCode20 Easy *

题目

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

思路一

利用头插法建立链栈,如果使用尾插法建立则不易删除节点(即出栈操作)。在遇到左括号的时候,将其入栈。在遇到右括号的时候,刚好就可以与栈中的左括号进行匹配,如果正确,就把左括号出栈 。 如果最终栈为空,说明全部匹配成功。

注意

注意JS的垃圾回收机制。在链表中:

let a = new ListNode(1);

let b = a;

a = null;

b仍然指向新建的空间,不为空。

另外需要使用头插法建立链表。

思路二

用 Map 数据类型,建立数组栈。在遇到左括号的时候,将其入栈。在遇到右括号的时候,刚好就可以与栈中的左括号进行匹配,如果正确,就把左括号出栈 。 如果最终栈为空,说明全部匹配成功。

12 合并两个有序链表 LeetCode21 Easy *

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路一

创建一个新链表,通过判断两个链表当前值,将较小值放到新链表的下个节点,较小值的链表重新赋值为其下一节点,直到参数链表都为空时结束。

思路二

用递归的方式, 若两个链表中有一个链表为空,则返回另一个链表,依次比较两个链表中首项的大小,保留数值小的为链表当前值,直到一个链表参数为空则结束。

13 括号生成 LeetCode22 Medium *

题目

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

思路一

采用回溯法,如果自定义的字符串长度刚好满足条件,那么就说明这个组合是正确的的,把它放入数组。 否则,递归执行添加左括号,添加右括号的操作。递归结束条件为结果字符串长度等于左右括号的总个数(2n),则返回最终结果。

14 合并K个升序链表 LeetCode23 Hard

题目

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

15 下一个排列 LeetCode31 Medium

题目

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。

例如,arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地,arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ,找出 nums 的下一个排列。

必须 原地 修改,只允许使用额外常数空间。

思路一

从后向前查找第一个相邻升序的元素对 (i,j),满足 A[i] < A[j]。此时 [j,end) 必然是降序,在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」,将 A[i] 与 A[k] 交换,可以断定这时 [j,end) 必然是降序,逆置 [j,end),使其升序.

注意

注意题目要求中的必须原地修改,不能使用splice()截取再使用concat()合并。另外需要注意sort()默认是字典排序( 例如:9>19)。

16 最长有效括号 LeetCode32 Hard

题目

给你一个只包含 '('')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

17. 搜索旋转排序数组 LeetCode33 Medium *

题目

整数数组 nums 按升序排列,数组中的值 互不相同 。

在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

思路一

先用Math.min.apply(null, nums)Math.max.apply(null, nums)计算数组中的最大最小值。当目标值大于数组最后一位时,数组查询位置从 0 到数字中在最大位置,当目标值小于等于数组最后一位时,数组查询位置从数组中最小值的位置开始,到数组的最后一 位。 循环二分查询,计算定位数组的中间值,数组的值等于目标查询结束。

注意

此方法时间复杂度不为 O(log n),因为求了最大值与最小值。

思路二

定义左右值分别为数组第一个和最后一个的下标 ,中间下标值为最大最小值的平均数 ,如果数组中间数等于目标直接返回下标 。数组的中间值小于数组最后一个值,后半部分还处于升序,如果目标值在这部分数组中,则左下标等于中间值+1,代表目标值在后半部分数组,反之重新定义右下标为中间值-1,目标在前半数组。 数组中间值大于数组最后一个值,代表前半部分数组处于升序,如果目标在前半数组中,右标 更新为中间值-1,反之,左下标更新为中间值+1。循环二分查询,计算定位数组的中间值,数组的值等于目标查询结束。

注意

二分查找主要是同过目标值与中间值进行比较,从而直接确定目标值在哪一部分。如果不是升序或降序数组,则需要进一步确定目标值位置。

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

题目

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

思路一

二分查找,找到左边第一个不小于目标值的位置 ,然后从位置开始到最后,二分查找,确定右边最后一个符合条件值的位置 ,最后校验下标是否符合,得到结果。

19. 组合总和 LeetCode39 Medium

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

思路一

回溯算法。递归的终止条件为已经找到一组数和为目标值或者数组中的数被全部遍历完。在每次递归中,我们可以选择跳过不用当前数,即搜索下标+1。也可以选择使用当前数,目标值减去当前数。因为到每个数字可以被无限制重复选取,因此搜索的下标不变。

20. 接雨水 LeetCode42 Hard

题目

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

21. 全排列 LeetCode46 Medium *

题目

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路一

回溯法.构造一颗生成树,遍历需要全排列的数组,将不同位置的数字与目前树结合起来 ,重复该操作直到需要全排列的数组长度为 0,即表明完成了全排列,因为数字不能重复,所以在每次遍历后应对数组做出处理,之后传入剩余的数组。

注意

在递归中应注意不要使用数组的push()方法,最好使用扩展运算符。

思路二

插值排列法。遍历需要全排列的数组,将不同位置的数字抽离出来,插入到剩余数组的不同位置,即可得到该数字与另一个数组的全排列结果。 将一个固定的数字,插入到另一个数组 的全排列结果的不同位置, 遍历需要全排列的数组,将不同的数字连接到不同的树上继续全排列剩下的数组与生成的树,当剩余数组长度为0时,表明完成了全排列。

22. 旋转图像 LeetCode48 Medium *

题目

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

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

思路一

先将矩阵沿左上角到右下角的对角线进行对称,运用for双层循环,内层循环的计数值的初始值为外层循环的计数值,然后将矩阵沿垂直中线对称即可。运用for双层循环,内层循环计数值小于Math.floor(n / 2),n为矩阵长度。

注意

注意两个for双层循环的内层循环计数值的初始值即范围。

23. 字母异位词分组 LeetCode49 Medium *

题目

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。

思路一

排序分类。先创建个空对象,用于储存字母异位词,然后创建个空数组,用与返回结果。遍历数组里的元素,将每个字母异位词进行排序,并将排序后的字符串作为 key,可知 key 值一样的即为字母异位 词,将他们置于同一个数组中, 待上述遍历结束,再遍历对象,将 对象的每一个值,push 到数组中。

思路二

计数分类。和思路一的不同在于判断两个字符串是否为字母异位词的方法不同。我们先遍历数组,每次都创建一个长度为 26,元素全是 0 的数组,用于记录每个单词中每个字符出现的次数;然后将其转化为字符串作为 key,将 key 值一样的字母异位词置于同一个数组中。最 后返回数组。

注意

数组间不能直接判断是否相同,可以运用JSON.stringify()转换数组为字符串进行判断。

24. 最大子数组和 LeetCode53 Medium *

题目

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。

思路一

从数组获取第一个值为最大值和中间值 ,遍历数组,如果中间值大于0,则和中间值相加,相加结果和最大值比较,较大值赋值给最大值。如果中间值小于0,则将当前值作为中间值。

思路二

分治方法。运用递归,每次求得左右两半部分各自最大子数组和,然后处理两个部分一起的最大子数组和。递归结束条件为左右下标相等。

25. 跳跃游戏 LeetCode55 Medium *

题目

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

思路一

贪心。先初始化最远位置为0,然后遍历数组,如果当前位置能到达,并且当前位置+跳数>最远位置,就更新最远位置, 每次循环都比较当前最远位置和当前数组下标,如果最远距离小于等于当前下标就返回false。

思路二

动态规划。遍历数组,每到一个点 ,我们就去判断是否可以到达当前点;如果可以,就记录true,否则为 false,最后判断是否可以到达最后一个点。

26. 合并区间 LeetCode56 Medium *

题目

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

思路一

先将列表中的区间按照左端点升序排序。定义一个新的数组,用于存储新的数组区间,新数组的第一个值为原数组的第一个值。然后从第二个值开始遍历原数组,比较当前区间的最小值是否大于新数组最后一个区间的最大值, 如果满足则push进入新的数组;又或者比较当前区间的最大值是否大于新新数组的随后一个区间的最大值,若满足则将新数组的最后一个区间的最大值替换成当前区间的最大值。

注意

要先进行原数组排序操作,可以降低做题难度。

27. 不同路径 LeetCode62 Medium *

题目

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

思路一

动态规划。利用双层for循环,状态转移方程为 dp[i][j] = dp[i − 1][j] + dp[i][j − 1]。

思路二

深度优先搜索+记忆化数组。dfs[i][j] = dfs[i − 1][j] + dfs[i][j − 1]。开辟一个记忆数组记录结果。

思路三

组合数学。从左上角到右下角的过程中,我们需要移动 m+n-2 次,其中有 m-1次向下移动,n-1次向右移动。因此路径的总数,就等于从 m+n-2次移动中选择 m-1次向下移动的方案数。

28. 最小路径和 LeetCode64 Medium

题目

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

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

思路一

动态规划。创建二维数组dp[i][j],与原始网格的大小相同,dp[i][j]表示从左上角出发到 (i,j)(i,j) 位置的最小路径和。元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。最后得到dp[m-1][n-1]即为从网格左上角到网格右下角的最小路径和。

29. 爬楼梯 LeetCode70 Easy *

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 12 个台阶。你有多少种不同的方法可以爬到楼顶呢?

思路一

递归+记忆化数组。递归函数:f(n) = f(n − 1) + f(n − 2),创建一个记忆化数组,记录楼层计算过的结果,降低时间复杂度。

思路二

动态规划+滚动数组。f(n) = f(n − 1) + f(n − 2)。但是由于这里的f(n)只和 f(n - 1) 与 f(n - 2)有关,所以可以用滚动数组思想.

30. 编辑距离 LeetCode72 Hard

题目

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

插入一个字符
删除一个字符
替换一个字符

31. 颜色分类 LeetCode75 Medium *

题目

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

进阶:

  • 你可以不使用代码库中的排序函数来解决这道题吗?
  • 你能想出一个仅使用常数空间的一趟扫描算法吗?

思路一

双指针遍历.设定一头一尾两个指针 begin 和 end,然后利用for循环从头开始遍历数组。如果遇到 0,则将该数值与begin指向的值交换,并且使begin++。 如果遇到 2,则将该数值与end指向的值交换,并且使end–。 如果遇到 1,则不做操作。

32. 最小覆盖子串 LeetCode76 Hard

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。

注意:

对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。

进阶:你能设计一个在 o(n) 时间内解决此问题的算法吗?

33. 子集 LeetCode78 Medium

题目

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

进阶:

  • 你可以不使用代码库中的排序函数来解决这道题吗?
  • 你能想出一个仅使用常数空间的一趟扫描算法吗?

思路一

双指针遍历.设定一头一尾两个指针 begin 和 end,然后利用for循环从头开始遍历数组。如果遇到 0,则将该数值与begin指向的值交换,并且使begin++。 如果遇到 2,则将该数值与end指向的值交换,并且使end–。 如果遇到 1,则不做操作。