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

风扫地

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

风扫地

/*
* 原地模拟出栈入栈操作
*/
char* removeDuplicates(char * S)
{
    int str_len     =   strlen(S) ;
    int i           =   0         ;
    int valid_index =   0         ;
                                  
    for(i = 0; i < str_len ; i++)
    {
        if(valid_index == 0)    /* 边界情况,一定是入栈*/
        {
            S[valid_index] = S[i]   ;
            valid_index++           ;
            continue                ;
        }
        
        if(S[i] == S[valid_index-1])    /* 碰到情侣就杀死*/
        {
            valid_index--           ;
            S[valid_index] = '\0'   ;
        }
        else                            /* 碰到单身狗就存好*/
        {
            S[valid_index] = S[i]   ;
            valid_index++           ;
            continue                ;
        }
    }
    
    S[valid_index] = '\0';
    return S;
}

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

风扫地

/*
* 实现2:原地模拟出栈入栈操作(优化循环)
*/
char* removeDuplicates(char * S)
{
    int i           =   0         ;
    int valid_index =   0         ;
                                  
    while(S[i] != '\0')
    {
        if(valid_index == 0)    /* 边界情况,一定是入栈*/
        {
            S[valid_index] = S[i]   ;
            valid_index++           ;
        }
        else
        {
            if(S[i] == S[valid_index-1])    /* 碰到情侣就杀死*/
            {
                valid_index--           ;
                S[valid_index] = '\0'   ;
            }
            else                            /* 碰到单身狗就存好*/
            {
                S[valid_index] = S[i]   ;
                valid_index++           ;
            }
        }
        i++;
    }
    
    S[valid_index] = '\0';
    return S;
}

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

jackz007

楼主测测我的代码呢：

char * removeDuplicates(char * S)
{
        int i = 1 , k , m                                          ;
        m = strlen(S)                                              ;
        while(m > 1 && i < m) {
                if (S[i] == S[i - 1]) {
                    for(k = i ; k <= m ; k ++) S[k - 1] = S[k + 1] ;
                    m -= 2                                         ;
                    i = 1                                          ;
                } else i ++                                        ;
        }
        return S                                                   ;
}

风扫地

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

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

jackz007

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

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char * removeDuplicates(char * S)
{
        int i = 1 , k , m                                          ;
        m = strlen(S)                                              ;
        while(m > 1 && i < m) {
                if (S[i] == S[i - 1]) {
                    for(k = i ; k <= m ; k ++) S[k - 1] = S[k + 1] ;
                    m -= 2                                         ;
                    i = 1                                          ;
                } else i ++                                        ;
        }
        return S                                                   ;
}

int main(void)
{
        char S[] = {"abbaca"}                                      ;
        printf("%s\n" , removeDuplicates(S))                       ;
}

风扫地

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

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

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