以下是 LeetCode 3003. 执行操作后的最大分割数量 的 Java 实现。这道题有两种主流解法1. 状态压缩 记忆化搜索代码简洁但复杂度分析需要仔细理解2. 前后缀分解线性复杂度实现较复杂这里提供两种实现---解法一状态压缩 记忆化搜索推荐核心思路用 mask位掩码记录当前分割块中已出现的字符集合cur 表示当前块中不同字符的数量。t 标记是否还能修改一个字符。javaclass Solution {private MapListInteger, Integer f new HashMap();private String s;private int k;private int n;public int maxPartitionsAfterOperations(String s, int k) {this.s s;this.k k;this.n s.length();return dfs(0, 0, 1);}/*** 记忆化搜索* param i 当前处理到的位置* param cur 当前分割块的字符掩码位掩码* param t 是否还能修改一个字符1可以0已用掉* return 从位置 i 开始能获得的最大分割数*/private int dfs(int i, int cur, int t) {if (i n) {return 1; // 到达末尾最后一个分割块计数}var key List.of(i, cur, t);if (f.containsKey(key)) {return f.get(key);}// 当前字符的位掩码int v 1 (s.charAt(i) - a);int nxt cur | v;int ans;// 不修改当前字符if (Integer.bitCount(nxt) k) {// 当前字符加入后超过 k 个不同字符必须开启新分割块ans dfs(i 1, v, t) 1;} else {// 继续当前分割块ans dfs(i 1, nxt, t);}// 尝试修改当前字符如果还能修改if (t 0) {for (int j 0; j 26; j) {nxt cur | (1 j);if (Integer.bitCount(nxt) k) {// 修改后需要开启新分割块ans Math.max(ans, dfs(i 1, 1 j, 0) 1);} else {// 修改后继续当前分割块ans Math.max(ans, dfs(i 1, nxt, 0));}}}f.put(key, ans);return ans;}}---解法二前后缀分解线性复杂度核心思路修改位置 i 的字符只会影响包含 s[i] 的那个分割块。预处理左右两侧的分割信息枚举每个修改位置快速计算。javaclass Solution {public int maxPartitionsAfterOperations(String s, int k) {int n s.length();// left[i][0] s[0..i-1] 的完整分割数// left[i][1] s[0..i-1] 最后一个未满块的字符掩码// left[i][2] s[0..i-1] 最后一个未满块的不同字符数int[][] left new int[n 1][3];// right[i][0] s[i..n-1] 的完整分割数// right[i][1] s[i..n-1] 第一个未满块的字符掩码// right[i][2] s[i..n-1] 第一个未满块的不同字符数int[][] right new int[n 1][3];// 预处理左侧int num 0, mask 0, count 0;for (int i 0; i n; i) {int bit 1 (s.charAt(i) - a);if ((mask bit) 0) { // 新字符count;if (count k) {mask | bit;} else {// 开启新块num;mask bit;count 1;}}left[i 1][0] num;left[i 1][1] mask;left[i 1][2] count;}// 预处理右侧反向num 0;mask 0;count 0;for (int i n - 1; i 0; i--) {int bit 1 (s.charAt(i) - a);if ((mask bit) 0) {count;if (count k) {mask | bit;} else {num;mask bit;count 1;}}right[i][0] num;right[i][1] mask;right[i][2] count;}int maxPartitions left[n][0] 1; // 不修改的情况// 枚举修改位置 ifor (int i 0; i n; i) {// 默认左侧完整分割 右侧完整分割 中间 2 块修改点单独成块或合并int seg left[i][0] right[i 1][0] 2;int leftMask left[i][1];int rightMask right[i 1][1];int totalMask leftMask | rightMask;int totalCount Integer.bitCount(totalMask);// 情况1左右未满块 修改后的字符可以合并为 1 块// 需要 totalCount 1 k1 是给修改后的字符留的位置if (Math.min(totalCount 1, 26) k) {seg--; // 合并为 1 块总分割数减 1}// 情况2左右块都已满各 k 个字符且存在一个两者都没出现的字符// 修改后的字符可以独立成块使中间区域分裂为 3 块else if (left[i][2] k right[i 1][2] k totalCount 26) {seg; // 分裂为 3 块总分割数加 1}maxPartitions Math.max(maxPartitions, seg);}return maxPartitions;}}---两种解法对比特性 状态压缩 记忆化搜索 前后缀分解时间复杂度 O(n \times 2^{26}) 表面实际有效状态 O(n \times 26 \times 26) O(n)空间复杂度 O(n \times 2^{26}) 表面实际有效状态有限 O(n)代码复杂度 简洁约 40 行 较复杂约 80 行核心思想 直接模拟分割过程枚举修改 利用修改只影响局部的性质关键点说明- 位掩码 mask用一个 int 的 26 个二进制位表示 a-z 字符是否在当前分割块中出现- Integer.bitCount()计算掩码中 1 的个数即不同字符数量- 记忆化状态(i, cur, t) 表示从位置 i 开始当前块字符掩码为 cur是否还能修改的状态。虽然 cur 有 2^{26} 种可能但实际遍历中有效状态远少于这个数
Kimi k2.6 LeetCode 3003. 执行操作后的最大分割数量 Java实现
发布时间：2026/6/5 0:38:44
以下是 LeetCode 3003. 执行操作后的最大分割数量 的 Java 实现。这道题有两种主流解法1. 状态压缩 记忆化搜索代码简洁但复杂度分析需要仔细理解2. 前后缀分解线性复杂度实现较复杂这里提供两种实现---解法一状态压缩 记忆化搜索推荐核心思路用 mask位掩码记录当前分割块中已出现的字符集合cur 表示当前块中不同字符的数量。t 标记是否还能修改一个字符。javaclass Solution {private MapListInteger, Integer f new HashMap();private String s;private int k;private int n;public int maxPartitionsAfterOperations(String s, int k) {this.s s;this.k k;this.n s.length();return dfs(0, 0, 1);}/*** 记忆化搜索* param i 当前处理到的位置* param cur 当前分割块的字符掩码位掩码* param t 是否还能修改一个字符1可以0已用掉* return 从位置 i 开始能获得的最大分割数*/private int dfs(int i, int cur, int t) {if (i n) {return 1; // 到达末尾最后一个分割块计数}var key List.of(i, cur, t);if (f.containsKey(key)) {return f.get(key);}// 当前字符的位掩码int v 1 (s.charAt(i) - a);int nxt cur | v;int ans;// 不修改当前字符if (Integer.bitCount(nxt) k) {// 当前字符加入后超过 k 个不同字符必须开启新分割块ans dfs(i 1, v, t) 1;} else {// 继续当前分割块ans dfs(i 1, nxt, t);}// 尝试修改当前字符如果还能修改if (t 0) {for (int j 0; j 26; j) {nxt cur | (1 j);if (Integer.bitCount(nxt) k) {// 修改后需要开启新分割块ans Math.max(ans, dfs(i 1, 1 j, 0) 1);} else {// 修改后继续当前分割块ans Math.max(ans, dfs(i 1, nxt, 0));}}}f.put(key, ans);return ans;}}---解法二前后缀分解线性复杂度核心思路修改位置 i 的字符只会影响包含 s[i] 的那个分割块。预处理左右两侧的分割信息枚举每个修改位置快速计算。javaclass Solution {public int maxPartitionsAfterOperations(String s, int k) {int n s.length();// left[i][0] s[0..i-1] 的完整分割数// left[i][1] s[0..i-1] 最后一个未满块的字符掩码// left[i][2] s[0..i-1] 最后一个未满块的不同字符数int[][] left new int[n 1][3];// right[i][0] s[i..n-1] 的完整分割数// right[i][1] s[i..n-1] 第一个未满块的字符掩码// right[i][2] s[i..n-1] 第一个未满块的不同字符数int[][] right new int[n 1][3];// 预处理左侧int num 0, mask 0, count 0;for (int i 0; i n; i) {int bit 1 (s.charAt(i) - a);if ((mask bit) 0) { // 新字符count;if (count k) {mask | bit;} else {// 开启新块num;mask bit;count 1;}}left[i 1][0] num;left[i 1][1] mask;left[i 1][2] count;}// 预处理右侧反向num 0;mask 0;count 0;for (int i n - 1; i 0; i--) {int bit 1 (s.charAt(i) - a);if ((mask bit) 0) {count;if (count k) {mask | bit;} else {num;mask bit;count 1;}}right[i][0] num;right[i][1] mask;right[i][2] count;}int maxPartitions left[n][0] 1; // 不修改的情况// 枚举修改位置 ifor (int i 0; i n; i) {// 默认左侧完整分割 右侧完整分割 中间 2 块修改点单独成块或合并int seg left[i][0] right[i 1][0] 2;int leftMask left[i][1];int rightMask right[i 1][1];int totalMask leftMask | rightMask;int totalCount Integer.bitCount(totalMask);// 情况1左右未满块 修改后的字符可以合并为 1 块// 需要 totalCount 1 k1 是给修改后的字符留的位置if (Math.min(totalCount 1, 26) k) {seg--; // 合并为 1 块总分割数减 1}// 情况2左右块都已满各 k 个字符且存在一个两者都没出现的字符// 修改后的字符可以独立成块使中间区域分裂为 3 块else if (left[i][2] k right[i 1][2] k totalCount 26) {seg; // 分裂为 3 块总分割数加 1}maxPartitions Math.max(maxPartitions, seg);}return maxPartitions;}}---两种解法对比特性 状态压缩 记忆化搜索 前后缀分解时间复杂度 O(n \times 2^{26}) 表面实际有效状态 O(n \times 26 \times 26) O(n)空间复杂度 O(n \times 2^{26}) 表面实际有效状态有限 O(n)代码复杂度 简洁约 40 行 较复杂约 80 行核心思想 直接模拟分割过程枚举修改 利用修改只影响局部的性质关键点说明- 位掩码 mask用一个 int 的 26 个二进制位表示 a-z 字符是否在当前分割块中出现- Integer.bitCount()计算掩码中 1 的个数即不同字符数量- 记忆化状态(i, cur, t) 表示从位置 i 开始当前块字符掩码为 cur是否还能修改的状态。虽然 cur 有 2^{26} 种可能但实际遍历中有效状态远少于这个数
