参考文章：代码随想录https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
一、题目
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下：
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。
例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。提示：
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= val <= 100
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/remove-element/description/
二、题解
1、暴力解法
最容易想到的就是遍历数组，找到 val 后就删除该元素，只不过数组的删除元素比较麻烦，得用后面的元素不断覆盖前面。
要注意的是，删除一个元素后，遍历范围也应该减 1，并且下标也应该向后移一位
public int removeElement(int[] nums, int val) {
int size = nums.length;
for (int i = 0; i < size; i++) {
// 发现需要移除的元素，就将数组集体向前移动一位
if (nums[i] == val) {
for (int j = i + 1; j < size; j++) {
nums[j - 1] = nums[j];
}
// 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
i--;
// 此时数组的大小-1
size--;
}
}
return size;
}2、双指针法
使用双指针就是为了在一个 for 循环下完成两个 for 循环的工作。
相比于快慢指针，我更愿意称之为读写指针，这样似乎更好理解一点。读指针指向原数组，写指针指向新数组，但这两个数组共用一块内存空间。读指针遍历数组，遇到的元素不为 val 时，则将该元素更新到写指针指向的位置；为 val 时，写指针不动，读指针继续向前。写指针指向的始终是新数组最后一个元素的下一个位置，所以最终读指针遍历完后，写指针的值就是新数组的长度，返回即可。
附上 carl 哥的图示会好理解一点：
public int removeElement(int[] nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
if (nums[fastIndex] != val) {
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
return slowIndex;
}3、相向双指针
为了减少新数组中元素的更新写入次数，可以考虑使用相向双指针。
左边指针从左边开始找等于 val 的元素，右边指针从右边开始找不等于 val 的元素，两边都找到后用右指针指向的值覆盖左指针指向的值。如此循环下去，直到右指针大于左指针。
注意左右指针寻找相应元素的循环条件还是要加上 left <= right，这样才能保证左指针最终指向的是新数组末尾元素的后一位。
这种方法相比于第二种双指针法还有一个区别，就是这种方法改变了元素的相对位置
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
// 找左边等于val的元素
while (left <= right && nums[left] != val) {
left++;
}
// 找右边不等于val的元素
while (left <= right && nums[right] == val) {
right--;
}
// 将右边不等于val的元素覆盖左边等于val的元素
if (left <= right) {
nums[left++] = nums[right--];
}
}
// leftIndex一定指向了最终数组末尾的下一个元素
return left;
}三、相关题目
1、T26 删除有序数组中的重复项
1.1、题目
给你一个 非严格递增排列 的数组 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已按 非严格递增 排列
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
1.2、题解
暴力解法
首先注意数组是有序的，那么重复的元素一定会相邻
因此遍历数组找到两个相等的元素，删除后面的元素即可，其他地方和 T27 类似。
要注意的是本题中两个 for 循环的边界条件都应该是 < size - 1，因为要防止下标 i + 1 和 j + 1 越界
public int removeDuplicates(int[] nums) {
int size = nums.length;
for (int i = 0; i < size - 1; i++) {
if (nums[i] == nums[i + 1]) {
for (int j = i + 1; j < size - 1; j++) {
nums[j] = nums[j + 1];
}
size--;
i--;
}
}
return size;
}双指针方法一
本题的双指针解法和 T27 类似，但是题目要求了不能改变数组元素的相对顺序，所以不能使用相对双指针。
要注意快指针的遍历范围是 [0，length -1），漏掉了数组最后一个元素，所以快指针遍历完后还要再将原数组最后一个元素写入慢指针所指向的新数组的位置。如果原数组最后一个元素和它前面一个元素（也就是倒数第二个元素）相同，由于写入新数组的始终是原数组两个或多个相同元素中位置处于最后面的那一个，所以它应该被写入新数组；如果它和前面一个元素不同，那它就更应该写入新数组
public int removeDuplicates(int[] nums) {
int dest = 0;
int src = 0;
for (; src < nums.length -1; src++) {
if (nums[src] != nums[src + 1]) {
nums[dest++] = nums[src];
}
}
nums[dest++] = nums[src];
return dest;
}双指针方法二
这种解法参考了力扣官方题解，链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/solutions/728105/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-tudo
第一种双指针解法容易漏掉最后一个元素，官方这种解法则规避了这种问题。简单摘抄下官方题解：
数组 nums 的长度大于等于 1，数组中至少包含一个元素，在删除重复元素之后也至少剩下一个元素，因此 nums[0] 保持原状即可，从下标 1 开始删除重复元素。
定义一个快指针 fast 和一个慢指针 slow，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标 1。
遍历结束之后，从 nums[0] 到 nums[slow−1] 的每个元素都不相同且包含原数组中的每个不同的元素，因此新的长度即为 slow，返回 slow 即可。
public int removeDuplicates(int[] nums) {
int dest = 1;
for (int src = 1; src < nums.length; src++) {
if (nums[src] != nums[src - 1]) {
nums[dest++] = nums[src];
}
}
return dest;
}2、T283 移动零
2.1、题目
给定一个数组 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
进阶：你能尽量减少完成的操作次数吗？
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/move-zeroes/description/
2.2、题解
暴力解法
本题可以看作 T27 中的 val 为 0 时的特殊情况，但是为了满足题目要求，删除完为 0 的元素后还要将原数组最后几个元素置为 0，这样才能达到移动零的效果。
public void moveZeroes(int[] nums) {
int size = nums.length;
for (int i = 0; i < size; i++) {
if (nums[i] == 0) {
for (int j = i + 1; j < size; j++) {
nums[j - 1] = nums[j];
}
i--;
size--;
}
}
for (int i = size; i < nums.length; i++) {
nums[i] = 0;
}
}双指针方法一
题目要求保持非零元素的相对顺序，所以本题也是不能使用相向双指针的。
整体和 T27 的双指针法类似，只是最后还要将原数组最后几个元素置为 0。
public void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
nums[slow++] = nums[fast];
}
}
for (int i = slow; i < nums.length; i++) {
nums[i] = 0;
}
}双指针方法二
这种方法参考了 王尼玛的题解 和 力扣官方题解，相比于第一种双指针法，减少了完成的操作次数。
这种方法的核心就是每当快指针指向非零数，则将快慢指针对应的数交换，同时慢指针右移。
用王尼玛大佬的话说，这里参考了快速排序的思想。快速排序是首先要确定一个待分割的元素做中间点 x，然后把所有小于等于 x 的元素放到 x 的左边，大于 x 的元素放到其右边。本题中是以 0 为中间点，把不等于 0 的放到 0 的左边，等于 0 的放到其右边。
附上王尼玛大佬创作的动态图更好理解：
public void moveZeroes(int[] nums) {
int n = nums.length, left = 0, right = 0;
while (right < n) {
if (nums[right] != 0) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
}
right++;
}
}3、T977 有序数组的平方
3.1、题目
给你一个按 非递减顺序 排序的整数数组 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)的算法解决本问题
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/squares-of-a-sorted-array/description/
3.2、题解
暴力解法
最容易想到的方法，先将原数组每个数平方，再对新数组进行排序
public int[] sortedSquares(int[] nums) {
for (int i = 0; i < nums.length; i++) {
nums[i] *= nums[i];
}
Arrays.sort(nums);
return nums;
}双指针法
原数组是个有序数组，有三种情况：全是负数、全是正数、有正有负。
数组 nums 中的所有非负数平方后，非负数部分子数组仍然保持升序；数组 nums 中的所有负数平方后，负数部分子数组会保持降序。
负数平方之后可能成为最大数了，所以不管是哪种情况，元素的平方最大值一定产生在原数组的最左边或者最右边。想到这一点很关键
题目要求新数组仍是非递减顺序，所以我们可以使用两个指针，分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择较大的那个逆序放入新数组（也就是先放入新数组的最后一个位置再依次往前放）并移动指针。
附上 carl 哥的动态图示：
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length - 1;
int[] result = new int[nums.length];
int index = result.length - 1;
while (left <= right) {
//if (nums[left] * nums[left] < nums[right] * nums[right]) {
if (Math.abs(nums[left]) < Math.abs(nums[right])) {
result[index--] = nums[right] * nums[right--];
} else {
result[index--] = nums[left] * nums[left++];
}
}
return result;
}4、T844 比较含退格的字符串
4.1、题目
给定 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)的空间复杂度解决该问题吗？
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/backspace-string-compare/description/
4.2、题解
使用栈
这道题我首先想到的就是使用栈来模拟退格操作，遍历字符串，遇到普通字符就将其入栈，遇到退格字符就将栈顶元素出栈。
注意题目中说对空文本输入退格字符，文本继续为空，所以弹栈前要先判断下栈是否为空
public boolean backspaceCompare(String s, String t) {
Stack<Character> stack_s = new Stack<>();
Stack<Character> stack_t = new Stack<>();
stringToStack(s, stack_s);
stringToStack(t, stack_t);
while (!stack_s.isEmpty() && !stack_t.isEmpty()) {
if (stack_s.pop() != stack_t.pop()) {
return false;
}
}
if (stack_s.isEmpty() && stack_t.isEmpty()) {
return true;
} else {
return false;
}
}
public void stringToStack(String str, Stack<Character> stack) {
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) != '#') {
stack.push(str.charAt(i));
} else {
if (!stack.isEmpty()) {
stack.pop();
}
}
}
}使用 StringBuilder
第二种思路：能不能直接对字符串进行操作，构造出进行退格操作后的字符串，然后比较两个字符串即可。
但 Java 中字符串不能修改，于是想到借助 StringBuilder 的 deleteChatAt() 方法。根据原字符串构造 StringBuilder，然后遍历，遇到退格字符就将其删除，并且还要删除其前一个字符。不过考虑到空文本退格操作，删除前一个字符前要判断一下有没有字符，这儿判断 i >= 0 即可。
public boolean backspaceCompare(String s, String t) {
StringBuilder stringBuilder_s = new StringBuilder(s);
StringBuilder stringBuilder_t = new StringBuilder(t);
s = deleteCharacter(stringBuilder_s);
t = deleteCharacter(stringBuilder_t);
return s.equals(t);
}
public String deleteCharacter(StringBuilder stringBuilder) {
int length = stringBuilder.length();
for (int i = 0; i < length; i++) {
if (stringBuilder.charAt(i) == '#') {
stringBuilder.deleteCharAt(i);
i--;
length--;
if (i >= 0) {
stringBuilder.deleteCharAt(i);
i--;
length--;
}
}
}
return stringBuilder.toString();
}继续第二种思路，这样构造字符串似乎有点麻烦，不如先构造一个空字符串，然后遍历原字符串，遇到普通字符就将其添加到新字符串末尾，遇到退格字符时删除新字符串末尾的字符即可。
这种方法的代码写完后，又看了下力扣上别人的题解，我突然反应过来，这种方式其实就是直接使用字符串来作为栈，末尾添加和弹出，StringBuilder 都有相应的接口，最后比较的时候，只要比较两个字符串就可以了，比比较栈里的元素方便一些。
public boolean backspaceCompare(String s, String t) {
s = appendCharacter(s);
t = appendCharacter(t);
return s.equals(t);
}
public String appendCharacter(String str) {
StringBuilder stringBuilder = new StringBuilder("");
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) != '#') {
stringBuilder.append(str.charAt(i));
} else {
if (!stringBuilder.toString().equals("")) {
stringBuilder.deleteCharAt(stringBuilder.length() - 1);
}
}
}
return stringBuilder.toString();
}双指针方法一
参考 T27，本题也可使用类似的双指针方法。
使用快指针来遍历原字符串，慢指针指向新字符串末尾元素的下一位。遇到普通字符时，将快指针指向的元素写入到慢指针指向的位置，然后快慢指针同步向前。遇到退格字符时，快指针继续向前，慢指针向后退一位，以此来实现退格效果。
可以直接用 StringBuilder 操作，也可以先将字符串转为数组再用双指针。
public boolean backspaceCompare(String s, String t) {
s = range(s);
t = range(t);
return s.equals(t);
}
public String range(String str) {
StringBuilder stringBuilder = new StringBuilder(str);
int slow = 0;
for (int fast = 0; fast < stringBuilder.length(); fast++) {
if (stringBuilder.charAt(fast) != '#') {
stringBuilder.setCharAt(slow, stringBuilder.charAt(fast));
slow++;
} else {
if (slow > 0) {
slow--;
}
}
}
return stringBuilder.substring(0, slow);
}双指针方法二
感觉这种方法思路勉强能理解，但代码不是很好写出来
public boolean backspaceCompare(String S, String T) {
int i = S.length() - 1, j = T.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (S.charAt(i) == '#') {
skipS++;
i--;
} else if (skipS > 0) {
skipS--;
i--;
} else {
break;
}
}
while (j >= 0) {
if (T.charAt(j) == '#') {
skipT++;
j--;
} else if (skipT > 0) {
skipT--;
j--;
} else {
break;
}
}
if (i >= 0 && j >= 0) {
if (S.charAt(i) != T.charAt(j)) {
return false;
}
} else {
if (i >= 0 || j >= 0) {
return false;
}
}
i--;
j--;
}
return true;
}