LeetCode 431-460

432. 全 O(1) 的数据结构

class AllOne {
    class DLinkedNode {
        int val;
        Set<String> keys;
        DLinkedNode next;
        DLinkedNode pre;

        public DLinkedNode(int val) {
            this.val = val;
            this.keys = new HashSet<>();
        }
    }

    DLinkedNode head, tail;//   双向链表从head到tail的value值依次减小
    Map<String, Integer> map1;//key->val
    Map<Integer, DLinkedNode> map2;//val -> DLinkedNode

    public AllOne() {
        this.head = new DLinkedNode(0);
        this.tail = new DLinkedNode(0);
        head.next = tail;
        tail.pre = head;
        this.map1 = new HashMap<>();
        this.map2 = new HashMap<>();
    }

    public void inc(String key) {
        if (map1.containsKey(key)) {
            int val = map1.get(key);
            map1.put(key, val + 1);
            DLinkedNode node = map2.get(val);
            node.keys.remove(key);
            DLinkedNode preNode = node.pre;
            if (preNode == head || preNode.val > val + 1) {
                DLinkedNode newNode = new DLinkedNode(val + 1);
                newNode.keys.add(key);
                newNode.next = node;
                newNode.pre = preNode;
                preNode.next = newNode;
                node.pre = newNode;
                map2.put(val + 1, newNode);
                preNode = newNode;
            } else {
                preNode.keys.add(key);
            }
            // 如果原节点在移除key后size为0，则删除该节点，并在map2中删除val->node的映射
            if (node.keys.size() == 0) {
                preNode.next = node.next;
                node.next.pre = preNode;
                map2.remove(val);
            }
        } else {
            map1.put(key, 1);
            DLinkedNode node = map2.get(1);
            if (node == null) {
                DLinkedNode newNode = new DLinkedNode(1);
                // 如果当前没有统计次数为1的节点，则新建节点并插入到双向链表的尾部，因为统计次数最小为1
                // 并将1->newNode的映射加入到map2中
                newNode.keys.add(key);
                newNode.next = tail;
                newNode.pre = tail.pre;
                tail.pre.next = newNode;
                tail.pre = newNode;
                map2.put(1, newNode);
            } else {
                node.keys.add(key);
            }
        }

    }

    public void dec(String key) {
        if (map1.containsKey(key)) {
            // 获取当前统计次数
            int val = map1.get(key);
            // 当前统计次数对应的节点
            DLinkedNode node = map2.get(val);
            // 从节点的keys set中移除当前key
            node.keys.remove(key);
            // 如果原统计次数为1，从map1中移除当前key
            if (val == 1) {
                map1.remove(key);
            } else {
                map1.put(key, val - 1);
                DLinkedNode nextNode = node.next;
                if (nextNode == tail || nextNode.val < val - 1) {
                    DLinkedNode newNode = new DLinkedNode(val - 1);
                    newNode.keys.add(key);
                    newNode.pre = node;
                    newNode.next = nextNode;
                    node.next = newNode;
                    nextNode.pre = newNode;
                    map2.put(val - 1, newNode);
                } else {    // 下一个节点的统计次数为val-1，将key加到下一节点的keys Set中
                    nextNode.keys.add(key);
                }
            }
            if (node.keys.size() == 0) {
                node.pre.next = node.next;
                node.next.pre = node.pre;
                map2.remove(val);
            }
        }
    }

    public String getMaxKey() {
        if (head.next == tail) {
            return "";
        } else {
            return head.next.keys.iterator().next();
        }
    }

    public String getMinKey() {
        if (tail.pre == head) {
            return "";
        } else {
            return tail.pre.keys.iterator().next();
        }
    }
}

433. 最小基因变化

双向bfs，和 127. 单词接龙一模一样。

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        char[] gene = {'A', 'G', 'C', 'T'};
        Set<String> set = new HashSet<>();
        for (String str : bank) {
            set.add(str);
        }
        set.add(start);
        if (set.isEmpty() || !set.contains(end)) {
            return -1;
        }
        Queue<String> q1 = new LinkedList<>();
        int step1 = 0;
        q1.offer(start);
        Set<String> isVisited1 = new HashSet<>();
        Queue<String> q2 = new LinkedList<>();
        int step2 = 0;
        q2.offer(end);
        Set<String> isVisited2 = new HashSet<>();
        while (!q1.isEmpty() && !q2.isEmpty()) {
            int size1 = q1.size();
            for (int i = 0; i < size1; i++) {
                String front = q1.poll();
                char[] chars = front.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char temp = chars[j];
                    for (int k = 0; k < 4; k++) {
                        if (gene[k] == temp) {
                            continue;
                        }
                        chars[j] = gene[k];
                        String str = String.valueOf(chars);
                        if (end.equals(str)) {
                            return step1 + 1;
                        }
                        if (isVisited2.contains(str)) {
                            return step1 + step2 + 1;
                        }
                        if (set.contains(str) && !isVisited1.contains(str)) {
                            q1.offer(str);
                            isVisited1.add(str);
                        }
                    }
                    chars[j] = temp;
                }
            }
            step1++;
            int size2 = q2.size();
            for (int i = 0; i < size2; i++) {
                String front = q2.poll();
                char[] chars = front.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char temp = chars[j];
                    for (int k = 0; k < 4; k++) {
                        if (gene[k] == temp) {
                            continue;
                        }
                        chars[j] = gene[k];
                        String str = String.valueOf(chars);
                        if (isVisited1.contains(str)) {
                            return step1 + step2 + 1;
                        }
                        if (set.contains(str) && !isVisited2.contains(str)) {
                            q2.offer(str);
                            isVisited2.add(str);
                        }
                    }
                    chars[j] = temp;
                }
            }
            step2++;
        }
        return -1;
    }
}

434. 字符串中的单词数

class Solution {
    public int countSegments(String s) {
        String[] splits = s.split(" ");
        int res = 0;
        for (String split : splits) {
            if (!"".equals(split)) {
                res++;
            }
        }
        return res;
    }
}

435. 无重叠区间

先把所有区间按照左端点从小到大排序。
然后遍历所有区间，只要某个区间的左端点小于前一个区间的右端点，那么有重复区间，需要移除某一个区间。
尽量保留右端点小的区间，尽量移除右端点大的区间。
这样移除区间的次数最优。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        int res = 0;
        int end = intervals[0][1];
        int pre = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[pre][1] > intervals[i][0]) {
                if (intervals[pre][1] > intervals[i][1]) {
                    pre = i;
                }
                res++;
            } else {
                pre = i;
            }
        }
        return res;
    }
}

436. 寻找右区间

暴力法：
时间复杂度On2

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int[] res = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            int minIndex = -1, minValue = Integer.MAX_VALUE;
            for (int j = 0; j < intervals.length; j++) {
                if (j == i) {
                    continue;
                }
                if (intervals[j][0] >= intervals[i][1] && intervals[j][0] < minValue) {
                    minValue = intervals[j][0];
                    minIndex = j;
                }
            }
            res[i] = minIndex;
        }
        return res;
    }
}

排序+二分搜索:
时间复杂度O(nlogn)

class Solution {
    private int binarySearh(int target, int[] arr) {
        if (arr[arr.length - 1] < target) {
            return -1;
        }
        int lo = 0, hi = arr.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] >= target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    public int[] findRightInterval(int[][] intervals) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] arr = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            arr[i] = intervals[i][0];
            map.put(intervals[i][0], i);
        }
        Arrays.sort(arr);
        int[] res = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            int val = binarySearh(intervals[i][1], arr);
            if (val == -1) {
                res[i] = -1;
            } else {
                res[i] = map.get(arr[val]);
            }
        }
        return res;
    }
}

437. 路径总和 III

class Solution {
    int res = 0;

    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        dfs(root, sum);
        pathSum(root.left, sum);
        pathSum(root.right, sum);
        return res;
    }

    private void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        sum -= root.val;
        if (sum == 0) {
            res++;
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
    }
}

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

暴力法：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] count = new int[26];
        for (char c : p.toCharArray()) {
            count[c - 'a']++;
        }
        for (int i = 0; i < s.length() - p.length()+1; i++) {
            boolean flag = false;
            String sub = s.substring(i, i + p.length());
            int[] count2 = new int[26];
            for (char c : sub.toCharArray()) {
                count2[c - 'a']++;
            }
            for (int j = 0; j < 26; j++) {
                if (count[j] != count2[j]) {
                    flag = true;
                    break;
                }
            }
            if (flag == true) {
                continue;
            }
            res.add(i);
        }
        return res;
    }
}

没必要每次都重新计算窗口内的字符，只需在移动窗口的过程中增减边界的字符数即可。
滑动窗口:

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length() < p.length()) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        int[] count = new int[26];
        for (char c : p.toCharArray()) {
            count[c - 'a']++;
        }
        int len = p.length();//窗口大小
        int[] cur = new int[26];
        for (int i = 0; i < len - 1; i++) {
            cur[s.charAt(i) - 'a']++;
        }
        for (int i = len - 1; i < s.length(); i++) {
            cur[s.charAt(i) - 'a']++;
            if (judge(cur, count)) {
                res.add(i - len + 1);
            }
            cur[s.charAt(i - len + 1) - 'a']--;
        }
        return res;
    }

    //判断是否相等
    private boolean judge(int[] a, int[] b) {
        for (int i = 0; i < 26; i++) {
            if (a[i] != b[i]) {
                return false;
            }
        }
        return true;
    }
}

440. 字典序的第K小数字

class Solution {
    public int findKthNumber(int n, int k) {
        int cur = 1;
        k--;
        while (k > 0) {
            long curNum = 0;
            long first = cur;
            long next = cur + 1;
            while (first <= n) {
                curNum += Math.min((long) (n + 1), next) - first;
                first *= 10;
                next *= 10;
            }
            if (curNum <= k) {
                cur++;
                k -= curNum;
            } else {
                k--;
                cur *= 10;
            }
        }
        return cur;
    }
}

441. 排列硬币

class Solution {
    public int arrangeCoins(int n) {
        int res = 1;
        while (n >= res) {
            n -= res;
            res++;
        }
        return res-1;
    }
}

442. 数组中重复的数据

题目说了1 ≤ a[i] ≤ n，说明数组内的每个数-1之后都可以对应到数组的某个下标0~n-1。
遍历数组，把nums[i]-1位置的数取反，如果取反之后，这个位置的数还大于0，说明nums[i]这个数出现了两次，加到结果中。

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            nums[index] = -nums[index];
            if (nums[index] > 0) {
                res.add(Math.abs(nums[i]));
            }
        }
        return res;
    }
}

443. 压缩字符串

class Solution {
    public int compress(char[] chars) {
        int len = 0;//压缩完之后的长度
        int begin = 0;//连续字符串的起始位置
        for (int i = 0; i < chars.length; i++) {
            if (i == chars.length - 1 || chars[i] != chars[i + 1]) {
                chars[len] = chars[begin];
                len++;
                if (i > begin) {//大于一个字符才进行压缩
                    for (char c : ("" + (i - begin + 1)).toCharArray()) {
                        chars[len] = c;
                        len++;
                    }
                }
                begin = i + 1;
            }
        }
        return len;
    }
}

445. 两数相加 II

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        ListNode dummy = new ListNode(0);
        int carry = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int a = stack1.isEmpty() ? 0 : stack1.pop();
            int b = stack2.isEmpty() ? 0 : stack2.pop();
            int sum = a + b + carry;
            ListNode node = new ListNode(sum % 10);
            node.next = dummy.next;
            dummy.next = node;
            carry = sum / 10;
        }
        return dummy.next;
    }
}

447. 回旋镖的数量

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        for (int[] point : points) {
            Map<Long, Integer> map = new HashMap<>();
            for (int[] point2 : points) {
                int dx = point2[0] - point[0];
                int dy = point2[1] - point[1];
                long dis = dx * dx + dy * dy;
                map.put(dis, map.getOrDefault(dis, 0) + 1);
            }
            for (int val : map.values()) {
                res += val * (val - 1);
            }
        }
        return res;
    }
}

448. 找到所有数组中消失的数字

先遍历的一次，将a[i]-1位置的数变成负数。
再遍历一次，只要a[i]是正数，那么i+1就是没出现过的数。

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            nums[index] = -Math.abs(nums[index]);
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                res.add(i + 1);
            }
        }
        return res;
    }
}

449. 序列化和反序列化二叉搜索树

public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) {
            return "null";
        }
        StringBuilder res = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode front = q.poll();
                if (front == null) {
                    res.append("null,");
                    continue;
                } else {
                    res.append(front.val + ",");
                    q.offer(front.left);
                    q.offer(front.right);
                }
            }
        }
        res.deleteCharAt(res.length() - 1);
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if ("null".equals(data)) {
            return null;
        }
        String[] splits = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(splits[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        for (int i = 1; i < splits.length; i++) {
            TreeNode front = q.poll();
            if (!"null".equals(splits[i])) {
                front.left = new TreeNode(Integer.parseInt(splits[i]));
                q.offer(front.left);
            }
            i++;
            if (!"null".equals(splits[i])) {
                front.right = new TreeNode(Integer.parseInt(splits[i]));
                q.offer(front.right);
            }
        }
        return root;
    }
}

450. 删除二叉搜索树中的节点

class Solution {
    private int getSuccessor(TreeNode root) {
        root = root.right;
        while (root.left != null) {
            root = root.left;
        }
        return root.val;
    }

    private int getPredecessor(TreeNode root) {
        root = root.left;
        while (root.right != null) {
            root = root.right;
        }
        return root.val;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null && root.right == null) {
                root = null;
            } else if (root.left != null) {
                root.val = getPredecessor(root);
                root.left = deleteNode(root.left, root.val);
            } else {
                root.val = getSuccessor(root);
                root.right = deleteNode(root.right, root.val);
            }
        }
        return root;
    }
}

451. 根据字符出现频率排序

class Solution {
    public <K extends Comparable, V extends Comparable> Map<K, V> sortMapByValues(Map<K, V> aMap) {
        HashMap<K, V> finalOut = new LinkedHashMap<>();
        aMap.entrySet()
                .stream()
                .sorted((p1, p2) -> p2.getValue().compareTo(p1.getValue()))
                .collect(Collectors.toList()).forEach(ele -> finalOut.put(ele.getKey(), ele.getValue()));
        return finalOut;
    }

    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        Map<Character, Integer> sorted = sortMapByValues(map);
        StringBuilder res = new StringBuilder();
        for (char c : sorted.keySet()) {
            int num = sorted.get(c);
            for (int i = 0; i < num; i++) {
                res.append(c);
            }
        }
        return res.toString();
    }
}

452. 用最少数量的箭引爆气球

每次射右边界一定是最优的情况，按照右边界从小到大排序。
注意以后lambda表达式里面不要写o1[1] - o2[1]了，可能会溢出造成错误的排序。改成Integer.compare(o1[1], o2[1]))。

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }
        Arrays.sort(points, (o1, o2) -> Integer.compare(o1[1], o2[1]));
        int res = 1;
        int right = points[0][1];
        for (int[] point : points) {
            if (point[0] > right) {
                right = point[1];
                res++;
            }
        }
        return res;
    }
}

453. 最小移动次数使数组元素相等

class Solution {
    public int minMoves(int[] nums) {
        int res = 0;
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            min = Math.min(min, nums[i]);
        }
        for (int i : nums) {
            if (i > min) {
                res += i - min;
            }
        }
        return res;
    }
}

454. 四数相加 II

分成两组做

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : A) {
            for (int j : B) {
                map.put(i + j, map.getOrDefault(i + j, 0) + 1);
            }
        }
        for (int i : C) {
            for (int j : D) {
                if (map.containsKey(-i - j)) {
                    res += map.get(-i - j);
                }
            }
        }
        return res;
    }
}

455. 分发饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0, j = 0;
        int res = 0;
        while (i < g.length && j < s.length) {
            if (g[i] <= s[j]) {
                i++;
                j++;
                res++;
            } else {
                j++;
            }
        }
        return res;
    }
}

456. 132模式

class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums.length == 0) {
            return false;
        }
        int[] min = new int[nums.length];
        min[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            min[i] = Math.min(min[i - 1], nums[i]);
        }
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] > min[i]) {
                while (!stack.isEmpty() && stack.peek() <= min[i]) {
                    stack.pop();
                }
                if (!stack.isEmpty() && stack.peek() < nums[i]) {
                    return true;
                }
                stack.push(nums[i]);
            }
        }
        return false;
    }
}

457. 环形数组循环

class Solution {
    private int getNext(int[] nums, int i, int next) {
        return (i + next % nums.length + nums.length) % nums.length;
    }

    public boolean circularArrayLoop(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < nums.length; i++) {
            boolean[] isVisited = new boolean[len];
            int j = i;
            int count = 0;
            while (isVisited[j] == false) {
                isVisited[j] = true;
                if (nums[j] > 0) {
                    j = getNext(nums, j, nums[j]);
                    if (nums[j] < 0) {
                        break;
                    }
                    count++;
                } else {
                    j = getNext(nums, j, nums[j]);
                    if (nums[j] > 0) {
                        break;
                    }
                    count++;
                }
            }
            if (j == i && count > 1) {
                return true;
            }
        }
        return false;
    }
}

458. 可怜的小猪

对于一只猪，可以在1h之内最多喝 4次水(60/15)，但是可以检验5个桶，如果前四次没死，说明第5个桶有毒。

对于2只猪，现在可以让一只猪一下喝5桶水，如图所示的一只猪喝行的五个，一只猪喝列的五个，这样就可以确定哪个桶有毒，可以检测25个桶。

3只猪可以检测125个桶。

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int pigs = 0;
        while (Math.pow((minutesToTest / minutesToDie + 1), pigs) < buckets) {
            pigs++;
        }
        return pigs;
    }
}

459. 重复的子字符串

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return (s + s).indexOf(s, 1) != s.length();
    }
}

460. LFU 缓存