海边别墅

# LeetCode 6

2021.11 ~

# 575. 分糖果

class Solution {
    public int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<>(candyType.length);
        int cnt = 0, n = candyType.length;
        for (int i : candyType) {
            if (set.add(i)) {
                cnt++;
            }
        }
        return cnt >= (n/2) ? (n/2) : cnt;
    }
}

# 409. 最长回文串

class Solution {
    public int longestPalindrome(String s) {
        int[] map = new int[58];
        for (char c : s.toCharArray()) {
            map[c-65]++;
        }
        // System.out.println(Arrays.toString(map));

        int cnt = 0;
        for (int i : map) {
            if (i >= 2) {
                cnt += (i/2*2);

            }
        }

        return cnt == s.length() ? cnt : cnt+1;
    }
}

# 918. 环形子数组的最大和

暴力枚举，超时：

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int max = nums[0];
        for (int i = 0; i < 2*n; i++) {
            int ii = i%n;
            int cmax = nums[ii];
            int csum = nums[ii];
            for (int j = i-1; j >= 0 && j > i-n; j--) {
                csum += nums[j%n];
                cmax = Math.max(cmax, csum);
            }
            // System.out.println("csum:"+csum+"cmax:"+cmax+"; max:"+max);
            max = Math.max(max, cmax);
        }
        return max;
    }
}

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int max = nums[0], maxSum = nums[0];
        int min = nums[0], minSum = nums[0];
        int singleMax = nums[0];
        int sum = nums[0];
        for (int i = 1; i < n; i++) {
            sum += nums[i];
            maxSum = (maxSum < 0 ? nums[i] : maxSum+nums[i]);
            max = Math.max(max, maxSum);
            minSum = minSum > 0 ? nums[i] : minSum+nums[i];
            min = Math.min(min, minSum);
            singleMax = Math.max(singleMax, nums[i]);
        }
        return Math.max(max, sum-min==0?singleMax:sum-min);
    }
}

将上述代码的Math方法换成三元表达式，可以提高运行效率

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int max = nums[0], maxSum = nums[0];
        int min = nums[0], minSum = nums[0];
        int singleMax = nums[0];
        int sum = nums[0];
        for (int i = 1; i < n; i++) {
            sum += nums[i];
            maxSum = (maxSum < 0 ? nums[i] : maxSum+nums[i]);
            max = max > maxSum ? max : maxSum;
            minSum = minSum > 0 ? nums[i] : minSum+nums[i];
            min = min < minSum ? min : minSum;
            singleMax = singleMax > nums[i] ? singleMax : nums[i];
        }
        return Math.max(max, sum-min==0?singleMax:sum-min);
    }
}

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

贪心

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> {
            if (a[1] > b[1]) {
                return 1;
            } else if (a[1] < b[1]) {
                return -1;
            } else {
                return 0;
            }
        });
        // System.out.println(Arrays.deepToString(points));
        int pre = points[0][1];
        int cnt = 1;
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > pre) {
                cnt++;
                pre = points[i][1];
            }
        }
        return cnt;
    }
}

# 407. 接雨水 II

优先队列

class Solution {
    public int trapRainWater(int[][] heightMap) {
        int row = heightMap.length;
        int col = heightMap[0].length;
        boolean[][] visited = new boolean[row][col];
        // 
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((o1, o2) -> o1[2] - o2[2]);
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (r == 0 || c == 0 || r == row-1 || c == col-1) {
                    visited[r][c] = true;
                    pq.offer(new int[]{r, c, heightMap[r][c]});
                }
            }
        }

        // print
        // while (!pq.isEmpty()) {
        //     System.out.println(Arrays.toString(pq.poll()));
        // }
        int res = 0;
        int[] dir = new int[]{-1, 0, 1, 0, -1};
        while (!pq.isEmpty()) {
            int[] poll = pq.poll();
            for (int k = 0; k < 4; k++) {
                int nr = poll[0]+dir[k];
                int nc = poll[1]+dir[k+1];
                if (nr >= 0 && nr < row && nc >= 0 && nc < col && !visited[nr][nc]) {
                    if (poll[2] > heightMap[nr][nc]) {
                        res += poll[2]-heightMap[nr][nc];
                    }
                    pq.offer(new int[]{nr, nc, Math.max(poll[2], heightMap[nr][nc])});
                    visited[nr][nc] = true;
                }
            }
        }

        return res;
    }
}

# 1094. 拼车

# 1427. 字符串的左右移

class Solution {
    public String stringShift(String s, int[][] shift) {
        int offset = 0;
        for (int[] i : shift) {
            if (i[0] == 0) {
                offset += i[1];
            } else {
                offset -= i[1];
            }
        }
        offset %= s.length();

        if (offset > 0) {
            return s.substring(offset) + s.substring(0, offset);
        } else {
            offset = -offset;
            return s.substring(s.length()-offset) + s.substring(0, s.length()-offset);
        }
    }
}

# 367. 有效的完全平方数

二分

class Solution {
    public boolean isPerfectSquare(int num) {
        long l = 1, r = (num+1) / 2;
        while (l <= r) {
            long mid = l+((r-l)>>1);
            long multi = mid*mid;
            if (multi == num) {
                return true;
            } else if (multi > num) {
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        return false;
    }
}

# 1567. 乘积为正数的最长子数组长度

动态规划

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

# 44. 通配符匹配

动态规划

class Solution {
    public boolean isMatch(String _s, String _p) {
        char[] s = _s.toCharArray();
        char[] p = _p.toCharArray();
        int sn = s.length;
        int pn = p.length;

        boolean[][] dp = new boolean[sn+1][pn+1];
        // init
        dp[0][0] = true;
        for (int j = 1; j < pn+1; j++) {
            dp[0][j] = p[j-1] == '*' && dp[0][j-1];
        }
        for (int i = 0; i < sn; i++) {
            for (int j = 0; j < pn; j++) {
                if (p[j] == '*') {
                    dp[i+1][j+1] = dp[i+1][j] || dp[i][j+1] || dp[i][j];
                } else {
                    dp[i+1][j+1] = firstMath(s, p, i, j) && dp[i][j];
                }
            }
        }
        // System.out.println(Arrays.deepToString(dp));
        return dp[sn][pn];
    }

    private boolean firstMath(char[] s, char[] p, int i, int j) {
        return s[i] == p[j] || p[j] == '?';
    }
}

# 598. 范围求和 II

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int r = m, c = n;
        for (int i = 0; i < ops.length; i++) {
            r = Math.min(r, ops[i][0]);
            c = Math.min(c, ops[i][1]);
        }
        return r*c;
    }
}

# 281. 锯齿迭代器

队列

public class ZigzagIterator {
    Queue<Integer> q = new LinkedList<>();
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        int n1 = v1.size();
        int n2 = v2.size();
        int n = Math.max(n1, n2);
        for (int i = 0; i < n; i++) {
            if (i < v1.size()) {
                q.offer(v1.get(i));
            }
            if (i < v2.size()) {
                q.offer(v2.get(i));
            }
        }
    }

    public int next() {
        return q.poll();
    }

    public boolean hasNext() {
        return !q.isEmpty();
    }
}

# 299. 猜数字游戏

class Solution {
    public String getHint(String secret, String guess) {
        int n = secret.length();
        int[] smap = new int[10];
        int[] gmap = new int[10];
        int x = 0, y = 0;
        for (int i = 0; i < n; i++) {
            int s = secret.charAt(i)-'0';
            int g = guess.charAt(i)-'0';
            if (s == g) {
                x++;
            } else {
                smap[s]++;
                gmap[g]++;
            }
        }

        for (int i = 0; i < 10; i++) {
            y += Math.min(smap[i], gmap[i]);
        }
        return new StringBuilder().append(x).append('A').append(y).append('B').toString();
    }
}

# 394. 字符串解码

利用栈特性

class Solution {
    public String decodeString(String s) {
        Stack<String[]> stack = new Stack<>();
        int i = 0;
        int n = s.length();
        StringBuilder str = new StringBuilder();
        while (i < n) {
            while (i < n && !(s.charAt(i) > '0' && s.charAt(i) < '9' || s.charAt(i) == ']')) {
                str.append(s.charAt(i));
                i++;
            }

            StringBuilder num = new StringBuilder();
            while (i < n && (s.charAt(i) >= '0' && s.charAt(i) <= '9')) {
                num.append(s.charAt(i));
                i++;
            }

            while (i < n && s.charAt(i) == ']') {
                String[] arr = stack.pop();
                StringBuilder pop = new StringBuilder();
                pop.append(arr[0]);
                for (int k = 0; k < Integer.valueOf(arr[1]); k++) {
                    pop.append(str);
                }
                str = pop;
                i++;
            }

            if (i < n && s.charAt(i) == '[') {
                stack.push(new String[]{str.toString(), num.toString()});
                str = new StringBuilder();
                i++;
            }
        }
        return str.toString();
    }
}

# 488. 祖玛游戏

dfs+剪枝

class Solution {
    int INF = 0x3f3f3f3f;
    int m;
    String b;
    Map<String, Integer> map = new HashMap<>();
    public int findMinStep(String board, String hand) {
        m = hand.length();
        b = hand;
        int ans = dfs(board, 1<<m);
        return ans == INF ? -1 : ans;
    }

    private int dfs(String a, int vis) {
        int n = a.length();
        if (n == 0) return 0;
        int ans = INF;
        if (map.containsKey(a)) return map.get(a);
        for (int i = 0; i < m; i++) {
            if (((vis >> i) & 1) == 1) continue;
            int next = (vis | (1 << i));
            for (int j = 0; j <= n; j++) {
                // 剪枝
                boolean ok = false;
                if (j > 0 && j < n && a.charAt(j) == a.charAt(j-1) && a.charAt(j-1) != b.charAt(i)) ok = true;
                if (j < n && a.charAt(j) == b.charAt(i)) ok = true;
                if (!ok) continue;
                StringBuilder str = new StringBuilder();
                str.append(a.substring(0, j)).append(b.substring(i, i+1));
                if (j < n) {
                    str.append(a.substring(j));
                }
                int k = j;
                while (k >= 0 && k < str.length()) {
                    char c = str.charAt(k);
                    int l = k, r = k;
                    while (l >= 0 && str.charAt(l) == c) {
                        l--;
                    }
                    while (r < str.length() && str.charAt(r) == c) {
                        r++;
                    }
                    if (r-1-l >= 3) {
                        str.delete(l+1, r);
                        k = l < 0 ? r : l;
                    } else {
                        break;
                    }
                }
                ans = Math.min(ans, dfs(str.toString(), next)+1);
            }
        }
        map.put(a, ans);
        return ans;
    }
}

# 495. 提莫攻击

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int res = duration;
        int pre = timeSeries[0]+duration-1;
        for (int i = 1; i < timeSeries.length; i++) {
            if (timeSeries[i] <= pre) {
                res -= (pre-timeSeries[i]+1);
            }
            res += duration;
            pre = timeSeries[i]+duration-1;
        }
        return res;
    }
}

# 402. 移掉 K 位数字

单调栈

class Solution {
    public String removeKdigits(String num, int k) {
        LinkedList<Character> q = new LinkedList<>();
        for (int i = 0; i < num.length(); i++) {
            char cur = num.charAt(i);
            while (!q.isEmpty() && k > 0 && q.peekLast() > cur) {
                q.pollLast();
                k--;
            }
            q.offer(cur);
        }

        StringBuilder res = new StringBuilder();
        int sz = q.size()-k;
        boolean firstZero = true;
        for (int i = 0; i < sz; i++) {
            char cur = q.pollFirst();
            if (firstZero && cur == '0') {
                continue;
            } else {
                firstZero = false;
            }
            res.append(cur);
        }
        String ans = res.toString();
        return ans.equals("") ? "0" : ans;
    }
}

# 1469. 寻找所有的独生节点

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> getLonelyNodes(TreeNode root) {
        dfs(root);
        return res;
    }
    private void dfs(TreeNode node) {
        if (node == null) return;

        int l = 0, r = 0;
        if (node.left != null) {
            l = 1;
            dfs(node.left);
        }
        if (node.right != null) {
            r = 1;
            dfs(node.right);
        }
        if ((l^r) == 1) {
            if (l == 1) res.add(node.left.val);
            if (r == 1) res.add(node.right.val);
        }
    }
}

# 1602. 找到二叉树中最近的右侧节点

class Solution {
    public TreeNode findNearestRightNode(TreeNode root, TreeNode u) {
        if (root == null) return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();
                if (cur == u) {
                    if (i < sz-1) {
                        return q.peek();
                    } else {
                        return null;
                    }
                }
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
        }
        return null;
    }
}

# 629. K个逆序对数组

没做出来，看了很久多题解才理解如何dp，但是写的时候仍然很困难，显然没有理解到位

class Solution {
    int mod = (int)1e9+7;
    public int kInversePairs(int n, int k) {
        long[][] dp = new long[n+1][k+1];
        long[][] pre = new long[n+1][k+1];
        dp[1][0] = 1;
        Arrays.fill(pre[1], 1);
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j] = j < i ? pre[i-1][j] : pre[i-1][j] - pre[i-1][j-(i-1)-1];
                dp[i][j] = (dp[i][j] + mod) % mod;
                pre[i][j] = j == 0 ? dp[i][j] : dp[i][j] + pre[i][j-1];
                pre[i][j] = (pre[i][j] + mod) % mod;
            }
        }
        return (int)dp[n][k];
    }
}

# 862. 和至少为 K 的最短子数组

前缀后+双端队列

class Solution {
    int N = Integer.MAX_VALUE;
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] pre = new long[n+1];
        for (int i = 0; i < n; i++) {
            pre[i+1] = pre[i] + nums[i];
        }
        // System.out.println(Arrays.toString(pre));
        int res = N;
        Deque<Integer> q = new LinkedList<>();
        // q.offer(0);
        for (int i = 0; i <= n; i++) {
            long cur = pre[i];
            if (q.isEmpty()) {
                if (cur >= k) {
                    res = Math.min(res, i+1);
                }
            } else {
                while (!q.isEmpty() && cur <= pre[q.peekLast()]) {
                    q.pollLast();
                }
                while (!q.isEmpty() && cur-pre[q.peekFirst()] >= k) {
                    int poll = q.pollFirst();
                    res = Math.min(res, i-poll);
                }
            }
            q.offerLast(i);
        }
        return res == N ? -1 : res;
    }
}

# 214. 最短回文串

class Solution {
    public String shortestPalindrome(String s) {
        int i = 0, n = s.length(), j = n-1;
        while (j >= 0) {
            if (s.charAt(i) == s.charAt(j)) {
                i++;
            }
            j--;
        }
        if (i == n) {
            return s;
        }
        String suffix = s.substring(i);
        StringBuilder rev = new StringBuilder(suffix).reverse();
        return rev.append(shortestPalindrome(s.substring(0, i))+s.substring(i)).toString();
    }
}

# 375. 猜数字大小 II

class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n+1][n+1];
        int INF = Integer.MAX_VALUE;
        for (int j = 2; j <= n; j++) {
            for (int i = j-1; i >= 1; i--) {
                dp[i][j] = INF;
                for (int k = i; k <= j; k++) {
                    int tmp = Math.max(k==i?0:(dp[i][k-1]+k), k==j?0:(dp[k+1][j]+k));
                    dp[i][j] = Math.min(dp[i][j], tmp);
                    // System.out.println("i:"+i+"; j:"+j+"; k:"+k+"; dp:"+dp[i][j]+"; tmp:"+tmp);
                }
            }
        }
        return dp[1][n];
    }
}

# 1522. N 叉树的直径

class Solution {
    int max = 0;
    public int diameter(Node root) {
        dfs(root);
        return max;
    }

    private int dfs(Node node) {
        if (node == null) return 0;
        int first = 0, sec = 0;
        List<Node> childs = node.children;
        for (Node n : childs) {
            int res = dfs(n);
            if (res > first) {
                sec = first;
                first = res;
            } else if (res <= first && res > sec) {
                sec = res;
            }
        }
        max = Math.max(max, first+sec);
        return first == 0 ? 1 : (first+1);
    }
}

# 520. 检测大写字母

class Solution {
    public boolean detectCapitalUse(String word) {
        int cnt = 0, up = 0;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (c >= 'A' && c <= 'Z') {
                up++;
            }
            cnt++;
        }
        return cnt == up || up == 0 || (cnt > 1 && up == 1 && word.charAt(0) >= 'A' && word.charAt(0) <= 'Z');
    }
}

# 366. 寻找二叉树的叶子节点

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> findLeaves(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int l = dfs(node.left);
        int r = dfs(node.right);
        int level = Math.max(l, r)+1;
        List<Integer> list;
        if (level-1 >= res.size()) {
            list = new ArrayList<>();
            res.add(level-1, list);
        } else {
            list = res.get(level-1);
        }
        list.add(node.val);
        return level;
    }
}

# 1325. 删除给定值的叶子节点

class Solution {
    int t;
    public TreeNode removeLeafNodes(TreeNode root, int target) {
        t = target;
        boolean res = dfs(root);
        if (res) root = null;
        return root;
    }

    private boolean dfs(TreeNode node) {
        if (node == null) return true;

        boolean l = dfs(node.left);
        boolean r = dfs(node.right);
        if (l) node.left = null;
        if (r) node.right = null;
        if (l && r && t == node.val) {
            return true;
        }
        return false;
    }
}

# 677. 键值映射

class MapSum {
    TrieNode root;
    public MapSum() {
        root = new TrieNode();
    }
    
    public void insert(String key, int val) {
        TrieNode p = root;
        for (int i = 0; i < key.length(); i++) {
            int c = (int) (key.charAt(i)-'a');
            if (p.ns[c] == null) {
                p.ns[c] = new TrieNode();
            }
            p = p.ns[c];
        }
        p.end = true;
        p.val = val;
    }
    
    public int sum(String prefix) {
        TrieNode p = root;
        for (int i = 0; i < prefix.length(); i++) {
            int c = (int) (prefix.charAt(i)-'a');
            if (p.ns[c] == null) {
                return 0;
            }
            p = p.ns[c];
        }
        return dfs(p);
    }

    private int dfs(TrieNode node) {
        int sum = node.val;
        for (TrieNode n : node.ns) {
            if (n != null) {
                sum += dfs(n);
            }
        }
        return sum;
    }

    class TrieNode {
        boolean end;
        TrieNode[] ns = new TrieNode[26];
        int val;
    }

}

# 319. 灯泡开关

class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.floor(Math.sqrt(n));
    }
}

# 886. 可能的二分法

class Solution {
    int[] father;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        int N = 2*n+1;
        father = new int[N];
        for (int i = 0; i < N; i++) {
            father[i] = i;
        }
        for (int i = 0; i < dislikes.length; i++) {
            int d0 = dislikes[i][0];
            int d1 = dislikes[i][1];
            int x = find(d0);
            int y = find(d1);
            int a = find(d0+n);
            int b = find(d1+n);
            if (x == y) {
                return false;
            } else {
                father[b] = x;
                father[a] = y;
            }
        }
        return true;
    }

    private int find(int x) {
        if (father[x] != x) {
            father[x] = find(father[x]);
        }
        return father[x];
    }
}

# 391. 完美矩形

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int area = 0;
        int[] left = null, right = null;
        Set<Integer> set = new HashSet<>();
        for (int[] rec : rectangles) {
            area += ((rec[2]-rec[0])*(rec[3]-rec[1]));
            if (left == null || rec[0] < left[0] || rec[1] < left[1]) {
                left = new int[]{rec[0], rec[1]};
            }
            if (right == null || rec[2] > right[0] || rec[3] > right[1]) {
                right = new int[]{rec[2], rec[3]};
            }
            int k1 = getKey(rec[0], rec[1]);
            int k2 = getKey(rec[0], rec[3]);
            int k3 = getKey(rec[2], rec[3]);
            int k4 = getKey(rec[2], rec[1]);
            if (!set.add(k1)) set.remove(k1);
            if (!set.add(k2)) set.remove(k2);
            if (!set.add(k3)) set.remove(k3);
            if (!set.add(k4)) set.remove(k4);
        }

        if (area != (right[0]-left[0])*(right[1]-left[1])) {
            return false;
        }
        
        return set.size() == 4 && set.contains(getKey(left[0], left[1])) && set.contains(getKey(left[0], right[1])) && set.contains(getKey(right[0], right[1])) && set.contains(getKey(right[0], left[1]));
    }

    private int getKey(int x, int y) {
        return x*1000001+y;
    }
}

# 261. 以图判树

并查集

class Solution {
    public boolean validTree(int n, int[][] edges) {
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }

        for (int i = 0; i < edges.length; i++) {
            int[] c = edges[i];
            int x = find(c[0]);
            int y = find(c[1]);
            if (x == y) {
                return false;
            } else {
                father[x] = y;
            }
        }
        for (int i = 0; i < n; i++) {
            find(i);
        }
        for (int i = 1; i < n; i++) {
            if (father[i]!=father[i-1]) {
                return false;
            }
        }
        return true;
    }

    int[] father;
    private int find(int x) {
        if (x != father[x]) {
            father[x] = find(father[x]);
        }
        return father[x];
    }
}

# 124. 二叉树中的最大路径和

class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 0;

        int left = dfs(node.left);
        int right = dfs(node.right);

        int res = node.val + Math.max(0, Math.max(left, right));
        max = Math.max(max, Math.max(res, left+right+node.val));
        return res;
    }
}

# 968. 监控二叉树

class Solution {
    int cnt = 0;
    Boolean ok = true;
    Boolean fail = false;
    public int minCameraCover(TreeNode root) {
        Boolean res = dfs(root);
        if (res == fail) cnt++;
        return cnt;
    }

    private Boolean dfs(TreeNode node) {
        if (node == null) return null;
        Boolean left = dfs(node.left);
        Boolean right = dfs(node.right);
        if (left == fail || right == fail) {
            cnt++;
            return true;
        }
        if (left == ok || right == ok) {
            return null;
        }
        return false;
    }
}

# 318. 最大单词长度乘积

同：剑指 Offer II 005. 单词长度的最大乘积

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] mask = new int[n];
        for (int i = 0; i < n; i++) {
            char[] cs = words[i].toCharArray();
            int m = 0;
            for (char c : cs) {
                m = m | (1 << (c-'a'));
            }
            mask[i] = m;
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if ((mask[i] & mask[j]) == 0) {
                    max = Math.max(max, words[i].length()*words[j].length());
                }
            }
        }        
        return max;
    }
}

# 990. 等式方程的可满足性

并查集

class Solution {
    int[] father;
    public boolean equationsPossible(String[] equations) {
        father = new int[26];
        for (int i = 0; i < 26; i++) {
            father[i] = i;
        }
        List<String> notEquals = new ArrayList<>();
        for (int i = 0; i < equations.length; i++) {
            if (equations[i].charAt(1) == '!') {
                notEquals.add(equations[i]);
            } else {
                int s0 = equations[i].charAt(0)-'a', s3 = equations[i].charAt(3)-'a';
                int r0 = find(s0);
                int r3 = find(s3);
                father[r0] = r3;
            }
        }
        for (String s : notEquals) {
            int s0 = s.charAt(0)-'a', s3 = s.charAt(3)-'a';
            int r0 = find(s0);
            int r3 = find(s3);
            if (r0 == r3) return false;
        }
        return true;
    }

    private int find(int x) {
        if (x != father[x]) {
            father[x] = find(father[x]);
        }
        return father[x];
    }
}

# 1319. 连通网络的操作次数

并查集

class Solution {
    int[] father;
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n-1) return -1;
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        for (int i = 0; i < connections.length; i++) {
            int r0 = find(connections[i][0]);
            int r1 = find(connections[i][1]);
            father[r0] = r1;
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            find(i);
            set.add(father[i]);
        }
        
        return set.size()-1;
    }

    private int find(int x) {
        if (x != father[x]) {
            father[x] = find(father[x]);
        }
        return father[x];
    }
}

# 563. 二叉树的坡度

class Solution {
    int res = 0;
    public int findTilt(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int l = dfs(node.left);
        int r = dfs(node.right);
        res += Math.abs(l-r);
        return l + r + node.val;
    }
}

# 305. 岛屿数量 II

并查集

class Solution {
    int[] father;
    int[][] dd = new int[][]{{0, 1},{1, 0},{0, -1},{-1,0}};
    int cnt = 0;
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int sz = m*n;
        father = new int[sz];
        boolean[] grid = new boolean[sz];
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < sz; i++) {
            father[i] = i;
        }
        for (int i = 0; i < positions.length; i++) {
            // x*n+y
            int x = positions[i][0];
            int y = positions[i][1];
            int pos = x*n+y;
            if (!grid[pos]) {
                cnt++;
                grid[pos] = true;
                for (int[] d : dd) {
                    int newX = x+d[0];
                    int newY = y+d[1];
                    int newPos = newX*n+newY;
                    if (inArea(newX, newY, m, n) && grid[newPos] && !isConnected(pos, newPos)) {
                        union(pos, newPos);
                    }
                }
            } 
            
            res.add(cnt);
        }
        return res;
    }

    private boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }

    private void union(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) {
            return;
        }
        father[rx] = ry;
        cnt--;
    }

    private int find(int x) {
        if (x != father[x]) {
            father[x] = find(father[x]);
        }
        return father[x];
    }

    private boolean inArea(int x, int y, int m, int n) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

# 1579. 保证图可完全遍历

并查集

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        UnionSet usa = new UnionSet(n+1);
        UnionSet usb = new UnionSet(n+1);
        int res = 0;
        for (int i = 0; i < edges.length; i++) {
            if (edges[i][0] == 3) {
                int a = edges[i][1];
                int b = edges[i][2];
                if (usa.isConnected(a, b)) {
                    res++;
                } else {
                    usa.union(a, b);
                    usb.union(a, b);
                }
            }
        }

        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][1];
            int b = edges[i][2];
            if (edges[i][0] == 1) {
                if (usa.isConnected(a, b)) {
                    res++;
                } else {
                    usa.union(a, b);
                }
            } else if (edges[i][0] == 2) {
                if (usb.isConnected(a, b)) {
                    res++;
                } else {
                    usb.union(a, b);
                }
            }
        }
        return usa.cnt*usb.cnt>1 ? -1 : res;
    }

    class UnionSet {
        int[] parent;
        int cnt;
        UnionSet(int n) {
            cnt = n-1;
            parent = new int[n];
            for (int i = 1; i < n; i++) {
                parent[i] = i;
            }
        }

        public void union(int x, int y) {
            int rx = find(x);
            int ry = find(y);
            if (rx == ry) return;
            parent[rx] = ry;
            cnt--;
        }

        public boolean isConnected(int x, int y) {
            return find(x) == find(y);
        }

        public int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

    }
}

# 1314. 矩阵区域和

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int row = mat.length, col = mat[0].length;
        int[][] pre = new int[row+2*k+1][col+2*k+1];
        for (int r = k+1; r <= row+2*k; r++) {
            for (int c = k+1; c <= col+2*k; c++) {
                int m = 0;
                if (r-k-1 >= 0 && r-k-1 < row && c-k-1 >= 0 && c-k-1 < col) {
                    m = mat[r-k-1][c-k-1];
                }
                pre[r][c] = pre[r-1][c]+pre[r][c-1]-pre[r-1][c-1]+m;
            }
        }
        int[][] ans = new int[row][col];
        for (int r = k+1; r < row+k+1; r++) {
            for (int c = k+1; c < col+k+1; c++) {
                ans[r-k-1][c-k-1] = pre[r+k][c+k] - pre[r-k-1][c+k] - pre[r+k][c-k-1] + pre[r-k-1][c-k-1];
            }
        }
        return ans;
    }
}

# 397. 整数替换

class Solution {
    Map<Long, Long> cache = new HashMap<>();
    public int integerReplacement(int n) {
        return (int)dfs(n);
    }

    private long dfs(long n) {
        Long res = cache.get(n);
        if (res != null) return res;
        if (n == 1) return 0;
        if (n % 2 == 0) {
            res = dfs(n/2) + 1;
        } else {
            res = Math.min(dfs(n+1), dfs(n-1)) + 1;
        }
        cache.put(n, res);
        return res;
    }
}

# 323. 无向图中连通分量的数目

class Solution {
    public int countComponents(int n, int[][] edges) {
        UnionSet us = new UnionSet(n);
        for (int[] e : edges) {
            us.union(e[0], e[1]);
        }
        return us.cnt;
    }
    class UnionSet {
        int[] parent;
        int cnt;
        UnionSet(int n) {
            parent = new int[n];
            cnt = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rx = find(x);
            int ry = find(y);
            if (rx == ry) return;
            parent[rx] = ry;
            cnt--;
        }
    }
}

# 1101. 彼此熟识的最早时间

class Solution {
    public int earliestAcq(int[][] logs, int n) {
        Arrays.sort(logs, (a, b)-> a[0]-b[0]);
        UnionSet us = new UnionSet(n);
        for (int[] log : logs) {
            us.union(log[1], log[2]);
            if (us.cnt == 1) {
                return log[0];
            }
        }
        return -1;
    }
    class UnionSet {
        int[] parent;
        int cnt;
        UnionSet(int n) {
            parent = new int[n];
            cnt = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rx = find(x);
            int ry = find(y);
            if (rx == ry) return;
            parent[rx] = ry;
            cnt--;
        }
    }
}

# 1227. 飞机座位分配概率

class Solution {
    public double nthPersonGetsNthSeat(int n) {
        return n == 1 ? 1 : 0.5;
    }
}

# 594. 最长和谐子序列

做复杂了

class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, int[]> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int[] def = new int[]{0, 0};
            int[] min = map.getOrDefault(nums[i]-1, def);
            int[] max = map.getOrDefault(nums[i]+1, def);
            int[] equal = map.getOrDefault(nums[i], def);
            int[] cur = new int[]{Math.max(min[1], equal[0])+1, Math.max(max[0], equal[1])+1};
            map.put(nums[i], cur);
            if (min[1] != 0 || max[0] != 0) {
                res = Math.max(res, Math.max(cur[0], cur[1]));
            }
        }
        return res == 1 ? 0 : res;
    }
}

计数即可

class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
        }
        for (Integer key : map.keySet()) {
            if (map.containsKey(key+1)) {
                res = Math.max(res, map.get(key)+map.get(key+1));
            }
        }
        return res;
    }
}

排序

class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int l = 0, r = 0, res = 0;
        while (r < nums.length) {
            while (nums[r]-nums[l] > 1) {
                l++;
            }
            if (nums[r]-nums[l] == 1){
                res = Math.max(res, r-l+1);
            }
            r++;
        }
        return res;
    }
}

# 559. N 叉树的最大深度

class Solution {
    int res = 0;
    public int maxDepth(Node root) {
        dfs(root, 0);
        return res;
    }

    private void dfs(Node node, int depth) {
        if (node == null) {
            res = Math.max(res, depth);
            return;
        }
        if (node.children.size() == 0) {
            res = Math.max(res, depth+1);
        }
        for (Node n : node.children) {
            dfs(n, depth+1);
        }
    }
}

更简洁

class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int res = 0;
        for (Node n : root.children) {
            res = Math.max(res, maxDepth(n));
        }
        return res+1;
    }
}

# 253. 会议室 II

优先队列

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if(intervals == null || intervals.length == 0) {
            return 0;
        }
        PriorityQueue<Integer> q = new PriorityQueue<>();
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        q.add(intervals[0][1]);
        for(int i = 1; i < intervals.length; i++){
            if(q.peek() <= intervals[i][0]){
                q.poll();
            } 
            q.add(intervals[i][1]);
        }
        return q.size();
    }
}

# 767. 重构字符串

class Solution {
    public String reorganizeString(String s) {
        StringBuilder res = new StringBuilder();
        int[] map = new int[26];
        for (char c : s.toCharArray()) {
            map[c-'a']++;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> map[b]-map[a]);
        for (int i = 0; i < 26; i++) {
            if (map[i] == 0) continue;
            pq.offer(i);
        }
        int last = -1;
        while (pq.size() > 1) {
            int first = pq.poll();
            int second = pq.poll();
            res.append((char) (first+'a'));
            res.append((char) (second+'a'));
            last = second;
            map[first]--;
            map[second]--;
            if (map[second] > 0) {
                pq.offer(first);
                pq.offer(second);
            } else if (map[first] > 0) {
                pq.offer(first);
            }
        }
        if (pq.size() > 0) {
            if (pq.peek() == last || map[pq.peek()] > 1) {
                return "";
            }
            res.append((char) (pq.poll()+'a'));
        }
        return res.toString();
    }
}

while中另一种写法

class Solution {
    public String reorganizeString(String s) {
        StringBuilder res = new StringBuilder();
        int[] map = new int[26];
        for (char c : s.toCharArray()) {
            map[c-'a']++;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> map[b]-map[a]);
        for (int i = 0; i < 26; i++) {
            if (map[i] == 0) continue;
            pq.offer(i);
        }
        int last = -1;
        while (!pq.isEmpty()) {
            if (pq.peek() == last) {
                return "";
            }
            int first = pq.poll();
            res.append((char) (first+'a'));
            last = first;
            map[first]--;
            if (!pq.isEmpty()) {
                int second = pq.poll();
                res.append((char) (second+'a'));
                last = second;
                map[second]--;
                if (map[second] > 0) {
                    pq.offer(first);
                    pq.offer(second);
                } else if (map[first] > 0) {
                    pq.offer(first);
                }
                continue;
            }
            if (map[first] > 0) {
                pq.offer(first);
            }
        }
        return res.toString();
    }
}

# 859. 亲密字符串

class Solution {
    public boolean buddyStrings(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;
        }
        int[] map = new int[26];
        if (s.equals(goal)) {
            for (int i = 0; i < s.length(); i++) {
                map[s.charAt(i)-'a']++;
                if (map[s.charAt(i)-'a'] > 1) {
                    return true;
                }
            }
            return false;
        } else {
            int first = -1, second = -1;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) != goal.charAt(i)) {
                    if (first == -1) {
                        first = i;
                    } else if (second == -1) {
                        second = i;
                    } else {
                        return false;
                    }
                }
            }
            return second != -1 && s.charAt(first) == goal.charAt(second) && s.charAt(second) == goal.charAt(first);
        }
    }
}

# 358. K 距离间隔重排字符串

class Solution {
    public String rearrangeString(String s, int k) {
        if (k == 0) return s;
        int[] map = new int[26];
        for (char c : s.toCharArray()) {
            map[c-'a']++;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
            if (map[b]-map[a] == 0) {
                return a-b;
            } else {
                return map[b]-map[a];
            }
        });
        StringBuilder res = new StringBuilder();
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if (map[i] > 0) {
                pq.offer(i);
            }
        }
        while (pq.size() >= k) {
            int kk = k;
            while (q.size() < k) {
                int cur = pq.poll();
                kk--;
                res.append((char) (cur+'a'));
                map[cur]--;
                q.offer(cur);
            }
            while (!q.isEmpty()) {
                int cur = q.poll();
                if (map[cur] > 0) {
                    pq.offer(cur);
                }
            }
            
        }
        while (pq.size() > 0) {
            int cur = pq.poll();
            if (map[cur] > 1) {
                return "";
            }
            res.append((char) (cur+'a'));
        }
        
        return res.toString();
    }
}

# 423. 从英文中重建数字

class Solution {
    String[] digit = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    int[] priority = new int[]{0, 8, 6, 3, 2, 7, 5, 9, 4, 1};
    public String originalDigits(String s) {
        int[] map = new int[26];
        for (char c : s.toCharArray()) {
            map[c-'a']++;
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < priority.length;) {
            boolean ok = true;
            for (char c : digit[priority[i]].toCharArray()) {
                if (map[c-'a'] <= 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                for (char c : digit[priority[i]].toCharArray()) {
                    map[c-'a']--;
                }
                res.append(priority[i]);
            } else {
                i++;
            }
        }
        char[] cs = res.toString().toCharArray();
        Arrays.sort(cs);
        return new String(cs);
    }
}

# 700. 二叉搜索树中的搜索

递归

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) return root;
        return val > root.val ? searchBST(root.right, val) : searchBST(root.left, val);
    }
}

# 519. 随机翻转矩阵

随机后，如果已随机过，从当前位置向两边搜索

class Solution {
    Set<Integer> set = new HashSet<>();
    Random random = new Random();
    int m;
    int n;
    public Solution(int m, int n) {
        this.m = m;
        this.n = n;
    }
    
    public int[] flip() {
        int l = random.nextInt(n*m), r = l;
        while (l > 0 && set.contains(l)) l--;
        while (r <= n*m && set.contains(r)) r++;
        int res = 0;
        if (!set.contains(l)) {
            set.add(l);
            res = l;
        } else if (!set.contains(r)) {
            set.add(r);
            res = r;
        }
        return new int[]{res/n, res%n};
    }
    
    public void reset() {
        set.clear();
    }
}

map记录位置，随机区间缩小

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int m, n, r;
    Random random = new Random();
    public Solution(int m, int n) {
        this.m = m;
        this.n = n;
        this.r = m*n;
    }
    
    public int[] flip() {
        int c = random.nextInt(r--);
        int res = map.getOrDefault(c, c);
        map.put(c, map.getOrDefault(r, r));
        return new int[] {res/n, res%n};
    }
    
    public void reset() {
        map.clear();
        r = m*n;
    }
}

# 593. 有效的正方形

正方形四个点有两条线，只有两种长度

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        Set<Integer> set = new HashSet<>();
        set.add(dist(p1, p2));
        set.add(dist(p1, p3));
        set.add(dist(p1, p4));
        set.add(dist(p2, p3));
        set.add(dist(p2, p4));
        set.add(dist(p3, p4));
        return !set.contains(0) && set.size() == 2;
    }

    private int dist(int[] a, int[] b) {
        return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]);
    }
}

# 786. 第 K 个最小的素数分数

优先队列

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)-> {
            return arr[a[0]]*arr[b[1]]-arr[a[1]]*arr[b[0]];
        });
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            pq.offer(new int[]{0, i});
        }
        int[] res = null;
        for (int i = 0; i < k; i++) {
            res = pq.poll();
            if (res[0] < res[1]-1) {
                int[] p = new int[]{res[0]+1, res[1]};
                pq.offer(p);
            }
        }
        return new int[]{arr[res[0]], arr[res[1]]};
    }
}

# 400. 第 N 位数字

模拟

class Solution {
    public int findNthDigit(int n) {
        if (n < 10) return n;
        int d = 1;
        long start = 9;
        for (; d < 100; d++) {
            if (n < d*start) {
                start /= 10;
                break;
            }
            n -= (start*d);
            start *= 10;
        }
        int s = (int)Math.pow(10, d-1);
        s += (n/d-1) + ((n%d>0)?1:0);
        int p = (n%d==0?d:(n%d));
        String str = String.valueOf(s);
        return Integer.valueOf(str.substring(p-1, p));
    }
}

# 1446. 连续字符

class Solution {
    public int maxPower(String s) {
        int cnt = 1;
        int max = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i-1)) {
                cnt++;
            } else {
                cnt = 1;
            }
            max = Math.max(max, cnt);
        }
        return max;
    }
}

# 759. 员工空闲时间

优先队列

class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> res = new ArrayList<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
             return schedule.get(a[0]).get(a[1]).start-schedule.get(b[0]).get(b[1]).start;
        });
        for (int i = 0; i < schedule.size(); i++) {
            pq.offer(new int[]{i, 0});
        }
        int pre = -1;
        while (!pq.isEmpty()) {
            int[] t = pq.poll();
            Interval poll = schedule.get(t[0]).get(t[1]);
            if (poll.start > pre) {
                res.add(new Interval(pre, poll.start));
            }
            if (poll.end > pre) {
                pre = poll.end;
            }
            if (t[1]+1 < schedule.get(t[0]).size()) {
                pq.offer(new int[]{t[0], t[1]+1});
            }
        }
        res.remove(0);
        return res;
    }
}

# 729. 我的日程安排表 I

有序列表

class MyCalendar {
    TreeMap<Integer, Integer> map;
    public MyCalendar() {
        map = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> left = map.floorEntry(start);
        Map.Entry<Integer, Integer> right = map.ceilingEntry(start);
        if (left != null) {
            if (start <= left.getKey() || start < left.getValue()) {
                return false;
            }
        }
        if (right != null) {
            if (start >= right.getKey() || end > right.getKey()) {
                return false;
            }
        }
        map.put(start, end);
        return true;
    }
}

# 506. 相对名次

class Solution {
    public String[] findRelativeRanks(int[] score) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < score.length; i++) {
            map.put(score[i], i);
        }
        Arrays.sort(score);
        String[] res = new String[score.length];
        int n = score.length;
        for (int i = n-1; i >= 0; i--) {
            String name = null;
            if (i == n-1) {
                name = "Gold Medal";
            } else if (i == n-2) {
                name = "Silver Medal";
            } else if (i == n-3) {
                name = "Bronze Medal";
            } else {
                name = String.valueOf(n-i);
            }
            res[map.get(score[i])] = name;
        }
        return res;
    }
}

# 1606. 找到处理最多请求的服务器

有序列表+优先队列 模拟一遍过程，发现进来一个新请求时先看i%k的服务器是否空闲，非空闲则继续往后查看是否空闲即可。 需要算法支持： 1.某一个请求来的时间点上，将所有该时间点之前能处理完的服务器置为空闲（优先队列） 2.快速找到后面空闲的服务器（有序列表）

class Solution {
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
            return a[0]-b[0];
        });
        Map<Integer, int[]> map = new HashMap<>();
        TreeMap<Integer, int[]> tree = new TreeMap<>();
        for (int i = 0; i < k; i++) {
//             {time, i, cnt}
            int[] obj = new int[]{0, i, 0};
            map.put(i, obj);
            tree.put(i, obj);
        }
        for (int i = 0; i < arrival.length; i++) {
            while (!pq.isEmpty() && pq.peek()[0] <= arrival[i]) {
                int[] cur = pq.poll();
                tree.put(cur[1], cur);
            }
            Map.Entry<Integer, int[]> entry = tree.ceilingEntry(i%k);
            if (entry == null) {
                entry = tree.ceilingEntry(0);
            }
            if (entry != null) {
                int[] cur = entry.getValue();
                cur[0] = arrival[i]+load[i];
                cur[2]++;
                pq.offer(cur);
                tree.remove(entry.getKey());
            }
        }
        int max = 0;
        List<Integer> res = new ArrayList<>();
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            if (entry.getValue()[2] > max) {
                max = entry.getValue()[2];
                res.clear();
                res.add(entry.getKey());
            } else if (entry.getValue()[2] == max) {
                res.add(entry.getKey());
            }

        }
        return res;
    }
}

# 1005. K 次取反后最大化的数组和

简单题，但是做法复杂了，导致实现时用时过长

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (k > 0) {
                if (nums[i] < 0) {
                    res += (-nums[i]);
                    k--;
                } else {
                    if (k % 2 == 0) {
                        res += nums[i];
                    } else {
                        if (i > 0 && nums[i] > (-nums[i-1])) {
                            res = res + nums[i-1] + nums[i-1] + nums[i];
                        } else {
                            res += (-nums[i]);
                        }
                    }
                    k = 0;
                }
            } else {
                res += nums[i];
            }
        }
        if (k != 0 && k % 2 == 1) {
            int n = nums.length;
            res = res + nums[n-1] + nums[n-1];
        }
        return res;
    }
}

# 336. 回文对

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            Integer ii = map.get(reverse(word));
            if (ii != null && ii != i) {
                res.add(Arrays.asList(ii, i));
            }
            int end = word.length();
            for (int k = 0; k <= end; k++) {
                String left = "";
                if (k > 0) {
                    left = word.substring(0, k);
                }
                String right = "";
                if (k != end) {
                    right = word.substring(k, end);
                }
                if (check(left)) {
                    Integer index = map.get(reverse(right));
                    if (index != null) {
                        res.add(Arrays.asList(index, i));
                    }
                }
                if (check(right)) {
                    Integer index = map.get(reverse(left));
                    if (index != null) {
                        res.add(Arrays.asList(i, index));
                    }
                }
            }
           
        }
        return  res;
    }

    private String reverse(String word) {
        StringBuilder str = new StringBuilder(word);
        return str.reverse().toString();
    }

    private boolean check(String word) {
        int l = 0, r = word.length()-1;
        if (l > r) return false;
        while (l < r) {
            if (word.charAt(l) != word.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

# 1858. 包含所有前缀的最长单词

class Solution {
    public String longestWord(String[] words) {
        root = new TrieNode();
        for (String word : words) {
            insert(word);
        }
        int max = 0;
        String res = "";
        for (String word : words) {
            if (search(word) && word.length() >= max) {
                if (word.length() > max || word.compareTo(res) < 0) {
                    max = word.length();
                    res = word;
                }
            }
        }
        return res;
    }

    class TrieNode {
        boolean end;
        TrieNode[] tns = new TrieNode[26];
    }

    TrieNode root;

    private void insert(String word) {
        TrieNode p = root;
        for (char w : word.toCharArray()) {
            int u = w-'a';
            if (p.tns[u] == null) p.tns[u] = new TrieNode();
            p = p.tns[u];
        }
        p.end = true;
    }

    private boolean search(String word) {
        TrieNode p = root;
        for (char w : word.toCharArray()) {
            int u = w-'a';
            if (p.tns[u] == null || !p.tns[u].end) return false;
            p = p.tns[u];
        }
        return true;
    }
}

# 372. 超级次方

class Solution {
    int mod = 1337;
    public int superPow(int a, int[] b) {
        return dfs(a, b, b.length-1);
    }

    private int dfs(int a, int[] b, int n) {
        if (n == -1) return 1;
        return quickPow(dfs(a, b, n-1), 10) * quickPow(a, b[n]) % mod;
    }

    private int quickPow(int a, int b) {
        int ans = 1;
        a %= mod;
        while (b != 0) {
            if ((b&1) != 0) {
                ans = ans * a % mod;
            }
            a = a * a % mod;
            b >>= 1;
        }
        return ans;
    }
}

# 1816. 截断句子

class Solution {
    public String truncateSentence(String s, int k) {
        int i = 0, n = s.length();
        for (; i <= n && k > 0; i++) {
            if (i == n || s.charAt(i) == ' ') {
                k--;
            }
        }
        return s.substring(0, i-1);
    }
}

# 1034. 边界着色

dfs

class Solution {
    int[][] grid;
    int[][] dir = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    int row;
    int col;
    boolean[][] vis;
    int color;
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        this.grid = grid;
        this.row = grid.length;
        this.col = grid[0].length;
        vis = new boolean[this.row][this.col];
        this.color = color;
        dfs(row, col, grid[row][col]);
        return grid;
    }

    private void dfs(int r, int c, int original) {
        if (r < 0 || r >= row || c < 0 || c >= col) return;
        vis[r][c] = true;
        for (int i = 0; i < 4; i++) {
            int nr = r+dir[i][0];
            int nc = c+dir[i][1];
            if (nr < 0 || nr >= row || nc < 0 || nc >= col || (!vis[nr][nc] && grid[nr][nc] != original)) {
                grid[r][c] = color;
                continue;
            }
            if (vis[nr][nc]) continue;
            dfs(nr, nc, original);
        }
    }
}

# 1756. 设计最近使用（MRU）队列

class MRUQueue {
    MTree tree;
    int[] val;
    int end;
    public MRUQueue(int n) {
        tree = new MTree(n);
        val = new int[n+4000];
        end = n;
        for (int i = 1; i <= end; i++) {
            val[i] = i;
        }
    }
    
    public int fetch(int k) {
        int l = 1, r = end;
        while (l < r) {
            int m = (l+r) >> 1;
            if (m - tree.query(m) >= k) {
                r = m;
            } else {
                l = m+1;
            }
        }
        val[++end] = val[l];
        tree.update(l);
        return val[l];
    }

    class MTree {
        int[] t;
        MTree(int n) {
            t = new int[n+4000];
        }
        public int lowbit(int x) {
            return x & (-x);
        }

        public void update(int i) {
            while (i < t.length) {
                t[i] += 1;
                i += lowbit(i);
            }
        }

        public int query(int i) {
            int res = 0;
            while (i > 0) {
                res += t[i];
                i -= lowbit(i);
            }
            return res;
        }
    }
}

# 689. 三个无重叠子数组的最大和

递归，超时了

class Solution {
    int k;
    int max = 0;
    List<Integer> maxPath = null;
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        this.k = k;
        int[] pre = new int[nums.length-k+1];
        for (int i = 0; i < k; i++) {
            pre[0] += nums[i];
        }
        for (int i = 1; i < pre.length; i++) {
            pre[i] = pre[i-1]-nums[i-1]+nums[i+k-1];
        }
        dfs(pre, 0, 0, 0, new ArrayList<>());
        int[] res = new int[3];
        int i = 0;
        for (int p : maxPath) {
            res[i++] = p;
        }
        return res;
    }

    private void dfs(int[] pre, int start, int sum, int cnt, List<Integer> path) {
        if (cnt >= 3) {
            if (sum > max) {
                max = sum;
                maxPath = new ArrayList<>(path);
            }
            return;
        }
        for (int i = start; i < pre.length; i++) {
            path.add(i);
            dfs(pre, i+k,  sum+pre[i], cnt+1, path);
            path.remove(path.size()-1);
        }
    }
}

正确解法

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] sum = new int[nums.length-k+1];
        for (int i = 0; i < k; i++) {
            sum[0] += nums[i];
        }
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i-1]-nums[i-1]+nums[i+k-1];
        }

        int n = sum.length;
        int max = 0;
        int index = 0;
        int[] left = new int[n];
        for (int i = 0; i < n; i++) {
            if (sum[i] > max) {
                max = sum[i];
                index = i;
            }
            left[i] = index;
        }

        max = 0;
        index = n-1;
        int[] right = new int[n];
        for (int i = n-1; i >= 0; i--) {
            if (sum[i] >= max) {
                max = sum[i];
                index = i;
            }
            right[i] = index;
        }

        max = 0;
        int[] res = null;
        for (int i = k; i < n-k; i++) {
            int v = sum[left[i-k]] + sum[i] + sum[right[i+k]];
            if (v > max) {
                max = v;
                res = new int[]{left[i-k], i, right[i+k]};
            }
        }
        return res;
    }
}

# 794. 有效的井字游戏

class Solution {
    public boolean validTicTacToe(String[] board) {
        int xcnt = 0, ocnt = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                char c = board[i].charAt(j);
                if (c == 'X') {
                    xcnt++;
                } else if (c == 'O') {
                    ocnt++;
                }
            }
        }
        if (xcnt < ocnt || xcnt - ocnt > 1) return false;
        int xwin = win(board, 'X');
        int owin = win(board, 'O');
        if (xwin > 0 && owin > 0) return false;
        if (xwin > 0 &&  xcnt - ocnt != 1) return false;
        if (owin > 0 && xcnt != ocnt) return false;
        return true;
    }

    private int win(String[] board, char c) {
        int cnt = 0;
        for (int i = 0; i < 3; i++) {
            int scnt = 0;
            for (int j = 0; j < 3; j++) {
                if (board[i].charAt(j) == c) {
                    scnt++;
                }
            }
            if (scnt == 3) {
                cnt++;
            }
        }

        for (int i = 0; i < 3; i++) {
            int scnt = 0;
            for (int j = 0; j < 3; j++) {
                if (board[j].charAt(i) == c) {
                    scnt++;
                }
            }
            if (scnt == 3) {
                cnt++;
            }
        }

        int upcnt = 0;
        for (int i = 0; i < 3; i++) {
            if (board[i].charAt(i) == c) {
                upcnt++;
            }
        }
        if (upcnt == 3) cnt++;

        int dcnt = 0;
        for (int i = 0; i < 3; i++) {
            if (board[i].charAt(2-i) == c) {
                dcnt++;
            }
        }
        if (dcnt == 3) cnt++;

        return cnt;
    }
}

# 709. 转换成小写字母

class Solution {
    public String toLowerCase(String s) {
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] >= 65 && cs[i] <= 90) {
                cs[i] = (char) (cs[i]+32);
            }
        }
        return new String(cs);
    }
}

# 642. 设计搜索自动补全系统

class AutocompleteSystem {
    TrieNode root;
    String st = "";
    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        for (int i = 0; i < sentences.length; i++) {
            insert(sentences[i], times[i]);
        }
    }
    
    public List<String> input(char c) {
        if (c == '#') {
            insert(st, 1);
            st = "";
            return new ArrayList<>();
        }
        st += c;
        return search(st);
    }

    class TrieNode {
        boolean end = false;
        TrieNode[] tns = new TrieNode[27];
        int cnt = 0;
        String st;
    }
    
    private void insert(String word, int cnt) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            char w = word.charAt(i);
            int u = w == ' ' ? 26 : w-'a';
            if (p.tns[u] == null) p.tns[u] = new TrieNode();
            p = p.tns[u];
        }
        p.end = true;
        p.cnt += cnt;
        p.st = word;
    }

    private List<String> search(String word) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            char w = word.charAt(i);
            int u = w == ' ' ? 26 : w-'a';
            if (p.tns[u] == null) return new ArrayList<>();
            p = p.tns[u];
        }
        List<Node> res = new ArrayList<>();
        dfs(p, res);
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b)->{
            if (a.cnt == b.cnt) {
                return a.st.compareTo(b.st);
            } else {
                return b.cnt-a.cnt;
            }
        });
        for (Node n : res) {
            pq.offer(n);
        }
        List<String> ans = new ArrayList<>();
        int k = 0;
        while (!pq.isEmpty() && k < 3) {
            ans.add(pq.poll().st);
            k++;
        }
        return ans;
    }

    private void dfs(TrieNode p, List<Node> list) {
        if (p == null) return;
        if (p.end) list.add(new Node(p.st, p.cnt));
        for (TrieNode next : p.tns) {
            if (next == null) continue;
            dfs(next, list);
        }
    }

    class Node {
        String st;
        int cnt;
        public Node(String st, int cnt) {
            this.st = st;
            this.cnt = cnt;
        }
        public String toString() {
            return "{"+st+","+cnt+"}";
        }
    }
}

# 807. 保持城市天际线

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int r = grid.length;
        int c = grid[0].length;
        int[] row = new int[r];
        int[] col = new int[c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                row[i] = Math.max(row[i], grid[i][j]);
                col[j] = Math.max(col[j], grid[i][j]);
            }
        }
        int res = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                res += (Math.min(row[i], col[j])-grid[i][j]);
            }
        }
        return res;
    }
}

# 630. 课程表 III

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a,b)->{
            return a[1]-b[1];
        });
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
            return b[0]-a[0];
        });
        int time = 0;
        for (int i = 0; i < courses.length; i++) {
            if (time+courses[i][0] <= courses[i][1]) {
                pq.offer(courses[i]);
                time += courses[i][0];
            } else if (!pq.isEmpty() && pq.peek()[0] > courses[i][0]) {
                time = time - pq.poll()[0] + courses[i][0];
                pq.offer(courses[i]);
            }
        }
        return pq.size();
    }
}

# 851. 喧闹和富有

class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] r : richer) {
            adj[r[1]].add(r[0]);
        }
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        for (int i = 0; i < n; i++) {
            dfs(adj, quiet, ans, i);
        }
        return ans;
    }

    private void dfs(List<Integer>[] adj, int[] quiet, int[] ans, int index) {
        if (ans[index] != -1) {
            return;
        }
        ans[index] = index;
        for (int i : adj[index]) {
            dfs(adj, quiet, ans, i);
            if (quiet[ans[i]] < quiet[ans[index]]) {
                ans[index] = ans[i];
            }
        }
    }
}

# 997. 找到小镇的法官

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] visited = new int[n+1];
        for (int i = 0; i < trust.length; i++) {
            visited[trust[i][0]]--;
            visited[trust[i][1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (visited[i] == n-1) {
                return i;
            }
        }
        return -1;
    }
}

# 1518. 换酒问题

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int cnt = numBottles / (numExchange-1);
        return (numBottles % (numExchange-1)) == 0 ? numBottles+cnt-1 : numBottles+cnt;
    }
}

# 475. 供暖器

将houses存入treeSet中，排序heaters，遍历heaters，每两个供暖器距离的中间值mid，找到mid靠左和靠右的最近的house，当前house时便是供暖器应该辐射的范围，取两者的最大值，在跟所有的最大值求最大即可

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        TreeSet<Integer> tree = new TreeSet<>();
        for (int h : houses) {
            tree.add(h);
        }
        int res = 0;
        Integer first = tree.first();
        if (first != null && first < heaters[0]) {
            res = heaters[0]-first;
        }

        Integer last = tree.last();
        if (last != null && last > heaters[heaters.length-1]) {
            res = Math.max(res, last-heaters[heaters.length-1]);
        }

        int pre = heaters[0];
        int mid = 0;
        int mid2 = 0;
        for (int i = 1; i < heaters.length; i++) {
            int h = heaters[i];
            mid = (pre + h) / 2;
            mid2 = ((pre+h)%2) != 0 ? mid+1 : mid;
            // left
            int left = 0;
            Integer rl = tree.floor(mid);
            if (rl != null && rl > pre) {
                left = rl-pre;
            }

            // right
            int right = 0;
            Integer rc = tree.ceiling(mid2);
            if (rc != null && rc < h) {
                right = h-rc;
            }
//            System.out.println("mid:"+mid+"; mid2:"+mid2+"; left:"+left+"; right:"+right);
            res = Math.max(res, Math.max(left, right));
            pre = h;
        }
        
        return res;
    }
}

根据题解方式，使用二分，借助treeSet，将heaters存入；遍历houses时，去搜索heaters是否存在最近的供暖器。

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        TreeSet<Integer> tree = new TreeSet<>();
        for (int h : heaters) {
            tree.add(h);
        }
        int N = Integer.MAX_VALUE;
        int res = 0;
        for (int h : houses) {
            int min = N;
            Integer floor = tree.floor(h);
            if (floor != null) {
                min = h-floor;
            }
            Integer ceiling = tree.ceiling(h);
            if (ceiling != null) {
                min = Math.min(min, ceiling-h);
            }
            res = Math.max(res, min);
        }
        return res;
    }
}

排序+双指针

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int i = 0, j = 0;
        int res = Integer.MIN_VALUE;
        while (i < houses.length) {
            if (houses[i] <= heaters[j]) {
                res = Math.max(res, heaters[j]-houses[i]);
                i++;
            } else {
                if (j+1 < heaters.length && Math.abs(heaters[j+1]-houses[i]) <= Math.abs(houses[i]-heaters[j])) {
                    j++;
                } else {
                    res = Math.max(res, houses[i]-heaters[j]);
                    i++;
                }
            }
        }
        return res;
    }
}

# 1154. 一年中的第几天

class Solution {
    static int[] mouth = new int[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    public int dayOfYear(String date) {
        String[] ds = date.split("-");
        int cnt = 0;
        int mm = Integer.valueOf(ds[1]);
        for (int i = mm-1; i >= 1; i--) {
            cnt += mouth[i-1];
        }
        int yy = Integer.valueOf(ds[0]);
        int dd = Integer.valueOf(ds[2]);
        if ((yy%4==0 && yy%100!=0) || yy%400==0) {
            if (mm > 2) {
                cnt++;
            }
        }
        return cnt+dd;
    }
}

# 686. 重复叠加字符串匹配

暴力解，超时

class Solution {
    public int repeatedStringMatch(String a, String b) {
        int cnt = 1;
        String aa = a;
        while (aa.length() <= b.length()*100) {
            if (aa.indexOf(b) != -1) return cnt;
            cnt++;
            aa = aa + a;
        }
        return -1;
    }
}

找到复制次数的上下界

class Solution {
    public int repeatedStringMatch(String a, String b) {
        int cnt = 0;
        StringBuilder aa = new StringBuilder();
        while (aa.length() < b.length()) {
            cnt++;
            aa.append(a);
        }
        aa.append(a);
        int index = aa.indexOf(b);
        if (index != -1) {
            return index+b.length() > a.length()*(cnt) ? cnt+1 : cnt;
        }
        return -1;
    }
}

# 1044. 最长重复子串

二分法+字符串哈希

class Solution {
    public String longestDupSubstring(String s) {
        int n = s.length();
        long[] h = new long[n+1];
        long[] p = new long[n+1];
        int P = 131; // 通常131不行就尝试1313131
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            h[i] = h[i-1]*P + (s.charAt(i-1)-'a');
            p[i] = p[i-1]*P;
        }
        
        String ans = "";
        int l = 0, r = n;
        while (l < r) {
            int len = l + ((r-l+1)>>1);
            String res = check(s, h, p, len);
            if (res.length() != 0) {
                l = len;
                ans = res.length() > ans.length() ? res : ans;
            } else {
                r = len-1;
            }
        }
        return ans;
    }

    private String check(String s, long[] h, long[] p, int len) {
        String res = "";
        Set<Long> set = new HashSet<>();
        for (int i = 1; i <= s.length()-len+1; i++) {
            long cur = h[i+len-1] - h[i-1]*p[len];
            if (!set.add(cur)) {
                res = s.substring(i-1, i+len-1);
                break;
            }
        }
        return res;
    }
}

# 1705. 吃苹果的最大数目

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->{
            int da = a+days[a], db = b+days[b];
            if ((da)==(db)) {
                return apples[a]-apples[b];
            } else {
                return da-db;
            }
        });

        int d = 0, a = 0, n = apples.length;
        while (!pq.isEmpty() || d < n) {
            if (d < n && (apples[d] != 0 && days[d] != 0)) {
                pq.offer(d);
            }
            int minus = 1;
            while (minus > 0 && !pq.isEmpty()) {
                int poll = pq.peek();
                if (poll+days[poll] <= d || apples[poll] <= 0) {
                    pq.poll();
                    continue;
                } else {
                    apples[poll]--;
                }
                minus--;
            }
            if (minus != 1) {
                a++;
            }
            d++;
        }
        return a;
    }
}

# 1609. 奇偶树

class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        boolean odd = false;
        while (!q.isEmpty()) {
            int sz = q.size();
            int pre = -1;
            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();
                if (odd) {
                    if (cur.val % 2 != 0) return false;
                    if (pre != -1 && cur.val >= pre) return false;
                } else {
                    if (cur.val % 2 == 0) return false;
                    if (pre != -1 && cur.val <= pre) return false;
                }
                pre = cur.val;
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
            odd = !odd;
        }
        return true;
    }
}

# 1078. Bigram 分词

class Solution {
    public String[] findOcurrences(String text, String first, String second) {
        String[] words = text.split(" ");
        int i = 0, n = words.length-2;
        List<String> res = new ArrayList<>();
        while (i < n) {
            if (first.equals(words[i]) && second.equals(words[i+1])) {
                res.add(words[i+2]);
            }
            i++;
        }
        return res.toArray(new String[res.size()]);
    }
}

# 825. 适龄的朋友

排序+二分，比较慢

class Solution {
    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int cnt = 0;
        for (int i = 0; i < ages.length; i++) {
            int edge = (int) (ages[i]*0.5+7);
            cnt += binarySearch(ages, 0, i-1, edge);
            cnt += binarySearch2(ages, i+1, ages.length-1, ages[i], edge);
        }
        return cnt;
    }

    private int binarySearch(int[] ages, int l, int r, int edge) {
        int right = r;
        if (r < 0 || ages[r] <= edge) return 0;
        while (l < r) {
            int mid = l + ((r-l)>>1);
            if (ages[mid] > edge) {
                r = mid;
            } else {
                l = mid+1;
            }
        }
        return right-r+1;
    }

    private int binarySearch2(int[] ages, int l, int r,int t, int edge) {
        int left = l;
        if (l >= ages.length || ages[l] != t || ages[l] <= edge) return 0;
        while (l < r) {
            int mid = l + ((r-l+1)>>1);
            if (ages[mid] == t) {
                l = mid;
            } else {
                r = mid-1;
            }
        }
        return l-left+1;
    }
}

排序+双指针

class Solution {
    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int l = 0, r = 0, n = ages.length;
        int cnt = 0;
        for (int a : ages) {
            if (a < 15) continue;
            int e = (int) (a*0.5+7);
            while (ages[l] <= e) {
                l++;
            }
            while (r+1 < n && ages[r+1] <= a) {
                r++;
            }
            cnt += r-l;
        }
        return cnt;
    }
}

计数排序+前缀和

class Solution {
    public int numFriendRequests(int[] ages) {
        int[] cnt = new int[121];
        for (int a : ages) {
            cnt[a]++;
        }
        int[] pre = new int[121];
        for (int i = 1; i < 121; i++) {
            pre[i] = pre[i-1]+cnt[i];
        }
        int ans = 0;
        for (int i = 15; i < 121; i++) {
            if (cnt[i] == 0) continue;
            ans += (pre[i]-pre[(int) (i*0.5+7)]-1)*cnt[i];
        }
        return ans;
    }
}

# 472. 连接词

# 1995. 统计特殊四元组

class Solution {
    public int countQuadruplets(int[] nums) {
        int n = nums.length;
        int cnt = 0;
        for (int a = 0; a < n; a++) {
            for (int b = a+1; b < n; b++) {
                for (int c = b+1; c < n; c++) {
                    for (int d = c+1; d < n; d++) {
                        if (nums[a]+nums[b]+nums[c] == nums[d]) {
                            cnt++;
                        }
                    }
                }
            }
        }
        return cnt;
    }
}

# 846. 一手顺子

排序+贪心

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        int n = hand.length;
        if (n % groupSize != 0) return false;
        Arrays.sort(hand);
        int index = 0;
        while (index < n) {
            if (hand[index] == -1) {
                index++;
                continue;
            }
            int left = index;
            int cnt = groupSize;
            int right = left+1;
            while (right < n && cnt > 1) {
                if (hand[right] == -1 || hand[right] == hand[left]) {
                    right++;
                    continue;
                }
                if (hand[right] != hand[left]+1) {
                    return false;
                }
                hand[left] = -1;
                left = right;
                right++;
                cnt--;
                if (cnt <= 1) hand[left] = -1;
            }
            if (cnt > 1) return false;
            index++;
        }
        return true;
    }
}

# 1296. 划分数组为连续数字的集合

同846. 一手顺子

# 507. 完美数

纯暴力解

class Solution {
    public boolean checkPerfectNumber(int num) {
        int sum = 0;
        int index = 1;
        while (index < num) {
            if (num % index == 0) {
                sum += index;
            }
            if (sum > num) return false;
            index++;
        }
        return sum == num;
    }
}

规律：如果有一个因子d小于根号num，则一定有一个因子等于num/d

class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num == 1) return false;
        int sum = 1;
        for (int i = 2; i*i <= num; i++) {
            if (num % i == 0) {
                sum += i;
                if (i*i != num) {
                    sum += num/i;
                }
            }
        }
        return sum == num;
    }
}
修改于: 8/15/2022, 5:02:01 PM

← LeetCode 2022 →