【数据结构与算法】-（8）栈之算法题

【数据结构与算法】-（1）基础篇

【数据结构与算法】-（2）线性表基础

【数据结构与算法】-（3）循环链表（单向）

【数据结构与算法】-（4）双向链表和双向循环链表

【数据结构与算法】-（5）链表面试题解析

【数据结构与算法】-（6）栈

【数据结构与算法】-（7）队列

0. 算法题解法

要进大厂，必须要迈过的一步，就是算法题，那么算法题的思路究竟是如何呢？

笔者总结了一下近十年工作中的精髓，思路如下：

我们遇到什么困难也不要怕，微笑着面对它……奥利给！

抱歉走错片场了……想说的真正意思上这样的：

0.1 方法

1. 充分阅读题目，了解题目背后的关键意思；
2. 分析题目，涉及到哪些数据结构，对问题进行分类——到底属于链表问题、栈思想问题、字符串问题、二叉树问题、图相关问题、排序问题；与你之前所接触过的算法题有没有类似，找到问题的解题思路
3. 实现算法。在算法的实现的过程，并不是一蹴而就，肯定是需要不断的调试、修改的。
4. 验证算法正确性。
5. 找到题源，看其他的开发者对齐的解决思路。
6. 找到题解建议之后，对于其他优秀思路，分析它的优势，并且学习它的思路，并且写成其他解法的代码
7. 算法题的解题能力来自于2点：
   • 对于数据结构与算法核心问题是否夯实；
   • 是否有足够多且足够耐心的积累；

0.2 思想应用

指的是利用栈的特性(先进后出)去解决问题,那么什么问题适合用栈思想解决了?

1. 数据是线性的。

2. 问题中常常涉及到数据的来回比较，匹配问题；例如：每日温度、括号匹配、字符串解码、去掉重复字母等问题。

3. 问题中涉及到数据的转置，例如进制问题、链表倒序打印问题等。

4. 注意并不是说栈思想只是一个解决的的参考思想，并不是万能的。它适用于以上这样的情况下去解决问题；利用栈思想解决问题时，首先需要透彻的解析问题之后，找到问题解决的规律，才能使用它解决。思想只有指导作用，遇到不同的题目，需要个例分析。在基本思想上去找到解决问题之道;

0.3 推荐书单

1. 进制转换

Q: 题目

如何将十进制转化为8进制的整形

A: 解答

1. 初始化栈

SqStack S;
SElemType e;
//1.初始化一个空栈S
InitStack(&S);

Status InitStack(SqStack *S){
    
    S->top = -1;
    return OK;
}

2. 压栈

循环取余，N 为除以8 的取余

//2.
while (N) {
    PushData(&S, N%8);
    N = N/8;
}

3. 出栈

当栈不为空，一直输出，pop出栈

while (!StackEmpty(S)) {
    Pop(&S, &e);
    printf("%d\n",e);
}

4. 打印结果：

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    conversion(5201314);
    return 0;
}

运行结果如下：

2. 括号匹配检验

Q: 题目

括号匹配检验（题源：LeetCode）

给定一个只包括 (，)，{，}，[，] 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

A: 解答

3. 每日温度

4. 杨辉三角

5. 爬楼梯

6. 字符串编码问题