作者： admin

目标

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

说明：

1 <= n <= 9

思路

将 n 个皇后放在 n x n 的棋盘上，使它们不在同一行、不在同一列并且不在同一斜线上。返回不同的解决方案数量。与 51_N皇后 相比，本题无需返回具体的布局。

关键点：

• 每行只能放一个皇后，枚举当前行的每一列，如果存在合法的位置则进入下一行
• 如何判断是否在一条斜线上，对于坐标 (i, j)，(a, b)，如果 i + j == a + b || i - j == a - b，那么它们在一条斜线上
• 使用数组保存已经存在皇后的斜线，由于 i - j 可能出现负数，我们将其右移 n，使用 i - j + n，最大值为 n - 1 + n，数组初始化为 2 * n，i + j 最大值为 n - 1 + n - 1 初始化为 2 * n - 1
• 从第 0 行开始，如果能够进入第 1 行，说明第 0 行存在皇后。同理如果能够进入第 2 行，说明前两行存在皇后，总共 2 个皇后。因此结束条件为 row == n

代码

/**
 * @date 2024-12-01 17:58
 */
public class TotalNQueens52 {

    public int res;
    public int n;
    public boolean[] colIndexSet;
    public boolean[] leftDiagonalSet;
    public boolean[] rightDiagonalSet;

    public int totalNQueens(int n) {
        this.n = n;
        colIndexSet = new boolean[n];
        leftDiagonalSet = new boolean[2 * n];
        rightDiagonalSet = new boolean[2 * n - 1];
        backTracing(0);
        return res;
    }

    public void backTracing(int row) {
        if (row == n) {
            res++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (colIndexSet[col] || leftDiagonalSet[row - col + n] || rightDiagonalSet[row + col]) {
                continue;
            }
            colIndexSet[col] = true;
            leftDiagonalSet[row - col + n] = true;
            rightDiagonalSet[row + col] = true;
            backTracing(row + 1);
            colIndexSet[col] = false;
            leftDiagonalSet[row - col + n] = false;
            rightDiagonalSet[row + col] = false;
        }
    }

}

性能

目标

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

说明：

• 1 <= n <= 9

思路

将 n 个皇后放在 n x n 的棋盘上，使它们不在同一行、不在同一列并且不在同一斜线上。返回所有不同的解决方案，使用 Q 表示皇后，. 表示空位。

枚举棋盘的每个格子，当该格子放置皇后时，其所在行、列、斜线的格子都不能有皇后。使用回溯算法，如果格子遍历完皇后数量刚好为 n 个则计数。

假设 (i, j) 位置上放置了皇后，那么所有 (i, *) (*, j) 以及所有满足 a - b == i - j || i + j == a + b 的 (a, b) 都不能再放置皇后。

使用整数的二进制位来表示列是否允许放置皇后，从左到右对应二进制的低位到高位：

• 由于逻辑与、或没有逆运算，所以必须以参数的方式传递，否则无法恢复现场
• 如果我们在第 0 行的第 i 列放置了皇后，那么第 1 行的第 i - 1, i, i + 1 列无法放置皇后，使用位运算的角度来看就是对 1 << i, 1 << (i + 1), 1 << (i - 1) 相与，即 1 << i, (1 << i) << 1, (1 << i) >> 1。令 c = 1 << i，再考虑当前行与前面行的限制，下一行 不能放置皇后的列为：colIndexSet | c，(leftDiagonalSet | c) << 1，(rightDiagonalSet | c) >> 1)，其中 colIndexSet 的 bit 1 表示无法放置皇后的列；leftDiagonalSet 的 bit 1 表示受 ↘ 斜线限制，无法放置皇后的列；rightDiagonalSet 的 bit 1 表示受 ↙ 斜线限制，无法放置皇后的列；c 表示将当前行放置皇后的列对应的 bit 位 置 1 所代表的数字
• valid = ((1 << n) - 1) & ~(colIndexSet | leftDiagonalSet | rightDiagonalSet) 表示合法的位置
• c = valid & -valid 得到 bit 1 的最低位表示的数字
• Integer.bitCount(c - 1) 表示列下标
• valid ^= c 将当前处理过的最低位 bit 1 置 0

当然也可以使用数组来记录不可放置皇后的列信息，差别不大，见 52_N皇后II

代码

/**
 * @date 2024-12-01 16:45
 */
public class SolveNQueens51 {

    public static class SolveNQueens {
        public List<List<String>> res;
        public int n;
        public int[] queens;

        public List<List<String>> solveNQueens(int n) {
            this.n = n;
            queens = new int[n];
            res = new ArrayList<>();
            backTracing(0, 0, 0, 0);
            return res;
        }

        public void backTracing(int row, int colIndexSet, int leftDiagonalSet, int rightDiagonalSet) {
            if (row == n) {
                List<String> solution = new ArrayList<>(n);
                char[] chars = new char[n];
                Arrays.fill(chars, '.');
                for (int i = 0; i < n; i++) {
                    chars[queens[i]] = 'Q';
                    solution.add(new String(chars));
                    chars[queens[i]] = '.';
                }
                res.add(solution);
                return;
            }
            int valid = ((1 << n) - 1) & ~(colIndexSet | leftDiagonalSet | rightDiagonalSet);
            while (valid > 0){
                int c = valid & -valid;
                queens[row] = Integer.bitCount(c - 1);
                backTracing(row + 1, colIndexSet | c,
                        (leftDiagonalSet | c) << 1,
                        (rightDiagonalSet | c) >> 1);
                valid ^= c;
            }
        }

    }

    public List<List<String>> res;
    public Set<Integer> rowIndexSet;
    public Set<Integer> colIndexSet;
    public Set<Integer> leftDiagonalSet;
    public Set<Integer> rightDiagonalSet;
    public ArrayList<int[]> indexList;
    public int end;
    public int n;

    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList<>(n);
        rowIndexSet = new HashSet<>(n);
        colIndexSet = new HashSet<>(n);
        leftDiagonalSet = new HashSet<>(n);
        rightDiagonalSet = new HashSet<>(n);
        indexList = new ArrayList<>(n);
        end = n * n;
        this.n = n;
        for (int i = 0; i < n; i++) {
            backTracing(i);
        }
        return res;
    }

    public void backTracing(int index) {
        int row = index / n;
        int col = index % n;
        int leftDiagonal = row - col;
        int rightDiagonal = row + col;
        rowIndexSet.add(row);
        colIndexSet.add(col);
        leftDiagonalSet.add(leftDiagonal);
        rightDiagonalSet.add(rightDiagonal);
        indexList.add(new int[]{row, col});
        if (indexList.size() == n) {
            StringBuilder sb = new StringBuilder();
            List<String> solution = new ArrayList<>(n);
            for (int[] cor : indexList) {
                for (int i = 0; i < n; i++) {
                    if (i == cor[1]) {
                        sb.append('Q');
                    } else {
                        sb.append('.');
                    }
                }
                solution.add(sb.toString());
                sb.setLength(0);
            }
            res.add(solution);
        }
        for (int i = index + 1; i < end; i++) {
            int r = i / n;
            int c = i % n;
            int ld = r - c;
            int rd = r + c;
            if (rowIndexSet.contains(r) || colIndexSet.contains(c)
                    || leftDiagonalSet.contains(ld)
                    || rightDiagonalSet.contains(rd)) {
                continue;
            }
            backTracing(i);
        }
        rowIndexSet.remove(row);
        colIndexSet.remove(col);
        leftDiagonalSet.remove(leftDiagonal);
        rightDiagonalSet.remove(rightDiagonal);
        indexList.remove(indexList.size() - 1);
    }

}

性能

目标

给你一个长度为 n 的 正 整数数组 nums 。

如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：

• 两个数组的长度都是 n 。
• arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。
• arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。
• 对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。

请你返回所有 单调 数组对的数目。

由于答案可能很大，请你将它对 109 + 7 取余 后返回。

示例 1：

输入：nums = [2,3,2]
输出：4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])

示例 2：

输入：nums = [5,5,5,5]
输出：126

说明：

• 1 <= n == nums.length <= 2000
• 1 <= nums[i] <= 1000

思路

有一个长度为 n 正整数数组 nums，可以将其拆成两个数组 arr1 arr2，使之满足 arr1[i] + arr2[i] == nums[i]。问 有多少种拆分方法使得 arr1 非递减 且 arr2 非递增。

与昨天的 3250.单调数组对的数目I 相比，nums[i] 的最大值从 50 变成了 1000。时间复杂度大概为 O(n*m^2)，m 为 nums[i] 的最大值，如果还沿用昨天的解法就会超时。

先将昨天的题目改写为动态规划，定义 dp[i][j] 表示最后一个元素为 j，长度为 i + 1 的满足条件的 arr1 个数。由于 arr1 是非递减的，如果最后一个元素为 arr1[i] = j 那么倒数第二个元素arr1[i - 1] <= j。同时我们还要考虑到 arr2 非递增，即 arr2[i - 1] >= arr2[i]，nums[i - 1] - arr1[i - 1] >= nums[i] - arr1[i]，arr1[i - 1] <= nums[i - 1] - nums[i] + arr1[i]。综上，arr1[i - 1] <= Math.min(j, nums[i - 1] - nums[i] + j)。

经过上面的分析，dp[i][j] = Σdp[i - 1][k]，其中 k ∈ [0, Math.min(j, nums[i - 1] - nums[i] + j)]。这样写会超时，针对每个 j，我们会进行多次重复的计算。

令 d = nums[i - 1] - nums[i]，当 d >= 0 时，上界为 j，否则上界为 j + d。

考虑 nums[i - 1] < nums[i]，即 d < 0：

• 当 arr1[i - 1] = j 时，令arr2[i - 1] = nums[i - 1] - j = a
• 当 arr1[i] = j 时，arr2[i] = nums[i] - arr1[i] = nums[i - 1] - d - j = a - d，d < 0。

也就是说，当 arr1[i] 的取值与上一层一样时，arr2[i] 比上一层的值大了 |d|。为了使第 i 层 arr2 非递增，那么 arr1 的取值只能从 |d| 开始。

它们之间的约束关系是这样的，当 nums[i] 变大，arr1 第 i 层取 j 时，arr2 的第 i 层比上一层增大了 |d|，这时我们必须舍弃 [0, |d|) 的取值，因为它必定大于上一层 arr2 的最大值。然后考虑第 i 层的 arr1 取 [|d|, nums[i]] 的情况，由于第 i 层的 arr2 相比第 i - 1 层增大了 |d|，因此需要减小第 i - 1 层的 arr1，使第 i - 1 层的 arr2 增大。所以第 i 层的 j 对应第 i - 1 层的 j - |d|。

dp[i][j] 的取值类似前缀和，只不过有约束条件，并不是所有值都合法。考虑简单的情况 nums[0] == nums[1] && i == 1，

• 当 j == 0 时，dp[1][0] = dp[0][0] = 1
• 当 j == 1 时，上一层（i == 0） arr1 可以取 0、1，dp[1][1] = dp[1][0] + dp[0][1] = 2
• 当 j == 2 时，上一层（i == 0） arr1 可以取 0、1、2，dp[1][2] = dp[1][1] + dp[0][2] = 3

因此我们有 dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d])。

代码

/**
 * @date 2024-11-29 9:39
 */
public class CountOfPairs3251 {

    public static int MOD = 1000000007;

    public int countOfPairs(int[] nums) {
        int res = 0;
        int n = nums.length;
        int[][] dp = new int[n][1001];
        for (int i = 0; i <= nums[0]; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            int d = Math.max(nums[i] - nums[i - 1], 0);
            for (int j = d; j <= nums[i]; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][0] % MOD;
                } else {
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % MOD;
                }
            }
        }
        for (int i : dp[n - 1]) {
            res = (res + i) % MOD;
        }
        return res;
    }

}

性能

目标

给你一个长度为 n 的 正 整数数组 nums 。

如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：

• 两个数组的长度都是 n 。
• arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。
• arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。
• 对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。

请你返回所有 单调 数组对的数目。

由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。

示例 1：

输入：nums = [2,3,2]
输出：4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])

示例 2：

输入：nums = [5,5,5,5]
输出：126

说明：

• 1 <= n == nums.length <= 2000
• 1 <= nums[i] <= 50

提示：

• Let dp[i][s] is the number of monotonic pairs of length i with the arr1[i - 1] = s.
• If arr1[i - 1] = s, arr2[i - 1] = nums[i - 1] - s.
• Check if the state in recurrence is valid.

思路

有一个长度为 n 的正整数数组 nums，可以将其拆成两个数组 arr1 arr2，使之满足 arr1[i] + arr2[i] == nums[i]。问 有多少种拆分方法使得 arr1 非递减 且 arr2 非递增。

显然 arr1 确定之后，arr2 也就确定了。考虑枚举 arr1，判断 arr1 是否非递减， 以及arr2 是否非递增。可以使用记忆化搜索，对于位置 i，arr1 与 arr2 需要满足下面的条件：

• arr1[i] >= arr1[i - 1]
• arr2[i] = nums[i] - arr1[i] <= arr2[i - 1] = nums[i - 1] - arr1[i - 1]，即 arr1[i] >= nums[i] - nums[i - 1] + arr1[i - 1]

也就是 nums[i] >= arr1[i] >= Math.max(nums[i] - nums[i - 1] + arr1[i - 1], arr1[i - 1])。

代码

/**
 * @date 2024-11-28 10:36
 */
public class CountOfPairs3250 {

    public static int MOD = 1000000007;

    public int countOfPairs(int[] nums) {
        int res = 0;
        int n = nums.length;
        int[][] mem = new int[n + 1][51];
        for (int[] arr : mem) {
            Arrays.fill(arr, -1);
        }
        for (int i = 0; i <= nums[0]; i++) {
            res = (res + dfs(nums, 1, i, mem)) % MOD;
        }
        return res;
    }

    public int dfs(int[] nums, int i, int prev, int[][] mem) {
        int n = nums.length;
        if (i == n) {
            return 1;
        }
        int lowerBound = Math.max(prev, nums[i] - nums[i - 1] + prev);
        int next = i + 1;
        int res = 0;
        for (int j = lowerBound; j <= nums[i]; j++) {
            if (mem[next][j] == -1) {
                mem[next][j] = dfs(nums, next, j, mem) % MOD;
            }
            res = (res + mem[next][j]) % MOD;
        }
        return res;
    }

}

性能

目标

你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释： 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]

说明：

• nums.length == k
• 1 <= k <= 3500
• 1 <= nums[i].length <= 50
• -10^5 <= nums[i][j] <= 10^5
• nums[i] 按非递减顺序排列

思路

有 k 个非递减排列的整数列表，找一个最小区间，使得 k 个列表中每个列表至少有一个元素包含其中。所谓最小区间指区间长度最小，如果长度相同，则起点小的区间更小。

可以将元素标记属于哪个列表，然后从小到大排序，使用滑动窗口，找到最小的窗口。

当元素移入/移出窗口，如何判断是否应该从集合中增加/删除列表种类？

• 可以记录每个列表元素的最大下标，如果移出的元素等于该下标则说明窗口内不包含该列表中的元素。元素移入窗口时可以根据最大下标是否小于左边界来判断是否应该增加列表种类，考虑到开始时左边界为 0，应该将数组初始化为 -1。
• 也可以记录每个列表在窗口元素的个数，如果从 0 变为 1 则增加种类，如果从 1 变为 0 则减少。

代码

/**
 * @date 2024-11-24 15:14
 */
public class SmallestRange632 {

    /**
     * 优化代码逻辑
     */
    public int[] smallestRange_v1(List<List<Integer>> nums) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (Integer num : nums.get(i)) {
                list.add(new int[]{num, i});
            }
        }
        int[] res = new int[]{0, 1000000};
        list.sort((a, b) -> a[0] - b[0]);
        int n = list.size(), k = nums.size();
        int l = 0;
        int[] typeMaxIndex = new int[k];
        Arrays.fill(typeMaxIndex, -1);
        int types = 0;
        for (int r = 0; r < n; r++) {
            int[] e = list.get(r);
            int right = e[0];
            int type = e[1];
            int lastTypeMaxIndex = typeMaxIndex[type];
            typeMaxIndex[type] = r;
            if (lastTypeMaxIndex < l){
                types++;
            }
            while (types == k) {
                int[] left = list.get(l);
                int lType = left[1];
                if (typeMaxIndex[lType] == l++) {
                    types--;
                    if (right - left[0] < res[1] - res[0]) {
                        res[0] = left[0];
                        res[1] = right;
                    }
                }
            }
        }
        return res;
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (Integer num : nums.get(i)) {
                list.add(new int[]{num, i});
            }
        }
        int[] res = new int[]{0, 1000000};
        list.sort((a, b) -> a[0] - b[0]);
        int n = list.size(), k = nums.size();
        int l = 0;
        int[] typeMaxIndex = new int[k];
        Set<Integer> set = new HashSet<>();
        for (int r = 0; r < n; r++) {
            int[] e = list.get(r);
            int right = e[0];
            int type = e[1];
            typeMaxIndex[type] = r;
            set.add(type);
            while (set.size() == k) {
                int[] left = list.get(l);
                int lType = left[1];
                if (typeMaxIndex[lType] == l++) {
                    set.remove(lType);
                }
            }
            if (l >= 1 && !set.contains(list.get(l - 1)[1]) && set.size() == k - 1) {
                int left = list.get(l - 1)[0];
                if (right - left < res[1] - res[0]) {
                    res[0] = left;
                    res[1] = right;
                }
            }
        }
        return res;
    }
}

性能