leetcode 27

27. Remove Element
    Easy
    Topics
    premium lock icon
    Companies
    Hint
    Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.
Custom Judge:

The judge will test your solution with the following code:

int[] nums = […]; // Input array
int val = …; // Value to remove
int[] expectedNums = […]; // The expected answer with correct length.
// It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,,]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

27. 移除元素

简单

相关主题：公司

提示

给你一个整数数组 nums 和一个整数 val，请你原地移除 nums 中所有等于 val 的元素。元素的顺序可以改变。然后返回 nums 中不等于 val 的元素个数。

设 nums 中不等于 val 的元素个数为 k，为了通过判题，你需要完成以下操作：

1. 修改数组 nums，使 nums 的前 k 个元素包含所有不等于 val 的元素。nums 中超出前 k 个元素的其余元素以及 nums 的长度不重要。
2. 返回 k。

自定义判题器：

判题器将使用以下代码测试你的解法：

int[] nums = […]; // 输入数组
int val = …; // 要移除的值
int[] expectedNums = […]; // 正确答案（已排序，不含等于 val 的元素）

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 对 nums 的前 k 个元素排序
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}

如果所有断言都通过，则你的解法被接受。

---

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,,]
解释：你的函数应返回 k = 2，且 nums 的前两个元素为 2。
超出返回的 k 个元素之后的内容不重要（因此用下划线表示）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,,,_]
解释：你的函数应返回 k = 5，且 nums 的前五个元素包含 0、0、1、3 和 4。
注意这五个元素可以按任意顺序返回。
超出返回的 k 个元素之后的内容不重要（因此用下划线表示）。

public class RemoveElement {

    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val){
                nums[slow] = nums[i];
                slow++;
            }
        }
        return slow;
    }
}

leetcode 26

26. Remove Duplicates from Sorted Array
    Easy
    Topics
    premium lock icon
    Companies
    Hint
    Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Consider the number of unique elements in nums to be k​​​​​​​​​​​​​​. After removing duplicates, return the number of unique elements k.

The first k elements of nums should contain the unique numbers in sorted order. The remaining elements beyond index k - 1 can be ignored.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = […]; // Input array
int[] expectedNums = […]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.
26. 删除有序数组中的重复项

简单

相关主题：公司

提示

给你一个按非递减顺序排列的整数数组 nums，请原地删除重复元素，使每个唯一元素只出现一次。元素的相对顺序应保持不变。

将 nums 中唯一元素的个数记为 k。删除唯一元素后，返回唯一元素的个数 k。

nums 的前 k 个元素应包含按排序顺序排列的唯一数字。超出索引 k - 1 的其余元素可以忽略。

自定义判题器：

判题器将使用以下代码测试你的解法：

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,_]
解释：函数应返回 k = 2，其中 nums 的前两个元素分别为 1 和 2。
超出返回的 k 之后的内容不重要（因此用下划线表示）。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4,,,,,_]
解释：函数应返回 k = 5，其中 nums 的前五个元素分别为 0、1、2、3 和 4。
超出返回的 k 之后的内容不重要（因此用下划线表示）。

---

约束条件：

• 1 <= nums.length <= 3 * 10⁴
• -100 <= nums[i] <= 100
• nums 按非递减顺序排列。

自己的写法

 public int removeDuplicates(int[] nums) {
    if(nums.length ==0) return 0;
    int slow = 0;
    for (int fast = 1; fast <= nums.length - 1; fast++) {
        if (nums[slow] != nums[fast]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

AI的写法

class Solution {
    /**
     * LeetCode 26: 删除有序数组中的重复项
     * 时间复杂度 O(n)，空间复杂度 O(1)
     */
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        
        int slow = 0; // 慢指针：最后一个不重复元素的位置
        
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        
        return slow + 1; // 不重复元素的个数
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // 示例 1
        int[] nums1 = {1, 1, 2};
        int k1 = sol.removeDuplicates(nums1);
        System.out.print("k=" + k1 + ", nums=[");
        for (int i = 0; i < nums1.length; i++) {
            System.out.print(nums1[i] + (i < nums1.length - 1 ? "," : ""));
        }
        System.out.println("]");
        // 输出: k=2, nums=[1,2,_]

        // 示例 2
        int[] nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        int k2 = sol.removeDuplicates(nums2);
        System.out.print("k=" + k2 + ", nums=[");
        for (int i = 0; i < nums2.length; i++) {
            System.out.print(nums2[i] + (i < nums2.length - 1 ? "," : ""));
        }
        System.out.println("]");
        // 输出: k=5, nums=[0,1,2,3,4,_,_,_,_,_]
    }
}

核心思想：双指针法（快慢指针）

由于数组已经有序，重复元素一定相邻。用两个指针：

• 慢指针 slow：指向当前已处理的不重复部分的最后一个位置
• 快指针 fast：遍历数组，寻找下一个不重复的元素

流程：

1. fast 从索引 1 开始遍历
2. 当 nums[fast] != nums[slow] 时，说明找到了新元素
3. 将 slow 前进一步，把 nums[fast] 复制到 nums[slow]
4. 遍历结束，slow + 1 就是不重复元素的个数

时间复杂度：O(n) — 只遍历一次
空间复杂度：O(1) — 原地修改

leetcode 844

844. Backspace String Compare
     Easy
     Topics
     premium lock icon
     Companies
     Given two strings s and t, return true if they are equal when both are typed into empty text editors. ‘#’ means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = “ab#c”, t = “ad#c”
Output: true
Explanation: Both s and t become “ac”.
Example 2:

Input: s = “ab##”, t = “c#d#”
Output: true
Explanation: Both s and t become “”.
Example 3:

Input: s = “a#c”, t = “b”
Output: false
Explanation: s becomes “c” while t becomes “b”.

Constraints:

1 <= s.length, t.length <= 200
s and t only contain lowercase letters and ‘#’ characters.

Follow up: Can you solve it in O(n) time and O(1) space?

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 <= 200
• s 和 t 只包含小写字母和 # 字符。

---

进阶： 你能在 O(n) 时间复杂度和 O(1) 空间复杂度内解决这个问题吗？

自己的写法

class Solution {
    public boolean backspaceCompare(String s, String t) {
         return getBackSpaceString(s).equals(getBackSpaceString(t));
    }

     private String getBackSpaceString(String s) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i <= s.length() - 1; i++) {
            if (s.charAt(i) != '#') {
                sb.append(s.charAt(i));
            } else {
                if (sb.length() >1) {
                    sb.delete(sb.length() - 1, sb.length());
                } else {
                    sb.delete(0,1);
                }
            }
        }
        return sb.toString();
    }
}

📌 核心思想

方法一：栈（直观思路）

遍历字符串，遇到普通字符就入栈，遇到 # 就出栈（退格）。最后比较两个字符串处理后的结果。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

方法二：双指针（进阶 O(1) 空间）

从后往前遍历，用 skip 计数器记录需要跳过的字符数：

1. 遇到 # → skip++（表示后面要跳过的字符数增加）
2. 遇到普通字符：
   • 如果 skip > 0 → 跳过该字符（相当于被退格了），skip–
   • 如果 skip == 0 → 该字符保留，参与比较
3. 两个字符串从后往前逐位比较，如果都保留的字符不相等，返回 false

时间复杂度：O(n)
空间复杂度：O(1) ✅

---

☕ Java 实现

方法一：栈

class Solution {
    /**
     * LeetCode 844: 比较含退格的字符串 - 栈方法
     * 时间 O(n)，空间 O(n)
     */
    public boolean backspaceCompare(String s, String t) {
        return build(s).equals(build(t));
    }

    private String build(String str) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : str.toCharArray()) {
            if (c == '#') {
                if (!stack.isEmpty()) {
                    stack.pop(); // 退格：删除前一个字符
                }
            } else {
                stack.push(c); // 普通字符入栈
            }
        }
        // 栈中剩余字符即为结果
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}

方法二：双指针（O(1) 空间）

class Solution {
    /**
     * LeetCode 844: 比较含退格的字符串 - 双指针法
     * 时间 O(n)，空间 O(1)
     */
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1; // s 的指针（从后往前）
        int j = t.length() - 1; // t 的指针（从后往前）

        while (i >= 0 || j >= 0) {
            // 找到 s 中下一个有效字符的位置
            i = getNextValidIndex(s, i);
            // 找到 t 中下一个有效字符的位置
            j = getNextValidIndex(t, j);

            // 如果两个指针都越界，说明都处理完了，相等
            if (i < 0 && j < 0) return true;
            // 如果一个越界另一个没越界，不相等
            if (i < 0 || j < 0) return false;
            // 比较当前有效字符
            if (s.charAt(i) != t.charAt(j)) return false;

            // 继续往前比较
            i--;
            j--;
        }

        return true;
    }

    /**
     * 从位置 index 往前找，返回下一个有效字符的索引
     * skip 记录需要跳过的字符数（退格抵消）
     */
    private int getNextValidIndex(String str, int index) {
        int skip = 0;
        while (index >= 0) {
            if (str.charAt(index) == '#') {
                skip++;       // 遇到退格，跳过计数+1
            } else if (skip > 0) {
                skip--;       // 普通字符但被退格抵消
            } else {
                break;        // 找到有效字符
            }
            index--;
        }
        return index;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // 示例 1
        System.out.println(sol.backspaceCompare("ab#c", "ad#c"));  // true

        // 示例 2
        System.out.println(sol.backspaceCompare("ab##", "c#d#"));  // true

        // 示例 3
        System.out.println(sol.backspaceCompare("a#c", "b"));      // false

        // 额外测试
        System.out.println(sol.backspaceCompare("a##c", "#a#c")); // true
        System.out.println(sol.backspaceCompare("bxj##tw", "bxo#j##tw")); // true
    }
}

---

🧮 双指针执行过程演示

以 s = “ab#c”, t = “ad#c” 为例：

s: a b # c t: a d # c
0 1 2 3 0 1 2 3

第1轮: i=3, j=3
s[3]=’c’ 有效, t[3]=’c’ 有效 → ‘c’==’c’ ✓
i=2, j=2

第2轮: i=2, j=2
s[2]=’#’ → skip=1, i=1
s[1]=’b’, skip>0 → skip=0, i=0
s[0]=’a’ 有效
t[2]=’#’ → skip=1, j=1
t[1]=’d’, skip>0 → skip=0, j=0
t[0]=’a’ 有效
‘a’==’a’ ✓
i=-1, j=-1

第3轮: i<0 && j<0 → 返回 true ✅

---

💡 方法对比

栈
• 时间: O(n)
• 空间: O(n)
• 思路: 直观，模拟输入过程

双指针
• 时间: O(n)
• 空间: O(1)
• 思路: 从后往前，跳过被退格的字符