LeetCode刷题Day02——数组（元素删除、移动）

/**
 * <pre>
 * <p>用O(1)的空间复杂度移除数组中某个值</p>
 * 最容易想到的莫过于从头到尾遍历数组，遇到目标值，则把该值后面的所有元素向前移动1位
 * 然而这样的方式时间复杂度时O(n^2)，并非最优解
 * 因为题目指出不需要考虑元素的顺序，也就是说移除了元素的那个位置不需要用它下一个元素替代
 * 那我们可以从后往前遍历数组，一遇到要删除的元素就用数组最后一个元素替代，时间复杂度只为O(n)
 * </pre>
 *
 * @author <a href="https://github.com/kil1ua">Ken-Chy129</a>
 * @date 2023/1/3 10:43
 */
public class 移除元素27 {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        // 为什么要从后往前遍历，因为所有元素是要集中在前面，而空白在后面
        // 而遇到要删除的元素使用最后的元素去替代的
        // 那么从后往前能够保证移到前面的一定是有值，因为后面的元素已经判断过了
        // 如果是从前往后遍历，那么用最后一个元素去替代的话他有可能也是要删除的元素
        for(int i=len-1; i>=0; i--) {
            if (nums[i] == val) {
                nums[i] = nums[len-1];
                len--;
            }
        }
        return len;
    }
    public int removeElement2(int[] nums, int val) {
        int pos = 0;
        for (int num : nums) {
            if (num != val) {
                nums[pos++] = num;
            }
        }
        return pos;
    }
}

/**
 * <pre>
 * <p>删除重复元素需要记录出现过的元素，因为数组是有序排列的，所以只需要记住上一个元素的值即可</p>
 * </pre>
 *
 * @author <a href="https://github.com/kil1ua">Ken-Chy129</a>
 * @date 2023/1/3 11:26
 */
public class 删除排序数组中的重复项26 {
    public int removeDuplicates(int[] nums) {
        int pos = 1, last = nums[0];
        for (int i=1; i<nums.length; i++) {
            // 如果新的一个元素等于last说明是重复元素
            if (last != nums[i]) {
                nums[pos++] = nums[i]; // 非重复元素则保存
                last = nums[i]; // 并更新last
            }
        }
        return pos;
    }
}

/**
 * <pre>
 * <p>等同于移动元素题，但是需要输出所有的元素，所以需要把最后的0给补上</p>
 * </pre>
 *
 * @author <a href="https://github.com/kil1ua">Ken-Chy129</a>
 * @date 2023/1/3 12:56
 */
public class 移动零283 {
    public void moveZeroes(int[] nums) {
        int pos = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[pos++] = num;
            }
        }
        for (int i=pos; i<nums.length; i++) {
            nums[i] = 0;
        }
    }
}

/**
 * <pre>
 * <p>退格有两种方式，一种是维护一个栈，需要额外的空间开销，
 * 另一种是双指针，并维护一个退格键数控制指针移动</p>
 * </pre>
 *
 * @author <a href="https://github.com/kil1ua">Ken-Chy129</a>
 * @date 2023/1/3 13:17
 */
public class 比较含退格的字符串844 {
    public boolean backspaceCompare(String s, String t) {
//        return build(s).equals(build(t));
        int pos1 = s.length()-1, pos2 = t.length()-1;
        int flag1 = 0, flag2 = 0; // flag表示需要删除的元素数量
        while (pos1>=0 || pos2>=0) {
            while (pos1 >= 0) {
                if (s.charAt(pos1) == '#') { // 如果是#号则表示增加一个退格数，且指针前移
                    flag1++;
                    pos1--;
                } else if (flag1 > 0) { // 是正常字符且退格数还未清零，表示该字符会被删掉
                    flag1--;
                    pos1--;
                } else { // 不是退格，且退格数已经清零，说明这个字符有效的需要拿来比较的
                    break;
                }
            }
            // 下面这个循环同理，出循环后得到需要比较的字符
            while (pos2 >= 0) {
                if (t.charAt(pos2) == '#') {
                    flag2++;
                    pos2--;
                } else if (flag2 > 0) {
                    flag2--;
                    pos2--;
                } else {
                    break;
                }
            }
            if (pos1 >= 0 && pos2 >= 0) { // 位置是有效的，都大于等于0（即都还没遍历完字符串）
                if (s.charAt(pos1) != t.charAt(pos2)) { // 如果不同那么肯定字符串是不同的
                    return false;
                }
            } else if (pos1 >= 0 || pos2 >= 0) {
                // 如果有一个字符串遍历完了，另一个还没遍历完那么两个字符串肯定不相同
                // 因为没遍历完的那个字符串前面肯定还有一些有效字符
                // 不可能全是退格键，因为最近的连续退格键会在循环中删掉，出来的会是有效字符
                return false;
            }
            // 接着往前判断
            pos1--;
            pos2--;
        }
        // 两个字符串同时遍历完也没有出现不同的字符则两个字符串相等
        return true;
    }
    // 维护一个栈结构，非#字符即入栈，检测到#字符则将栈顶元素出栈，时间复杂度和空间复杂度都为O(n+m)
    public String build(String s) {
        StringBuffer str = new StringBuffer();
        int len = s.length();
        for (int i=0; i<len; i++) {
            if (s.charAt(i) != '#') {
                str.append(s.charAt(i));
            } else {
                if (!str.isEmpty()) {
                    str.deleteCharAt(str.length() - 1);
                }
            }
        }
        return str.toString();
    }
}

/**
 * <pre>
 * <p>使用两个指针分别指向位置 0 和 n-1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针</p>
 * </pre>
 *
 * @author <a href="https://github.com/kil1ua">Ken-Chy129</a>
 * @date 2023/1/4 10:19
 */
public class 有序数组的平方977 {
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        // 左指针从最左边开始，右指针从最右边开始
        // 因为原先数组有序，负数越小其平方越大，所以对于负数来说平方后最大的值出现在最左侧
        int left = 0, right = nums.length-1, pos = nums.length-1;
        while (pos >= 0) { // 结果数组没有放完（原数组没有遍历完）
            if (nums[left] < 0) {
                if (-nums[left] < nums[right]) { // 负数的绝对值小，则pos放的是正数的平方，且右指针左移
                    res[pos--] = nums[right] * nums[right--];
                } else { // 负数的绝对值大，则pos放的是负数的平法，且左指针右移
                    res[pos--] = nums[left] * nums[left++];
                }
            } else { // 如果left所在的位置大于0了，那么接下来的位置其实都是有序的不需要再比较了，因为无序只出现在负数平方变大
                // 直接放入
                for (int i=0; i<=pos; i++) {
                    res[i] = nums[left] * nums[left++];
                }
                break;
            }
        }
        return res;
    }
}