【刷题】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)，可以说是非常非常牛了。
那具体是如何操作的呢？？？

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

只看思路似乎迷迷糊糊，这是如何做到的？？？下面我们来图解一下：

我们来逐步分析：
首先为什么这样可以做到整理字符串？
该操作类似于原地删除，一旦符合条件，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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

思路很舒畅~

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！