行业资讯
Kimi LeetCode 3614. 用特殊操作处理字符串 II Java实现
以下是 LeetCode 3614. 用特殊操作处理字符串 II 的 Java 实现。题目概述给定字符串 s由小写字母和特殊字符 *、#、% 组成和整数 k按以下规则处理- 小写字母追加到结果中- *删除最后一个字符退格- #将当前结果复制一份追加到末尾- %反转当前结果返回最终字符串中第 k 个字符0 开始越界返回 .。关键难点# 操作会导致字符串长度指数级增长可达 10^{15}无法直接构造完整字符串。解题思路倒推法1. 正向遍历计算最终字符串长度 m2. 如果 k m直接返回 .3. 倒序遍历字符串根据操作类型将 k 映射回操作前的位置- *长度 1倒推时恢复被删除的字符- #长度减半若 k 在右半部分则减去左半长度- %k 变为对称位置 m - 1 - k- 字母长度 -1若 k m 则找到答案Java 实现javaclass Solution {public char processStr(String s, long k) {long m 0;// 第一遍正向计算最终长度for (int i 0; i s.length(); i) {char c s.charAt(i);if (c *) {m Math.max(0, m - 1);} else if (c #) {m 1; // 长度翻倍} else if (c ! %) {m 1; // 字母}// % 不改变长度}// k 越界if (k m) {return .;}// 第二遍倒推找第 k 个字符for (int i s.length() - 1; ; i--) {char c s.charAt(i);if (c *) {// 倒推恢复被删除的字符长度1m 1;} else if (c #) {// 倒推长度减半m / 2;// 若 k 在右半部分映射到左半部分if (k m) {k - m;}} else if (c %) {// 倒推反转操作k 变为对称位置k m - 1 - k;} else {// 字母长度-1m - 1;// 若当前位置就是要找的字符if (k m) {return c;}}}}}复杂度分析- 时间复杂度O(n)两次遍历字符串- 空间复杂度O(1)仅使用常数额外空间关键点说明1. 使用 long 类型因为长度可能达到 10^{15}必须用 long 避免溢出2. 倒推时忽略 *正向已计算好长度倒推只需恢复长度不影响 k 的位置判断3. # 的映射复制后左半部分是原串右半部分是副本。若 k 在右半减去左半长度即可映射回原位置4. % 的对称性反转后位置 k 对应反转前的位置 m - 1 - k 来源参考
郑州网站建设
网页设计
企业官网
