1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def binary_search(data, target, left, right):
    while left <= right:
        mid = left + ((right - left) >> 1)
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            left = mid + 1
        else:
            right = mid - 1


if __name__ == '__main__':
    array = [i for i in range(50, 100)]
    target = 67
    find = binary_search(array, target, 0, len(array) - 1)
    print(find)
    print(array[find])

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
from collections import deque


graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}


def neighbor(node):
    return graph[node]


def breadth_first_search(start, target):
    que = deque([start])
    visited = {start}
    steps = 0
    while que:
        for _ in range(len(que)):
            cur = que.popleft()
            if cur == target:
                return steps
            for node in neighbor(cur):
                if node in visited:
                    continue
                que.append(node)
                visited.add(node)
        steps += 1
    return -1


if __name__ == '__main__':
    step = breadth_first_search('A', 'F')
    print(step)

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

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}


def neighbor(node):
    return graph[node]


def depth_first_search(node, visited):
    if node == target:
        return True
    for cur in neighbor(node):
        if cur in visited:
            continue
        visited.add(cur)
        if depth_first_search(cur, visited):
            return True
        visited.remove(cur)
    return False


if __name__ == '__main__':
    start = 'B'
    target = 'F'
    visited = {start}
    find = depth_first_search(start, visited)
    print(find)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def permutation(n, m, cur, used):
    if len(cur) == m:
        print(cur)
        return
    for i in range(n):
        if used[i]:
            continue
        used[i] = True
        cur.append(i + 1)
        permutation(n, m, cur, used)
        cur.pop()
        used[i] = False


if __name__ == '__main__':
    n = 3
    m = 3
    permutation(n, m, [], [False] * n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def combination(n, m, s, cur):
    if len(cur) == m:
        print(cur)
        return
    for i in range(s, n):
        cur.append(i + 1)
        combination(n, m, i + 1, cur)
        cur.pop()


if __name__ == '__main__':
    n, m = 5, 3
    combination(n, m, 0, [])

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

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class LinkList(object):

    def reverse_list(self, head):
        pre, cur = None, head
        while cur:
            cur.next, pre, cur = pre, cur, cur.next
        return pre

    def swap_pairs(self, head):
        dummy = ListNode(0)
        pre, pre.next = dummy, head
        while pre.next and pre.next.next:
            a = pre.next
            b = a.next
            pre.next, b.next, a.next = b, a, b.next
            pre = a
        return dummy.next

    def detect_cycle(self, head):
        slow = fast = head
        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

    def find_k_to_last_element(self, head, k):
        slow = fast = head
        while fast and k > 0:
            fast = fast.next
            k -= 1
        if k > 0:
            return None
        while fast:
            fast = fast.next
            slow = slow.next
        return slow

    def find_the_middle(self, head):
        slow = fast = head
        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def find_the_cycle_location(self, head):
        slow = fast = head
        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                break
        slow = head
        while slow is not fast:
            slow = slow.next
            fast = fast.next
        return slow


if __name__ == '__main__':
    node1 = ListNode(1)
    node2 = ListNode(2)
    node1.next = node2
    node3 = ListNode(3)
    node2.next = node3
    node4 = ListNode(4)
    node3.next = node4
    node5 = ListNode(5)
    node4.next = node5
    head = LinkList()
    # result = head.reverse_list(node1)
    # while result:
    #     print('{0} -> '.format(result.val), end='')
    #     result = result.next

    result2 = head.swap_pairs(node1)
    while result2:
        print('{0} -> '.format(result2.val), end='')
        result2 = result2.next

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

def shell_sort(data):
    groups = len(data) >> 1
    # 分组
    while groups:
        # 组内挪步
        for stride in range(groups):
            for i in range(stride + groups, len(data), groups):
                cur = data[i]
                j = i - groups
                # 找合适位置：当前数 比 前面的数 小，往前移
                while j >= 0 and cur < data[j]:
                    data[j + groups] = data[j]
                    j -= groups
                # 找到合适位置，插入数值
                data[j + groups] = cur
        groups >>= 1
    return data


def selection_sort(data):
    for i in range(len(data)):
        min_value = data[i]
        index = i
        for j in range(i + 1, len(data)):
            if data[j] < min_value:
                min_value = data[j]
                index = j
        data[index], data[i] = data[i], data[index]
    return data


def quick_sort_partition(data, low, high):
    pivot = data[low]
    while low < high:
        while low < high and data[high] >= pivot:
            high -= 1
        data[low] = data[high]
        while low < high and data[low] <= pivot:
            low += 1
        data[high] = data[low]
    data[low] = pivot
    return low


def quick_sort(data, low, high):
    if low < high:
        pivot_position = quick_sort_partition(data, low, high)
        quick_sort(data, low, pivot_position - 1)
        quick_sort(data, pivot_position + 1, high)
    return data


if __name__ == '__main__':
    data = [12, 49, 59, 14, 15, 71,  8, 41,  2, 73, 85, 99, 20, 84, 83, 53,  0, 77, 11, 29]
    print(data)
    print(shell_sort(data))
    print(selection_sort(data))
    print(quick_sort(data, 0, len(data) - 1))