企业官网建设流程全解析

以下是 LeetCode 3614. 用特殊操作处理字符串 II 的 Java 实现。

题目概述

给定字符串 `s`（由小写字母和特殊字符 `'*'`、`'#'`、`'%'` 组成）和整数 `k`，按以下规则处理：

- 小写字母：追加到结果中
- `*`：删除最后一个字符（退格）
- `#`：将当前结果复制一份追加到末尾
- `%`：反转当前结果

返回最终字符串中第 `k` 个字符（0 开始），越界返回 `'.'`。

关键难点：`#` 操作会导致字符串长度指数级增长（可达 10^{15}），无法直接构造完整字符串。

解题思路：倒推法

1. 正向遍历计算最终字符串长度 `m`
2. 如果 `k >= m`，直接返回 `'.'`
3. 倒序遍历字符串，根据操作类型将 `k` 映射回操作前的位置：
- `*`：长度 `+1`（倒推时恢复被删除的字符）
- `#`：长度减半，若 `k` 在右半部分则减去左半长度
- `%`：`k` 变为对称位置 `m - 1 - k`
- 字母：长度 `-1`，若 `k == m` 则找到答案

Java 实现

```java
class 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 == '*') {
// 倒推：恢复被删除的字符，长度+1
m += 1;
} else if (c == '#') {
// 倒推：长度减半
m /= 2;
// 若 k 在右半部分，映射到左半部分
if (k >= m) {
k -= m;
}
} else if (c == '%') {
// 倒推：反转操作，k 变为对称位置
k = m - 1 - k;
} else {
// 字母：长度-1
m -= 1;
// 若当前位置就是要找的字符
if (k == m) {
return c;
}
}
}
}
}
```

复杂度分析

- 时间复杂度：O(n)，两次遍历字符串
- 空间复杂度：O(1)，仅使用常数额外空间

关键点说明

1. 使用 `long` 类型：因为长度可能达到 10^{15}，必须用 `long` 避免溢出
2. 倒推时忽略 `*`：正向已计算好长度，倒推只需恢复长度，不影响 `k` 的位置判断
3. `#` 的映射：复制后左半部分是原串，右半部分是副本。若 `k` 在右半，减去左半长度即可映射回原位置
4. `%` 的对称性：反转后位置 `k` 对应反转前的位置 `m - 1 - k`

> 来源参考：