# leetcode

**Repository Path**: CoolguyHolmes/leetcode

## Basic Information

- **Project Name**: leetcode
- **Description**: 学习用基础数据结构与常见算法二刷leetcode相关题目
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-05-01
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

这是本人学习数据结构一个月后第二次复习数据结构和算法，重新在leetcode上写解并记录思路的过程。


链表总结：
由于链表是非连续的，所以没有办法进行随机访问，而且一个链表的储存在于头节点的保存，只有拥有头节点，才能完整的访问整个链表，所以时刻注意保留一个指向头节点的指针是最重要的，另外比较麻烦的一点是链表的末尾是一个空，不存有val，如果不注意辨别空的话很容易报错
另外链表由于本身天然的递归结构，不少题目是可以递归来进行解答的
链表核心技巧：
1.虚拟头节点：使用虚拟头节点常见的作用包括：创建一个稍慢的指针（对比在head的指针慢了一格）；在删除等操作上如果头节点有问题有很多需要考虑的情况，如果使用虚拟头节点可以轻松的避免这种情况的发生
2.双指针：通过控制双指针的不同移动速率或起点，来形成差别，可以达到寻找中间节点，寻找第N个节点，寻找倒数第N个节点等目的
3.翻转：翻转基本是常见的链表问题中最核心和最难的问题，翻转整条链表相对来说是最简单的，更难的是内部进行翻转，其实只要弄懂原理就不会特别难，我关于该类题型的解答模式基本统一使用3指针迭代前进的方式进行节点指针的改写如果是内部翻转的话那就需要在翻转整个链表的基础上加上判断
4.活用数据结构，在leetcode中出现的标记有链表的问题我基本全部解答了，从记录中可以看出来虽然链表本身就是一种数据结构，但是不少情况下链表其实不只是一个链表的问题，如果能够活用栈，堆，字典等数据结构能够轻松解决问题。


树总结：
树天然的具有递归的性质，可以使用递归来简化题解过程，锻炼递归的熟练度。


列表总结：
一种很基本的可变数据类型，其可随机访问的性质使其在使用上比链表更方便，其余的和链表很像。
并且这种数据类型和数组很接近，在leetcode上很多规律题都涉及到这些容器的使用，但是核心问题都是规律问题，而不是数组列表的问题。


堆总结：
在leetcode中使用到堆进行解题的题目比较少一些，估计原因可能是堆虽然是一种很优秀的容器，但是其使用方法真的很简单，所以没有特别多的延伸方向。


栈总结：
从使用方法上来说栈就是一种简单的后进先出的结构，但是如果深入了解他的结构和应用方向，会发现栈这种结构其实很强大，他有很多我们一开始根本想不到的用法，是一种需要多了解多学习使用的结构。


队列总结：
一种简单的先进先出的结构，使用上多见于BFS。暂时还没发现特别需要注意的问题。


贪心算法：
虽然会使用贪心的思想去解答简单的问题，但是其实并没有很透彻理解这种算法思路，在后续的学习中再掌握。
需要注意的是我觉得贪心算法的难点是学会判断一道题是否可以使用贪心算法，日后要好好钻研这个方向。


动态规划：
动态规划是一个很好的思想，本人在短暂的学习过后也有很多想法，详情请见另一个文档：动态规划之我见，里面详细描述了我对于动态规划的一些粗浅认识。


回溯法：
首先明确几点：回溯法其实属于暴力破解(枚举所有可能)的一种具体方案，基于枚举的特性这种算法思想其实也属于深度优先遍历的一种，并且是偏有序性的
（按一定的顺序枚举当前层数所有可能并直至适当的时候结束）这解决了一部分无法用很直观的暴力破解法解决的问题， 
所以当我们需要罗列当前可能性中所有可能的时候，可以使用回溯法；另外回溯法的行为具有一定的顺序性，我们可以很轻松的分析出枚举的大致过程
（必然是按一定顺序的），如果我们只需要其中的第一个正确的结果，明显回溯法也是可以满足我们的要求的，所以当我们只需要获取所有可能中的其中一种的话，
我们也可以使用回溯法；基于前面提到的枚举所有可能，我们可以稍稍改变思路，在每次获得一种合理的可能结果时，
对其记数，这样我们就可以得到所有合理可能的数量了，以上是三种常见使用回溯法的时机
另外，以上三种并不是都应该使用回溯法，因为在不同的情况下，会有别的算法应用起来更加好用，

要求1：列举所有合理的可能性的所有具体情况，这种要求应该使用回溯法；
要求2：获取其中一种合理的可能性后结束，这种要求下使用回溯法也是可以的；
要求3：列出所有合理可能性的数量，这种要求虽然也表达了枚举的含义，但是并不需要枚举所有合理可能的具体内容，
所以如果使用回溯法是不如使用动态规划来得方便的
基于以上分析，以后在判断枚举所有合理可能的数量的时候，我会使用动态规划而不是回溯法
详细的回溯法思想和解题过程及剪枝思路，可以看我的排列与组合中回溯算法的剪枝分析