回溯算法实现（DFS）

回溯算法其实就是我们常说的 DFS 算法，本质上就是一种暴力穷举算法

递归遍历二叉树

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

def back_track(nums, track, res):
    # 结束条件
    if len(nums)== len(track):
        # res.extend(track) # 正常
        res.append(track)# 不正常
        return None
    # 遍历选择列表
    for num in nums:
        if num in track:
            continue
        track.append(num)
				back_track(nums, track.copy(), res)
				track.pop()
return None

if __name__ == '__main__':
    nums =[1, 2, 3]
		track =[]
		res =[]
		back_track(nums, track, res)
		print(res)
  • 某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。而今天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。

LRU（Least recently used）算法实现

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

算法步骤

  1. 新数据插入到链表头部
  2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部
  3. 当链表满的时候，将链表尾部的数据丢弃。
 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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 1. 新数据插入到链表头部
# 2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部
# 3. 当链表满的时候，将链表尾部的数据丢弃

from collections import deque

class Lru(object):
    def __init__(self, queen_length: int):
        self.queen_length = queen_length
        self.queen = deque(maxlen=self.queen_length)

    def get_or_put(self, element):
        # assert len(self.queen) == 0, "Queen is Empty."

        try:
            # 命中元素
            index = self.queen.index(element)
            return self.queen[index]
        except ValueError:
            self.queen = self._put(element)
            return self.get_or_put(element)

    def _put(self, element):
        # deque 自带了增加淘汰策略，暂不用考虑队满和队空的情况
        self.queen.appendleft(element)
        return self.queen

if __name__ == '__main__':
    lru = Lru(3)
    res = lru.get_or_put(3)
    print(res)
    print(lru.queen)