leetcode——移除数组
26.删除有序数组中的重复项
给你一个 非严格递增排列 的数组
nums，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回nums中唯一元素的个数。考虑
nums的唯一元素的数量为k，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。- 返回
k。判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组 int[] expectedNums = [...]; // 长度正确的期望答案 int k = removeDuplicates(nums); // 调用 assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度2，并且原数组 nums 的前两个元素被修改为1,2。不需要考虑数组中超出新长度后面的元素。示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度5， 并且原数组 nums 的前五个元素被修改为0,1,2,3,4。不需要考虑数组中超出新长度后面的元素。提示：
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums已按 非严格递增 排列
原理
初始化两个指针：
left：指向当前有效元素的最后位置，起始值为 0。right：指向当前正在遍历的元素，起始值为 0。遍历整个数组：
- 使用
right指针遍历整个数组。- 如果
nums[left]等于nums[right]，说明nums[right]是一个重复的元素，right指针右移，继续向右遍历。- 如果
nums[left]不等于nums[right]，说明找到了一个新的、未出现过的元素。此时，left指针向右移动，并将nums[right]的值赋给nums[left]。返回数组的有效长度：
- 最后，返回
left + 1，这是新的数组长度，因为left是最后一个有效元素的索引。为什么返回
left + 1：
left指针指向的是数组中唯一元素的最后一个位置，而数组的长度是从 0 开始的，所以最终的长度应该是left + 1。复杂度分析：
时间复杂度：
O(n)，其中 n 是数组的长度。我们只需要一次遍历数组，进行常数时间的操作。空间复杂度：
O(1)，使用了两个指针，额外的空间开销为常数。
代码
class Solution {
public int removeDuplicates(int[] nums) {
// 如果数组为空，直接返回0
if (nums.length == 0) {
return 0;
}
// 初始化两个指针，left 和 right
int left = 0, right = 0;
// 使用 right 指针遍历整个数组
while (right < nums.length) {
// 如果 left 和 right 指向的元素相同，说明 right 指向的元素是重复的，右指针右移
if (nums[left] == nums[right]) {
right++;
} else {
// 如果 left 和 right 指向的元素不相同，说明 nums[right] 是新的元素
left++; // left 向右移动，准备接收新元素
nums[left] = nums[right]; // 将新元素放到 left 后
}
}
// 返回新的数组长度，即 left + 1
return left + 1;
}
}
283.移动零
给定一个数组
nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums =[0,1,0,3,12]输出:[1,3,12,0,0]示例 2:
输入: nums =[0]输出:[0]提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1进阶：你能尽量减少完成的操作次数吗？
原理
初始化指针：
left：指向当前未处理的非零元素的目标位置，起始时指向数组的第一个位置。right：指向当前正在检查的元素，起始时也是指向数组的第一个位置。第一次遍历：
- 在数组中查找第一个
0。一旦找到0，我们初始化left和right指针，且right从当前0开始遍历，left用来标记非零元素将要被移动的位置。- 如果没有找到
0，则left和right都会指向数组的最后一个元素，此时数组中已经没有0，可以直接返回。第二次遍历：
right指针继续向右遍历整个数组。- 如果
right指向的是0，说明当前元素不需要处理，继续向右移动right指针。- 如果
right指向的是非零元素，说明这是一个需要移动的元素。我们将这个元素交换到left指针的位置，并将left向右移动。然后，我们将当前right指向的位置置为0，继续处理下一个元素。最终结果：
- 最终，所有的非零元素都会被移动到数组的前面，所有的
0都会被移动到数组的末尾。复杂度分析：
时间复杂度：
O(n)，其中 n 是数组的长度。我们进行了两次遍历，第一遍是找第一个0，第二遍是对数组进行重排。空间复杂度：
O(1)，我们只使用了常数空间来存储两个指针left和right，没有额外使用其他数据结构。
代码
class Solution {
public void moveZeroes(int[] nums) {
// 如果数组长度为 1，直接返回，因为不存在移动的必要
if (nums.length == 1) {
return;
}
// 初始化两个指针，left 和 right
int left = 0, right = 0;
// 第一次遍历，找到第一个 0，初始化 left 和 right
for (int i = 0; i < nums.length; i++) {
// 如果当前元素是 0，初始化 left 和 right 指针
if (nums[i] == 0) {
left = right = i;
break;
}
left++;
right++;
}
// 如果数组中没有 0，直接返回
if (left == nums.length) {
return;
}
// 第二次遍历，进行移动操作
while (right < nums.length) {
// 如果 right 指向的是 0，继续向右移动
if (nums[right] == 0) {
right++;
}
// 如果 right 指向的是非 0 元素，将该元素移动到 left 位置，并将该位置置为 0
else {
int temp = nums[right]; // 记录非零元素
nums[right] = 0; // 将右边的元素置为 0
nums[left++] = temp; // 将非零元素放到左边的空位上
}
}
}
}
844.比较含退格的字符串
给定
s和t两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回true。#代表退格字符。注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c" 输出：true 解释：s 和 t 都会变成 "ac"。示例 2：
输入：s = "ab##", t = "c#d#" 输出：true 解释：s 和 t 都会变成 ""。示例 3：
输入：s = "a#c", t = "b" 输出：false 解释：s 会变成 "c"，但 t 仍然是 "b"。提示：
1 <= s.length, t.length <= 200s和t只含有小写字母以及字符'#'进阶：
- 你可以用
O(n)的时间复杂度和O(1)的空间复杂度解决该问题吗？
原理
初始化两个指针：
right1和right2分别指向字符串s和t的最后一个字符。它们将用于从右到左遍历字符串。count1和count2用来处理退格符#，即跳过退格符后的字符。遍历字符串：
处理
#退格符：
如果当前字符是#，则意味着我们需要删除一个字符。通过循环，跳过所有连续的#退格符，并且每次遇到#时向左移动指针，直到找到一个有效字符。然后继续比较下一个字符。非
#字符：
如果遇到的不是退格符#，就直接将当前字符移到下一个位置进行比较。结束条件：
- 当
right1和right2都指向有效字符时，检查两个字符是否相等。如果不相等，则返回false。- 当两个字符串都遍历完且没有不匹配的字符时，返回
true。边界情况：
- 如果两个字符串中有退格符导致的空字符，则跳过空字符，继续向左遍历直到遇到有效字符。
复杂度分析：
时间复杂度：
O(n)，其中n是字符串的长度。在最坏情况下，每个字符会被遍历一次。空间复杂度：
O(1)，只使用了常数空间存储指针right1和right2，没有使用额外的空间。
代码
class Solution {
public boolean backspaceCompare(String s, String t) {
// 初始化两个指针，分别指向两个字符串的最后一个字符
int right1 = s.length() - 1, count1 = 0;
int right2 = t.length() - 1, count2 = 0;
// 当两个字符串还有字符待处理时，继续循环
while (right1 >= 0 || right2 >= 0) {
// 处理字符串 s 的当前字符
if (right1 >= 0) {
if (s.charAt(right1) == '#') { // 如果当前字符是退格符 '#'
// 退格符需要跳过一个字符，因此记录 count1
int temp = right1;
right1 -= 2; // 跳过退格符并定位到退格前的位置
count1 = 1;
// 循环跳过所有退格符，并处理被退格删除的字符
while (count1 != 0) {
count1 = 0;
int right11 = right1, temp1 = temp;
for (int i = Math.max(0, right11); i < temp1; i++) {
if (s.charAt(i) == '#') {
right1 -= 2;
if (right1 < 0) {
count1 = 0;
continue;
}
count1++;
}
}
temp = right11;
if (count1 == 0) {
right1--;
}
}
} else {
// 如果当前字符不是 '#', 就直接向左移动
right1--;
}
} else {
right1--; // 确保索引有效
}
// 处理字符串 t 的当前字符
if (right2 >= 0) {
if (t.charAt(right2) == '#') { // 如果当前字符是退格符 '#'
// 退格符需要跳过一个字符，因此记录 count2
int temp = right2;
right2 -= 2; // 跳过退格符并定位到退格前的位置
count2 = 1;
// 循环跳过所有退格符，并处理被退格删除的字符
while (count2 != 0) {
count2 = 0;
int right21 = right2, temp2 = temp;
for (int i = Math.max(0, right21); i < temp2; i++) {
if (t.charAt(i) == '#') {
right2 -= 2;
if (right2 < 0) {
count2 = 0;
continue;
}
count2++;
}
}
temp = right21;
if (count2 == 0) {
right2--;
}
}
} else {
// 如果当前字符不是 '#', 就直接向左移动
right2--;
}
} else {
right2--; // 确保索引有效
}
// 比较两个字符串的当前字符，如果不相等则返回 false
if (right1 < -1 && right2 < -1) {
return true;
} else if (right1 == -1 && right2 < -1) {
return false;
} else if (right1 < -1 && right2 == -1) {
return false;
} else if (right1 >= -1 && right2 < -1) {
return false;
} else if (right2 >= -1 && right1 < -1) {
return false;
} else if (s.charAt(right1 + 1) != t.charAt(right2 + 1)) {
return false;
}
}
return true; // 如果遍历完成都没有不相等的字符，则返回 true
}
}
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] <= 104nums已按 非递减顺序 排序进阶：
- 请你设计时间复杂度为
O(n)的算法解决本问题
原理1
问题分析：
- 给定一个按非递减顺序排列的整数数组
nums，需要返回一个包含每个数字平方的新数组，并且结果数组同样按非递减顺序排列。- 数字的平方后，负数变为正数，因此数组中可能有负数、零和正数。为了有效处理这种情况，考虑使用双指针的方法来同时遍历负数部分和正数部分。
双指针法的思路：
- 使用两个指针，
left和right，分别从数组的两端开始。
left指向数组的负数部分的最后一个元素。right指向数组的非负数部分的第一个元素。- 通过比较
left和right位置的平方值，选择较小的平方值放入结果数组。- 移动相应的指针，继续比较，直到遍历完数组。
处理特殊情况：
- 全部负数： 如果数组的所有元素都是负数，则从数组的末尾开始平方并填充到结果数组中。
- 全部非负数： 如果数组的所有元素都是非负数，则直接平方并填充结果数组。
时间复杂度：
- 由于我们只遍历了一次数组，且每次操作是常数时间，因此时间复杂度是 O(n)，其中
n是数组nums的长度。空间复杂度：
- 我们需要额外创建一个数组
ans用来存储平方后的结果，空间复杂度是 O(n)。
代码1
class Solution {
public int[] sortedSquares(int[] nums) {
// 特殊情况：数组只有一个元素
if (nums.length == 1) {
nums[0] *= nums[0]; // 直接平方并返回
return nums;
}
// 创建一个新的数组用来存储平方后的结果
int[] ans = new int[nums.length];
// 初始化指针，left 指向负数部分的最后一个元素，right 指向非负数部分的第一个元素
int left = 0, right = 0, middle = 0;
// 查找第一个非负数的位置（即 0 或大于 0 的元素）
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= 0) {
right = i; // 记录非负数部分的起始位置
middle = right;
left = middle - 1; // left 右移一位
break; // 找到非负数部分后停止
}
}
int index = 0; // 用于向结果数组中插入元素
// 如果左侧部分全是负数（左指针位于数组开头）
if (left == middle) {
left = nums.length - 1;
// 逆向插入负数平方到结果数组中
for (int i = left; i >= 0; i--) {
ans[index++] = nums[i] * nums[i];
}
return ans;
}
// 如果右侧部分全是正数
if (middle == 0) {
// 直接将平方后的正数按顺序放入结果数组中
for (int i = 0; i < nums.length; i++) {
ans[i] = nums[i] * nums[i];
}
return ans;
}
// 双指针法：从两端开始比较
while (left >= 0 && right < nums.length) {
// 比较绝对值较小的数字，放入结果数组
if (nums[left] * nums[left] < nums[right] * nums[right]) {
ans[index++] = nums[right] * nums[right++]; // 右边的数字平方
} else {
ans[index++] = nums[left] * nums[left--]; // 左边的数字平方
}
}
// 处理剩余的元素：如果左边的数字没有遍历完
if (left < 0 && right < nums.length) {
for (int i = index; i < nums.length; i++) {
ans[i] = nums[right] * nums[right++]; // 右边剩余元素的平方
}
}
// 如果右边的数字没有遍历完
else if (left >= 0 && right >= nums.length) {
for (int i = left; i >= 0; i--) {
ans[index++] = nums[i] * nums[i]; // 左边剩余元素的平方
}
}
return ans; // 返回排序后的平方数组
}
}
提示：可从最左边和最右边比较最大值，然后反向放入数组中，会很好多