算法图解学习

1
大前提是先按大小排好序
2
def binary_search(list, item):
3
  # low and high keep track of which part of the list you'll search in.
4
  low = 0
5
  high = len(list) - 1
6

7
  # While you haven't narrowed it down to one element ...
8
  while low <= high:
9
    # ... check the middle element
10
    mid = (low + high) // 2
11
    guess = list[mid]
12
    # Found the item.
13
    if guess == item:
14
      return mid
15
    # The guess was too high.
16
    if guess > item:
17
      high = mid - 1
18
    # The guess was too low.
19
    else:
20
      low = mid + 1
21

22
  # Item doesn't exist
23
  return None
24

25
my_list = [2, 3, 5, 7, 11,13]
26
print(binary_search(my_list, 13)) # => 1
27
# 返回所在位置
28
# 'None' means nil in Python. We use to indicate that the item wasn't found.
29
print(binary_search(my_list, -1)) # => None

1
运行时间O(n*1/2*n)

1
# Finds the smallest value in an array
2
def findSmallest(arr):
3
  # Stores the smallest value
4
  smallest = arr[0]
5
  # Stores the index of the smallest value
6
  smallest_index = 0
7
  for i in range(1, len(arr)):
8
    if arr[i] < smallest:
9
      smallest_index = i
10
      smallest = arr[i]
11
  return smallest_index
12

13
# Sort array
14
def selectionSort(arr):
15
  newArr = []
16
  for i in range(len(arr)):
17
      # Finds the smallest element in the array and adds it to the new array
18
      smallest = findSmallest(arr)
19
      newArr.append(arr.pop(smallest))
20
  return newArr
21

22
print(selectionSort([5, 3, 6, 2, 10]))

1
def quicksort(array):
2
  if len(array) < 2:
3
    # base case, arrays with 0 or 1 element are already "sorted"
4
    return array
5
  else:
6
    # recursive case
7
    pivot = array[0]
8
    # sub-array of all the elements less than the pivot
9
    less = [i for i in array[1:] if i <= pivot]
10
    # 这是什么操作（python还有这种写法？）
11
    # 从1开始，往后循环
12
    # sub-array of all the elements greater than the pivot
13
    greater = [i for i in array[1:] if i > pivot]
14
    return quicksort(less) + [pivot] + quicksort(greater)
15

16
print(quicksort([10, 5, 2, 3, 8]))

1
book = {"apple": 0.67, "milk": 1.49, "avocado": 1.49}
2
book["Lisa"] = 100
3
print(book)

1
voted = {}
2
def check_voter(name):
3
  if voted.get(name):
4
    print("kick them out!")
5
  else:
6
    voted[name] = True
7
    print("let them vote!")
8

9
check_voter("tom")
10
check_voter("mike")
11
check_voter("mike")

1
from collections import deque
2

3
def person_is_seller(name):
4
      return name[-1] == 'm'
5

6
graph = {}
7
graph["you"] = ["alice", "bob", "claire"]
8
graph["bob"] = ["anuj", "peggy"]
9
graph["alice"] = ["peggy"]
10
graph["claire"] = ["thom", "jonny"]
11
graph["anuj"] = []
12
graph["peggy"] = []
13
graph["thom"] = []
14
graph["jonny"] = []
15

16
def search(name):
17
    search_queue = deque() #定义其为队列
18
    search_queue += graph[name]
19
    # This array is how you keep track of which people you've searched before.
20
    searched = []
21
    while search_queue:
22
        person = search_queue.popleft()
23
        # Only search this person if you haven't already searched them.
24
        if person not in searched:
25
            if person_is_seller(person):
26
                print(person + " is a mango seller!")
27
                return True
28
            else:
29
                search_queue += graph[person]
30
                # Marks this person as searched
31
                searched.append(person)
32
    return False
33

34
search("you")

1
# the graph
2
# 用于确定父连接
3
graph = {}
4
graph["start"] = {}
5
graph["start"]["a"] = 6
6
graph["start"]["b"] = 2
7

8
graph["a"] = {}
9
graph["a"]["fin"] = 1
10

11
graph["b"] = {}
12
graph["b"]["a"] = 3
13
graph["b"]["fin"] = 5
14

15
graph["fin"] = {}
16

17
# the costs table
18
# 用于初始化
19
infinity = float("inf")
20
costs = {}
21
costs["a"] = 6
22
costs["b"] = 2
23
costs["fin"] = infinity
24

25
# the parents table
26
parents = {}
27
parents["a"] = "start"
28
parents["b"] = "start"
29
parents["fin"] = None
30

31
processed = []
32

33
def find_lowest_cost_node(costs):
34
    lowest_cost = float("inf")  #函数初始化
35
    lowest_cost_node = None
36
    # Go through each node.
37
    for node in costs:
38
        cost = costs[node]
39
        # If it's the lowest cost so far and hasn't been processed yet...
40
        if cost < lowest_cost and node not in processed:
41
            # ... set it as the new lowest-cost node.
42
            lowest_cost = cost
43
            lowest_cost_node = node
44
    return lowest_cost_node
45

46
# Find the lowest-cost node that you haven't processed yet.
47
node = find_lowest_cost_node(costs)
48
# If you've processed all the nodes, this while loop is done.
49
while node is not None:
50
    cost = costs[node]
51
    # Go through all the neighbors of this node.
52
    neighbors = graph[node]
53
    for n in neighbors.keys():
54
        new_cost = cost + neighbors[n]
55
        # If it's cheaper to get to this neighbor by going through this node...
56
        if costs[n] > new_cost:
57
            # ... update the cost for this node.
58
            costs[n] = new_cost
59
            # This node becomes the new parent for this neighbor.
60
            parents[n] = node
61
    # Mark the node as processed.
62
    processed.append(node)
63
    # Find the next node to process, and loop.
64
    node = find_lowest_cost_node(costs)
65

66
print("Cost from the start to each node:")
67
print(costs)

1
# You pass an array in, and it gets converted to a set.
2
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
3

4
stations = {}
5
stations["kone"] = set(["id", "nv", "ut"])
6
stations["ktwo"] = set(["wa", "id", "mt"])
7
stations["kthree"] = set(["or", "nv", "ca"])
8
stations["kfour"] = set(["nv", "ut"])
9
stations["kfive"] = set(["ca", "az"])
10

11
final_stations = set()
12
#   第一遍时ktwo因为长度与kone的范围一样而没被纳入
13
while states_needed: #在遍历中，直到states_needed全部清空
14
  best_station = None
15
  states_covered = set()
16
  for station, states_for_station in stations.items():  ##没看懂
17
    covered = states_needed & states_for_station  ## 取交集
18
    if len(covered) > len(states_covered):
19
      best_station = station
20
      states_covered = covered
21

22
  states_needed -= states_covered
23
  final_stations.add(best_station)
24

25
print(final_stations)