什么是栈 大家好，我是bigsai，今天给大家聊聊栈这种数据结构。 栈在我们日常编码中遇到的非常多，很多人对栈的接触可能仅仅局限在 递归使用的是栈 和 StackOverflowException，栈是一种后进先出的数据结构(可以想象生化金字塔的牢房和生化角斗场的狗洞)。 栈是这么定义的： 栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新...

前言 大家好，我是bigsai，今天给大家分享一下双链表的设计和实现，比较适合数据结构与算法刚学的童鞋！前面有很详细的讲过线性表(顺序表和链表)，当时讲的链表以但链表为主，但实际上在实际应用中双链表的应用多一些就比如LinkedList。   双链表与单链表区别 逻辑上它们均是线性表的链式实现，主要的区别是节点结构上的构造有所区别，这个区别从而引起操作的一些差异。单链表： 单链表的一个节点，有储存数据的data，还有后驱节点next(指针)。也就是这个单链表想要一些遍历的操作都得通过前节点—>后节点。 双链表： 双链表的一个节点，有存储数据的data,也有后驱节点next(指针)，这和单...

前言 大家好，我是bigsai，好久不见甚是想念。 昨晚有个同学参加了阿里的笔试题，笔试完后同学说这次笔试感觉难，跟我说了其中一道题，我看了感觉还是挺有质量的，看着这个难度都是第二题，总共三题感觉还是有难度的(瑟瑟发抖)，想着还是和大家分享一下。 描述 一个正m边形，他想知道多边形中等腰锐角三角形的数量。(三角形的顶点要在多边形的顶点上)不同的三角形的定义:两个三角形，只要有一个点不在同一个位置上就算做不同的三角形。 数据范围3-10^7 分析 昨天看到这个问题，觉得还是比较新颖，也有很多细节，但是刚拿到这个问题自己懵逼的画了好久也才想出来，这里给大家share一下。 问题的描述很简单，边为n...

循环链表模拟 这个问题最本质其实就是循环链表的问题，围成一个圈之后，就没有结尾这就是一个典型的循环链表嘛！一个一个顺序报数，那不就是链表的遍历枚举嘛！数到对应数字的出列，这不就是循环链表的删除嘛！  并且这里还有非常方便的地方：  循环链表的向下枚举不需要考虑头尾问题，直接node=node.next向下 循环聊表的删除也不需要考虑头尾问题，直接node.next=node.next.next删除  当然也有一些需要注意的地方   形成环形链表很简单，只需要将普通链表的最后一个节点的next指向第一个节点即可   循环链表中只有一个节点的时候停止返回，即node.next=node的时候   ...

这一题刚拿到手可能没啥思路解决，不知道采用什么数学方法，但是你要看到所有可能的括号组合。所有二字，摆明是搜索题，可以dfs或者bfs，这里采用dfs完成。 dfs搜索需要考虑遍历所有情况，还有就是初始和停止的条件，我们知道dfs是回溯的，如果字符串频繁创建删除效率很低，所以利用回溯回来过程将字符串还原(StringBuilder)这样可以大大提升效率。而具体需要这样思考： n对括号，说明有n个(和n个)，可用两个数字标记两个个数。 (个数不能小于)的个数，否则不满足有效括号。 如果(用完，那么只能添加)，如果(未用完且不满足小于)个数，那么当前既可添加(也可添加)。 注意作用域，参数等问题 具...

前言 各位小伙伴们好，我是bigsai，本年度2021最后一篇原创于此啦。 总结这个东西，阶段性还是很有必要的，自己后面看看也挺有回忆的味道。 在19年4月那会对18年总结了一下，当时就是在博客上写的直接照搬过来：从博客时间轴总结这一年 20年初，刚考完研那会，也对自己19那一年进行了小总结：是时候介绍一下自己 当时的那种心情，可能跟此刻刚考完的你很相似，偶数年，考完就考完了，觉得这个过程体验已经很值得了。 21年初我并没有对20年总结，当时觉得没什么总结，其实那年发生的事情也蛮多的，经历疫情找工作又狗上岸可以说哪一年也是比较幸运的一年。 而今年，怎么说呢，虽说技术上没啥进步，也没啥成就，但是...

前言 牛友门大家好，我是bigsai，好久不见，甚是想念！ 很久前就有小伙伴被动态规划所折磨，确实，很多题动态规划确实太难看出了了，甚至有的题看了题解理解起来都费劲半天。 动态规划的范围虽然确实是很广很难，但是从整个动态规划出现的频率来看，这几种基础的动态规划理解容易，学习起来压力不大，并且出现频率非常高。  这几个常见的动态规划有：连续子数组最大和，子数组的最大乘积，最长递增子序列(LIS)，最长公共子序列(LCS)，最长公共子串，最长公共子串，不同子序列。 什么是动态规划 首先很多人问，何为动态规划？动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程...

前言 大家好，我是bigsai。 最近不少小伙伴跟我交流刷题肿么刷，我给的建议就是先剑指offer和力扣hot100，在这些题中还有些重要程度和出现频率是非常非常高的，今天给大家分享当今出现频率最高的10道算法题，学到就是赚到。  0X01翻转链表 力扣206和剑指offer24原题，题意为： 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。   分析： 翻转链表，本意是不创建新的链表节点然后在原链表上实现翻转，但是这个图有点会误导人的思维，其实更好的理解你可以看下面这幅图：  具体实现上两个思路，非递归和递归的实现方式，非递归的实现方式比较简单，利用一个pre节点记录前驱节...

前言 hello，大家好，我是bigsai哥哥，好久不见，甚是想念哇🤩！ 今天给大家分享一个TOPK问题，不过我这里不考虑特别大分布式的解决方案，普通的一道算法题。这道题也在高频考题中：  首先搞清楚，什么是topK问题？  topK问题，就是找出序列中前k大(或小)的数，topK问题和第K大(或小)的解题思路其实大致一致的。  TopK问题是一个非常经典的问题，在笔试和面试中出现的频率都非常非常高(从不说假话)。下面，从小小白的出发点,认为topK是求前K大的问题，一起认识下TopK吧！ 当前，在求TopK和第K大问题解法差不多，这里就用力扣215数组的第k个大元素 作为解答的题演示啦。学...

前言 大家好，我是bigsai，好久不见，甚是想念！ 最近有个小伙伴跟我诉苦，说他没面到LRU，他说他很久前知道有被问过LRU的但是心想自己应该不会遇到，所以暂时就没准备。并且在牛客高频题出现LRU他也没刷，真是可惜了。  奈何不巧，这还就真的考到了！他此刻的心情，可以用一张图来证明：   他说他最终踉踉跄跄的写了一个效率不是很高的LRU，面试官看着不是很满意……后来果真GG了。 防止日后再碰到这个坑，今天和大家一起把这个坑踩了，这道题我自身刚开始也是用较为普通的方法，但是好的方法虽然不是很难但是想了真的很久才想到，虽然花了太多时间不太值，总算是自己想出来了，将这个过程给大家分享一下(只从算法...

前言 hello，大家好，我是bigsai，好久不见，甚是想念！ 在日常生活中，很多人喜欢玩游戏，因为游戏中有着对抗博弈、控制的喜悦，用灵魂指法完成一波靓丽的操作。 但实际上，你的按键都是对应代码中一个个方法函数去执行操作，并且界面做到一个图形变化渲染让你感觉你控制的是这个图形界面。 虽然游戏的底层都是一行行代码堆砌的逻辑，但是我们对其并没有半点兴趣因为写代码的过程枯燥无趣，完全需要脑子去抽象出一个页面、执行逻辑，出错的时候有很简单的找了半天…… 输出、debug各种方式去找问题。 对于咱们这种懒人来说，想要锻炼自己编程能力、算法真的是进入一种畏难的无限死循环，希望要么简单点、要么有趣点，写的...

前言 大家好，我是bigsai，好久不见！今天就给各位小伙伴分享我自己刷题力扣的一些小方法，不一定很有用但是可以参考，祝你更高效的变强！ 最近在一些群聊、私聊中遇到很多的一个问题就是：刷题，大家也都重视到算法刷题对冲击大厂的重要性，越来越多的人开始卷起来了！   但有的人是这样卷起来的，卷的自己都懵了。   今天，我就给偏初学者的各种问题谈谈个人刷力扣这方面的观点。 刷哪些题？ 大家刷力扣，目标肯定就是为了冲击大厂的面试笔试，小部分就是为了坚持刷题保持感觉提升自己算法编程能力，那么你肯定要把重点内容先掌握，哪些是重点内容呢？ 剑指offer： 首先是剑指offer，剑指offer的优先级还是很...

什么是字典树 字典树，是一种空间换时间的数据结构，又称Trie树、前缀树，是一种树形结构(字典树是一种数据结构)，典型用于统计、排序、和保存大量字符串。所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。   可能大部分情况你很难直观或者有接触的体验，可能对前缀这个玩意没啥概念，可能做题遇到前缀问题也是暴力匹配蒙混过关，如果字符串比较少使用哈希表等结构可能也能蒙混过关，但如果字符串比较长、相同前缀较多那么使用字典树可以大大减少内存的使用和效率。一个字典树的应用场景：在搜索框输入部分单词下面会有一些神关联的搜...

前言 栈和队列是一对好兄弟，前面我们介绍过一篇栈的文章(栈，不就后进先出)，栈的机制相对简单，后入先出，就像进入一个狭小的山洞，山洞只有一个出入口，只能后进先出(在外面的先出去，堵在里面先进去的就有点倒霉)。而队列就好比是一个隧道，后面的人跟着前面走，前面人先出去(先入先出)。日常的排队就是队列运转形式的一个描述！ 栈是一种喜新厌旧的数据结构，来了新的就会处理新的把老的先停滞在这(我们找人、约人办事最讨厌这种人)，队列就是大公无私的一种数据结构，排队先来先得，讲究顺序性，所以这种数据结构在程序设计、中间件等都非常广泛的应用，例如消息队列、FIFO磁盘调度、二叉树层序遍历、BFS宽度优先搜索等等...