【数据结构与算法】-(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. 字符串编码问题


文章作者: 李佳
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 李佳 !
评论
 上一篇
【数据结构与算法】-(8.1)字符串去重算法 【数据结构与算法】-(8.1)字符串去重算法
【数据结构与算法】-(1)基础篇 【数据结构与算法】-(2)线性表基础 【数据结构与算法】-(3)循环链表(单向) 【数据结构与算法】-(4)双向链表和双向循环链表 【数据结构与算法】-(5)链表面试题解析 【数据结构与算法】-(6)栈
2020-04-22 李佳
下一篇 
【iOS进阶】-启动优化 【iOS进阶】-启动优化
总结中…近期更新
2020-04-19 李佳
  目录