Day06 递归算法实战 LeetCode17+46

LeetCode17 电话号码的组合

思路：
要求n个数字对应字母的组合，如果前n-1个数字的组合以及组好（假设有x组），那么n个数字的组合就是这 x组，每组分别再加上第n个数字对应的字母即可。
同理，要求n-1个数字对应的字母组合，如果前n-2个数字对应的字母组合已求好（假设有y组），那么n-1个数字对应的字母组合即求得的y组每组再加上第n-1个数对应的字母即可。
…
直至将原问题分解到只剩下一个数字的时候，直接从字典中调出对应的字母即可。

首先将每个数字对应的字母通过字典表示出来，接下来即可按照递归的方法按照上述思想即可。

求解：

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        
        dic={
            2:['a','b','c'],
            3:['d','e','f'],
            4:['g','h','i'],
            5:['j','k','l'],
            6:['m','n','o'],
            7:['p','q','r','s'],
            8:['t','u','v'],
            9:['w','x','y','z']
        }
        
        res_str=[]
        if len(digits)==0:
            return []
        if len(digits)==1:
            return dic[int(digits[0])]
        result=self.letterCombinations(digits[1:])
        
        for r in result:
            for j in dic[int(digits[0])]:
                res_str.append(j+r)
        return res_str

LeetCode46 全排列

思路：
和上道题思路一样，利用递归的方法，假设求数列1234的全排列，如果234的全排列已知，那么将1加上即可；要求234的全排列，如果34的全排列已经求出，加上2即可；同理，要求34的全排列，求出4的全排列即可。
引用别的一句话：递归的把这组数的规模一个一个的缩写，比如，1234，先把1固定，递归的求234的全排列。又把2固定，递归的求34的全排列…直至只剩一个数，输出这个排列。直至只剩一个数，有终止条件，说明可以用递归，而不会无限循环下去。
但是这道题目和上面题目不同之处在于，得到上一层递归结果后，和本层的这个数的结合方式。由于是排列问题，不同于组合，组合不需要数字之间的顺序，排列需要顺便。因此，本层的数与上一层排列结果进行结合时放置在不同的位置，得到的排列结果也不同。
具体做法如下：
例如求[1 2 3 4]的全排列：
[1 2 3 4]=(1+[2 3 4])
[2 3 4]=(2+[3 4])
[3 4]=(3+[4])
[4]=4
所以：
[3 4]=（3 4）（4 3）
[2 3 4]=(2 3 4) (3 2 4) (3 4 2)
（2 4 3） （4 2 3） （4 3 2）
[1 2 3 4]=(1 2 3 4 ) (2 1 3 4 ) (2 3 1 4) (2 3 4 1) (根据上一层结果的 234，将1放在不同位置得到不同的排列结果)
(1 3 2 4) (3 1 2 4) (3 2 1 4) (3 2 4 1)
（1 3 4 2）（3 1 4 2）（3 4 1 2）（3 4 2 1）
。。。。。。

解法：

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums)==1:
            return [nums]         
        mylist=self.permute(nums[1:])        
        l=len(mylist)        
        k=len(mylist[0])        
        for i in range(l):            
            for j in range(k):                
                mylist.append(mylist[i][0:j]+[nums[0]]+mylist[i][j:])            
            mylist[i]=mylist[i]+[nums[0]]        
        return mylist 

知识回顾：

哈希表：根据关键值直接进行访问的数据结构。结合了数组和链表的优点。
应用：两数之和
应用哈希表的思想可以很巧妙的解决。利用好哈希表根据关键值进行访问的特点，将要求的两个数根据关键值-存放数值的形式存放在哈希表中。例如要求和为7的两个数，5+2=7，3+4=7，那么将存贮5的关键值设为2，将存贮3的关键值设为4即可。

环形链表
根据龟兔赛跑的思想，如果在环内跑，那么两个速度不同的动物（指针）必定会相遇，因此设置两个快慢不同的指针来判断是否有环；

根据这幅图可知，相遇后，如果再设置一个慢指针p从A点出发，那么会和之前的慢指针slow在B点，即环开始出相遇。

堆和对列
堆是一种完全二叉树，分为大根堆和小根堆。
对列是一种先进先出的思想。至于用堆和对列求解滑动窗口最大值的解法还是没有完全搞明白…

二叉树
每个结点只有两个子结点的树。
前序遍历：先根、再左、再右
中序遍历：先左、再根、再右
后续遍历：先左、再右、再根。

搜索二叉树：
每个结点的左根必须小于根结点，右根必须大于根结点，并且所以左子树、右子树也必须满足同样的条件。
可利用递归的方法验证，只有该树的左子树、右子树都满足搜索二叉树的条件，该树才是搜索二叉树。