1047_删除字符串中的所有相邻重复项

风扫地

1. 
   
2. /*
   
3. 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
   
4. 在 S 上反复执行重复项删除操作，直到无法继续删除。
   
5. 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
   
6. 示例：
   
7. 输入："abbaca"
   
8. 输出："ca"
   
9. 解释：
   
10. 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
    
11. 提示：
    
12.     1 <= S.length <= 20000
    
13.     S 仅由小写英文字母组成.
    
14. */

复制代码

风扫地

1. /*
   
2. * 原地模拟出栈入栈操作
   
3. */
   
4. char* removeDuplicates(char * S)
   
5. {
   
6.     int str_len     =   strlen(S) ;
   
7.     int i           =   0         ;
   
8.     int valid_index =   0         ;
   
9.                                  
   
10.     for(i = 0; i < str_len ; i++)
    
11.     {
    
12.         if(valid_index == 0)    /* 边界情况,一定是入栈*/
    
13.         {
    
14.             S[valid_index] = S[i]   ;
    
15.             valid_index++           ;
    
16.             continue                ;
    
17.         }
    
18.         
    
19.         if(S[i] == S[valid_index-1])    /* 碰到情侣就杀死*/
    
20.         {
    
21.             valid_index--           ;
    
22.             S[valid_index] = '\0'   ;
    
23.         }
    
24.         else                            /* 碰到单身狗就存好*/
    
25.         {
    
26.             S[valid_index] = S[i]   ;
    
27.             valid_index++           ;
    
28.             continue                ;
    
29.         }
    
30.     }
    
31.    
    
32.     S[valid_index] = '\0';
    
33.     return S;
    
34. }
    

复制代码

1. /*
   
2. 执行用时 :12 ms, 在所有 C 提交中击败了81.25%的用户
   
3. 内存消耗 :8 MB, 在所有 C 提交中击败了100.00%的用户
   
4. */

复制代码

风扫地

1. /*
   
2. * 实现2:原地模拟出栈入栈操作(优化循环)
   
3. */
   
4. char* removeDuplicates(char * S)
   
5. {
   
6.     int i           =   0         ;
   
7.     int valid_index =   0         ;
   
8.                                  
   
9.     while(S[i] != '\0')
   
10.     {
    
11.         if(valid_index == 0)    /* 边界情况,一定是入栈*/
    
12.         {
    
13.             S[valid_index] = S[i]   ;
    
14.             valid_index++           ;
    
15.         }
    
16.         else
    
17.         {
    
18.             if(S[i] == S[valid_index-1])    /* 碰到情侣就杀死*/
    
19.             {
    
20.                 valid_index--           ;
    
21.                 S[valid_index] = '\0'   ;
    
22.             }
    
23.             else                            /* 碰到单身狗就存好*/
    
24.             {
    
25.                 S[valid_index] = S[i]   ;
    
26.                 valid_index++           ;
    
27.             }
    
28.         }
    
29.         i++;
    
30.     }
    
31.    
    
32.     S[valid_index] = '\0';
    
33.     return S;
    
34. }

复制代码

1. /*
   
2. 实现2:
   
3. 执行用时 :4 ms, 在所有 C 提交中击败了93.25%的用户
   
4. 内存消耗 :8 MB, 在所有 C 提交中击败了100.00%的用户
   
5. */
   

复制代码

jackz007

楼主测测我的代码呢：

1. char * removeDuplicates(char * S)
   
2. {
   
3.         int i = 1 , k , m                                          ;
   
4.         m = strlen(S)                                              ;
   
5.         while(m > 1 && i < m) {
   
6.                 if (S[i] == S[i - 1]) {
   
7.                     for(k = i ; k <= m ; k ++) S[k - 1] = S[k + 1] ;
   
8.                     m -= 2                                         ;
   
9.                     i = 1                                          ;
   
10.                 } else i ++                                        ;
    
11.         }
    
12.         return S                                                   ;
    
13. }

复制代码

风扫地

jackz007 发表于 2019-6-20 10:21
楼主测测我的代码呢：

貌似有越界，提交编译失败～

jackz007

风扫地 发表于 2019-6-20 10:34
貌似有越界，提交编译失败～

    越界？完全不可能，我这里用 TDM-GCC 5.1.0 g++  编译，没有任何问题。
    这是全部代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. char * removeDuplicates(char * S)
   
6. {
   
7.         int i = 1 , k , m                                          ;
   
8.         m = strlen(S)                                              ;
   
9.         while(m > 1 && i < m) {
   
10.                 if (S[i] == S[i - 1]) {
    
11.                     for(k = i ; k <= m ; k ++) S[k - 1] = S[k + 1] ;
    
12.                     m -= 2                                         ;
    
13.                     i = 1                                          ;
    
14.                 } else i ++                                        ;
    
15.         }
    
16.         return S                                                   ;
    
17. }
    
18. 
    
19. int main(void)
    
20. {
    
21.         char S[] = {"abbaca"}                                      ;
    
22.         printf("%s\n" , removeDuplicates(S))                       ;
    
23. }
    

复制代码

风扫地

jackz007 发表于 2019-6-20 10:40
越界？完全不可能，我这里用 TDM-GCC 5.1.0 g++  编译，没有任何问题。
    这是全部代码：

跟了一下你的代码，好像没啥问题。不过力扣会反馈异常信息 heap-buffer-overflow

你可以尝试自己提交一下。
https://leetcode-cn.com/problems ... plicates-in-string/