简单的数组问题

题解报告LeetCode#125：验证回文串

题意：LeetCode#125：验证回文串

  1.     给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

思路：

代码：

public class Solution {

    public boolean isPalindrome(String s) {
        int len = s.length();
        // 如果字符只有 0 或 1 个字母，那么也一定是回文数
        if (len < 2) {
            return true;
        }

        // 只考虑字母和数字字符，可以忽略字母的大小写
        s = s.toLowerCase();
        // 只保留小写字母和数字
        s = s.replaceAll("[^0-9a-z]", "");
        char[] charArray = s.toCharArray();

        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            char cl = charArray[left];
            char cr = charArray[right];
            if (cl != cr) {
                return false;
            }
            left ++;
            right --;
        }

        return true;
    }

}

题解报告LeetCode#26：删除排序数组中的重复项

题意：LeetCode#26：删除排序数组中的重复项

思路：双指针

代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0, j = 1;
        while (j < nums.length) {
            if (nums[i] != nums[j]) {
                i++;
                nums[i] = nums[j];
            }
            j++;
        }

        return i + 1;
    }
}

题解报告LeetCode#27：移除元素

题意：LeetCode#27：移除元素

思路：双指针

代码：

class Solution {
    public int removeElement(int[] nums, int val) {
        int ans = 0;
        for (int num : nums) {
            if (num != val) {
                nums[ans] = num;
                ans++;
            }
        }
        return ans;
    }
}

题解报告LeetCode#75：颜色分类

题意：LeetCode#75：颜色分类

思路：三指针

代码：

public class Solution {

    public void sortColors(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }

        // all in [0, zero) = 0
        // all in [zero, i) = 1
        // all in [two, len - 1] = 2

        // 循环终止条件是 i == two，那么循环可以继续的条件是 i < two
        // 为了保证初始化的时候 [0, zero) 为空，设置 zero = 0，
        // 所以下面遍历到 0 的时候，先交换，再加
        int zero = 0;

        // 为了保证初始化的时候 [two, len - 1] 为空，设置 two = len
        // 所以下面遍历到 2 的时候，先减，再交换
        int two = len;
        int i = 0;
        // 当 i == two 上面的三个子区间正好覆盖了全部数组
        // 因此，循环可以继续的条件是 i < two
        while (i < two) {
            if (nums[i] == 0) {
                swap(nums, i, zero);
                zero++;
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                two--;
                swap(nums, i, two);
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

题解报告LeetCode#80：删除排序数组中的重复项Ⅱ

题意：LeetCode#80：删除排序数组中的重复项Ⅱ

思路：双指针

代码：

public class Solution {

    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len < 3) {
            return len;
        }

        // 循环不变量：[0, j) 是最终返回的数组
        // 初始化的时候，前 2 位有效
        // [0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4]
        //           j
        //              i
        // j 指向下一个要填写的元素
        int j = 2;
        for (int i = 2; i < len; i++) {
            if (nums[i] != nums[j - 2]) {
                nums[j] = nums[i];
                j++;
            }
        }

        return j;
     }
}

题解报告LeetCode#283：移动零

题意：LeetCode#283：移动零

思路：双指针

代码：

public class Solution {
    public void moveZeros(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }

        int next = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != 0) {
                nums[next] = nums[i];
                next++;
            }
        }

        for (int i = next; i < len; i++) {
            nums[i] = 0;
        }
    }
}