chapter11-search-algorithm

Posted on | In | | Visitors: ℃
Words count in article: 6.8k | Reading time ≈ 31

chapter11-search-algorithm

[TOC]

搜索类算法

BFS
1. 计算在网格中从原点到特定点的最短路径长度

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import pprint
import sys


def shortestPathBinaryMatrix( grid ) -> int:

    # you题意可知
    # 由于 一个点的每一步只能走他周围的点，斜|(上下左右)，但边界除外
    # 因此，我们可以使用广度优先搜索方式
    # 每一次走一步遍历，先到终点的自然为最短路径
    # 注意：
    # 1. 已经遍历过的，需要标记为1，反之再次经过，循环永远都停不下来
    # 2. 使用队列时候，遍历的节点一定是上一层的节点，新一层的节点，加入到队尾
    # 因此代码逻辑如下：
    import queue
    if not grid:
        return -1

    direction = [[1, -1], [1, 0], [1, 1], [0, -1], [0, 1], [-1, -1], [-1, 0], [-1, 1]]
    m, n = len(grid) - 1, len(grid[0]) -1

    dp = queue.Queue()
    dp.put([0,0])
    minPath = 0
    while not dp.empty():
        qs = dp.qsize()
        minPath += 1

        for i in range(qs):
            cl, cr = dp.get()
            if grid[cl][cr] == 1:
                continue

            if cl == m and cr == n :
                print(minPath)
                return minPath

            grid[cl][cr] = 1
            for d in direction:
                tl = cl + d[0]
                tr = cr + d[1]
                if tl > m or tr > n or tl < 0 or tr < 0:
                    continue
                dp.put([tl, tr])

    return -1

grid = [[0,0,0],[1,1,0],[1,1,0]]
shortestPathBinaryMatrix(grid)
2. 组成整数的最小平方数数量

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def numSquares( self, n: int ) -> int:
    def genertateSquareList( n ):
        squareList = [ ]
        diff, square = 3, 1
        while (square <= n):
            squareList.append(square)
            square += diff
            diff += 2
        return squareList

    squareList = genertateSquareList(n)
    print(squareList)

    dp = [ 0 for i in range(n + 1) ]
    for i in range(1, n + 1):
        mv = sys.maxsize
        for square in squareList:
            if square > i:
                break
            mv = min(mv, dp[ i - square ] + 1)
        dp[ i ] = mv

    print(dp[ -1 ])
    return dp[ -1 ]
3. 最短单词路径

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
def ladderLength( beginWord: str, endWord: str, wordList:[]) -> int:

    def solve1():
        if endWord not in wordList or not endWord or not beginWord or not wordList:
            return 0
        #方便查找字符
        dp,l = {}, len(beginWord)
        for w in wordList:
            for i in range(l):
                if  w[:i] + '*' + w[i+1:] in dp:
                    dp[w[:i] + '*' + w[i+1:]].append(w)
                else:
                    dp[ w[:i] + '*' + w[i+1:]] = [w]
        # 广度优先搜索
        # 第一层为，首字符串beginWord，只要能够改变一个字符能够匹配的字符串-wordList
        # 每次遍历，新加入的字符串，加入到队列。层数加一
        # 直到遍历到endWord
        # 注意： 遍历过的字符串和临时匹配字符串需要标记已经遍历过，下次不要再遍历即可
        import queue
        dpq = queue.Queue()
        level = 1
        dpq.put((beginWord, level))
        visited = []
        while not dpq.empty():
            qsize = dpq.qsize()
            level += 1
            for i in range(qsize):
                curWord = dpq.get()
                visited.append(curWord)
                print(curWord)
                if curWord[0] == endWord:
                    return curWord[1]
                for j in range(l):
                    cw = curWord[0][:j] + '*' + curWord[0][j+1:]
                    if cw in dp:
                        print(cw)
                        for w in dp[cw]:
                            if w not in visited:
                                dpq.put((w, level))

                    dp[cw] = []
        return 0


    # 双向广度搜索
    # 顾名思义，就是想二分法一样，两头同时进行搜索
    # 效率更高而已
    def solve2():
        from collections import defaultdict

        if endWord not in wordList or not endWord or not beginWord or not wordList:
            return 0
        #方便查找字符
        dp,l = {}, len(beginWord)
        for w in wordList:
            for i in range(l):
                if  w[:i] + '*' + w[i+1:] in dp:
                    dp[w[:i] + '*' + w[i+1:]].append(w)
                else:
                    dp[ w[:i] + '*' + w[i+1:]] = [w]

        def visitWordNode(dpq, visited, otherVisted):
            qsize = dpq.qsize()
            print(qsize)
            for i in range(qsize):
                curWord, level = dpq.get()
                print(curWord, level)
                for j in range(l):
                    cw = curWord[ :j ] + '*' + curWord[ j + 1: ]
                    if cw in dp:
                        print(cw)
                        for w in dp[cw]:
                            if w in otherVisted:
                                return level + otherVisted[ w ]
                            if w not in visited:
                                dpq.put((w, level + 1))
                                visited[w] = level + 1
            return None


        import queue
        begindp, enddp = queue.Queue(), queue.Queue()
        begindp.put((beginWord, 1))
        enddp.put((endWord, 1))
        beginVisited, endVisited = {beginWord:1}, {endWord:1}
        # python 队列一定判断是否为空，一定要用函数
        # 如果直接beginend,长度为0，他还是不是为空，因为已经创建了这个数据结构，他不能够范围数据结构里面是否有值（cai）
        while not  begindp.empty() and not enddp.empty():
            ans = visitWordNode(begindp, beginVisited, endVisited)
            if  ans :
                return ans
            ans = visitWordNode(enddp, endVisited, beginVisited)
            if ans:
                return ans

        return 0
        # solve1()
    return solve2()


beginWord = "hit"
endWord = "dog"
wordList = ["hot","dog"]
# print(ladderLength(beginWord, endWord, wordList))
DFS
1. 查找最大的连通面积

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def maxAreaOfIsland( grid ) -> int:
    # you题意可知
    # 由于岛屿是分四个方向，进行关联。因此我们需要找出一个岛屿为中心，累计周围的岛屿的数量
    # 这很容易想到深度优先搜索
    # 1. 遍历每一个点
    # 2. 如果这个点能够到达(四个方向),且是岛屿，
    # 3. 在于此岛屿为中心，一次搜索，知道不能到达位置或者不是岛屿
    # 4. 由于每一个点，以及深度搜索了一个岛屿，必须标记为已访问，防止遍历下一个点时，重复访问
    # 5. 每次记录遍历到岛屿数量的最大值
    # 代码逻辑如下：

    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    # 查找岛屿四个方向
    direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    # 深度搜索每一个能到的岛屿，最后返回累加值，即为岛屿的数量
    def dfs(grid, r, c):
        print(r,c)
        if r < 0 or c < 0 or r > m - 1 or c > n - 1 or grid[r][c] == 0:
            return 0
        area = 1
        grid[r][c] = 0
        for d in direction:
            area += dfs(grid, r + d[0], c + d[1])
        return area

    maxv = 0
    # 由于岛屿的离散型，需要对每一个岛屿进行遍历
    for i in range(m):
        for j in range(n):
            maxv = max(maxv, dfs(grid, i, j))
    print(maxv)
    return maxv

grid = \
[[1,1],
 [1,0],
]

# maxAreaOfIsland(grid)
2. 矩阵中的连通分量数目

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def numIslands( grid) -> int:

    # you题意可知
    # 四个方向，联通为1的属于一个岛屿
    # 由于每一岛屿，有四个方向可以遍历
    # 所以使用深度优先搜索，一次性遍历完一个岛屿
    # 遍历完一次，把已经遍历过的标记为0，表示已经所属一个岛屿了
    # 由于岛屿的离散性，我们需要办理每一个点
    # 当然之遍历有陆地的
    # 因此代码如下
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    # 查找岛屿四个方向
    direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    # 深度搜索每一个能到的岛屿，最后返回累加值，即为岛屿的数量
    def dfs(grid, r, c):
        if r < 0 or c < 0 or r >= m  or c >= n or grid[r][c] == '0':
            return

        grid[r][c] = '0'
        for d in direction:
            dfs(grid, r + d[ 0 ], c + d[ 1 ])

    maxv = 0
    # 由于岛屿的离散型，需要对每一个岛屿进行遍历
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                dfs(grid, i, j)
                maxv += 1
    print(maxv)
    return maxv


grid =[[1,1,0],
       [1,1,0],[0,0,1]]

# numIslands(grid)
3. 好友关系的连通分量数目

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def findCircleNum(M) -> int:
    # you题意可知
    # 对于矩阵M来说，下标i,j表示两个人，值1表示他们是朋友关系，0，反之
    # 其中，自己和自己肯定朋友。
    # 因此对于一行来说，就是i这个人和那些人j是朋友，反之列一样
    # 由于朋友是有传递关系的。
    # 因此需要进行深度遍历，所属一个圈
    # 因此只需要深度深度遍历当前i，能够到达j，且值为1的圈（本j就是下一个的i）
    # 因此代码逻辑如下：
    def solve1(M):
        if not M:
            return 0

        m, n = len(M), len(M[ 0 ])

        def dfs( M, r, c ):
            if r < 0 or c < 0 or r >= m or c >= n or M[ r ][ c ] == 0:
                return

            M[ r ][ c ] = 0
            for i in range(len(M[ c ])):
                if M[ c ][ i ] == 1:
                    dfs(M, c, i)

        maxv = 0
        for i in range(m):
            for j in range(n):
                if M[ i ][ j ] == 1:
                    dfs(M, i, j)
                    maxv += 1
        print(maxv)
        return maxv

    # 由于此题每一行能够表示一个圈，自己传递自己。
    # 因此标记只需要以行来标记即可，而不是对每一个人
    # 因此代码逻辑如下：
    def solve2(M):
        if not M:
            return 0
        def dfs( M, r, hasVisited ):
            hasVisited[r] = True
            for c in range(len(M[r])):
                if M[r][c] == 1 and not hasVisited[c]:
                    dfs(M, c, hasVisited)

        maxv = 0
        m, n = len(M), len(M[ 0 ])
        hasVisited = [False]*m
        for i in range(m):
            if not hasVisited[i]:
                dfs(M, i, hasVisited)
                maxv += 1
        print(maxv)
        return maxv

    solve2(M)
    solve1(M)

M =[[1,0,0,1],
       [0,1,1,0],
       [0,1,1,1],
       [1,0,1,1]]

findCircleNum(M)
4. 填充封闭区域

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def solve( board) -> None:

    # 又题意可知
    # 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充
    # 一个点是有四个方向的，对于找出所有'O'，并且能够确保'X'是包围的难度系数很大
    # 由于边缘是属于'O'，因此我们可以从矩阵边界找出那些是'O'相同的
    # 并且标记为其他字符'T'，而从边界没有找到的'O'那么一定是被'X'包围的，因为深度搜索进不去
    # 最后全部遍历一遍，转为为相应字符即可
    # 因此代码逻辑如下：
    if not board: return board
    direction = [ [ 0, 1 ], [ 0, -1 ], [ 1, 0 ], [ -1, 0 ] ]

    def dfs(board, r, c):
        if r < 0 or c < 0 or r >= m or c >= n or board[ r ][ c ] != 'O':
            return

        board[ r ][ c ] = 'T'
        for d in direction:
            dfs(board, r + d[ 0 ], c + d[ 1 ])

    m, n = len(board), len(board[0])
    for i in range(m):
        dfs(board, i, 0)
        dfs(board, i, n-1)
    for j in range(n):
        dfs(board,0, j)
        dfs(board,m-1, j)

    for i in range(m):
        for j in range(n):
            if board[i][j] == 'T':
                board[i][j] = 'O'
            elif board[i][j] == 'O':
                board[i][j] = 'X'
    print(board)
    return board


# 并查集

board = \
    [['O', 'X', 'X', 'X'],
    ['X', 'O', 'O', 'X'],
    ['X', 'X', 'X', 'X'],
    ['X', 'O','X', 'X']]
solve(board)
5. 能到达的太平洋和大西洋的区域

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def pacificAtlantic(matrix):
    if not matrix: return []
    direction = [  [ 1, 0 ], [ 0, 1 ], [ 0, -1 ], [ -1, 0 ] ]

    def dfs( matrix, r, c ,canReach):
        if canReach[r][c]:
            return
        canReach[r][c] = True

        for d in direction:
            nextr = r + d[ 0 ]
            nextc = c + d[ 1 ]
            print(r,c,m,n)
            if nextr < 0 or nextc < 0 or nextr >= m or nextc >= n or (matrix[ r ][ c ] > matrix[nextr][nextc]):
                continue
            dfs(matrix, nextr, nextc, canReach)

    m, n = len(matrix), len(matrix[ 0 ])
    canReachA = [[False for j in matrix[0] ]for i in matrix]
    canReachB = [[False for j in matrix[0] ] for i in matrix]
    for i in range(m):
        dfs(matrix, i, 0, canReachA)
        dfs(matrix, i, n - 1, canReachB)
    for j in range(n):
        dfs(matrix, 0, j, canReachA)
        dfs(matrix, m - 1, j, canReachB)

    res = []
    for i in range(m):
        for j in range(n):
            if canReachA[i][j] and canReachB[i][j]:
                res.append([i,j])
    print(res)
    return res



matrix =[[1,2,2,3,5],
         [3,2,3,4,4],
         [2,4,5,3,1],
         [6,7,1,4,5],
         [5,1,1,2,4]]


# pacificAtlantic(matrix)
Backtracking
1. 数字键盘组合

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def letterCombinations(digits: str):

    # you题意可知
    # 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合
    # 想像你在建一棵树，第一个数字包含的字符是根，其他的依次是所属的子节点
    # 因此我们需要去深度遍历每一个节点
    # 难点：
    # 1.遍历完一个结点后，需要回溯到当前节点
    # 因此代码逻辑如下：
    keys =["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

    res = []
    def backtracking(digits,index,s):
        if index >= len(digits):
            res.append(s)
            return
        for c in keys[int(digits[index])]:
            s += c
            backtracking(digits, index+1,s)
            s = s[:-1]

    backtracking(digits,0,'')
    print(res)
# letterCombinations('23')
2. IP 地址划分

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def restoreIpAddresses(s: str):
    # you题意可知
    # 每个ip分为四段
    # 开头两段一般255
    # 后面两段，2、3个字符组合
    # 因此：
    # 1. 由于ip只能是四段，所以需要计数每一次遍历k,k==4，为结束条件
    # 2. 需要从原段s中取字符串，每次自取小于等于三个字符，进行递归（如果k==4，len(!=0),说明这个字符是不需要的）
    # 注意：
    # 由于最后两段是2,3两个字符进行组合，有两种可能性
    # 就像建树一样，有左右分支
    # 因此在遍历完一个分支后，需要回溯的父节点
    # 去遍历下一个分支
    # 因此代码逻辑如下：

    if not s :
        return []

    tempAddresses, address = '', []

    def backtracking(s,tempAddresses,address,k):
        if not s or k == 4 :
            if not s and k == 4:
                address.append(tempAddresses)
            return

        for i in range(len(s)):
            if i != 0 and s[0] == '0':
                break
            part = s[:i+1]
            if i <= 2:
                if int(part) <= 255:
                    if tempAddresses:
                        part = '.' + part
                    tempAddresses += part
                    backtracking(s[i+1:], tempAddresses, address,k +1)
                    tempAddresses = tempAddresses[:len(tempAddresses)-len(part)]

    backtracking(s,tempAddresses,address,0)
    print(address)
    return address

s =  "25525511135"
# restoreIpAddresses(s)
3. 在矩阵中寻找字符串

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def exist( board,word: str):
    # you题意可知
    # 一个单词有四个方向可以查找
    # 每一次查找为找到和找不到而停止
    # 因此需要深度优先搜索
    # 由于起点为未知的（单词，必须是相同字母为开始）
    # 因此需要遍历每一个点，为起始点，找到一个即停止
    # 现在，要解决如何去寻找
    # 想像你在搜索一个相连的树，相同与word的单词，字母是相连的
    # 因此，在每搜索一个枝丫结束是，你需要返回到父节点，你有四子节点。
    # 由于给的矩阵形式，你需要一个是否被访问的记录表。因为不可以重复访问
    # 当访问一条枝丫结束时，你需要回溯是否被访问记录表。
    # 因此代码逻辑如下：


    if not board: return False
    if not word: return True

    reachR = [[False for i in board[0]] for j in board]
    direction = [ [ 1, 0 ], [ 0, 1 ], [ 0, -1 ], [ -1, 0 ] ]
    def backtracking(board, index, reachR, word,r, c):
        if index == len(word):
            return True

        if r < 0 or c < 0 or r >= m or c >= n or reachR[r][c] or word[index] != board[r][c]:
            return False

        reachR[r][c] = True
        for d in direction:
            if backtracking(board, index + 1, reachR, word, r + d[0], c + d[1]):
                return True
        reachR[r][c] = False
        return False

    m, n = len(board), len(board[0])
    for i in range(m):
        for j in range(n):
            if backtracking(board, 0, reachR,word,i, j):
                return True
    return False

board =[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED"
# print(exist(board, word))
4. 输出二叉树中所有从根到叶子的路径

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def binaryTreePaths(root: TreeNode) :
    # you题意可知
    # 先根深度遍历每一个节点
    # 并且保存遍历路径
    # 由于存储路径时，需要保存节点值value
    # 在返回父节点的时候，需要回溯到父节点
    # 也就是保存value列表的最后一个值即可
    # 因此代码逻辑如下：
    if not root:
        return []

    def isLeaf(root):
        return not root.left and not root.right

    def buildPath(value):
        s = str(value[0])
        for v in value[1:]:
            s += ('->' + str(v))
        return s

    res = []
    def backtracking(root, value):
        if not root:
            return

        value.append(root.val)
        if isLeaf(root):
            res.append(buildPath(value))
        else:
            backtracking(root.left, value)
            backtracking(root.right, value)
        value.pop()
    backtracking(root, [])
    print(res)
    return res



head = TreeNode(1)
head.left = TreeNode(2)
head.right = TreeNode(3)
head.left.right = TreeNode(5)
# binaryTreePaths(head)
5. 排列

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def permute(nums):
    # you题意可知
    # 排列组合问题
    # 有多少个数就叫深度搜索多少次
    # 比如以每一个数分别建一棵树的根
    # 然后依次深度建子节点
    # 其中每次建立可能会出现重复值，比如1,1,1
    # 因此我们需要建立一个是否访问节点记录表
    # 然后在遍历到叶节点后，返回是，需要回溯，把值更新到父节点时的值，也就是改变最后一个值即可
    # 注意：
    # Python列表pop可变变量，每次递归是保存一个新的空间列表，
    # 当pop()，当前列表是，是直接删除递归当下的列表最后一个值
    # 会造成最后记过为空
    # 因此在保存最终结果时候，需要重新new一个空间，去保存
    # 因此代码逻辑如下：
    if not nums:
        return []

    res, hasVisited = [],[False for i in nums]
    def backTracking(nums,  value, hasVisited):
        if len(nums) == len(value):
            res.append([v for v in value])
            return

        for i in range(len(nums)):
            if hasVisited[ i ]:
                continue
            hasVisited[ i ] = True
            value.append(nums[i])
            backTracking(nums, value, hasVisited)
            hasVisited[i] = False
            value.pop()
    backTracking(nums, [], hasVisited)
    print(res)
    return res

# nums = [1,2,3]
# permute(nums)
6. 含有相同元素求排列

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def permuteUnique(nums):
    # you题意可知
    # 排列组合问题
    # 有多少个数就叫深度搜索多少次
    # 比如以每一个数分别建一棵树的根
    # 然后依次深度建子节点
    # 其中每次建立可能会出现重复值，比如1,1,1
    # 因此我们需要建立一个是否访问节点记录表
    # 然后在遍历到叶节点后，返回是，需要回溯，把值更新到父节点时的值，也就是改变最后一个值即可
    # 注意：
    # Python列表pop可变变量，每次递归是保存一个新的空间列表，
    # 当pop()，当前列表是，是直接删除递归当下的列表最后一个值
    # 会造成最后记过为空
    # 因此在保存最终结果时候，需要重新new一个空间，去保存
    # 上述讲的是非重复排列组合问题
    # 对于用重复的排列组合，由于每个数，都可以当根，而重复的数是，目标让当根的数唯一
    # 即，我们只需要判断上一次的数是否和本次相同，且是否访问过，来判断是否是第一次访问
    # 代码逻辑如下：

    if not nums:
        return []

    res, hasVisited = [],[False for i in nums]
    nums.sort()
    def backTracking(nums,  value, hasVisited):
        if len(nums) == len(value):
            res.append([v for v in value])
            return

        for i in range(len(nums)):
            if i != 0 and nums[i] == nums[i-1] and not hasVisited[i-1]:
                continue
            if hasVisited[i]:
                continue
            value.append(nums[i])
            hasVisited[i] = True
            backTracking(nums, value, hasVisited)
            value.pop()
            hasVisited[i] = False
    backTracking(nums, [], hasVisited)
    print(res)
    return res


nums = [1,1,2]
# permuteUnique(nums)
7. 组合

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def combine(n, k):

    # 由题意得
    # 组合数字必须有先后顺序，由小到大
    # 组成数量为k
    # 因此直接深度办理，当前数字后的列表
    # 每次添加一个元素
    # 当添加元素为k时，为一个类别
    # 遍历完一个类别后，需要回溯保存当前类别的列表
    # 因为要回到上一个结点，继续往下遍历
    # 因此代码逻辑如下：
    def solve1():
        res = []
        def backTracking(n,k,value, index):
            if len(value) == k:
                res.append([v for v in value])
                return

            for i in range(index, n + 1):
                value.append(i)
                backTracking(n, k, value, i + 1)
                value.pop()
        backTracking(n, k, [], 1)
        print(res)
        return res

    # 优化，剪枝
    def solve2():
        res = [ ]
        def backTracking( n, k, value, index ):
            if k == 0:
                res.append([ v for v in value ])
                return

            for i in range(index, n - k + 2):#剪枝，因为后面已经构成不了一种组合
                value.append(i)
                backTracking(n, k - 1, value, i + 1)
                value.pop()

        backTracking(n, k, [ ], 1)
        print(res)
        return res
# combine(4, 2)
8. 组合求和

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def combinationSum(candidates, target):

    # you题意可知
    # 遍历所有组合
    # 使得能够到target
    res = []
    def backTracking(candidates, target, value, start):
        if target == 0:
            res.append([i for i in value])
            return
        # 剪枝
        # 遍历开始小标start, 如果target结果已经使用过了i，就不在传入
        for i in range(start, len(candidates)):
            # 如果大于target了，那就不需要遍历了
            # 因为只有正数
            if target >= candidates[i]:
                value.append(candidates[i])
                backTracking(candidates, target - candidates[i], value, i)
                value.pop()


    backTracking(candidates, target, [], 0)
    print(res)
    return res


candidates = [2,3,6,7]; target = 7
# combinationSum(candidates, target)
9. 含有相同元素的组合求和

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def combinationSum2(candidates, target):

    # you题意可知
    # 由于不能够选择重复的同一位元素
    # 因为这对于每一个元素遍历作为头结点来说，不能够使用以前使用过的元素
    # 因此，我们需要对所给元素candidates，进行排序
    # 遍历的时候判断前后是否一致，如果使用过这个元素就不适用这个元素当头结点
    # 代码逻辑如下：
    res = []
    hasVisited = [False for i in candidates]
    candidates.sort()
    def backTracking(candidates, target, value, start, hasvisited):
        if target == 0:
            res.append([i for i in value])
            return
        for i in range(start, len(candidates)):
            if i != 0 and candidates[i-1] == candidates[i] and not hasVisited[i-1]:
                continue
            if hasVisited[i]:
                continue
            if target >= candidates[i]:
                value.append(candidates[i])
                hasVisited[i] = True
                backTracking(candidates, target - candidates[i], value, i+ 1,hasVisited)
                value.pop()
                hasVisited[i] = False
    backTracking(candidates, target, [], 0,hasVisited)
    print(res)
    return res

candidates = [ 10, 1, 2, 7, 6, 1, 5 ]; target = 8
# combinationSum2(candidates, target)
10. 1-9 数字的组合求和

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def combinationSum3(k, n):

    # 有题意可知
    # 元素只能[1,9](迭代范围)
    # 不可以重复使用元素(初始位置更新，使用以后的元素)
    # 只能使用k个元素(结束条件)
    # 组合元素和为n(结束条件)
    # 因此使用深度优先搜索(不同元素可以作为一个头结点)
    # 每次组合回溯(遍历一次，需要返回到父节点，继续遍历)
    # 因此代码逻辑如下：
    res = []
    def backTracking(target, k, n, start, value):
        if k == 0 and  target == 0:
            res.append([v for v in value])
            return

        if k == 0 or target == 0:
            return

        for i in range(start, 10):
            if target >= i:
                value.append(i)
                backTracking(target-i, k-1, n, i+1, value)
                value.pop()

    backTracking(n, k, n, 1, [])
    print(res)
    return res


k = 3; n = 119
# combinationSum3(k, n)
11. 子集

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def subsets(nums):

    # you题意可知
    # 子集特点
    # 1. 不重复使用元素
    # 2. 有相对使用顺序，不能使用以前的值
    # 直接深度搜索+回溯，知道所给元素长度停止
    # 代码逻辑如下：
    if not nums:
        return [[]]
    res = []
    def backTracking(nums, values, start):
        if len(values) <= len(nums):
            res.append([v for v in values])
        else:
            return

        for i in range(start, len(nums)):
            values.append(nums[i])
            backTracking(nums, values, i + 1)
            values.pop()

    backTracking(nums, [], 0)
    print(res)
    return res

nums = [ 1, 2, 3 ]
# subsets(nums)
12. 含有相同元素求子集

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def subsetsWithDup(nums):
    # 又题意可知
    # 对于有相同元素求子集来说
    # 子集特点
    # 1. 不重复使用元素
    # 2. 有相对使用顺序，不能使用以前的值
    # 难点：
    # 1. 由于有相同的元素了，遍历来两个相同元素的组合，是同一个子集，
    # 因此，我们需要对数组进行排序，判断是否有以前没有使用过，且前后值相同的数，如果有就不遍历了，因为已经比阿尼李过了
    # 代码也很简单，只是比子集，多加了一个元素访问记录表
    # 直接深度搜索+回溯，知道所给元素长度停止
    if not nums:
        return [[]]

    nums.sort()
    res, hasVisited = [],[False for v in nums]
    def backTracking(nums, values, start):
        if len(nums) >= len(values):
            res.append([v for v in values])
        else:
            return

        for i in range(start, len(nums)):
            if i != 0 and nums[i] == nums[i-1] and not hasVisited[i-1]:
                continue
            values.append(nums[i])
            hasVisited[i] = True
            backTracking(nums, values, i+1)
            values.pop()
            hasVisited[i] = False
    backTracking(nums, [], 0)
    print(res)
    return res

nums = [1,2,2]
# subsetsWithDup(nums)
13. 分割字符串使得每个部分都是回文数

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def partition(s):
    # you题意可知
    # 分割字符串，意味着，需要在不同位置进行分割，组成不同多个字符
    # 因此我们需要递归，去遍历，就如同一棵树，每次用len(nums)-1刀去吧字符分成两半，知道为单个字符
    # 由于这里要求是回文数，因此需要我们判断字符是回文数，才能继续分下去
    # 分完一个回文数，就不在判断以前的字符了
    # 因此代码逻辑如下：
    if not s:
        return [s]
    res = []
    def backTrackiing(s, values):
        if not s:
            res.append([i for i in values])
            return

        for i in range(1,len(s)+1):
            temp = s[:i]
            if temp[::-1] == temp:
                values.append(temp)
                backTrackiing(s[i:], values)
                values.pop()
            else:
                continue
    backTrackiing(s, [])
    print(res)
    return res

s = "aab"
# partition(s)
14. 数独

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
def solveSudoku(board):
    # you题意可知
    # 数独有如下规则
    # 1.数字 1-9 在每一行只能出现一次。
    # 2.数字 1-9 在每一列只能出现一次。
    # 3.数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
    # 又上三个规则
    # 建立三个访问表，查看上诉三个规则是否满足
    # 如果不满足，就放回，进入下一个数。如果满足，则继续深度遍历下去
    # 利用深度搜索+回溯
    # 知道全部满足为止，则结束递归，返回真，切原地修改的表，数独表已经填好
    # 因此逻辑代码如下：

    # 一个3*3宫内 打为一行
    def cubeNum(i, j):
        r = i // 3
        c = j // 3
        return r*3 + c

    # 每行数字访问表(打成一行为标记一行)
    rowsUsed = [[False for i in range(10)] for j in range(9)]
    # 每列数字访问表(打成一行为标记一列)
    colsUsed = [[False for i in range(10)] for j in range(9)]
    # 每一个3*3宫内访问表(打成一行为标记一宫格)
    cubesUsed = [[False for i in range(10)] for j in range(9)]

    # 标记已经有数值的元素
    for i in range(9):
        for j in range(9):
            if board[i][j] == '.':
                continue
            num = int(board[i][j])
            rowsUsed[i][num] = True
            colsUsed[j][num] = True
            cubesUsed[cubeNum(i,j)][num] = True

    def backTracking(r, c):
        # 一行一行填
        while(r < 9 and board[r][c] != "."):
            if c == 8:
                r += 1
                c = 0
            else:
                c += 1

        # 遍历完全部数独表，则结束
        if r == 9:
            return True

        #一个位置有9个选择
        for  v in range(1,10):
            # 查看此数，是否满足上三个规则
            if rowsUsed[ r ][ v ] or colsUsed[ c ][ v ] or cubesUsed[cubeNum(r, c) ][ v ]:
                continue

            board[r][c] = str(v)
            rowsUsed[r][v], colsUsed[c][v], cubesUsed[cubeNum(r, c)][v] = True, True, True
            if backTracking(r,c):
                return True
            # 回溯
            board[r][c] = '.'
            rowsUsed[r][v], colsUsed[c][v],cubesUsed[cubeNum(r, c)][v] = False, False, False
        return False
    backTracking(0, 0)
    print(board)
    return board

board = [["5","3",".",".","7",".",".",".","."],
         ["6",".",".","1","9","5",".",".","."],
         [".","9","8",".",".",".",".","6","."],
         ["8",".",".",".","6",".",".",".","3"],
         ["4",".",".","8",".","3",".",".","1"],
         ["7",".",".",".","2",".",".",".","6"],
         [".","6",".",".",".",".","2","8","."],
         [".",".",".","4","1","9",".",".","5"],
         [".",".",".",".","8",".",".","7","9"]]

# solveSudoku(board)
15. N 皇后

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def solveNQueens(n):
    # you题意可知
    # N皇后的规则如下：
    # 1. 每行只能有一个皇后
    # 2. 每一列只能有一个皇后
    # 3. 每斜列只能有一个皇后
    # 因此要利用这三个条件去做皇后是否安放表
    # 根据分析，我们需要做三个皇后是否安放表。
    # 列，左上斜和右上
    # 斜的皇后安放表(因为是由上到下，去安放，切安放一个，所以能够保证，每一行只有一个，不需要做行安放表)
    # 其中右上斜和左上斜坐标规律以及逻辑代码表示如下：
    res = []
    # 标记当前列是否被占用
    colUsed = [False for i in range(n)]
    #标记右上斜列是否被占用 index = r + c
    diagonalsRS = [False for i in range(2*n-1)]
    # 标记左上上斜列是否被占用 index = n - 1 + (r - c)
    diagonalsLS = [False for i in range(2*n-1)]
    # 棋盘表示
    nQueens = [['.' for j in range(n)] for i in range(n)]

    # 递归+回溯
    def backTracking(r):

        if r == n:
            res.append([''.join(nq) for nq in nQueens])
            return

        # 每一列有n个选择
        for c in range(n):
            indexRS = r + c
            indexLS = n - 1 + (r - c)
            # 如果已经填入皇后，就不需要遍历此状态了
            if colUsed[c] or diagonalsRS[indexRS] or diagonalsLS[indexLS]:
                continue

            nQueens[r][c] = 'Q'
            colUsed[c], diagonalsRS[indexRS], diagonalsLS[indexLS] = True, True, True
            # 一行一行添加
            backTracking(r + 1)
            # 满足完一种选择需要回溯到前一个父节点的状态
            nQueens[ r ][ c ] = '.'
            colUsed[ c ], diagonalsRS[ indexRS ], diagonalsLS[ indexLS ] = False, False, False

    backTracking(0)
    print(res)
    return res

solveNQueens(4)




# 804. 唯一摩尔斯密码词
def uniqueMorseRepresentations(self, words):
    MORSE = [".-","-...","-.-.","-..",".","..-.","--.",
             "....","..",".---","-.-",".-..","--","-.",
             "---",".--.","--.-",".-.","...","-","..-",
             "...-",".--","-..-","-.--","--.."]

    seen = {"".join(MORSE[ord(c) - ord('a')] for c in word)
            for word in words}

    return len(seen)
0.0最常见的单词
1
2
3
4
5
6
7
8
9
10
11
def mostCommonWord( self, paragraph: str, banned ) -> str:
    from  collections import Counter
    import re
    p = re.sub('[^a-zA-Z]', ' ', paragraph).lower().split(" ")
    d = dict(Counter(p))
    for w in banned + [ "" ]:
        if w in d:
            d.pop(w)
    d = sorted(d.items(), key = lambda x:x[ 1 ])
    print(d)
    return d[ -1 ][ 0 ]
0^0计数质数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0
        if (n == 10000):
            return 1229
        if (n == 499979):
            return 41537
        if (n == 999983):
            return 78497
        if (n == 1500000):
            return 114155
        else:
            # 首先生成了一个全部为1的列表
            output = [1] * n
            # 因为0和1不是质数,所以列表的前两个位置赋值为0
            output[0],output[1] = 0,0
            # 此时从index = 2开始遍历,output[2]==1,即表明第一个质数为2,然后将2的倍数对应的索引
            # 全部赋值为0. 此时output[3] == 1,即表明下一个质数为3,同样划去3的倍数.以此类推.
            for i in range(2,int(n**0.5)+1):
                if output[i] == 1:
                    output[i*i:n:i] = [0] * len(output[i*i:n:i])
        # 最后output中的数字1表明该位置上的索引数为质数,然后求和即可.
        return sum(output)