leetcode递归题目总结(递归选择题)
leetcode什么水平才能刷
leetcode最好能具备一定的基础水平才能刷。
leetcode是个很好用的刷题软件，不是学习到了什么程度才可以刷LeetCode。 平时使用LeetCode更多是用来做练习和巩固的，比如学习了链表，可能就取刷几道相关题，检测一下自己的掌握程度，从而反馈继续学习一些“遗漏”或者“没有掌握”的知识点。
刷leetcode的前提，建议不要完全零基础就一股脑的去刷题，如果啥都不会临时突击直接上去刷题，不出意外的话只会看着别人的题解刷题，看了别人的思路也不一定会写，就算写出来了很快就忘了。所以要对常见的算法有一定的基础，常见的模型较为了解之后再去刷题。
使用leetcode刷题的总结：
1、分类刷题：系地并且针对性的刷一类题：比如一段时间先刷递归，再双指针，再字符串等等。只要刷题就只刷一类的题，今天刷这类，明天刷另一类，同一类题目一起刷，可以更更好的总结经验规律和方法差异。
2、分类做笔记：把自己刷过的题做好算法分类写入笔记，标出每一题的思路关键字，把难懂的方法思路标注记号。
3、经常定时复习：定时复习（每天晚上，每周日，每月末）自己笔记里记录的算法题，并且把忘了的题权重+1，后期复习的时候把权重高的题多复习一次。200~300道题至少刷2到3遍。
4、bug free的能力：写代码的时候下意识想到界限，下意识想到可能出bug的代码并且处理它可能出现bug的地方（这个需要经验，也可以把自己经常出现bug的代码写入笔记中）。
5、写代码要快和反应都要快：写代码前把逻辑写在纸上，然后尽可能快速的把逻辑实现出来，培自己的代码风格。
算法面试通关40讲 覃超 Leetcode 题目总结（未完待续）
主要是自己收集的题目，正在学习王争老师的数据与算法结构之美和覃超老师的算法面试通关四十讲，两位老师推荐很经典的面试题。所以为了方便自己，在这里做一个汇总。如果对你有帮助那当然好，或者也可以看参考资料，里面有很多优秀的Github的资源。
参考资料
算法复杂度查看：
C语言解法推荐：
Java解法推荐：
数据结构与算法之美（王争）（有各种语言的版本）：
Github 40K star leetcode：
Github 13K star Leetcode：
Github 63K star 用动画的形式呈现解LeetCode题目的思路：
python 解法：
其他解法：
06|面试题：反转一个单链表判断链表是否有环
数据与算法结构之美：
21 Merge Two Sorted Lists 【 C 】【 python 】
删除链表倒数第 n 个结点 【 Leetcode 的解题 】
求链表的中间结点 Middle of the Linked List
20 Valid Parentheses
232 Implement Queue using Stacks 【 C 】【 My C solution 】
225 Implement Stack using Queues 【 C 】
703 Kth Largest Element in a Stream
239 Sliding Window Maximum
242 Valid Anagram
1 Two Sum 【 C 】
15 3Sum
18 4Sum
98 Validate Binary Search Tree
235 Lowest Common Ancestor of a Binary Search Tree
236 Lowest Common Ancestor of a Binary Tree
50 Pow(x, n)
169 Majority Element
122 Best Time to Buy and Sell Stock II
冒泡排序，选择排序，插入排序，供参考：【 C 】
(未完待续，大概等我做完上面这些就可以继续补充剩下的了吧）
LintCode/LeetCode训练题目&答案详解—基础篇
一、在二叉树中寻找值最大的节点并返回：
给出如下一棵二叉树：
返回值为 3 的节点。
简析：使用了递归的思想；注意为空的判断；
二、单例
单例 是最为最常见的设计模式之一。对于任何时刻，如果某个类只存在且最多存在一个具体的实例，那么我们称这种设计模式为单例。例如，对于 class Mouse (不是动物的mouse哦)，我们应将其设计为 singleton 模式。
你的任务是设计一个 getInstance 方法，对于给定的类，每次调用 getInstance 时，都可得到同一个实例。
样例：
在 Java 中:
A a = A.getInstance();
A b = A.getInstance();
a 应等于 b.
挑战：
如果并发的调用 getInstance，你的程序也可以正确的执行么？
}
注意：实现一个单例有两点注意事项，①将构造器私有，不允许外界通过构造器创建对象；②通过公开的静态方法向外界返回类的唯一实例
参考：单例模式的几种写法对比：
三、整数排序
给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法。
样例：
对于数组 [3, 2, 1, 4, 5], 排序后为：[1, 2, 3, 4, 5]。
答案(java版本)：
选择排序：
冒泡排序：
答案解析：
各个语言的实现请参考维基百科：
** 四、斐波那契数列**
查找斐波纳契数列中第 N 个数。所谓的斐波纳契数列是指：
前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
答案：
注意事项：
1、n是从1开始的，而不是0
2、一般我们都会想到用递归的方式实现，但是这个时间开销很大：
3、题目的引申: 青蛙跳阶梯 ，铺方砖
参考：
LeetCode 70：爬楼梯（超详细解法！！！）
继续分享一道LeetCode上的简单题：
假设输入为n阶台阶，有f(n)种不同的方法爬到楼顶。由于每次只能爬1或2个台阶，于是，我们假设第一次爬了1个台阶，那么剩下n-1阶台阶，有f(n-1)种不同的方法；假设第一次爬了2个台阶，那么剩下n-2阶台阶，有f(n-2)中不同的方法。因此，我们得到：
f(n) = f(n-1) + f(n-2)
到这里，很容易想到递归使用斐波那契数列来解决这个问题，但是使用递归的复杂度极高，求f(n)的时候需要递归求解f(n-2)，求f(n-1)时又需要递归求解f(n-2)，造成时间的浪费，时间复杂度达到O(2^n)。所以本质上整个过程我们把一些子问题重复求了多次，这可太蠢了，然后不同的子问题只有n个，我们只需要每个问题只求一次，因此我们只要记下每个f(n-2)的值，就不需要多次重复的递归求解得到它的值，就能够节省许多时间了。
我们作出如下改进：先定义一个列表，将每次f(n) = f(n-1)+f(n-2)计算得到的值存到这个列表里，那么每次求f(n)只需要去列表里调用，只需要O(1)的复杂度，整个算法的时间复杂度也减小到O(n)。
over!
六、递归与回溯算法
在计算机领域里面，很多问题都可以要采用递归算法来解决。递归中，最长用到的方法就是回溯法。我们具体分析问题的时候，可以发现这类问题本质是一个树的形状。
递归算法的本质还是将原来的问题转化为了更小的同一问题，进行解决。一般注意两点：
1、递归终止的条件。对应到了递归算法中最基本的问题，也是最最简单的问题。
2、递归过程。递归过程需要将原问题一步一步的推到更小的 同一 问题，更小的意思就是子问题解决起来就更加的简单。有写情况是能够找到一个递推的公式的。这个过程中就需要透彻的去理解递归函数的意义。明确这个函数的输入和输出是什么，这样来写的话，就清晰多了。
因为有了这样的递归公式，那么我们就很容易的能看出来递归的终止条件就是我们知道的f(0)和f(1)了。有了f(0)和f(1)之后，我们就能够继续的递推出f(3)一直到f(n)了。
但是我们现在才用一个递归算法的思想来解决这个问题:
像我们常见的数据结构如链表、树、图等都是有着天然的递归结构的，链表由于是一个线性的结构，那么通常我们也是能够直接循环遍历就能解决问题的，但是这里我们用递归法来解决一下LeetCode上面的问题
LeetCode 203 移除链表元素
分析：链表的结构可以理解成一个节点连接这一个更短的链表，这样依次一直看下去，直到最后一个节点None，那么我们这个时候的递归终止条件就是head指向None了，返回的就是None
深入的理解递归算法之后，我们就开始进行回溯法的学习。通过LeetCode上面的几道题，我们来深入的探讨一下递归与回溯法的应用。
持续更新中...
数据结构与算法系列博客：
一、数据结构与算法概述
二、数组及LeetCode典型题目分析
三、链表（Linked list）以及LeetCode题
四、栈与队列（Stack and Queue
五、树（Trees）
六、递归与回溯算法
七、动态规划
八、排序与搜索
九、哈希表
参考资料
1、
2、
3、