算法-数据结构-递归

算法

实现pow函数 (分治递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        
        if n<0:
            return 1/self.my_pow(x,-n)
        else:
            return self.my_pow(x,n)
        
    
    def my_pow(self,x,y):
        if y==0: return 1
        if y==1: return x
        if y%2==0:
            n=y/2
            return self.my_pow(x, n)*self.my_pow(x, n)
        else:
            n=(y-1)/2
            return self.my_pow(x, n) * self.my_pow(x, n)*x

括号生成 （递归，树的深度遍历，剪枝）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        self.res=[]
        self._gen("",n,n)
        return self.res
    
    def _gen(self,s_kuo,left,right):
        if left==0 and right==0:
            self.res.append(s_kuo)  
        if left>0:
            self._gen(s_kuo+"(",left-1,right)
        if right>left:
            self._gen(s_kuo+")",left,right-1)

八皇后问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def solveNQueens(self, n):
        """
        坐标逆时针旋转90度理解p+q ,p-q
        :type n: int
        :rtype: List[List[str]]
        """
        def DFS(cols,pie,na):
            p=len(cols)
            if p>=n:
                result.append(cols)
                return None
            for q in range(n):
                if q not in cols and p-q not in pie and p+q not in na:
                    DFS(cols+[q],pie+[p-q],na+[p+q])
        result=[]
        DFS([],[],[])
        return [[ '.'*i+'Q'+'.'*(n-1-i) for i in cols] for cols in result]