栈与队列算法题合集(上)

算法，是我们程序员纵向发展所必须攀登的一座大山，下面我们做一些算法题，难度逐渐递增。当然我们碰见解不开的题时千万不要气馁，有时候一天做出一道题，都是很不容易的。下面我将自己的一些做算法的方法分享一下，如有不当，还望包涵。
①. 充分阅读题目.了解题目背后的关键意思;
②. 分析题目,涉及到哪些数据结构,对问题进行分类. 到底属于链表问题, 栈思想问题, 字符串问题,二叉树问题,图相关问题,排序问题; 与你之前所接触过的算法题有没有类似,找到问题的解题思路
③. 实现算法. 在算法的实现的过程,并不是一蹴而就, 肯定是需要不断的调试,修改的;
④. 验证算法正确性
⑤. 找到题源, 看其他的开发者对齐的解决思路.
⑥. 找到题解建议之后, 对于其他优秀思路,分析它的优势,并且学习它的思路.并且写成其他解法的代码
⑦. 算法题的解题能力来自于2点: 对于数据结构与算法核心问题是否夯实 + 是否有足够多且足够耐心的积累;

其中第五步和第六步格外的重要，我们在作出算法题之后，不要沉迷于短暂的喜悦之中，而是要多看看其他大神的解题思路，取其精华，学习思想，算法最重要的还是思想，只做题的话就有点拣了芝麻丢了西瓜的意思了。

我们做算法的时候可以多利用栈的思想（先进后出）解决问题，有时候会特别方便，那么什么时候可以利用栈思想呢？大体分为以下三点：

1. 数据是线性的
2. 问题中常常涉及到数据的来回比较,匹配问题;例如,每日温度,括号匹配,字符串解码,去掉重复字母等问题.
3. 问题中涉及到数据的转置,例如进制问题.链表倒序打印问题等

Tip：注意并不是说栈思想只是一个解决的的参考思想.并不是万能的.它适用于以上这样的情况下去解决问题;

一、进制转化问题（LeetCode-简单）
给定一个十进制的数字N，将其转化为M进制（以8为例）。
首先我们实现一个栈
解题思路：

1. 初始化一个空栈S
2. 当十进制N非零时,循环执行以下操作
   • 把N与8求余得到的八进制数压入栈S;
   • N更新为N与8的商;
3. 当栈S非空时,循环执行以下操作
   • 弹出栈顶元素e;
   • 输出e;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

/* 顺序栈结构 */
typedef struct
{
    SElemType data[MAXSIZE];
    int top; /* 用于栈顶指针 */
}SqStack;

//4.1 构建一个空栈S
Status InitStack(SqStack *S){
    
    S->top = -1;
    return OK;
}


//4.2 将栈置空
Status ClearStack(SqStack *S){
    
    //疑问: 将栈置空,需要将顺序栈的元素都清空吗?
    //不需要,只需要修改top标签就可以了.
    S->top = -1;
    return OK;
}

//4.3 判断顺序栈是否为空;
Status StackEmpty(SqStack S){
    if (S.top == -1)
        return TRUE;
    else
        return FALSE;
}

//4.4 返回栈的长度
int StackLength(SqStack S){
    return S.top + 1;
}

//4.5 获取栈顶
Status GetTop(SqStack S,SElemType *e){
    if (S.top == -1)
        return ERROR;
    else
        *e = S.data[S.top];
    
    return OK;
    
}

//4.6 插入元素e为新栈顶元素
Status PushData(SqStack *S, SElemType e){
    
    //栈已满
    if (S->top == MAXSIZE -1) {
        return ERROR;
    }
    
    //栈顶指针+1;
    S->top ++;
    //将新插入的元素赋值给栈顶空间
    S->data[S->top] = e;
    
    return OK;
}

//4.7 删除S栈顶元素,并且用e带回
Status Pop(SqStack *S,SElemType *e){
    
    //空栈,则返回error;
    if (S->top == -1) {
        return ERROR;
    }
    
    //将要删除的栈顶元素赋值给e
    *e = S->data[S->top];
    //栈顶指针--;
    S->top--;
    
    return OK;
}

//4.8 从栈底到栈顶依次对栈中的每个元素打印
Status StackTraverse(SqStack S){
    int i = 0;
    printf("此栈中所有元素");
    while (i<=S.top) {
        printf("%d ",S.data[i++]);
    }
    printf("\n");
    return OK;
}

解题如下：

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);
    }
    
}

二：爬楼梯问题（LeetCode-中等）
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
示例例1:
输⼊入: 2
输初: 2
解释: 有2种⽅方法可以爬到楼顶
①. 1阶+1阶
②. 2阶
示例例2:
输⼊入: 3
输初: 3
解释: 有3种⽅方法可以爬到楼顶
①. 1阶+1阶+1阶
②. 1阶+2阶
③. 2阶+1阶
我们分为两种方法解答：①.递归法 ②. 动态规划法

方法一:递归求解法

/*
 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);
}

方法二:动态规划法

int ClimbStairs(int n){
    if(n==1) return 1;
    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];
}

三、杨辉三角（LeetCode-中等）
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

我们利用动态规划法解决这个问题。
思路:

1. 第一层循环控制行数i : 默认[i][0] = 1,[i][i] = 1
2. 第二层循环控制列数j : triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]

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;
    
}

最后我们对动态规划思想做一个总结，
动态规划(英语:Dynamic programming，简称 DP)是一种在数学、管理理科学、计算机科学、经济学和⽣生物信息 学中使⽤用的，通过把原问题分解为相对简单的⼦子问题的⽅方式求解复杂问题的方法。

动态规划常常适⽤用于有重叠⼦子问题和最优⼦子结构性质的问题，动态规划⽅方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。⼤致上，若要解一个给定问题，我们需要解其不不同部分(即⼦问题)，再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利⽤用动态规划的思想可以减少计算量。通常许多子问题⾮常相似，为此动态规划法试图仅仅解决每个子问题一次，从⽽而减少计算量。

⼀旦某个给定⼦子问题的解已经算出，则将其记忆化存储，以便下次需要同一个⼦问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增⻓时特别有用。