5月31日

4的幂

class Solution {
    public boolean isPowerOfFour(int n) {
        // 0x2aaaaaaa也可以，因为n是有符号的32位整数
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
}

5月30日🥗

2 的幂⭐

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n == 0) return false;
        long b = (long) n;
        return (b & (b - 1)) == 0;
    }
}

二叉树中的最大路径和⭐

⚡ 递归

class Solution {
    int ans;
    public int maxPathSum(TreeNode root) {
        ans = Integer.MIN_VALUE;
        maxGain(root);
        return ans;
    }

    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        // 获取左右节点的最大贡献值
        int leftVal = Math.max(maxGain(node.left), 0);
        int rightVal = Math.max(maxGain(node.right), 0);
        // 当前节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int currentVal = node.val + leftVal + rightVal;
        // 更新答案
        ans = Math.max(ans, currentVal);
        // 返回最大贡献值
        return node.val + Math.max(leftVal, rightVal);
    }
}

最小面积矩形

⚡ 枚举对角线

class Solution {
    static int N = 40001;
    public int minAreaRect(int[][] points) {
        Set<Integer> set = new HashSet<>();
        for (int[] p : points) set.add(p[0] * N + p[1]);
        int n = points.length;
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++ i) {
            for (int j = i + 1; j < n; ++ j) {
                if (points[i][0] != points[j][0] && points[i][1] != points[j][1]) {
                    if (set.contains(points[i][0] * N + points[j][1]) && set.contains(points[j][0] * N + points[i][1])) {
                        ans = Math.min(ans, Math.abs(points[i][0] - points[j][0]) * Math.abs(points[i][1] - points[j][1]));
                    }
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

5月29日

元素和为目标值的子矩阵数量⭐

⚡ 前缀和 & 压缩

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int cnt = 0;

        for (int i = 0; i < m; ++ i) {
            int[] pre = new int[n];
            for (int j = i; j < m; ++ j) {
                for (int k = 0; k < n; ++ k) {
                    pre[k] += matrix[j][k]; // 压缩为一维
                }
                cnt += subarraySum(pre, target);
            }
        }
        return cnt;
    }

    // 和为K的子数组数量
    private int subarraySum (int[] nums, int k) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>(){{
            put(0, 1);
        }};

        int pre = 0, cnt = 0;
        for (int i = 0; i < n; ++ i) {
            pre += nums[i];
            cnt += map.getOrDefault(pre - k, 0);
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return cnt;
    }
}

5月28日

汉明距离总和⭐

⚡ 逐位统计

class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 30; i >= 0; -- i) {
            int tmp = 0;
            for (int j = 0; j < n; ++ j) {
                tmp += (nums[j] >> i) & 1;
            }
            ans += tmp * (n - tmp);
        }
        return ans;
    }
}

5月27日

汉明距离

class Solution {
    public int hammingDistance(int x, int y) {
        int ans = 0, s = x ^ y;
        // Brian Kernighan 算法： 只需遍历 1
        while (s != 0) {
            s &= s - 1;
            ++ ans;
        }
        return ans;
    }
}

5月26日

反转每对括号间的子串

⚡ 栈O(n2)

class Solution {
    public String reverseParentheses(String s) {
        Deque<Character> stack = new LinkedList<>();
        Queue<Character> queue = new LinkedList<>();

        int n = s.length();
        for (int i = 0; i < n; ++ i) {
            if (s.charAt(i) == ')') {
                while (stack.peek() != '(') {
                    queue.offer(stack.pop());
                }
                stack.pop();
                while (!queue.isEmpty()) {
                    stack.push(queue.poll());
                }
            } else {
                stack.push(s.charAt(i));
            }
        }
        StringBuilder str = new StringBuilder();
        while (!stack.isEmpty()) {
            str.append(stack.pop());
        }
        return str.reverse().toString();
    }
}

⚡ 预处理 & 指针 O(n)

class Solution {
    public String reverseParentheses(String s) {
        Deque<Integer> stack = new LinkedList<>();
        int n = s.length();
        int[] pair = new int[n];
        for (int i = 0; i < n; ++ i) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else if (s.charAt(i) == ')'){
                pair[i] = stack.peek();
                pair[stack.pop()] = i;
            }
        }

        StringBuilder str = new StringBuilder();
        int step = 1, idx = 0;
        while (idx < n) {
            char ch = s.charAt(idx);
            if (ch == '(' || ch == ')') {
                idx = pair[idx];
                step = -step;
            } else {
                str.append(ch);
            }
            idx += step;
        }
        return str.toString();
    }
}

合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> x[0] - y[0]);
        List<int[]> list = new LinkedList<>();
        int l = intervals[0][0], r = intervals[0][1];
        for (int i = 1; i < intervals.length; ++ i) {
            if (r >= intervals[i][0]) {
                r = Math.max(r, intervals[i][1]);
            } else {
                list.add(new int[]{l, r});
                l = intervals[i][0];
                r = intervals[i][1];
            }
        }
        list.add(new int[]{l,r});

        int n = list.size();
        int[][] ans = new int[n][2];
        for (int i = 0; i < n; ++ i) {
            ans[i] = list.get(i);
        }
        return ans;
    }
}

数组中的第K个最大元素⭐

⚡ 随机数快排

class Solution {
    Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }

    public void quickSort(int[] nums, int start, int end) {
        if (start >= end) return;
        int l = start, r = end;
        int randIdx = random.nextInt(r - l + 1) + l;
        swap(nums, l, randIdx);
        int piovt = nums[l];
        while (l < r) {
            while (l < r && nums[r] >= piovt) -- r;
            if (l < r) nums[l] = nums[r];
            while (l < r && nums[l] <= piovt) ++ l;
            if (l < r) nums[r] = nums[l]; 
        }
        nums[l] = piovt;
        quickSort(nums, start, l - 1);
        quickSort(nums, l + 1, end);
    }

    private void swap (int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

二叉树的右视图

⚡ 层序遍历

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> q = new LinkedList<>();    
        q.offer(root);
        while (!q.isEmpty()) {
            int levelSize = q.size();
            for (int i = 1; i <= levelSize; ++ i) {
                TreeNode node = q.poll();
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
                if (i == levelSize) list.add(node.val);
            }
        }
        return list;
    }
}

5月25日

使所有区间的异或结果为零

跳跃游戏II

⚡ 贪心

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int step = 0;
        int end = 0;
        int maxPosition = 0;
        for (int i = 0; i < n - 1; ++ i) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                step ++;
            }
        }
        return step;
    }
}

类似题型：
LeetCode动态规划专题 - 跳跃游戏
LC-Weekly242 - 跳跃游戏VII

5月24日🥗

奇怪的打印机⭐

⚡ 区间dp

class Solution {
    public int strangePrinter(String s) {
        int n = s.length();
        // f[i][j]表示[i, j]的需要打印的最小次数
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; -- i) {
            f[i][i] = 1; // 边界条件
            for (int j = i + 1; j < n; ++ j) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i][j - 1];
                } else {
                    int min = Integer.MAX_VALUE;
                    for (int k = i; k < j; ++ k) {
                        min = Math.min(min, f[i][k] + f[k + 1][j]);
                    }
                    f[i][j] = min;
                }
            }
        }
        return f[0][n - 1];
    }
}

func strangePrinter(s string) int {
    n := len(s);
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n)
    }
    for i := n - 1; i >= 0; i -- {
        f[i][i] = 1
        for j := i + 1; j < n; j ++ {
            if s[i] == s[j] {
                f[i][j] = f[i][j - 1];
            } else {
                f[i][j] = math.MaxInt64
                for k := i; k < j; k ++ {
                    f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j])
                }
            }
        }
    }
    return f[0][n - 1];
}

func min (a, b int) int {
    if a > b {
        return b
    }
    return a
}

两数相除⭐

⚡ 二分 & 快速乘

class Solution {
    public int divide(int dividend, int divisor) {
        boolean sign = true;
        long x = dividend, y = divisor;
        if ((x > 0 && y < 0) || (x < 0 && y > 0))
            sign = false;
        if (x < 0) x = -x;
        if (y < 0) y = -y;
        long l = 0, r = x;
        while (l < r) {
            long mid = (l + r + 1) >> 1;
            if (mul(mid, y) > x) r = mid - 1;
            else l = mid;
        }
        l *= sign == true ? 1 : -1;
        // 越界处理
        if (l > Integer.MAX_VALUE || l < Integer.MIN_VALUE) l = Integer.MAX_VALUE;
        return (int)l;
    }

    // 快速乘模板
    private long mul (long a, long k) {
        long ans = 0;
        while (k > 0) {
            if ((k & 1) == 1) ans += a;
            k >>= 1;
            a += a;
        }
        return ans;
    }
}

在排序数组中查找元素的第一个和最后一个位置⭐

⚡ 二分 & 细节

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int left = binarySort(nums, target, true);
        int right = binarySort(nums, target, false) - 1;
        if (left <= right && right < n && nums[left] == target && nums[right] == target)
            return new int[]{left, right};
        return new int[]{-1, -1};
    }

    private int binarySort (int[] nums, int tar, boolean flag) {
        int l = 0, r = nums.length - 1;
        int ans = nums.length; // 关键
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > tar || (flag && nums[mid] == tar)) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}

搜索插入位置

⚡ 二分 - 模板题

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        int ans = n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) {
                r = mid - 1;
                ans = mid;
            }
            else l = mid + 1;
        }
        return ans;
    }
}

全排列

⚡ 回溯

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(nums, 0, list, ans);
        return ans;
    }

    private void dfs (int[] nums, int idx, List<Integer> list, List<List<Integer>> ans) {
        if (idx == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = idx; i < nums.length; ++ i) { 
            list.add(nums[i]);
            swap(nums, idx, i);
            dfs(nums, idx + 1, list, ans);
            list.remove(list.size() - 1);
            swap(nums, idx, i);
        }
    }

    private void swap (int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

⚡ 回溯优化

class Solution {
    boolean[] visited;
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        visited = new boolean[nums.length];
        dfs(nums, list, ans);
        return ans;
    }

    private void dfs (int[] nums, List<Integer> list, List<List<Integer>> ans) {
        if (list.size() == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; ++ i) {
            if (visited[i]) continue;
            list.add(nums[i]);
            visited[i] = true;
            dfs(nums, list, ans);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

全排列II⭐

⚡ 回溯

class Solution {
    boolean[] visited;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        visited = new boolean[nums.length];
        dfs(nums, list, ans);
        return ans;
    }

    private void dfs (int[] nums, List<Integer> list, List<List<Integer>> ans) {
        if (list.size() == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; ++ i) {
            if (visited[i] || (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1])) // 关键
                continue;
            list.add(nums[i]);
            visited[i] = true;
            dfs(nums, list, ans);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

5月23日

与数组中元素的最大异或值

⚡ Trie树

class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        int len = queries.length;
        int n = nums.length;
        int[][] queriesCopy = new int[len][3];
        for (int i = 0; i < len ; ++ i) {
            queriesCopy[i][0] = queries[i][0];
            queriesCopy[i][1] = queries[i][1];
            queriesCopy[i][2] = i;
        }
        Arrays.sort(queriesCopy, (x, y) -> x[1] - y[1]);
        Arrays.sort(nums);

        int[] ans =  new int[len];
        Trie trie = new Trie();
        int idx = 0;
        for (int[] query : queriesCopy) {
            while (idx < n && nums[idx] <= query[1]) {
                trie.insert(nums[idx ++]);
            }
            if (idx == 0) { // 字典树为空
                ans[query[2]] = -1;
            } else {
                ans[query[2]] = trie.getXorMax(query[0]);
            }
        }
        return ans;
    }
}

class Trie {
    TrieNode root;
    public Trie () {
        root = new TrieNode();
    }

    // 插入
    public void insert (int x) {
        TrieNode cur = root;
        for (int i = 30; i >= 0; -- i) {
            int tmp = (x >> i) & 1; 
            if (cur.sub[tmp] == null) {
                cur.sub[tmp] = new TrieNode();
            }
            cur = cur.sub[tmp];
        }
    }

    // 求x最大异或值
    public int getXorMax (int x) {
        TrieNode cur = root;
        int ans = 0;
        for (int i = 30; i >= 0; -- i) {
            int tmp = (x >> i) & 1;
            if (cur.sub[tmp ^ 1] != null) {
                ans = ans * 2 + 1;
                cur = cur.sub[tmp ^ 1];
            } else {
                ans = ans * 2;
                cur = cur.sub[tmp];
            }
        }
        return ans;
    }

    class TrieNode {
        TrieNode[] sub = new TrieNode[2];
    }
}

⚡ 加入限制的Trie树

class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        int len = queries.length;
        int n = nums.length;
        Trie trie = new Trie();
        for (int num : nums) {
            trie.insert(num);
        }
        int[] ans = new int[len];
        for (int i = 0; i < len; ++ i) {
            ans[i] =  trie.getXorMaxWithLimit(queries[i][0], queries[i][1]);
        }
        return ans;
    }
}

class Trie {
    TrieNode root;
    public Trie () {
        root = new TrieNode();
    }

    // 插入
    public void insert (int x) {
        TrieNode cur = root;
        cur.min = Math.min(cur.min, x);
        for (int i = 30; i >= 0; -- i) {
            int tmp = (x >> i) & 1; 
            if (cur.sub[tmp] == null) {
                cur.sub[tmp] = new TrieNode();
            }
            cur = cur.sub[tmp];
            cur.min = Math.min(cur.min, x);
        }
    }

    // 求x最大异或值 加入限制
    public int getXorMaxWithLimit (int x, int m) {
        TrieNode cur = root;
        if (m < cur.min) return -1;
        int ans = 0;
        for (int i = 30; i >= 0; -- i) {
            int tmp = (x >> i) & 1;
            if (cur.sub[tmp ^ 1] != null && cur.sub[tmp ^ 1].min <= m) {
                ans = ans * 2 + 1;
                cur = cur.sub[tmp ^ 1];
            } else {
                ans = ans * 2;
                cur = cur.sub[tmp];
            }
        }
        return ans;
    }

    class TrieNode {
        TrieNode[] sub = new TrieNode[2];
        int min;
        public TrieNode() {
            min = Integer.MAX_VALUE;
        }
    }
}

类似题型: 数组中两个数的最大异或值