26. 删除有序数组中的重复项
题目描述
给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过: 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。
来源:力扣(LeetCode) 原题链接
问题分析
这个问题可以用一个简单的双指针解决。首先定义fast、slow指针,slow指向数组第一个元素,fast指向数组第二个元素。接下来fast指针在for循环中遍历数组。当fast指针指向的数与slow指针不相同时,slow指针便向右移动一位,此时slow指针指向的值被更新为fast指针所指向的值。但倘若fast与slow指向相同的数时,slow指针便不动,fast指针继续遍历直到遍历到不同的数。在遇到第一个不同的数之后,执行先前的操作:slow指针向后移动一位,其指向的值变为fast指针所指向的不同的数。一直这样下去,直到fast指针将数组遍历完。此时数组的有效长度为slow + 1,因为fast的初始值是1,遍历次数只有nums.size() - 1
次。当数组的长度为0或1时,直接返回它本身的长度即可。
代码实现
283. 移动零
题目描述
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。
来源:力扣(LeetCode) 原题链接
问题分析 / 实现思路
初始化i,j指针,i指针为快指针,从头到尾遍历数组中的所有元素。快指针在遍历过程中,如果遇到的数不为0,那么慢指针随其一同向右移一位;如果遇到了0,快指针继续遍历但慢指针将留在原地。也就是说,我们用快指针遍历到的所有非零数都通过慢指针赋予给数组元素。遍历到最后,j的值便是非零元素的个数,数组的前j项便是其去除了所有0项的结果。此时我们将数组后面剩下的元素都赋值为0即可。
代码实现
844. 比较含退格的字符串
题目描述
给定 s 和 t 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true 。# 代表退格字符。 注意:如果对空文本输入退格字符,文本继续为空。 来源:力扣(LeetCode) 原题链接
使用栈的解法
由于栈的先进后出性质,用栈解本题十分方便。我们只需从前往后遍历,在遍历到的字符不为"#"时令其入栈,遇到"#"时令栈最上端的元素出栈,最后判断两个栈是否相等即可。但由于使用了栈,占用了额外空间,所以空间复杂度为O(n)。 注:此处并不一定要用c++的栈,可以使用字符串来模拟栈。因为最终两者比较时字符串更加方便。另外,由于#号可能在栈空的情况下出现,我们必须判断,并在栈非空的情况下pop_back。
双指针解法
本题可用快慢指针解决。《代码随想录》提供了另外一种双指针的解法——但理解上可能稍有困难,在文末会附上相关链接。快慢指针的思路是,将fast和slow指针指向数组的首端,fast开始遍历数组。当fast指针指向的元素不为#时,便更新slow指针所指向的值,并将slow指针右移一位;fast指针指向#时,slow指针便向左移动一位,指向的元素便是需要退格的元素。这里注意,因为#在索引为0的情况下是不需要操作的,所以需要判断条件else if (slow != 0)
。
关于为什么slow指针此时指向的元素为需要被退格的元素:例如,数组总共有8个元素,在数组索引为3处有退格符。那么索引等于2的元素需要被退格。我们的快慢指针从索引0开始遍历,在遇到#前慢指针都是跟着快指针走。但当快指针指向#,也就是索引为3时,慢指针从3回退到2,循环继续。在下一个循环中,由于快指针右移,指向了索引为4的元素,慢指针指向的值便被更新为了该元素。也就是说,处于慢指针与快指针中间的元素此时均被忽略,索引为4的元素替代了索引为2的元素。以此类推,而在最后结束时,我们可以将数组resize为慢指针的大小,也就是此时数组的有效长度。
以下是《代码随想录》中提供的解法:
当然还可以有使用 O(1) 的空间复杂度来解决该问题。
同时从后向前遍历S和T(i初始为S末尾,j初始为T末尾),记录#的数量,模拟消除的操作,如果#用完了,就开始比较S[i]和S[j]。
如果S[i]和S[j]不相同返回false,如果有一个指针(i或者j)先走到的字符串头部位置,也返回false。
代码如下:
class Solution { public: bool backspaceCompare(string S, string T) { int sSkipNum = 0; // 记录S的#数量 int tSkipNum = 0; // 记录T的#数量 int i = S.size() - 1; int j = T.size() - 1; while (1) { while (i >= 0) { // 从后向前,消除S的# if (S[i] == '#') sSkipNum++; else { if (sSkipNum > 0) sSkipNum--; else break; } i--; } while (j >= 0) { // 从后向前,消除T的# if (T[j] == '#') tSkipNum++; else { if (tSkipNum > 0) tSkipNum--; else break; } j--; } // 后半部分#消除完了,接下来比较S[i] != T[j] if (i < 0 || j < 0) break; // S 或者T 遍历到头了 if (S[i] != T[j]) return false; i--;j--; } // 说明S和T同时遍历完毕 if (i == -1 && j == -1) return true; return false; } };
时间复杂度:O(n + m)
空间复杂度:O(1)
977. 有序数组的平方
题目描述
给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
来源:力扣(LeetCode) 原题链接
排序解法
一般的思路是将该数组全部取绝对值然后排序并平方。不过由于排序的时间复杂度平均为O(nlogn),不符合题目要求的O(n) ,故应用双指针解决。
双指针解法
上文解法忽略了题目所给的条件——原数组nums已按照升序排列。利用好这一点将大大优化时间复杂度。由于原数组中含有正负数,也就是说,平方后最大的数在数组的左右两端,越往数组中间靠近,那么该数平方后的值就越小。利用这个性质,我们可以定义左右指针,一个指向数组最左端,一个指向数组最右端。每次循环时,我们比较左指针与右指针所指向的数字的平方,将较大的那个数放在res(答案数组)的最左端(这一点比较好实现,因为答案数组与nums是等长的)。当该指针指向的数的平方被放入答案数组后,我们就能将该指针右移(左移)一位,在下一次循环中继续比较。在循环执行n次后,我们便得到了一个排好序的res数组,时间复杂度为O(n)。