一、字符编码问题

题目: 字符串编码，编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
例如：
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

算法思路

以"3[a]2[bc]"为例：
1、初始化一个栈stack，用来存储结果；
2、遍历字符串，将']'字符前的所有字符都入栈，此时stack里面保存的字符为3[a；
3、当检测到字符']'时，说明已经有一个完整编码的字符串了（此时为"3[a]"），此时开始对栈里面的字符串进行解码。
4、由编码格式可以看出，字符是在[]中，循环次数是在[]外面。因此，可将栈里面的数据元素依次出栈。
4.1 当遇见'['之前，此时出栈的都是字符，可暂时写入另一个栈。
4.2 当遇见'['时，说明编码的字符已经完全出栈，栈里面剩下的就是循环次数了。
4.3 将栈里面的数据继续出栈，直至栈为空或者栈顶数据不是数字字符时，停止出栈。
由上面三步可以得出，编码的字符串为"a"，编码的次数为"3"。因此，只需要将字符串"a"循环3次再次入stack栈即可。入栈完成后，stack里面的保存的数据为"aaa"；
5、当原字符串未结束时，重复2-4步，直至完成整个字符串的搜索。
6、得到最终于的字符串''aaabcbc"保存在stack栈中。

代码实现

BOOL isNum(char c){
    if(c >= '0' && c <= '9') return YES;
    return NO;
}

char * decodeString(char * s){
    int len = strlen(s);
    int stackSize = 50;
    char *stack = (char*)malloc(stackSize*sizeof(char));
    int stackTop = -1;
    int numTimes = 0;
    
    int i = 0;
    while(i < len){
        if(s[i] != ']'){
            stack[++stackTop] = s[i];
            i++;
        }
        else{
            char *charTemp = (char*)malloc(stackSize*sizeof(char));
            int charTempTop = -1;
            while(stack[stackTop] != '['){
                charTemp[++charTempTop] = stack[stackTop];
                stackTop--;
            }
            stackTop--;
            numTimes = 0;
            char strOfInt[11] = {0};
            int oriTop = stackTop;
            while(stackTop != -1 && isNum(stack[stackTop])){
                stackTop --;
            }
            for(int j = stackTop+1; j<=oriTop; j++){
                strOfInt[j-stackTop-1] = stack[j];
            }
            numTimes = atoi(strOfInt);
            
            for(int i = 0; i < numTimes; i++){
                int j = charTempTop;
                while(j != -1){
                    stack[++stackTop] =charTemp[j--];
                }
            }
            free(charTemp);
            charTemp = NULL;
            i++;
        }
    }
    return stack;
}

二、去掉重复字母问题

给定一个仅包含小写字母的字符串，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
例如：
"bcabc" 返回"abc"
"cbacdcbc" 返回"acdb"
"zab" 返回"zab"

算法思路

该题目的重点是：返回字典序最小，且不打乱其它字符的位置。
如何返回字典序最小？则按字母顺序排列即可。
那不打乱其它字符的位置？此时，字符出现的剩余次数就可以用来判断。
例如："cdacdcbc"，为了保证字典序最小，栈里面的元素应该从小到大排列。当栈里面的元素按"cd"排列时，突然出现比"d"小的字符"a"，并且后面不会再出现"d"字符，此时应该将a入栈，并从"a"开始重新按字母大小排序，这样才能保证字典序最小。

代码实现

char *removeDuplicateLetters(char *s){
    int len = strlen(s);
    char* stack = (char*)malloc(len*2 * sizeof(char));
    int stackTop = -1;
    //1、 遍历s，标记每个字符出现的次数
    char record[26+1] = {0};
    for(int i = 0; i < len; i++){
        record[s[i]-'a'] += 1;
    }
    
    for(int i = 0; i<len; i++){
        //遍历栈里面存的数据，查看是否是栈已经存放了该数据
        int exist = 0;
        for(int j = 0; j<=stackTop; j++){
            if(stack[j] == s[i]){
                exist = 1;
                break;
            }
        }
        
        if(exist == 1){
            record[s[i] - 'a']--;
        }
        else{
            //当前栈里面的元素是否为空，不为空的话，需要将当前字符与栈顶比较；
            //1、栈顶为空时，直接将元素入栈；
            //2、栈顶不为空时，且当前元素比栈顶元素小时：
            //2.1 栈顶元素后面不会再出现，即record[stack[stackTop] - 'a']>1，此时当前元素直接入栈；
            //  如s=cdacbcbc，当前元素s[2]=a时，由于d后面不会再有，因此此时的a直接入栈；
            //2.2 栈顶元素后面还会再出现，需要将当前栈元素出栈，并且由于栈顶元素已经比较过一次，故record[s[i] - 'a']--；
            //  重复比较栈顶，直至所有符合2.2条件的数据都出栈后，再将s[i]入栈；
            //  如s=bcabc,
            //      当前元素s[2]=a时,由于c后面还会出现，故c需要先出栈，且c出现的次数要减1；
            //      此时栈中剩下b，由于b比a大且b后面也会再出现，因此b也要先出栈，且b出现的次数要减1；
            //      此时栈里面已经没有元素了，则需要将a入栈；
            while(stackTop != -1 && stack[stackTop]>s[i] && record[stack[stackTop] - 'a']>1){
                record[stack[stackTop] - 'a']--;
                stackTop--;
            }
            stack[++stackTop] = s[i];
        }
    }
    stack[++stackTop] = '\0';
    
    return stack;
}