lcp337

奇偶位数

方法一：暴力

class Solution {
    public int[] evenOddBit(int n) {
        int odd = 0, even = 0;
        String str = Integer.toBinaryString(n);
        StringBuilder sb = new StringBuilder(str);
        sb.reverse();
        str = sb.toString();
        for (int i = 0; i < str.length(); ++i) {
            char ch = str.charAt(i);
            if (ch == '1') {
                if (i % 2 == 0)
                    even++;
                else
                    odd++;
            }
        }
        return new int[]{even, odd};
    }
}

检查骑士巡视方案

方法一：dfs

class Solution {
    public boolean checkValidGrid(int[][] grid) {
        if (grid[0][0] != 0)
            return false;
        this.grid = grid;
        n = grid.length;
        return dfs(0, 0, 0);
    }

    private boolean dfs(int i, int j, int step) {
        if (step == n * n - 1)
            return grid[i][j] == n * n - 1;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] == step + 1 && dfs(row, col, step + 1))
                return true;
        }
        return false;
    }

    private boolean isValid(int row, int col) {
        return row >= 0 && col >= 0 && row < n && col < n;
    }

    int[][] grid, dirs = new int[][]{{-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {-2, 1}, {-1, 2}, {2, 1}, {1, 2}};
    int n;
}

美丽子集的数目

方法一：backtrack

不能用containsKey判断，数量为0就好！

class Solution {
    int ans = -1;
    Map<Integer, Integer> cnt = new HashMap<>();
    
    public int beautifulSubsets(int[] nums, int k) {
        dfs(nums, k, 0);
        return ans;
    }
    
    private void dfs(int[] nums, int k, int i) {
        if (i == nums.length) {
            ans++;
            return;
        }
        dfs(nums, k, i + 1);
        int x = nums[i];
        if (cnt.getOrDefault(x - k, 0) == 0 && cnt.getOrDefault(x + k, 0) == 0) {
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
            dfs(nums, k, i + 1);
            cnt.put(x, cnt.get(x) - 1);
        }
    }
}

执行操作后的最大 MEX

方法一：