数据结构与算法 习题2

1.括号匹配检验: (字节出现过的算法⾯试题/LeetCode) 假设表达式中允许包含两种括号:圆括号与⽅括号,其嵌套顺序随意,即() 或者[([][])]都是正 确的.⽽这[(]或者(()])或者([()) 都是不正确的格式. 检验括号是否匹配的⽅法可⽤”期待的急迫 程度"这个概念来描述.例如,考虑以下括号的判断: [ ( [ ] [ ] ) ]

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

typedef struct Node{
    struct Node* next;
    char data;
}Node;

typedef struct {
    Node* top;
    int length;
}CharStack;

int initStack(CharStack* stack){
    stack->top = NULL;
    stack->length = 0;
    return 1;
}

int pushElement(CharStack *stack,char e){
    Node* node = malloc(sizeof(Node));
    if (node == NULL) {
        return 0;
    }
    node->data = e;
    node->next = stack->top;
    stack->top = node;
    stack->length++;
    return 1;
}

int popElement(CharStack *stack, char* e){
  if (stack -> top == NULL) {
  return 0;
  }
    Node* tem = stack->top -> next;
    *e = stack->top;
    free(stack->top);
    stack->top = tem;
    stack->length--;
    return 1;
}

int traverseStack(CharStack stack){
    Node* tem = stack.top;
    while (tem) {
        printf("%c ", tem->data);
        tem = tem->next;
    }
    printf("\n");
    return 1;
}
char getTop(CharStack stack){
    if (stack.top == NULL) {
        return '#';
    }
    return stack.top->data;
}
int compareString(CharStack stack, char* data){
    char tem_char;
    for (int i = 0; i < strlen(data); i++) {
        char top = getTop(stack);
        switch (top) {
            case '{':
            {
                if (data[i] == '}') {
                    popElement(&stack, &tem_char);
                }else{
                    pushElement(&stack, data[i]);
                    
                }
            }
                
                break;
            case '[':
            {
                if (data[i] == ']') {
                    popElement(&stack, &tem_char);
                }else{
                    pushElement(&stack, data[i]);
                    
                }
            }
                break;
            
            default://top返回’#‘这种情况
                pushElement(&stack, data[i]);
                break;
        }
    }
    if (stack.top == NULL) {
        return 1;
    }
    return 0;
    
}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    CharStack stack;
    initStack(&stack);
    char* string = "{[][]}";
    int result = compareString(stack, string);
    printf("result:%s", result?"匹配":"不匹配");
    
    return 0;
}

2.每⽇⽓温: (LeetCode-中等) 题⽬: 根据每⽇⽓温列表，请重新⽣成⼀个列表，对应位置的输⼊是你需要再等待多久温度才 会升⾼超过该⽇的天数。如果之后都不会升⾼，请在该位置0来代替。例如，给定⼀个列 表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。提示：⽓温 列表⻓度的范围是 [1, 30000]。每个⽓温的值的均为华⽒度，都是 在 [30, 100] 范围内的整数

//倒比法
//说下我的理解，如果倒比暴力破解的话应该是
//将下面的 j+= tem[j]改成 j++
//如下就是标准的暴力破解
int *dailyTemperatures_2(int* T, int TSize, int* reuturnSize){
    *reuturnSize = TSize;
    int * tem = malloc(sizeof(int) * TSize);
    tem[TSize - 1] = 0;
    for (int i = TSize - 2; i >= 0; i --) {
        for (int j = i + 1; j < TSize; j ++) {
            if (T[i] < T[j]) {
                tem[i] = j - i;
                break;
            }
        }
    }
    return tem;
}

//但是为了优化，我们可以将已经破解过的也就是i后面的i+1的元素的值为参考（为什么？因为i+1他的结果所指向的位置肯定是比i+1值大的），以跳跃到 i + tem[i+1]位置的方式去进行减少运算达到优化的效果
int *dailyTemperatures_2opt(int* T, int TSize, int* reuturnSize){
    *reuturnSize = TSize;
    int * tem = malloc(sizeof(int) * TSize);
    tem[TSize - 1] = 0;
    for (int i = TSize - 2; i >= 0; i --) {
        for (int j = i + 1; j < TSize; j += tem[i+1]) {
            if (T[i] < T[j]) {
                tem[i] = j - i;
                break;
            }else{
                if (tem[j] == 0) {
                    tem[i] = 0;
                }
            }
        }
    }
    return tem;
}
//栈方法
int *dailyTemperatures_3(int* T, int TSize, int* reuturnSize){
    *reuturnSize = TSize;
    int* result = malloc(sizeof(int) * TSize);
    int* stack_indexs = malloc(sizeof(int) * TSize);
    int top = -1;
    for (int i = 0; i < TSize; i++)
        result[i] = 0;
    
    for (int i = 0;  i < TSize; i++) {
        while  (top >= 0 && T[i] > T[stack_indexs[top]]) {
             //出栈
            int top_index = stack_indexs[top];
            result[top_index] = i - top_index;
            top--;
         }
            //入栈
        top++;
        stack_indexs[top] = i;

    }
    return result;
}

3.爬楼梯问题:(LeetCode-中等) 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不 同的⽅法可以爬到楼顶呢？注意：给定 n 是⼀个正整数

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

/*
 方法一:递归求解法
 f(n) = f(n-1) + f(n-2);
 f(1)=1;
 f(2)=1;
 */
int ClimbStairs_1(int n){
    
    if (n<1)  return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;
    
    return ClimbStairs_1(n-1) + ClimbStairs_1(n-2);
}

4.去除重复字⺟(LeetCode-困难) 给你⼀个仅包含⼩写字⺟的字符串，请你去除字符串中重复的字⺟，使得每个字⺟只出现⼀ 次。需保证返回结果的字典序最⼩（要求不能打乱其他字符的相对位置）

解题关键:
 字典序: 字符串之间比较和数字比较不一样; 字符串比较是从头往后挨个字符比较,那个字符串大取决于两个字符串中第一个对应不相等的字符; 例如 任意一个a开头的字符串都大于任意一个b开头的字符串;例如字典中apple 大于 book;
 题目的意思,你去除重复字母后,需要按最小的字典序返回.并且不能打乱其他字母的相对位置;
 例如 bcabc 你应该返回abc, 而不是bca,cab;
 例如 cbacdcbc 应该返回acdb,而不是cbad,bacd,adcb
 例如 zab,应该返回zab,而不是abz;
 
 */
char *removeDuplicateLetters(char *s)
{
    /*
     ① 特殊情况处理,s为空,或者字符串长度为0;
     ② 特殊情况,s的长度为1,则没有必要后续的处理,则直接返回s;
     */
    if (s == NULL || strlen(s) == 0) {
        return "";
    }
    if (strlen(s) == 1) {
        return s;
    }
    
    char record[26] = {0};
    int len = (int)strlen(s);
    
    char* stack = (char*)malloc(len * 2 * sizeof(char));
    //memset(void *s, int ch, size_t n) 将stack len*2*sizeof(char)长度范围的空间填充0;
    memset(stack, 0, len * 2 * sizeof(char));
    //stack 栈顶赋初值为-1;
    int top = -1;
    
    //1.统计每个字符的频次
    int i;
    for (i = 0; i < len; i++) {
        record[s[i] - 'a']++;
    }
    
    //2.遍历s,入栈
    for (i = 0; i < len; i++) {
        
        
        int isExist = 0;
        for (int j = 0; j <= top; j++) {
            if (s[i] == stack[j]) {
                isExist = 1;
                break;
            }
        }
        
        if (isExist == 1) {
            record[s[i] - 'a']--;
        } else {
            while (top > -1 && stack[top] > s[i] && record[stack[top] - 'a'] > 1) {
               
                // 跳过该元素，频次要减一
                record[stack[top] - 'a']--;
                // 出栈
                top--;
            }

            top++;
            // 入栈
            stack[top] = s[i];
        }
    }
    
    //结束栈顶添加字符结束符
    stack[++top] = '\0';
    
    return stack;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("去掉重复字母! LeetCode-困难 \n");
    
    char *s ;
    s = removeDuplicateLetters("bcabc");
    printf("%s\n",s);
 
    s = removeDuplicateLetters("zab");
    printf("%s\n",s);

    s = removeDuplicateLetters("cbacdcbc");
    printf("%s\n",s);
    
    printf("\n");
    return 0;
}

5.字符串编码(LeetCode-中等) 给定⼀个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中⽅括号内部的 encoded_string 正好重复 k 次。 注意 k 保证为正整数。你可以认为输⼊字符串总是有效的；输⼊字符串中没有额外的空格， 且输⼊的⽅括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只 表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输⼊。 例如: s = "12[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

char * decodeString(char * s){
   
    /*.
     1.获取字符串长度
     2.设置默认栈长度50
     3.开辟字符串栈(空间为50)
     4.设置栈头指针top = -1;
     */
    int len = (int)strlen(s);
    int stackSize = 50;
    char* stack = (char*)malloc(stackSize * sizeof(char));
    int top = -1;
    
    //遍历字符串,在没有遇到"]" 之前全部入栈
    for (int i = 0; i < len; ++i) {
        if (s[i] != ']') {
            //将字符入栈stack
            stack[++top] = s[i];
        }
        else {
            int tempSize = 10;
            char* temp = (char*)malloc(tempSize * sizeof(char));
            int topOfTemp = -1;
            
            while (stack[top] != '[') {
                ++topOfTemp;
                temp[topOfTemp] = stack[top];
                //stack出栈,则top栈顶指针递减;
                top--;
            }
            
            //找到倍数数字.strOfInt字符串;
            char strOfInt[11];
            int curTop = top;
            top--;
            while (top != -1 && stack[top] >= '0' && stack[top] <= '9') {
                top--;
            }
            for (int j = top + 1; j < curTop; ++j) {
                strOfInt[j - (top + 1)] = stack[j];
            }
            //为字符串strOfInt数组加一个字符结束后缀'\0'
            strOfInt[curTop - (top + 1)] = '\0';

            //把字母复制strOfInt份到stack中去;
            int curNum = atoi(strOfInt);
            for (int k = 0; k < curNum ; ++k) {
                
                int kk = topOfTemp;
                while (kk != -1) {

                    ++top;
                    stack[top] = temp[kk];
                    kk--;
                    
                }
            }
            free(temp);
            temp = NULL;
        }
    }
    
    //realloc 动态内存调整;
    //void *realloc(void *mem_address, unsigned int newsize);
    //构成字符串stack后, 在stack的空间扩容.
    char* ans = realloc(stack, (top + 1) * sizeof(char));
    ans[++top] = '\0';
    
    //stack 栈不用,则释放;
    free(stack);
    return ans;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("字符串编码问题!\n");
    
    char *s ;
    s = decodeString("12[a]");
    printf("字符编码后的结果: %s\n\n\n\n",s);
    
    s = decodeString("3[a]2[bc]");
    printf("字符编码后的结果: %s\n\n\n\n",s);

    s = decodeString("3[a2[c]]");
    printf("字符编码后的结果: %s\n\n\n\n",s);

    s = decodeString("2[abc]3[cd]ef");
    printf("字符编码后的结果: %s\n\n\n\n",s);

    printf("\n");

    return 0;
}