思想：双指针主要用于遍历数组，两个指针指向不一样的元素，从而协同完成任务。java

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
返回的下标值（index1 和 index2）不是从零开始的。
你能够假设每一个输入只对应惟一的答案，并且你不能够重复使用相同的元素。python

 

 3.反转字符串中的元音字母
编写一个函数，以字符串做为输入，反转该字符串中的元音字母。
示例 1:
输入: “hello”
输出: “holle”
示例 2:
输入: “leetcode”
输出: “leotcede”
说明:
元音字母不包含字母"y"。git
 
 

 

 4.验证回文字符串II（easy 680)
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。web
 
 

 
 

 
 

 输入: “abca”
输出: True
解释: 你能够删除c字符。数组
 
 

 
 

 
 

 解法一：
通常而言，对于有序数组能够经过 双指针法 达到O(n + m)的时间复杂度。
最直接的算法实现是将指针p1 置为 nums1的开头， p2为 nums2的开头，在每一步将最小值放入输出数组中。
因为 nums1 是用于输出的数组，须要将nums1中的前m个元素放在其余地方，也就须要 O(m)的空间复杂度。app
 
 

 解法二：
解法一的延伸版：若是从结尾开始改写 nums1 的值这里没有信息，所以不须要额外空间。
 
 

 
 
 
 
 
 
 

 6.判断环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，咱们使用整数 pos 来表示链表尾链接到链表中的位置（索引从 0 开始）。 若是 pos 是 -1，则在该链表中没有环。
思路一：
使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步，指针fast每次走2步。若是存在环，则指针slow、fast会相遇；若是不存在环，指针fast遇到NULL退出。。
放一个证实 
 
 

 
 

 思路2：
遍历全部结点并在哈希表中存储每一个结点的引用（或内存地址）。若是当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么咱们已经遍历完整个链表，而且该链表不是环形链表。若是当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）。
 
 

 
 

 7.经过删除字母匹配到字典中最长的单词（medium 524)
 
 

 给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串能够经过删除给定字符串的某些字符来获得。若是答案不止一个，返回长度最长且字典顺序最小的字符串。若是答案不存在，则返回空字符串。
示例 1:
输入:
s = “abpcplea”, d = [“ale”,“apple”,“monkey”,“plea”]
输出:
“apple”
思路：
实际上是一个最长子序列问题。经过删除字符串 s 中的一个字符能获得字符串 t，能够认为 t 是 s 的子序列，咱们可使用双指针来判断一个字符串是否为另外一个字符串的子序列。
 
 
 
 
 
 
 
 
 
 
 

 二分查找也称为折半查找，每次都能将查找区间减半，这种折半特性的算法时间复杂度为 O(logN)。 有序
 
 

 
 

 中值m的计算：有两种计算中值 m 的方式：
m = (l + h) / 2
m = l + (h - l) / 2
l + h 可能出现加法溢出，也就是说加法的结果大于整型可以表示的范围。可是 l 和 h 都为正数，所以 h - l 不会出现加法溢出问题。因此，最好使用第二种计算法方法。
 
 

 未成功查找的返回值
循环退出时若是仍然没有查找到 key，那么表示查找失败。能够有两种返回值：
（1）-1：以一个错误码表示没有查找到 key
(2) l：将 key 插入到 nums 中的正确位置
 
 

 变种
二分查找能够有不少变种，实现变种要注意边界值的判断。例如在一个有重复元素的数组中查找 key 的最左位置的实现以下：
 
 

 该实现和正常实现有如下不一样：
 
 

 
 

 在 h 的赋值表达式为 h = m 的状况下，若是循环条件为 l <= h，那么会出现循环没法退出的状况，所以循环条件只能是 l < h。如下演示了循环条件为 l <= h 时循环没法退出的状况：
 
 

 
 

 8.x的平方根（easy 69)
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
因为返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
思路1：
一个数 x 的开方 sqrt 必定在 0 ~ x 之间，而且知足 sqrt == x / sqrt。能够利用二分查找在 0 ~ x 之间查找 sqrt。
对于 x = 8，它的开方是 2.82842…，最后应该返回 2 而不是 3。在循环条件为 l <= h 而且循环退出时，h 老是比 l 小 1，也就是说 h = 2，l = 3，所以最后的返回值应该为 h 而不是 l。
 
 

 9.寻找比目标字母大的最小字母
给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。
 
 

 

 法2：二分查找，只需将target插入正确的位置，l便是target右边的第一个位置
 
 

 

 给定一个只包含整数的有序数组，每一个元素都会出现两次，惟有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
 
 

 
 

 
 

 

 11.旋转数组中的最小值（medium 153）
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你能够假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
 
 

 

 如果非递减数组，存在重复元素，例如出现1101111这样的，mid=h,只能h–,挨个查找
 
 

 12.在排序数组中查找目标元素的第一个位置和最后一个位置（medium 34）
 
 

 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
若是数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
思路：
能够用二分查找找出第一个位置和最后一个位置，可是寻找的方法有所不一样，须要实现两个二分查找。咱们将寻找 target 最后一个位置，转换成寻找 target+1 第一个位置，再往前移动一个位置。这样咱们只须要实现一个二分查找代码便可。
 
 

 中的位置，也就是数组最后一个位置再日后一个位置，即 nums.length。因此咱们须要将 h 取值为 nums.length，从而使得 findFirst返回的区间更大，可以覆盖 target 大于 nums 最后一个元素的状况。
 
 

 也能够用两次二分法，分别查找左边界和右边界
 
 

 插入一个大佬总结的好用的二分法查找模板

 

 
（1）数据结构 堆
堆就是用数组实现的二叉树，全部它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。
堆的经常使用方法：
构建优先队列
支持堆排序
快速找出一个集合中的最小值（或者最大值）
堆分为两种：最大堆和最小堆，二者的差异在于节点的排序方式。
在最大堆中，父节点的值比每个子节点的值都要大。在最小堆中，父节点的值比每个子节点的值都要小。这就是所谓的“堆属性”，而且这个属性对堆中的每个节点都成立。最大堆：

堆中父节点和子节点的关系
注意：在堆中，在当前层级全部的节点都已经填满以前不容许开是下一层的填充，
cpp中：构建最小堆（小顶堆）
 
 有两个原始操做用于保证插入或删除节点之后堆是一个有效的最大堆或者最小堆：
shiftUp(): 若是一个节点比它的父节点大（最大堆）或者小（最小堆），那么须要将它同父节点交换位置。这样是这个节点在数组的位置上升。
shiftDown(): 若是一个节点比它的子节点小（最大堆）或者大（最小堆），那么须要将它向下移动。这个操做也称做“堆化（heapify）”。
其它删除 插入等操做都是基于这两个原始操做

 

 (2选择排序
1.在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
2.第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。
3.重复以上操做直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。
时间复杂度O(n^2)

 

 (3)快速选择排序(partition)
快速选择排序：是一个在平均状况下的时间复杂度为O(nlogn)，最坏的时间复杂度为O(n^{2}) ，且是一个不稳定的排序方法，但通常状况下它的排序速度很快，只有当数据基本有序的时候速度是最慢的。
 
1 通常选择待排序表中的第一个记录做为基准数，而后初始化两个指针 low 和 high ,分别指向表的上界和下界
2 从表的最右侧开始依次向左搜索，找到第一个关键字小于基准数的记录，将其移到 low 处并high--。
3 接着从表的最左侧位置开始依次向右边搜索，找到第一个大于基准数的记录，将其移到 high 的位置后 low++.
4 重复操做2和3，直至 low 和 high 相等，此时 low 和 high 的位置即为基准数在此序列中的最终位置。
5 经过递归调用把小于基准元素和大于基准元素的子序列进行排序。
 

 另外一种写法的快排：这一种方法是从左右两个方向同时进行的快排（速度更快）
 
 

 
 

 1.数组中第K大的元素（medium 215）
在未排序的数组中找到第 k 个最大的元素。请注意，你须要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不一样的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
法一：
 
 

 

 
 

 “分而治之”，就是把一个复杂的问题分红两个或更多的相同或类似的子问题，再把子问题分红更小的子问题……直到最后子问题能够简单的直接求解，原问题的解即子问题的解的合并。
 
 

 (1)为运算符表达式设计优先级（241 medium）
给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不一样的结果。你须要给出全部可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例 1:
 
 

 
 

 分治思想分解过程
输入:23-45
以运算符为分界
第一步的分解：a:2和3-45；b:23和45；c:23-4和5；
第二部的细分：a部分：左边：直接返回2 右边：在分解，aa:3和45，ab:3-4和5
补充：同一个符号的左右各会产生至少一个，至多多个数值。左多个数和右多个数进行运算（两个循环搞定全部结果） 如a:2和3-45 ，左边产生2，右边产生-5和-17，那么a这一级最终有-10，-34两个数值。
 
 
 
 
 

 贪心算法通常用来解决须要 “找到要作某事的最小数量” 或 “找到在某些状况下适合的最大物品数量” 的问题，且提供的是无序的输入。
 
 

 贪心算法的思想是每一步都选择最佳解决方案，最终得到全局最佳的解决方案。
标准解决方案具备 O(NlogN) 的时间复杂度且由如下两部分组成：
1.思考如何排序输入数据（\mathcal{O}(N \log N)O(NlogN) 的时间复杂度）。
2.思考如何解析排序后的数据O(N) 的时间复杂度）
若是输入数据自己有序，则咱们不须要进行排序，那么该贪心算法具备 O(N) 的时间复杂度。
 
 

 如何证实你的贪心思想具备全局最优的效果：可使用反证法来证实。
 
 

 1.分发饼干（easy 455)
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。可是，每一个孩子最多只能给一块饼干。对每一个孩子 i ，都有一个胃口值 gi ，这是能让孩子们知足胃口的饼干的最小尺寸；而且每块饼干 j ，都有一个尺寸 sj 。若是 sj >= gi ，咱们能够将这个饼干 j 分配给孩子 i ，这个孩子会获得知足。你的目标是尽量知足越多数量的孩子，并输出这个最大数值。
注意：
 
 

 你能够假设胃口值为正。
一个小朋友最多只能拥有一块饼干。
示例 1:
输入: [1,2,3], [1,1]
输出: 1
解析：
1.给一个孩子的饼干应当尽可能小而且又能知足该孩子，这样大饼干才能拿来给知足度比较大的孩子。
2.由于知足度最小的孩子最容易获得知足，因此先知足知足度最小的孩子。
在以上的解法中，咱们只在每次分配时饼干时选择一种看起来是当前最优的分配方法，但没法保证这种局部最优的分配方法最后能获得全局最优解。咱们假设能获得全局最优解，并使用反证法进行证实，即假设存在一种比咱们使用的贪心策略更优的最优策略。若是不存在这种最优策略，表示贪心策略就是最优策略，获得的解也就是全局最优解。
证实：假设在某次选择中，贪心策略选择给当前知足度最小的孩子分配第 m 个饼干，第 m 个饼干为能够知足该孩子的最小饼干。假设存在一种最优策略，能够给该孩子分配第 n 个饼干，而且 m < n。咱们能够发现，通过这一轮分配，贪心策略分配后剩下的饼干必定有一个比最优策略来得大。所以在后续的分配中，贪心策略必定能知足更多的孩子。也就是说不存在比贪心策略更优的策略，即贪心策略就是最优策略。
 
 

 

 2.无重叠区间（mediu,435)
给定一个区间的集合，找到须要移除区间的最小数量，使剩余区间互不重叠。
注意:
能够认为区间的终点老是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
思路：
先计算最多能组成的不重叠区间个数，而后用区间总个数减去不重叠区间的个数。
在每次选择中，区间的结尾最为重要，选择的区间结尾越小，留给后面的区间的空间越大，那么后面可以选择的区间个数也就越大。
按区间的结尾进行排序，每次选择结尾最小，而且和前一个区间不重叠的区间。
 
 

 
 

 3.用最少数量的箭引爆气球（medium 452）
在二维空间中有许多球形的气球。对于每一个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。因为它是水平的，因此y坐标并不重要，所以只要知道开始和结束的x坐标就足够了。开始坐标老是小于结束坐标。平面内最多存在104个气球。
 
 

 一支弓箭能够沿着x轴从不一样点彻底垂直地射出。在坐标x处射出一支箭，如有一个气球的直径的开始和结束坐标为 xstart，xend， 且知足 xstart ≤ x ≤ xend，则该气球会被引爆。能够射出的弓箭的数量没有限制。 弓箭一旦被射出以后，能够无限地前进。咱们想找到使得全部气球所有被引爆，所需的弓箭的最小数量。
Example:
输入:
[[10,16], [2,8], [1,6], [7,12]]
输出:
2
解释:
对于该样例，咱们能够在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）
 
 

 思路:
咱们能够跟踪气球的结束坐标，若下个气球开始坐标在当前气球的结束坐标前，则咱们能够用一支箭一块儿引爆；若下个气球的开始坐标在当前气球的结束坐标后，则咱们必须增长箭的数量。并跟踪下个气球的结束坐标。
因此也是计算不重叠的区间个数，跟上一题思路同样，不过和 Non-overlapping Intervals 的区别在于，[1, 2] 和 [2, 3] 在本题中算是重叠区间。
 
 
 

 
 

 先排身高更高的，这是要防止后排入人员影响先排入人员位置
每次排入新人员[h,k]时，已处于队列的人身高都>=h，因此新排入位置就是people[k]
有了这两个思路代码实现就很是简单了
 
 

 先将people按照身高降序排序，又因为每次插入的位置是k，因此相同身高须要按k升序排序，不然插入位置会越界
因为后续须要频繁使用insert()操做，建议使用list做为中间容器
循环地从头读取people，根据people[i][1]也就是k,插入list，注意list的迭代器不支持随机访问，须要使用advance()找到应插入位置
将完成全部插入操做的list重建为vector返回
 
 

 
 
 
 
 
 
 
 
 
 
 

 5.买卖股票的最佳时机（easy 121)
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
若是你最多只容许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 由于卖出价格须要大于买入价格。
思路：
只要记录前面的最小价格，将这个最小价格做为买入价格，而后将当前的价格做为售出价格，查看当前收益是否是最大收益。
 
 

 

 6.股票买卖最佳时机II(122 easy)
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你能够尽量地完成更多的交易（屡次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉以前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能得到利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能得到利润 = 6-3 = 3
 
 

 
 

 

 思路2：
不断的找谷值和峰值，计算利润（注意不要错过一个峰值而去寻找下一个峰值，这样可能会损失一笔收益）
 
 

 

 7.种花问题（easy 605)
思路1：
贪心思想，咱们从左到右扫描数组 flowerbed，若是数组中有一个 0，而且这个 0 的左右两侧都是 0，那么咱们就能够在这个位置种花，即将这个位置的 0 修改为 1，并将计数器 count 增长 1。对于数组的第一个和最后一个位置，咱们只须要考虑一侧是否为 0。
 
 

 思路2：
在最左侧和左右侧分别加一个0，这样能够不用考虑边界问题，只要出现连续三个0，就能够在中间种一棵树
 
 

 知识点：c++建立m*n的二维空数组
 
 

 递归和动态规划都是将原问题拆成多个子问题而后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算
重点是找状态转移方程
1.斐波那契数列
(1) 爬楼梯（easy 70)
题目描述：有 N 阶楼梯，每次能够上一阶或者两阶，求有多少种上楼梯的方法。
从第三个台阶开始，知足斐波那契数列
第 i 个楼梯能够从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。
考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，所以能够只用两个变量来存储 dp[i - 1] 和 dp[i - 2]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。
 
 

 
 

 (2)打家劫舍初级版（easy 198)
抢劫一排住户，可是不能抢邻近的住户，求最大抢劫量
示例 1:
 
 

 
 

 (3)打家劫舍II(medium 213)
这个地方全部的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，若是两间相邻的房屋在同一夜被小偷闯入，系统会自动报警。
偷从第一个到倒数第二个 或 第二个到最后一个 其中金额比较大的一个便可
 
 

 (4)母牛生产
题目描述：假设农场中成熟的母牛每一年都会生 1 头小母牛，而且永远不会死。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年以后成熟又能够生小母牛。给定整数 N，求 N 年后牛的数量。
 
 

 
 

 2.矩阵路径问题
(1)最小路径（medium 64）
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 由于路径 1→3→1→1→1 的总和最小。
思路：动态规划
状态转移方程：dp[i][j]=dp[i][j]+min(dp[i-1][j],dp[i][j-1]
注意在最左侧和最上侧的状况，此时只有一种走法
 
 

 (2)不一样路径（medium 62）
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不一样的路径？
 
 

 

 
 

 你能够假设数组不可变。
会屡次调用 sumRange 方法。
由于要屡次调用，因此没办法每次都求一次[i,j]的和，
求区间 i ~ j 的和，能够转换为 sum[j + 1] - sum[i]，其中 sum[i] 为 0 ~ i-1的和。
 
 

 

 4.分割整数问题(太难理解了，以后再补充吧）
（1）整数拆分（medium 343）
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你能够得到的最大乘积。
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
思路：动态规划
令dp[i]表示整数i对应的最大乘积，那么dp[i]的值应是dp[j](i-j),j属于[1,i-1]的最大值，同时注意dp[i]对应的值是通过拆分了的，因此还应判断两个数拆分的状况，即j(i-j)的值，取最大便可。
 
 

 
 

 （2）彻底平方和数
给定正整数 n，找到若干个彻底平方数（好比 1, 4, 9, 16, …）使得它们的和等于 n。你须要让组成和的彻底平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
思路：
对于数字n，能够进行分解，分解成某个数s和彻底平方数的和，因而就有了
dp[n] = dp[s] + 1 。
而后咱们假设(dp(n) )表示数字(n )最少能够表示为(dp(n) )个彻底平方数的和，就能写出状态转移方程：
dp[i]=min(dp[i],dp[i-j*j]+1)
 
 

 1.BFS
广度优先搜索一层一层地进行遍历，每层遍历都是以上一层遍历的结果做为起点，遍历一个距离能访问到的全部节点。须要注意的是，遍历过的节点不能再次被遍历
每一层遍历的节点都与根节点距离相同。设 di 表示第 i 个节点与根节点的距离，推导出一个结论：对于先遍历的节点 i 与后遍历的节点 j，有 di <= dj。利用这个结论，能够求解最短路径等 最优解 问题：第一次遍历到目的节点，其所通过的路径为最短路径。应该注意的是，使用 BFS
 只能求解无权图的最短路径，无权图是指从一个节点到另外一个节点的代价都记为 1。
在程序实现 BFS 时须要考虑如下问题：
队列：用来存储每一轮遍历获得的节点；
标记：对于遍历过的节点，应该将它标记，防止重复遍历。
代码模板以下：
 
 定义备忘录，用于记录已经访问的位置；
 判断边界条件，是否能直接返回结果的。
 将起始位置加入到队列中，同时更新备忘录。
 获取当前队列中的元素个数。
 判断是否到达终点位置。
 获取它对应的下一个全部的节点。
 条件判断，过滤掉不符合条件的位置。
 

 （1）二进制路径中的最短路径（1091 medium）
在一个 N × N 的方形网格中，每一个单元格有两种状态：空（0）或者阻塞（1）。
一条从左上角到右下角、长度为 k 的畅通路径，由知足下述条件的单元格 C_1, C_2, …, C_k 组成：
相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不一样且共享边或角）
C_1 位于 (0, 0)（即，值为 grid[0][0]）
C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
若是 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）
返回这条从左上角到右下角的最短畅通路径的长度。若是不存在这样的路径，返回 -1 。

 

 
 
 

 （2)彻底平方数（279 medium）
给定正整数 n，找到若干个彻底平方数（好比 1, 4, 9, 16, …）使得它们的和等于 n。你须要让组成和的彻底平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
思路一：BSF
能够一层一层的算。第一层依次减去一个平方数获得第二层，第二层依次减去一个平方数获得第三层。直到某一层出现了 0，此时的层数就是咱们要找到平方数和的最小个数。
举个例子，n = 12，每层的话每一个节点依次减 1, 4, 9…。以下图，灰色表示当前层重复的节点，不须要处理。
 
 

 
 
 

 2.dfs
(1)岛屿的最大面积
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (表明土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你能够假设 grid 的四个边缘都被 0（表明水）包围着。
找到给定的二维数组中最大的岛屿面积。(若是没有岛屿，则返回面积为 0 。)
示例 1:
 
 

 
 

 

 3.Backtracking（回溯）
Backtracking属于 DFS。
1.普通 DFS 主要用在 可达性问题 ，这种问题只须要执行到特色的位置而后返回便可。
2.而 Backtracking 主要用于求解 排列组合 问题，例若有 { ‘a’,‘b’,‘c’ } 三个字符，求解全部由这三个字符排列获得的字符串，这种问题在执行到特定的位置返回以后还会继续执行求解过程。
 
 

 

 

 
 

 (1) 电话号码的字母组合（medium 17）
给定一个仅包含数字 2-9 的字符串，返回全部它能表示的字母组合。
给出数字到字母的映射以下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
 
 

 思路：深度遍历，并记录每次组合的值，给res (回溯）
 
 
 

 （2)全排列（46 medium)
给定一个 没有重复 数字的序列，返回其全部可能的全排列。