风扫地 发表于 2019-6-20 09:41:30

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


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




风扫地 发表于 2019-6-20 09:42:27

/*
* 原地模拟出栈入栈操作
*/
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 = S   ;
            valid_index++         ;
            continue                ;
      }
      
      if(S == S)    /* 碰到情侣就杀死*/
      {
            valid_index--         ;
            S = '\0'   ;
      }
      else                            /* 碰到单身狗就存好*/
      {
            S = S   ;
            valid_index++         ;
            continue                ;
      }
    }
   
    S = '\0';
    return S;
}


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

风扫地 发表于 2019-6-20 09:53:30

本帖最后由 风扫地 于 2019-6-20 09:58 编辑

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


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

jackz007 发表于 2019-6-20 10:21:05

本帖最后由 jackz007 于 2019-6-20 10:23 编辑

楼主测测我的代码呢：
char * removeDuplicates(char * S)
{
      int i = 1 , k , m                                          ;
      m = strlen(S)                                              ;
      while(m > 1 && i < m) {
                if (S == S) {
                  for(k = i ; k <= m ; k ++) S = S ;
                  m -= 2                                       ;
                  i = 1                                          ;
                } else i ++                                        ;
      }
      return S                                                   ;
}

风扫地 发表于 2019-6-20 10:34:16

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

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

jackz007 发表于 2019-6-20 10:40:54

本帖最后由 jackz007 于 2019-6-20 10:42 编辑

风扫地 发表于 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 == S) {
                  for(k = i ; k <= m ; k ++) S = S ;
                  m -= 2                                       ;
                  i = 1                                          ;
                } else i ++                                        ;
      }
      return S                                                   ;
}

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

风扫地 发表于 2019-6-20 10:54:40

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

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

你可以尝试自己提交一下。
https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
页: [1]
查看完整版本: 1047_删除字符串中的所有相邻重复项