二分查找-排序-递归-算法实现
# 查找元素在列表中的位置 def binary_search(lst, item): low = 0 # low和high用于跟踪要在其中查找的列表部分 high = len(lst)-1 while low <= high: #←-------------只要范围没有缩小到只包含一个元素， mid = (low + high) // 2 #←-------------就检查中间的元素 guess = lst[mid] if guess == item: #←-------------找到了元素 return mid if guess > item: #←-------------猜的数字大了 high = mid - 1 else: #←---------------------------猜的数字小了 low = mid + 1 return None #←--------------------没有指定的元素 my_list = [1, 3, 5, 7] # ←------------来测试一下！ print(binary_search(my_list, 3)) # => 1 ←--------------------别忘了索引从0开始，第二个位置的索引为1 print(binary_search(my_list, -1)) # => None ←--------------------在Python中，None表示空，它意味着没有找到指定的元素选择排序
# Finds the smallest value in an array def findSmallest(arr): # Stores the smallest value smallest = arr[0] # Stores the index of the smallest value smallest_index = 0 for i in range(1, len(arr)): if arr[i] < smallest: smallest_index = i smallest = arr[i] return smallest_index # Sort array def selectionSort(arr): newArr = [] for i in range(len(arr)): # Finds the smallest element in the array and adds it to the new array smallest = findSmallest(arr) newArr.append(arr.pop(smallest)) return newArr print(selectionSort([5, 3, 6, 2, 10]))递归（分而治之）
(1) 找出简单的基线条件；
(2) 确定如何缩小问题的规模，使其符合基线条件。
# 递归求列表最大值 def max_(lst): if len(lst) == 0: return None if len(lst) == 1: return lst[0] else: sub_max = max_(lst[1:]) return lst[0] if lst[0] > sub_max else sub_max # 求列表和 def sum(list): if list == []: return 0 return list[0] + sum(list[1:])快速排序
def quicksort(array): if len(array) < 2: return array # ←------基线条件：为空或只包含一个元素的数组是“有序”的 else: pivot = array[0] # ←------递归条件 less = [i for i in array[1:] if i <= pivot] # ←-----所有小于基准值的元素组成的子数组 greater = [i for i in array[1:] if i > pivot] # ←------所有大于基准值的元素组成的 return quicksort(less) + [pivot] + quicksort(greater) print(quicksort([10, 5, 2, 3]))广度优先搜索
from collections import deque def person_is_seller(name): return name[-1] == 'm' graph = {} graph["you"] = ["alice", "bob", "claire"] graph["bob"] = ["anuj", "peggy"] graph["alice"] = ["peggy"] graph["claire"] = ["thom", "jonny"] graph["anuj"] = [] graph["peggy"] = [] graph["thom"] = [] graph["jonny"] = [] def search(name): search_queue = deque() search_queue += graph[name] # This is how you keep track of which people you've searched before. searched = set() while search_queue: person = search_queue.popleft() # Only search this person if you haven't already searched them. if person not in searched: if person_is_seller(person): print(person + " is a mango seller!") return True else: search_queue += graph[person] # Marks this person as searched searched.add(person) return False search("you")Dijkstra 算法
# the graph graph = {} graph["start"] = {} graph["start"]["a"] = 6 graph["start"]["b"] = 2 graph["a"] = {} graph["a"]["fin"] = 1 graph["b"] = {} graph["b"]["a"] = 3 graph["b"]["fin"] = 5 graph["fin"] = {} # the costs table infinity = float("inf") costs = {} costs["a"] = 6 costs["b"] = 2 costs["fin"] = infinity # the parents table parents = {} parents["a"] = "start" parents["b"] = "start" parents["fin"] = None processed = [] def find_lowest_cost_node(costs): lowest_cost = float("inf") lowest_cost_node = None # Go through each node. for node in costs: cost = costs[node] # If it's the lowest cost so far and hasn't been processed yet... if cost < lowest_cost and node not in processed: # ... set it as the new lowest-cost node. lowest_cost = cost lowest_cost_node = node return lowest_cost_node # Find the lowest-cost node that you haven't processed yet. node = find_lowest_cost_node(costs) # If you've processed all the nodes, this while loop is done. while node is not None: cost = costs[node] # Go through all the neighbors of this node. neighbors = graph[node] for n in neighbors.keys(): new_cost = cost + neighbors[n] # If it's cheaper to get to this neighbor by going through this node... if costs[n] > new_cost: # ... update the cost for this node. costs[n] = new_cost # This node becomes the new parent for this neighbor. parents[n] = node # Mark the node as processed. processed.append(node) # Find the next node to process, and loop. node = find_lowest_cost_node(costs) print("Cost from the start to each node:") print(costs)贪心算法
# You pass an array in, and it gets converted to a set. states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) stations = {} stations["kone"] = set(["id", "nv", "ut"]) stations["ktwo"] = set(["wa", "id", "mt"]) stations["kthree"] = set(["or", "nv", "ca"]) stations["kfour"] = set(["nv", "ut"]) stations["kfive"] = set(["ca", "az"]) final_stations = set() while states_needed: best_station = None states_covered = set() for station, states_for_station in stations.items(): covered = states_needed & states_for_station if len(covered) > len(states_covered): best_station = station states_covered = covered states_needed -= states_covered final_stations.add(best_station) print(final_stations)
