🌟欢迎来到 我的博客 —— 探索技术的无限可能！
19.学生出勤记录 II
题目链接：552. 学生出勤记录 II
可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
‘A’：Absent，缺勤
‘L’：Late，迟到
‘P’：Present，到场
如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
按 总出勤 计，学生缺勤（‘A’）严格 少于两天。
学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（‘L’）记录。
给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 109 + 7 取余 的结果。
示例 1：
输入：n = 2
输出：8
解释：
有 8 种长度为 2 的记录将被视为可奖励：
“PP” , “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”
只有"AA"不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。
示例 2：
输入：n = 1
输出：3
示例 3：
输入：n = 10101
输出：183236316
提示：
1 <= n <= 105
题解：
方法：递归搜索 + 保存递归返回值 = 记忆化搜索
class Solution { private static final int MOD = 1_000_000_007; private static final int MX = 100_001; private static final int[][][] memo = new int[MX][2][3]; public int checkRecord(int n) { return dfs(n, 0, 0); } private static int dfs(int i, int j, int k) { if (i == 0) { return 1; } if (memo[i][j][k] > 0) { // 之前计算过 return memo[i][j][k]; } long res = dfs(i - 1, j, 0); // 填 P if (j == 0) { res += dfs(i - 1, 1, 0); // 填 A } if (k < 2) { res += dfs(i - 1, j, k + 1); // 填 L } return memo[i][j][k] = (int) (res % MOD); } }
20.到达第 K 级台阶的方案数
题目链接：3154. 到达第 K 级台阶的方案数
给你有一个 非负 整数 k 。有一个无限长度的台阶，最低 一层编号为 0 。
Alice 有一个整数 jump ，一开始值为 0 。Alice 从台阶 1 开始，可以使用 任意 次操作，目标是到达第 k 级台阶。假设 Alice 位于台阶 i ，一次 操作 中，Alice 可以：
向下走一级到 i - 1 ，但该操作 不能 连续使用，如果在台阶第 0 级也不能使用。
向上走到台阶 i + 2jump 处，然后 jump 变为 jump + 1 。
请你返回 Alice 到达台阶 k 处的总方案数。
注意，Alice 可能到达台阶 k 处后，通过一些操作重新回到台阶 k 处，这视为不同的方案。
示例 1：
输入：k = 0
输出：2
解释：
2 种到达台阶 0 的方案为：
Alice 从台阶 1 开始。
执行第一种操作，从台阶 1 向下走到台阶 0 。
Alice 从台阶 1 开始。
执行第一种操作，从台阶 1 向下走到台阶 0 。
执行第二种操作，向上走 20 级台阶到台阶 1 。
执行第一种操作，从台阶 1 向下走到台阶 0 。
示例 2：
输入：k = 1
输出：4
解释：
4 种到达台阶 1 的方案为：
Alice 从台阶 1 开始，已经到达台阶 1 。
Alice 从台阶 1 开始。
执行第一种操作，从台阶 1 向下走到台阶 0 。
执行第二种操作，向上走 20 级台阶到台阶 1 。
Alice 从台阶 1 开始。
执行第二种操作，向上走 20 级台阶到台阶 2 。
执行第一种操作，向下走 1 级台阶到台阶 1 。
Alice 从台阶 1 开始。
执行第一种操作，从台阶 1 向下走到台阶 0 。
执行第二种操作，向上走 20 级台阶到台阶 1 。
执行第一种操作，向下走 1 级台阶到台阶 0 。
执行第二种操作，向上走 21 级台阶到台阶 2 。
执行第一种操作，向下走 1 级台阶到台阶 1 。
提示：
0 <= k <= 109
题解：
方法：记忆化搜索
class Solution { public int waysToReachStair(int k) { return dfs(1, 0, 0, k, new HashMap<>()); } // preDown = 0/1 表示 false/true private int dfs(int i, int j, int preDown, int k, Map<Long, Integer> memo) { if (i > k + 1) { // 无法到达终点 k return 0; } // 把状态 (i, j, preDown) 压缩成一个 long long mask = (long) i << 32 | j << 1 | preDown; if (memo.containsKey(mask)) { // 之前算过了 return memo.get(mask); } int res = i == k ? 1 : 0; res += dfs(i + (1 << j), j + 1, 0, k, memo); // 操作二 if (preDown == 0) { res += dfs(i - 1, j, 1, k, memo); // 操作一 } memo.put(mask, res); // 记忆化 return res; } }
21.价值和小于等于 K 的最大数字
给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x，2x，3x 等位置处
设置位
的数目（从最低有效位开始）。下面的表格包含了如何计算价值的例子。
x num Binary Representation Price
1 13 000001101 3
2 13 000001101 1
2 233 011101001 3
3 13 000001101 1
3 362 101101010 2
num 的 累加价值 是从 1 到 num 的数字的 总 价值。如果 num 的累加价值小于或等于 k 则被认为是 廉价 的。
请你返回 最大 的廉价数字。
示例 1：
输入：k = 9, x = 1
输出：6
解释：由下表所示，6 是最大的廉价数字。
x num Binary Representation Price Accumulated Price
1 1 001 1 1
1 2 010 1 2
1 3 011 2 4
1 4 100 1 5
1 5 101 2 7
1 6 110 2 9
1 7 111 3 12
示例 2：
输入：k = 7, x = 2
输出：9
解释：由下表所示，9 是最大的廉价数字。
x num Binary Representation Price Accumulated Price
2 1 0001 0 0
2 2 0010 1 1
2 3 0011 1 2
2 4 0100 0 2
2 5 0101 0 2
2 6 0110 1 3
2 7 0111 1 4
2 8 1000 1 5
2 9 1001 1 6
2 10 1010 2 8
提示：
1 <= k <= 1015
1 <= x <= 8
题解：
方法：二分答案 + 数位 DP
class Solution { public long findMaximumNumber(long k, int x) { this.x = x; // 开区间二分，原理见 https://www.bilibili.com/video/BV1AP41137w7/ long left = 0; long right = (k + 1) << x; while (left + 1 < right) { long mid = (left + right) >>> 1; if (countDigitOne(mid) <= k) { left = mid; } else { right = mid; } } return left; } private int x; private long num; private long memo[][]; private long countDigitOne(long num) { this.num = num; int m = 64 - Long.numberOfLeadingZeros(num); memo = new long[m][m + 1]; for (long[] row : memo) { Arrays.fill(row, -1); } return dfs(m - 1, 0, true); } private long dfs(int i, int cnt1, boolean isLimit) { if (i < 0) { return cnt1; } if (!isLimit && memo[i][cnt1] != -1) { return memo[i][cnt1]; } int up = isLimit ? (int) (num >> i & 1) : 1; long res = 0; for (int d = 0; d <= up; d++) { // 枚举要填入的数字 d res += dfs(i - 1, cnt1 + (d == 1 && (i + 1) % x == 0 ? 1 : 0), isLimit && d == up); } if (!isLimit) { memo[i][cnt1] = res; } return res; } }
22.数组最后一个元素的最小值
题目链接：3133. 数组最后一个元素的最小值
给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。
返回 nums[n - 1] 可能的 最小 值。
示例 1：
输入：n = 3, x = 4
输出：6
解释：
数组 nums 可以是 [4,5,6] ，最后一个元素为 6 。
示例 2：
输入：n = 2, x = 7
输出：15
解释：
数组 nums 可以是 [7,15] ，最后一个元素为 15 。
提示：
1 <= n, x <= 108
题解：
方法：位运算
class Solution { public long minEnd(int n, int x) { n--; // 先把 n 减一，这样下面讨论的 n 就是原来的 n-1 long ans = x; int i = 0, j = 0; while ((n >> j) > 0) { // x 的第 i 个比特值是 0，即「空位」 if ((ans >> i & 1) == 0) { // 空位填入 n 的第 j 个比特值 ans |= (long) (n >> j & 1) << i; j++; } i++; } return ans; } }
23.大数组元素的乘积
题目链接：3145. 大数组元素的乘积
一个非负整数 x 的 强数组 指的是满足元素为 2 的幂且元素总和为 x 的最短有序数组。下表说明了如何确定 强数组 的示例。可以证明，x 对应的强数组是独一无二的。
数字 二进制表示 强数组
1 00001 [1]
8 01000 [8]
10 01010 [2, 8]
13 01101 [1, 4, 8]
23 10111 [1, 2, 4, 16]
我们将每一个升序的正整数 i （即1，2，3等等）的 强数组 连接得到数组 big_nums ，big_nums 开始部分为 [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, …] 。
给你一个二维整数数组 queries ，其中 queries[i] = [fromi, toi, modi] ，你需要计算 (big_nums[fromi] * big_nums[fromi + 1] * … * big_nums[toi]) % modi 。
请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。
示例 1：
输入：queries = [[1,3,7]]
输出：[4]
解释：
只有一个查询。
big_nums[1…3] = [2,1,2] 。它们的乘积为 4。结果为 4 % 7 = 4。
示例 2：
输入：queries = [[2,5,3],[7,7,4]]
输出：[2,2]
解释：
有两个查询。
第一个查询：big_nums[2…5] = [1,2,4,1] 。它们的乘积为 8 。结果为 8 % 3 = 2。
第二个查询：big_nums[7] = 2 。结果为 2 % 4 = 2。
提示：
1 <= queries.length <= 500
queries[i].length == 3
0 <= queries[i][0] <= queries[i][1] <= 1015
1 <= queries[i][2] <= 105
题解：
方法：试填法
class Solution { public int[] findProductsOfElements(long[][] queries) { int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { long[] q = queries[i]; long er = sumE(q[1] + 1); long el = sumE(q[0]); ans[i] = pow(2, er - el, q[2]); } return ans; } private long sumE(long k) { long res = 0; long n = 0; long cnt1 = 0; // 之前填的 1 的个数 long sumI = 0; // 之前填的 1 的幂次之和 for (long i = 63 - Long.numberOfLeadingZeros(k + 1); i >= 0; i--) { long c = (cnt1 << i) + (i << i >> 1); // 新增的幂次个数 if (c <= k) { k -= c; res += (sumI << i) + ((i * (i - 1) / 2) << i >> 1); sumI += i; cnt1++; n |= 1L << i; // 填 1 } } // 剩余的 k 个幂次，由 n 的低 k 个 1 补充 while (k-- > 0) { res += Long.numberOfTrailingZeros(n); n &= n - 1; // 去掉最低位的 1（置为 0） } return res; } private int pow(long x, long n, long mod) { long res = 1 % mod; // 注意 mod 可能等于 1 for (; n > 0; n /= 2) { if (n % 2 == 1) { res = res * x % mod; } x = x * x % mod; } return (int) res; } }
24.两个字符串的排列差
题目链接：3146. 两个字符串的排列差
给你两个字符串 s 和 t，每个字符串中的字符都不重复，且 t 是 s 的一个排列。
排列差 定义为 s 和 t 中每个字符在两个字符串中位置的绝对差值之和。
返回 s 和 t 之间的 排列差 。
示例 1：
输入：s = “abc”, t = “bac”
输出：2
解释：
对于 s = “abc” 和 t = “bac”，排列差是：
“a” 在 s 中的位置与在 t 中的位置之差的绝对值。
“b” 在 s 中的位置与在 t 中的位置之差的绝对值。
“c” 在 s 中的位置与在 t 中的位置之差的绝对值。
即，s 和 t 的排列差等于 |0 - 1| + |2 - 2| + |1 - 0| = 2。
示例 2：
输入：s = “abcde”, t = “edbac”
输出：12
解释： s 和 t 的排列差等于 |0 - 3| + |1 - 2| + |2 - 4| + |3 - 1| + |4 - 0| = 12。
提示：
1 <= s.length <= 26
每个字符在 s 中最多出现一次。
t 是 s 的一个排列。
s 仅由小写英文字母组成。
题解：
方法：哈希
class Solution { public int findPermutationDifference(String s, String t) { int[] pos = new int[26]; for (int i = 0; i < s.length(); i++) { pos[s.charAt(i) - 'a'] = i; } int ans = 0; for (int i = 0; i < t.length(); i++) { ans += Math.abs(i - pos[t.charAt(i) - 'a']); } return ans; } }
25.划分为k个相等的子集
题目链接：698. 划分为k个相等的子集
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
示例 2:
输入: nums = [1,2,3,4], k = 3
输出: false
提示：
1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
每个元素的频率在 [1,4] 范围内
题解：
方法：DFS + 剪枝
class Solution { private int[] nums; private int[] cur; private int s; public boolean canPartitionKSubsets(int[] nums, int k) { for (int v : nums) { s += v; } if (s % k != 0) { return false; } s /= k; cur = new int[k]; Arrays.sort(nums); this.nums = nums; return dfs(nums.length - 1); } private boolean dfs(int i) { if (i < 0) { return true; } for (int j = 0; j < cur.length; ++j) { if (j > 0 && cur[j] == cur[j - 1]) { continue; } cur[j] += nums[i]; if (cur[j] <= s && dfs(i - 1)) { return true; } cur[j] -= nums[i]; } return false; } }
