Leetcode每日一题 —— 3614. 用特殊操作处理字符串 II

魔法师 2026-06-17 10:00 1

思路

虽然是系列题，但今天的题跟昨天是完全不同的。 1 <= s.length <= 10^5 看这范围模拟显然是不行的。不过题目只需要获取第k个字符，所以我们只需要在这点上下功夫即可。

正向看的时候我们无法知道k字符在当前的哪个位置，这样就不得不计算所有字符，这又回到了模拟的老路。

反向看的时候我们可以完全定位k当前所在的位置，这样我们只需要一直跟踪k，直到它是新插入的字符。

代码

class Solution {

    public char processStr(String s, long k) {

        long len = 0;

        char[] chars = s.toCharArray();

        for (char chr : chars) {

            if (chr == '*') {

                if (len > 0) {

                    len--;

                }

            } else if (chr == '#') {

                len <<= 1;

            } else if (chr != '%') {

                len++;

            }

        }

        if (len <= k) {

            return '.';

        }

        for (int i = chars.length - 1; i >= 0; i--) {

            char chr = chars[i];

            if (chr == '*') {

                len ++;

            } else if (chr == '#') {

                len >>= 1;

                if (k >= len) {

                    k -= len;

                }

            } else if (chr == '%') {

                k = len - k - 1;

            } else {

                if (k == len - 1) {

                    return chr;

                }

                len--;

            }

        }

        return ' ';

    }

}

最新回复 (4)

SomeBottle 06-17 10:18

1楼

先生成最终的字符串长度，然后反向操作，把 k 映射回字符串中的某个字符。

有两个需要注意的点：

计算最终字符串长度时，遇到 * 时要有字符的时候才删。

反向操作在遇到小写字母时，如果这个小写字母插入的位置正好是目前跟踪到的位置，则就是这个字符，可以早停。

class Solution {

public:

    char processStr(string s, long long k) {

        // 注意 s 输入规模可能很大

        // 最后 k 下标字符肯定源自 s

        // 因此要找到其对应原始 s 字符串中的哪个位置

        // 可以反着来把 k 位置逐渐映射回去

        int n=s.size();

        long long finalLen=0; // 计算 s 操作后的字符串长度

        for(char c:s){

            switch(c){

                case '*':

                    // 注意这里有坑，别忘了有字符才能删

                    finalLen=max(0LL,finalLen-1);

                    break;

                case '#':

                    finalLen<<=1;

                    break;

                case '%':

                    break;

                default:

                    finalLen++;

            }

        }

        long long pos=k;

        if(finalLen<=pos){

            // 在最终的长度之外直接 pass

            return '.'; 

        }

        // cout<<finalLen<<endl;

        for(int i=n-1;i>=0;i--){

            switch(s[i]){

                case '*':

                    // 是删除字符

                    finalLen++;

                    break;

                case '#':

                    // 复制。如果 pos 在后半段则映射回前半段

                    // 这里 finalLen 肯定是偶数

                    if(pos>=(finalLen>>1)){

                        pos=(finalLen>>1)-(finalLen-pos);

                    }

                    finalLen>>=1;

                    break;

                case '%':

                    // 反转

                    // 注意此时 finalLen 可能是奇数

                    pos=finalLen-1-pos;

                    break;

                default:

                    // 添加字符

                    if(finalLen-1==pos){

                        // 如果反向移除的这个字符正好在 pos 这个位置

                        // 那么就找到了

                        return s[i];

                    }

                    finalLen--;

                    break;

            }

        }

        // 最后映射回去越界了

        if(pos<0||pos>=n){

            return '.';

        }

        return s[pos];

    }

};

Qiansui 06-17 10:19

2楼

逆向到字符刚添加进去的时候 ~

class Solution {

public:

    char processStr(string s, long long k) {

        ++ k;

        long long len = 0;

        for(auto& ch : s){

            if(ch >= 'a' && ch <= 'z') ++ len;

            else if(ch == '*'){

                if(len) -- len;

            }else if(ch == '#') len *= 2;

        }



        char ans = '.';

        if(k <= len){

            for(auto iter = s.rbegin(); iter != s.rend(); ++ iter){

                char ch = *iter;

                if(ch >= 'a' && ch <= 'z'){

                    if(k == len){

                        ans = ch;

                        break;

                    }else if(len) -- len;

                }else if(ch == '*'){

                    ++ len;

                }

                else if(ch == '#'){

                    if(k > len / 2) k -= len / 2;

                    len /= 2;

                }else if(ch == '%'){

                    k = len + 1 - k;

                }

            }

        }

        return ans;

    }

};

Lvvvv 06-17 11:46

3楼

完全不喜欢做这种题O.o。。写的我好难受

class Solution {

public:

    char processStr(string s, long long k) {

        long long len = 0;

        for(const auto&c : s) {

            if(c == '*') {

                if(len > 0) {

                    len--;

                }

            } else if(c == '#') {

                len *= 2;

            } else if(c != '%') {

                len++;

            }

        }

        if(k + 1 > len) {

            return '.';

        }

        for(int i = s.size() - 1; i >= 0; i--) {

            char c = s[i];

            if(c == '*') {

                len++;

            } else if(c == '#') {

                if(k  + 1 >  (len + 1) / 2) {

                    k -= len / 2;

                }

                len = (len + 1) / 2;

            } else if(c == '%') {

                if(k <= len - 1) {

                    k = len - 1 - k;

                }

            } else {

                if(k + 1 == len) {

                    return c;

                } else {

                    len--;

                }

            }

        }

        return '.';

    }

};

CPython 06-17 18:05

4楼
得了一种看到困难就不想写的病

力扣 LeetCode

1021. 删除最外层的括号 - 力扣（LeetCode）

1021. 删除最外层的括号 - 有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。

* 例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1...
```
class Solution:

    def removeOuterParentheses(self, s: str) -> str:

        astack = []

        ans = []

        for elem in s:

            if elem == ")":

                astack.pop()

            if astack:

                ans.append(elem)

            if elem == "(":

                astack.append(elem)

        return "".join(ans)
```

* 帖子来源Linux.do

附近帖子

↑火山的codingplan上新glm5.2，求一个感受
↑应该不是巧合，GPT Free 账号最好即搓即用
↑用fable5写了一个超级马里奥
↑利用招行visa卡套Google Play开通GPT Plus绑卡需要还注意什么问题？
↑any这几天是不是上不去呀
📍 Leetcode每日一题 —— 3614. 用特殊操作处理字符串 II
↓grok heavy公益站，免费体验grok-composer-2.5-fast
↓如图，兄弟们，我这个参加过抽奖被举报过，还能升级三级吗
↓如何在君の公益使用opus 4.8
↓岂不闻，光阴如骏马加鞭，岁月如梭 ...
↓有佬目前主力 terminal 使用 ghostty 的吗

飞读

魔法师

主题数
1

帖子数
1

注册排名
3

随机推荐