栈-算法练习题

作者: 大橘猪猪侠 | 来源:发表于2020-04-18 16:24 被阅读0次

通过之前学习的了栈的设计和代码的编写，再去了解一些跟栈有关的一些题目。

第一题：杨辉三角

杨辉三角是一个经典的题目，在我们上大学的时候，只要是计算机专业的学生，基本上都学过如何去实现杨辉三角。学会去解决一个问题，首先要学会去分析一个题目中需要实现的图像的结构特性。

思路:

用两层循环，第一层循环控制行数 i，让 [i][0] = [i][i]=1
第二层控制循环的列数：让 [i][j] = [i-1][j]+[i-1][j-1]

核心代码

int** generate(int numRows, int* returnSize){
    
    *returnSize = numRows;
    
    int **res = (int **)malloc(sizeof(int*)*numRows);
    
    for (int i = 0; i < numRows; i++) {res[i] = (int *)malloc(sizeof(int)*(i+1));
        res[i][0] = 1;
        res[i][i] = 1;
        
        for (int j = 1; j < i; j++) {res[i][j] = res[i-1][j] + res[i-1][j-1];
        }
    }
    return res;
}

第二题：十进制转八进制

解决这一题，我们首先需要知道如何用十进制转八进制，
通过十进制数与 8 求余，再取反。因此，我们可以通过栈的思想去解决这一题。
思路：
1、初始化一个空栈
2、把十进制 N 非零时，循环执行 N 与 8 求余得到的八进制数压栈，N 更新为 N 与 8 的商
3、当栈非空时，循环将栈顶元素 e 输出

核心代码

void conversion(int N){
    
    SqStack S;
    SElemType e;
    //1. 初始化一个空栈 S
    InitStack(&S);
    
    //2.
    while (N) {PushData(&S, N%8);
        N = N/8;
    }
    //3.
    while (!StackEmpty(S)) {Pop(&S, &e);
        printf("%d\n",e);
    }
    
}

关于如何栈的一些操作不会的，可以去看我之前写的简书，在这里我就不写多余的代码了。

第三题：爬楼梯问题

假设你正在爬楼梯，需要 n 阶你才能到达楼顶，每次你可以爬 1 或 2 个台阶，你有多少种不同的方法可以爬到楼顶（n 为正整数）。

从题目意思可以看出，当只有一阶，两阶时，方法分别为1，2，为3阶时，方法有3个，4阶，5个，5阶，8个，可以得出，当前的一阶为前两阶的方法数之和。

思路：
解决这一题，或许我们最先想到的方法就是递归，通过递归去逐渐查找已知的条件。
这是最暴力的一种解法，因此，我们换一种方法去解决这一题，用一种巧妙的算法技巧 - 动态规划法去解决这个问题。
动态规划：是一种在数学、管理科学、计算机科学等学科中使用的，通过把原问题分解为相对简单的子问题的方式去求解复杂问题的方法。
动态规划法常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时往往小于朴素解法。
动态规划法背后的基本思想非常简单，解决一个给定的问题，我们需要将它分解不同的子问题，再根据子问题的得出原问题的解。利用动态规划的思想可以减少计算量。

核心代码：

//动态规划法
int ClimbStairs(int n){
    if(n<0) return 0;
    int temp = n+1;
    int *sum = (int *)malloc(sizeof(int) * temp);
    sum[0] = 0;
    sum[1] = 1;
    sum[2] = 2;
    for (int i = 3; i<=n; i++) {
        sum[i] = sum[i-1]+sum[i-2];
    }
    return sum[n];
}

第四题：每日气温

根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置0来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

题目的意思很好理解，简单来说，找到第一个大于当前气温的数值，将大于数值的位置数减去当前数值的位置数就可以

思路：
一、暴力法

从左到右开始遍历,从第一个数到最后一个数开始遍历. 最后一个数因为后面没有元素,默认是0,不需要计算;
从[i+1,TSize]遍历,每个数直到找到比它大的数,数的次数就是对应的值;

int  *dailyTemperatures_1(int* T, int TSize, int* returnSize){
    
    int *result = (int *)malloc(sizeof(int) * TSize);
    *returnSize = TSize;
    result[TSize-1] = 0;
    
    for(int i = 0;i < TSize-1;i++)
        if(i>0 && T[i] == T[i-1])
            result[i] = result[i-1] == 0?0:result[i-1]-1;
        else{
            for (int j = i+1; j < TSize; j++) {
                if(T[j] > T[i]){
                    result[i] = j-i;
                    break;
                }
                if (j == TSize-1) {
                    result[i] = 0;
                }
            }
        }
    
    return result;
}

二、跳跃对比:

从右到左遍历. 因为最后一天的气温不会再升高,默认等于0;
i 从[TSize-2,0]; 从倒数第二天开始遍历比较. 每次减一;
j 从[i+1,TSize]遍历, j+=result[j],可以利用已经有结果的位置进行跳跃,从而减少遍历次数
-若T[i]<T[j],那么Result = j - i;
-若reuslt[j] == 0,则表示后面不会有更大的值,那么当前值就应该也是0;

int dailyTemperatures_2(int T, int TSize, int* returnSize){

int *result = (int *)malloc(sizeof(int) * TSize);
*returnSize = TSize;
result[TSize-1] = 0;

for (int i=TSize-2; i >= 0; i--) {
    for (int j = i+1; j < TSize; j+=result[j]) {
        if (T[i] < T[j]) {
            result[i] = j-i;
            break;
        }else
        {
            if (result[j] == 0) {
                result[i] = 0;
                break;
            }
        }
    }
}
return result;

}

三、用栈的思想去解决问题

初始化一个栈(用来存储索引),value数组
栈中存储的是元素的索引值index;
2.将当前元素和栈顶元素比较;
如果栈为空,那么直接将当前元素索引index 存储到栈中;
如果栈顶元素>当前元素,则将当前元素索引index 存储到栈中;
如果栈顶元素<当前元素,则将当前元素索引index-栈顶元素index,计算完毕则将当前栈顶元素移除,将当前元素索引index 存储到栈中

int* dailyTemperatures_3(int* T, int TSize, int* returnSize) {
    
    int* result = (int*)malloc(sizeof(int)*TSize);
    // 用栈记录T的下标。
    int* stack_index = malloc(sizeof(int)*TSize);
    *returnSize = TSize;
    // 栈顶指针。
    int top = 0;
    int tIndex;
    
    for (int i = 0; i < TSize; i++)
        result[i] = 0;
    
    for (int i = 0; i < TSize; i++) {
        printf("\n循环第%d次,i = %d\n",i,i);
       
        // 若当前元素大于栈顶元素，栈顶元素出栈。即温度升高了，所求天数为两者下标的差值。
        while (top > 0 && T[i] > T[stack_index[top-1]]) {
            tIndex = stack_index[top-1];
            result[tIndex] = i - tIndex;
            top--;
            printf("tIndex = %d; result[%d] = %d, top = %d \n",tIndex,tIndex,result[tIndex],top);
        }
        
        // 当前元素入栈。
        stack_index[top] = i;
        printf("i= %d;  StackIndex[%d] = %d ",i,top,stack_index[top]);
        top++;
        
        printf(" top = %d \n",top);
    }
    
    return result;
}

从上面三个思路中，思路二是最巧妙的解题方法，从后向前与遍历，利用已知结果的位置进行跳跃，从而减少遍历次数。

第五题：括号匹配

给定一个只包含 '('，')'，'['和']'的字符串，判断字符串是否有效。有效的条件为：括号必须有相同的括号对应，且括号必须以正确的顺序对应。

从这一题，我们可以得知，判断条件是否成立，需要括号必须有相同的括号对应，且顺序不能变，这一题的解法我们可以利用栈的结构特性来解决，通过判断数据的第一个数据与第二数据是否匹配，匹配的话，就将第一个数据出栈。
思路：
1、将输入的数据用数组保存起来
2、将数据的第0个数入栈
3、循环遍历，判断数组第1个数与栈顶是否匹配，不匹配就入栈，匹配就出栈，直至循环结束
代码部分：

/*
 初始化栈
 
 如果栈底为空
 分配一个最大容量的Stack_Init_Size的数组，将栈底和栈顶都指向它
 初始化栈的最大容量Stack_Init_Size
 */
int Init(Stack *stack){
    stack->base = (char *)malloc(Stack_Init_Size*sizeof(char));
    stack->top = stack->base;
    if(stack->base==NULL)  return -1;//表示无法初始化栈
    stack->stacksize = Stack_Init_Size;
    printf("初始化成功\n");
    return 0;
}
/*
 获取栈顶元素
 
 判断栈是否为空
 非空，则栈顶指针 -1，返回栈顶元素
 */
char GetTop(Stack stack){
    if(stack.top == stack.base){
        printf("栈中没有数据\n");
        return '#';
    }
    return *(stack.top-1);
}
/*
插入元素
 
 判断栈是否已满，
 栈满，则容量增加
 将元素e压栈
 栈顶指针+1
 */
int Push(Stack *stack,char e){
    if(stack->top - stack->base == stack->stacksize){
        stack->base = (char *)realloc(stack->base, Stack_Increment*sizeof(char));
        stack->top = stack->base+stack->stacksize;
        stack->stacksize+=Stack_Increment;
    }
    *stack->top = e;
    stack->top+=1;
    return 0;;
}
/*
 删除栈顶元素
 
 判断栈是否为空
 非空取栈顶元素，栈顶-1
 */
char pop(Stack *stack){
    if(stack->top == stack->base){
        printf("栈为空\n");
        return '#';
    }
    return *--stack->top;
}
//销毁栈
int Destory(Stack *stack){
    free(stack->base);
    stack->stacksize = 0;
    return 0;
}

核心代码


/*
 处理数据
 
 1、将第0个元素压栈
 2、遍历[1,strlen(data)]
     1、取栈顶字符
     2、检查该字符是左括号
        a、是左 (，则判断下一个数是否为右
            yes，压栈，NO，出栈
        b、是左 [,
            yes，压栈，NO，出栈
        c、表示如果以#结尾，则判断其后的data是左
            yes，压栈，no ，-1
            
 */
int ExecuteData(Stack stack,char *data){
    Push(&stack, data[0]);
    for (int i = 1; i<strlen(data); i++) {
        char top = GetTop(stack);
        switch (top) {
            case '(':
                if(data[i] == ')')pop(&stack);
                else Push(&stack, data[i]);
                break;
            case '[':
                if(data[i] == ']')pop(&stack);
                else Push(&stack, data[i]);
                break;
            case '#':
                if(data[i] == '(' || data[i] == '['){
                    Push(&stack, data[i]);
                    break;
                }else
                    default:return -1;break;
        }
    }
    if(stack.top == stack.base){
        Destory(&stack);
        return 0;
    }else{
        Destory(&stack);
        return -1;
    }
}

main函数和打印结果

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    Stack stack;
    Init(&stack);
    char data[180];
    scanf("%s",data);
    int result = ExecuteData(stack,data);
    if(result==0)printf("括号是正确匹配的\n");
    else printf("括号匹配不正确\n");
    return 0;
}

15871964348733.png

15871964860638.png

第六题：字符串编码

编码规则为: 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".

这一题相比前几题更难一点，看到题目的示例，是不是觉得很复杂，我们可以先考虑一个简单的例子，例如 5[a],返回“aaaaa”，这个题目的突破口就是两个中括号“[]”。
解题思路
1、获取字符串长度
2、设置默认栈长度50，
3、开辟字符串栈
4、设置头指针top = -1
5、遍历字符串，在“]”之前的字符串全部入栈
6、用另一栈记录在“[”之前的字符串
7、将“[”之前的数字保存在数组当中，将数组转为整型n。
8、循环遍历，将“[]”内的字符串重复入栈n次，
9、释放临时保存字符串的栈。

char *decodeString(char *s){
    int len = (int)strlen(s);
    //栈的大小
    int stackSize = 50;
    //动态申请内存空间
    char *stack = (char *)malloc(sizeof(char)*stackSize);
    int top = -1;
    
    //遍历字符串，在没遇到"]"之前全部入栈
    for (int i = 0; i<len; ++i) {
        if(s[i]!=']'){
            //入栈
            stack[++top] = s[i];
        }else{
            //存放字符串的栈的大小
            int tempSize = 10;
            //动态申请内存空间
            char *temp = (char*)malloc(sizeof(char)*tempSize);
            int topOfTemp = -1;
            //判断“[”之前的字符串
            while (stack[top] != '[') {
                ++topOfTemp;
                //将字符串入栈
                temp[topOfTemp] = stack[top];
                //stack出栈，则top栈顶指针递减
                top--;
            }
            //找到倍数数字，strOfInt字符串
            char strOfInt[11];
            int curTop = top;
            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 index = topOfTemp;
                while (index!=-1) {
                    ++top;
                    stack[top] = temp[index];
                    index -- ;
                }
                
            }
            free(temp);
            temp = NULL;
        }
    }
    //realloc 动态内存调整
    //构成字符串stack后，在stack的空间扩容
    char *m= realloc(stack, (top+1)*sizeof(char));
    m[++top] = '\0';
    free(stack);
    return m;
}

main函数

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

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

打印结果

15871978193530.png

栈-算法练习题

第一题：杨辉三角

第二题：十进制转八进制

第三题：爬楼梯问题

第四题：每日气温

第五题：括号匹配

第六题：字符串编码

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读