盒子
盒子
文章目录
  1. 1.深度优先搜索
  2. 2.比较巧妙的递归，在递归中设置激活按钮
  3. 3.回溯法

递归的思考

2016.10.20 nichunquan machine learning  热度 ℃

递归想了想差不多能够分清楚有哪些题型了

1）和回溯相关

1.深度优先搜索

IP地址的可能排列

dfs(s,tmp,index,res)

一般都是这样的格式，就是，第一个参数是输入原始参数，比如数啊，string啊之类的，tmp是临时的结果组合，index是组合到了什么程度，就是跳出递归的条件，最后res是存放每次递归的tmp结果的

1，leetcode#93

Restore IP Addresses

输入: “25525511135”

输出: [“255.255.11.135”, “255.255.111.35”]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        def dfs(s,tmp,indx, res):
		    if indx==4 and s=='':
		        res.append(tmp[:-1])
		        return
		    if indx==4:
		        return
		    for i in range(3):
		        if i==0 and len(s)>0:
		            dfs(s[1:],tmp+s[:1]+'.',indx+1,res)
		        if i==1 and len(s)>1 and s[0]!='0':
		            dfs(s[2:],tmp+s[:2]+'.',indx+1,res)
		        if i==2 and len(s)>2 and int(s[:3])<256 and s[0]!='0':
            dfs(s[3:],tmp+s[:3]+'.',indx+1,res)
        res = []
        
        dfs(s,'',0,res)
        return res

2.比较巧妙的递归，在递归中设置激活按钮

1，leetcode#695

Max Area of Island
Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

1
2
3
4
5
6
7
8
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]

return 6

1
2
3
4
5
6
7
8
9
10
11
def maxAreaOfIsland(self, grid):
     m, n = len(grid), len(grid[0])
     def dfs(i, j):
         if 0 <= i < m and 0 <= j < n and grid[i][j]:
             grid[i][j] = 0
             return 1 + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i + 1, j) + dfs(i, j - 1)
         return 0
     areas = [dfs(i, j) for i in range(m) for j in range(n) if grid[i][j]]
     return max(areas) if areas else 0

这一题需要流程的想象，比如上面例子中遍历到grid（0，6），他会先关闭递归的触发条件，然后进入递归，这样就不会重复递归

3.回溯法

比如比较常见的permutation

input 123

output [123,132,213,231,312,312]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def backtrack(res,templist,nums):
    if(len(templist) == len(nums)):
        res.append(templist[:])
    else:
        for i in nums:
            if(i in templist): #如果在当前排列中已经有i了，就continue，相当于分支限界，即不对当前节点子树搜寻了
                continue
            templist.append(i)
            self.backtrack(rtlist,templist,nums)
            templist.pop() #把结尾的元素用nums中的下一个值替换掉，遍历下一颗子树
def permute(nums):
    rtlist = []
    templist = []
    self.backtrack(rtlist,templist,nums)
    return rtlist

采用回溯法一定要注意res.append的结果一定要是tmp的复制而不是，指针就是一定要加上[:]