做算法题的⽅法: (必看)


1. 充分阅读题⽬.了解题⽬背后的关键意思;
2. 分析题⽬,涉及到哪些数据结构,对问题进⾏分类. 到底属于链表问题, 栈思想问题, 字符串问题,⼆叉树问
题,图相关问题,排序问题; 与你之前所接触过的算法题有没有类似,找到问题的解题思路
3. 实现算法. 在算法的实现的过程,并不是⼀蹴⽽就, 肯定是需要不断的调试,修改的;
4. 验证算法正确性
5. 找到题源, 看其他的开发者提供的解决思路.
6. 找到题解建议之后, 对于其他优秀思路,分析它的优势,并且学习它的思路.并且写成其他解法的代码(借⼒,
不要单纯的闭⻔造⻋)
7. 算法题的解题能⼒来⾃于2点: 对于数据结构与算法核⼼问题是否夯实 + 是否有⾜够多且⾜够耐⼼的积
累;

例如如果你连基本的链表操作都不知道, 如果去解决链表翻转问题; 例如你连图的存储.遍历等都不清楚,如
何去解决图的最⼩路径问题?,如果解决图的问题; 例如你都⽆法⾃⼰不了解⼆叉树,如果去计算⼆叉树的深
度问题?

栈的思想应⽤

指的是利⽤栈的特性(先进后出)去解决问题,那么什么问题适合⽤栈思想解决了?
1. 数据是线性的
2. 问题中常常涉及到数据的来回⽐较,匹配问题;例如,每⽇温度,括号匹配,字符串解码,去掉重复字⺟等问题.
3. 问题中涉及到数据的转置,例如进制问题.链表倒序打印问题等
4. 注意并不是说栈思想只是⼀个解决的的参考思想.并不是万能的.它适⽤于以上这样的情况下去解决问题;

利⽤栈思想解决问题时,⾸先需要透彻的解析问题之后,找到问题解决的规律.才能使⽤它解决;
思想只有指导作⽤,遇到不同的题⽬,需要个例分析.在基本思想上去找到具体问题具体的解决问题之道;

括号匹配检验: (字节出现过的算法⾯试题/LeetCode)
假设表达式中允许包含两种括号:圆括号与⽅括号,其嵌套顺序随意,即() 或者[([][])]都是正确的.⽽这
[(]或者(()])或者([()) 都是不正确的格式. 检验括号是否匹配的⽅法可⽤

期待的急迫程度”这个概念来描
述.例如,考虑以下括号的判断: [ ( [ ] [ ] ) ]
a. 将 0 个元素压栈;
b. 遍历字符范围[1,strlen(data)]
c. 取栈顶字符
d. 检查该括号是左括号
i. 左: 判断后⾯字符data[i] 是右括号, YES ⼊栈/ NO 出栈;
e.遍历结束. 判断栈是否为空,如果空匹配成功,匹配失败;

实现下⾯算法题:
括号匹配检验: (字节出现过的算法⾯试题/LeetCode)
假设表达式中允许包含两种括号:圆括号与⽅括号,其嵌套顺序随意,即() 或者[([][])]都是正
确的.⽽这[(]或者(()])或者([()) 都是不正确的格式. 检验括号是否匹配的⽅法可⽤

期待的急迫
程度”这个概念来描述.例如,考虑以下括号的判断: [ ( [ ] [ ] ) ]
每⽇⽓温: (LeetCode-中等)
题⽬: 根据每⽇⽓温列表，请重新⽣成⼀个列表，对应位置的输⼊是你需要再等待多久温度才
会升⾼超过该⽇的天数。如果之后都不会升⾼，请在该位置0来代替。例如，给定⼀个列
表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1,
1, 0, 0]。提示：⽓温 列表⻓度的范围是 [1, 30000]。每个⽓温的值的均为华⽒度，都是
在 [30, 100] 范围内的整数
爬楼梯问题:(LeetCode-中等)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不
同的⽅法可以爬到楼顶呢？注意：给定 n 是⼀个正整数å
去除重复字⺟(LeetCode-困难)
给你⼀个仅包含⼩写字⺟的字符串，请你去除字符串中重复的字⺟，使得每个字⺟只出现⼀
次。需保证返回结果的字典序最⼩（要求不能打乱其他字符的相对位置）
字符串编码(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”.

算法练习

1. 括号匹配检验

题目： 假设表达式中允许包含两种括号:圆括号与方括号,其嵌套顺序随意,即() 或者[([][])]都是正确的.而这 [(]或者(()])或者([()) 都是不正确的格式. 检验括号是否匹配的方法可用”期待的急迫程度”这个概念来描述. 例如,考虑以下括号的判断:

  1. [ ( [ ] [ ] ) ]
  3. 1 2 3 4 5 6 7 8

栈的定义

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  5. #define Stack_Init_Size 100
  6. #define Stack_Increment 10
  7. //栈的定义
  8. typedef struct {
  9.     char* base; //栈底指针
  10.     char* top;  //栈顶指针
  11.     int stacksize;  //栈MaxSize
  12. }SqStack;

初始化栈

  1. /*
  2.  思路:
  3.  1. 如果栈底为空
  4.  2. 分配一个最大容量Stack_Init_Size的数组,栈底/栈顶都指向与它.[参考图空栈情况]
  5.  3. 初始化栈的最大容易Stack_Init_Size
  6.  */
  7. int Init(SqStack *stack){
  9.     if(!stack->base){
  10.         stack->base=(char*)malloc(Stack_Init_Size*sizeof(char));
  11.         stack->top=stack->base;
  12.         stack->stacksize = Stack_Init_Size;
  13.         printf("初始化成功\n");
  14.         return 0; //初始化成功
  15.     }
  16.     else return -1;//表示无法初始化已出始化栈
  17. }

获取栈顶元素

  1. /*
  2.  思路:
  3.  1.判断栈是否为空
  4.  2.非空,则栈定指针-1,返回栈顶元素;
  5.  */
  6. char GetTop(SqStack stack){
  8.     if(stack.base==stack.top){
  9.         //printf("栈中没有数据\n");
  10.         return '#';
  11.     }
  12.     //printf("获取栈顶数据成功\n");
  13.     return *(stack.top-1);
  14. }

往栈中插入元素

  1. /*
  2.  思路:
  3.  1.判断栈是否已满,若满则返回ERROR #问题:如何判断栈是否已满?
  4.  2.栈满,则续容空间 #问题:如何给已满栈续容空间?
  5.  3.将元素element压栈
  6.  4.栈顶指针加"1"
  7.  */
  8. int Push(SqStack *stack,char element){
  9.     if(stack->top-stack->base==stack->stacksize){
  10.         stack->base=(char*)realloc(stack->base,Stack_Increment*sizeof(char));
  11.         stack->top=stack->base+stack->stacksize;
  12.         stack->stacksize+=Stack_Increment;
  13.     }
  14.     *stack->top=element;
  15.     stack->top+=1;
  16.     return 0;
  17. }

删除栈顶元素

  1. /*
  2.  思路:
  3.  1.判断栈是否已空
  4.  2.非空,则获取栈顶元素,并将栈顶减"1";
  5.  */
  6. char Pop(SqStack *stack){
  7.     if(stack->top==stack->base){
  8.         printf("栈为空\n");
  9.         return '#';
  10.     }
  11.     //printf("删除数据成功");
  12.     return *--stack->top;
  13. }

释放栈空间

  1. //释放栈空间
  2. int Destroy(SqStack *stack){
  3.     free(stack->base);
  4.     stack->stacksize=0;
  5.     return 0;
  6. }

处理数据，借助栈判断

  1. /*
  2.  思路:
  3.  1. 将第0个元素压栈
  4.  2. 遍历[1,strlen(data)]
  5.     (3). 取栈顶字符
  6.     (4). 检查该字符是左括号("(","[")
  7.          a.是左"(",则判断紧接其后的data[i]是为右")"
  8.             YES->压栈,NO->出栈
  9.          b.是左"[",则判断紧跟其后的data[i]是为右"]"
  10.             YES->压栈,NO->出栈
  11.          c.表示式如果以"#"结尾,则判断紧跟其后的data是为左"(""]"
  12.             YES->压栈,NO->-1;
  14.  3.遍历结束,则判断栈是否为空,为空则表示匹配成功;否则匹配失败;
  15.  [ ( [ ] [ ] ) ]
  16.  1 2 3 4 5 6 7 8
  17.  */
  18. int ExecuteData(SqStack stack,char* data){
  19.     Push(&stack,data[0]);
  20.     for(int i=1;i<strlen(data);i++){
  21.         char top = GetTop(stack);
  22.         switch(top){
  23.             case '(':
  24.                 if(data[i]==')')Pop(&stack);
  25.                 else Push(&stack,data[i]);
  26.                 break;
  27.             case '[':
  28.                 if(data[i]==']')Pop(&stack);
  29.                 else Push(&stack,data[i]);
  30.                 break;
  31.             case '#':
  32.                 if(data[i]=='('||data[i]=='['){
  33.                     Push(&stack,data[i]);
  34.                     break;
  35.                 }
  36.                 else
  37.                     default:return -1;break;
  38.         }
  39.     }
  41.     //如果栈为空,则返回"0"->匹配成功 否则返回"-1"匹配失败
  42.     if(stack.top==stack.base){
  43.         Destroy(&stack);
  44.         return 0;
  45.     }
  46.     else{
  48.         Destroy(&stack);
  49.         return -1;
  50.     }
  51. }

main函数调用

  1.  int main(){
  2.     /*
  3.      算法问题:
  4.      假设表达式中允许包含两种括号:圆括号与方括号,其嵌套顺序随意,即([]()) 或者[([][])]都是正确的.而这
  5.      [(]或者(()])或者([()) 都是不正确的格式. 检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述. 例如,考虑以下括号的判断:
  7.      [ ( [ ] [ ] ) ]
  8.      1 2 3 4 5 6 7 8
  9.      */
  11.     SqStack stack;
  12.     Init(&stack);
  13.     char data[180];
  14.     printf("请输入待匹配的字符串\n");
  15.     scanf("%s",data);
  16.     int result = ExecuteData(stack,data);
  17.     if(result==0)printf("括号是正确匹配的\n");
  18.     else printf("括号匹配不正确\n");
  19.     return 0;
  20. }