数据结构与算法-数组系列

naive双指针

26. 删除排序数组中的重复项

快慢指针, fast != slow就可以把slow的下一个重复的值删掉.

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

83. 删除排序链表中的重复元素

可以用类似26题的方法做.

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode slow = head, fast = head;
        while (fast != null) {
            if (slow.val != fast.val) {
                slow = slow.next;
                slow.val = fast.val;
            }
            fast = fast.next;
        }
        slow.next = null;
        return head;
    }
}

27. 移除元素

如果fast的值等于val, 直接跳过, 否则就将这个值赋值给slow.

class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) return 0;
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        return slow;
    }
}

283. 移动零

和27题类似, 只是多了把slow后面的值都赋值成0的操作.

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums.length == 0) return;
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != 0) {
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        while (slow < nums.length) {
            nums[slow++] = 0;
        }
    }
}

滑动窗口-子串问题

76. 最小覆盖子串

根据框架来写, 重要的参数除了左右指针就是valid的个数. 左右指针实际对应的是index, 所以我们是用的区间都是左闭右开的.

class Solution {
    public String minWindow(String s, String t) {
        int left = 0, right = 0;
        int valid = 0;
        HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
        }

        int start = 0, len = s.length() + 1;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++; //区间左闭右开
            if (need.getOrDefault(c, 0) > 0) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) valid++; //Integer比较
            }
            while (valid == need.size()) { //要收缩区间
                if (right - left < len) {
                    start = left; //先记录当前的最优起始值
                    len = right - start;
                }
                char d = s.charAt(left);
                left++;
                if (need.getOrDefault(d, 0) > 0) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == s.length() + 1 ? "" : s.substring(start, start+len);
    }
}

567. 字符串的排列

收缩区间的条件改变, 因为题目中要求的是子串, 必须是连续的

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int left = 0, right = 0;
        int valid = 0;
        HashMap<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            need.put(s1.charAt(i), need.getOrDefault(s1.charAt(i), 0) + 1);
        }
        while (right < s2.length()) {
            char c = s2.charAt(right++);
            if (need.getOrDefault(c, 0) > 0) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) valid++;
            }
            while (right - left >= s1.length()) {
                if (valid == need.size()) return true; //只要满足条件就会收缩, 所以if中一定满足长度相同
                char d = s2.charAt(left++);
                if (need.getOrDefault(d, 0) > 0) {
                    if (window.get(d).equals(need.get(d))) valid--;
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return false;
    }
}

438. 找到字符串中所有字母异位词

同上.

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int left = 0, right = 0;
        int valid = 0;
        HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
        List<Integer> res = new LinkedList<>();
        for (int i = 0; i < p.length(); i++) need.put(p.charAt(i), need.getOrDefault(p.charAt(i), 0) + 1);

        while (right < s.length()) {
            char c = s.charAt(right++);
            if (need.getOrDefault(c, 0) > 0) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (need.get(c).equals(window.get(c))) valid++;
            }
            while (right - left >= p.length()) {
                if (valid == need.size()) res.add(left);
                char d = s.charAt(left++);
                if (need.getOrDefault(d, 0) > 0) {
                    if (need.get(d).equals(window.get(d)))
                        valid--;
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return res;
    }
}

3. 无重复字符的最长子串

无重复本身相当于代替了之前几道题的need条件, 最后计算res要在left滑动之后才满足条件. 始终记住区间是左闭右开的, 所以结果的长度并不用加1(之前加过了).

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        int left = 0, right = 0;
        HashMap<Character, Integer> window = new HashMap<>();
        while (right < s.length()) {
            char c = s.charAt(right++);
            window.put(c, window.getOrDefault(c, 0) + 1);
            while (window.get(c) > 1) {
                char d = s.charAt(left++);
                window.put(d, window.get(d) - 1);
            }
            res = Math.max(res, right - left);
        }
        return res;
    }
}