【刷题】leetcode 1544.整理字符串

在这里插入图片描述

刷题

1544.整理字符串
- 思路一（模拟栈速解版）
- 思路二（原地算法巧解版）
- 思路三（C++栈版）
Thanks♪(･ω･)ﾉ谢谢阅读！！！
下一篇文章见！！！

1544.整理字符串

来看题目描述
在这里插入图片描述
我看到本题的第一想法是双指针法，但是我所构想的逻辑无法达到目的，具体来说我采用前后指针，依次前进，然后满足条件就跳过，这样就导致会忽略许多满足的结构，就让我十分头疼，调试了半天还是不行，甚至想要使用三指针，四指针…服啦！结果表明都是不行的。下面来一起看看正确解法吧

思路一（模拟栈速解版）

这个和括号匹配问题很像，把字符串依次入栈，然后满足条件的就一起消除，主要就用到栈的压栈操作和取栈顶操作。这样一一匹配就能达到要求。来看图解：
在这里插入图片描述
按照栈的方法很快速的就解决了问题，所以选择真的大于努力，这个问题选择栈就能快速解决，要是使用多指针就深陷泥潭了，来看代码实现：

char* makeGood(char* s) {
    if (*s == '\0') return s;
    if (*(s + 1) == '\0') return s;

    int top = 0;
    // 使用栈的思想
    char* ret = (char*)malloc(sizeof(char) * 100);
    char* cur = s;
    ret[top] = ' ';
    //依次入栈 并检查是否与栈顶元素符合条件
    while (*cur != '\0') {
        if (abs(ret[top] - *cur) == abs('A' - 'a')) {
            ret[top] = '\0';
            top--;
            cur++;
        }
        else {
            top++;
            ret[top] = *cur;
            cur++;
        }
    }
    //切记数组结尾加入 ‘\0’
    ret[++top] = '\0';
    return ret + 1;
}

来看效果：
在这里插入图片描述
顺利通过！！！大声欢呼：过啦！！！！！！！

思路二（原地算法巧解版）

这个思路十分奇妙的一个算法，空间复杂度为O(1)，可以说是非常非常牛了。
那具体是如何操作的呢？？？

首先定义双指针 i j 分别指向头和头的下一个位置。
设置循环，j 遍历到尾结束。
开始判断，如果不满足条件（互不为大小写并且 i 不等于-1）则 s[++i] = s[ j++ ] （关键一步）否则 i–。
依次往复，就可以完成任务。

只看思路似乎迷迷糊糊，这是如何做到的？？？下面我们来图解一下：
在这里插入图片描述
我们来逐步分析：
首先为什么这样可以做到整理字符串？
该操作类似于原地删除，一旦符合条件，i-- j++ 直接把他们就跳过了，然后如果不满足条件，就将 j 指向的内容拷贝到 i 位置，
然后继续判断。这样就可以完成操作了。
其次是为什么要加入i == -1 ？？？
因为会遇到前面全部被删除的情况，所以要加入i == -1。
来看代码实现：

char * makeGood(char * s){
    int i = 0, j = 1;
    //开始遍历
    while(j < strlen(s)){
        if(i == -1 ||  abs(s[i] - s[j]) != abs('A' - 'a')){
            s[++i] = s[j++];
        }
        //相当于删除元素
        else{
            i--;
            j++;
        }
    }
    s[++i] = '\0';
    return s;
}

来看效果：
在这里插入图片描述
非常好！！！过啦！！！！！！！

思路三（C++栈版）

我们来看C++栈的写法，思路与思路一致：

void dfs(struct TreeNode *node, bool *color) {
    color[node->val] = true;
    if (node->left ) dfs(node->left , color);
    if (node->right) dfs(node->right, color);
}
int numColor(struct TreeNode* root){
    bool *color = (bool *)calloc(1, sizeof(bool) * 1001);int ans = 0;
    dfs(root, color);
    for (int i = 1; i < 1001; ++ i)
        if (color[i]) ++ ans;
    return ans;
}

作者：_G_
链接：https://leetcode.cn/problems/sZ59z6/solutions/2580610/shen-du-you-xian-sou-suo-by-admiring-men-2rzv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。