datetime:2024/1/21 14:18
author:nzb
前缀树和贪心算法
前缀树
前缀树（Trie），也称为字典树或单词查找树，是一种树形数据结构，通常用于存储动态集合或关联数组，其中键通常是字符串。它的主要优势在于高效地支持字符串的插入、删除和查找操作，尤其适用于需要快速搜索和匹配前缀的场景。
例子:
一个字符串类型的数组arr1，另一个字符串类型的数组arr2。
- arr2中有哪些字符，是arr1中出现的？请打印。
- arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印。
- arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印arr2中出现次数最大的前缀。
"""
["abc", "ab", "bc", "bck"]
O代表节点，字符在路上
p代表走过的个数，pass
e代表结束，end
O p=4,e=0
/ \
/ \
a b
/ \
/ \
O p=2,e=0 O p=2,e=0
/ |
b |
/ c
O p=2,e=1 |
| |
| O p=2,e=1
c |
| |
| k
O p=1,e=1 |
|
O p=1,e=1
1、问有没有加入过 "bc" 字符串：从头结点开始查，结尾看节点的end，还能看出加过几次
2、加入过的字符串有多少以"ab"作为前缀的：遍历"ab"，从头结点开始，看pass值
"""
class TrieNode:
def __init__(self):
self.pass_num: int = 0
self.end_num: int = 0
self.children: dict = {} # 代表路
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str):
if not word:
return
node = self.root
node.pass_num += 1
for char in word:
# 不存在路，新建
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.pass_num += 1 # 路加1
node.end_num += 1
def delete(self, word: str):
if self.search(word):
node = self.root
node.pass_num -= 1
for char in word:
parent = node
node = node.children[char]
node.pass_num -= 1
if node.pass_num == 0: # 如果pass都为0了，说明后续没了，删掉后面的路
parent.children.pop(char)
return
node.end_num -= 1
def search(self, word: str):
if not word:
return False
node = self.root
for char in word:
if char not in node.children:
# return False, 0
return False
node = node.children[char]
# return True, node.end_num # 多少次
return True if node.end_num != 0 else False
def starts_with_prefix(self, prefix: str):
if not prefix:
return False
node = self.root
for char in prefix:
if char not in node.children:
# return False, 0
return False
node = node.children[char]
# return True, node.pass_num # 多少次
return True
ins = Trie()
for item in ["abc", "ab", "ab", "bc", "bck", "bc"]:
# 增
ins.insert(item)
# # 查
# print(ins.search("bc"))
# print(ins.search("bk"))
# # 查前缀
# print(ins.starts_with_prefix("bc"))
# print(ins.starts_with_prefix("ab"))
# print(ins.starts_with_prefix("bk"))
# 删除
print(ins.search("ab"))
print(ins.search("abc"))
print(ins.starts_with_prefix("ab"), end="\n\n")
ins.delete("ab")
print(ins.search("ab"))
print(ins.search("abc"))
print(ins.starts_with_prefix("ab"), end="\n\n")
ins.delete("ab")
print(ins.search("ab"))
print(ins.search("abc"))
print(ins.starts_with_prefix("ab"))
贪心算法
贪心策略代码一般都很短
在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫作贪心算法。 也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
- 局部最优 -?-> 整体最优
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（局部最优）的选择，从而希望能够导致全局最好或最优（全局最优）的结果。 贪心算法不回溯，一旦做出了某个决策，就不再改变。这种策略通常适用于一些最优化问题，例如最小生成树、最短路径、任务调度等。
- 贪心算法的一般步骤：
- 问题建模： 将问题抽象成一组子问题。
- 确定选择策略： 对于每个子问题，确定一个局部最优解的选择策略。
- 迭代求解： 通过迭代地做出局部最优选择，最终得到全局最优解或近似最优解。
- 贪心算法的特点：
- 局部最优性： 贪心算法每一步选择都是当前状态下的局部最优解。
- 不回溯： 一旦做出决策，就不再改变。
- 不保证全局最优： 贪心算法不保证总是能够得到全局最优解，但在一些问题中能够产生接近最优解的结果。
应用场景：
- 最小生成树问题：
Kruskal算法、Prim算法。 - 最短路径问题：
Dijkstra算法。 - 任务调度问题： 按照某个标准选择任务执行的顺序，例如最早截止时间优先（Earliest Deadline First，EDF），例如：会议室使用。
- 会议室是问题：比如会议室空闲时间：早上6.00到下午6.00
- 按最早时间开始排，如果有个会议室早上6.00到下午5.00的，就只能安排一个会议，此方案不行
- 按会议最短时间开始排，会议1(6.00-12.00)，会议2(11.00-2.00)，会议3(1.00-6.00)，只能安排会议2，此方案不行
- 只能按最早截止时间优先
- 会议室是问题：比如会议室空闲时间：早上6.00到下午6.00
- 最小生成树问题：
贪心算法的在笔试时的解题套路
- 1，实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
- 2，脑补出贪心策略A、贪心策略B、贪心策略C...
- 3，用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
- 4，不要去纠结贪心策略的证明
从头到尾展示最正统的贪心策略求解过程
- 例子：给定一个字符串类型的数组strs，找到一种拼接方式，使得把所有字符串拼起来之后形成的字符串具有最小的字典序。
- 证明贪心策略可能是件非常腌心的事情。平时当然推荐你搞清楚所有的来龙去脉，但是笔试时用对数器的方式！ - 看左神视频1:18:43
贪心策略在实现时，经常使用到的技巧：
- 1，根据某标准建立一个比较器来排序
- 2，根据某标准建立一个比较器来组成堆
会议室问题
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)， 你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回这个最多的宣讲场次。
from collections import namedtuple
import typing
program = namedtuple("Program", ["name", "start", "end"]) # 项目或会议
def best_arrange(data: typing.List[program], time_point: int):
data = sorted(data, key=lambda x: x.end)
cnt = 0
for item in data:
if time_point <= item.start:
cnt += 1
time_point = item.end
print(item.name)
return cnt
pros = [program(start=6, end=9, name="会议1"), program(start=6, end=10, name="会议2"), program(start=7, end=8, name="会议3"),
program(start=9, end=11, name="会议4"), program(start=9, end=12, name="会议5"),
program(start=12, end=15, name="会议6"), program(start=14, end=17, name="会议7"),
program(start=15, end=18, name="会议8")]
print(best_arrange(pros, 6))
# 会议3
# 会议4
# 会议6
# 会议8
金条切分
- 一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。
- 一群人想整分整块金条，怎么分最省铜板?
- 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60。金条要分成10,20,30三个部分。 如果先把长度60的金条分成10和50，花费60； 再把长度50的金条分成20和30，花费50；一共花费110铜板。但是如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20，花费30；一共花费90铜板。
- 输入一个数组，返回分割的最小代价。
import typing
import heapq
def less_money(data: typing.List[int]):
hq = []
for it in data:
heapq.heappush(hq, it)
sum_total = 0
while len(hq) > 1:
tmp = heapq.heappop(hq) + heapq.heappop(hq)
sum_total += tmp
heapq.heappush(hq, tmp)
return sum_total
print(less_money([10, 20, 30]))
获得的最大钱数
- 输入：
- 正数数组costs
- 正数数组profits
- 正数k
- 正数m
- 含义：
- costs[i]表示i号项目的花费
- profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
- k表示你只能串行的最多做k个项目
- m表示你初始的资金
- 说明：
- 你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。输出：
- 你最后获得的最大钱数。
- 解题思路
- 先把项目按照花费加入小根堆
- 然后根据启动资金，解锁项目，解锁出来的按照利润加入到大根堆
- 消费大根堆
import heapq
import heapq_max # pip install heapq_max
def find_max_profit(costs: list, profits: list, k: int, m: int):
"""
:param costs: 花费
:param profits: 利润
:param k: 你只能串行的最多做k个项目
:param m: 表示你初始的资金
:return:
"""
min_hq = []
for it in zip(costs, profits):
heapq.heappush(min_hq, it)
max_hq = []
for i in range(k):
while min_hq and min_hq[0][0] <= m: # 只要满足成本就解锁
# cost = list(heapq.heappop(min_hq))
# cost[0], cost[1] = cost[1], cost[0]
# heapq_max.heappush_max(max_hq, tuple(costs))
profit = heapq.heappop(min_hq)[1] # 利润，加入大根堆排序
heapq_max.heappush_max(max_hq, profit)
if not max_hq: # 没项目可做
return m
m += heapq.heappop(max_hq) # 消费大根堆
return m
costs_data = [1, 1, 2, 2, 3, 4]
profits_data = [1, 4, 3, 7, 2, 10]
print(find_max_profit(costs_data, profits_data, 2, 2))
n皇后问题
def n_queens(n: int):
if n < 1:
return 0
records = [-1] * n # records[i] -> 表示第i行的皇后，放在第几列
return process(0, records, n)
def process(i: int, records: list, n: int):
"""
:param i:目前第i行
:param records:
潜台词：只要进入该函数，records[0...i-1] 上的皇后，任意两个皇后都不共行，不共列，不共斜线
:param n:一共多少行， n * n
:return:
"""
# base case
if i == n: # 终止行，如果到这说明有符合的一种摆放
# print(records)
return 1
cnt = 0
for j in range(n): # 遍历尝试每一列
if is_valid(records, i, j):
records[i] = j
cnt += process(i + 1, records, n)
return cnt
def is_valid(records: list, i: int, j: int):
"""
是否不共行，不共列，不共斜线
:param records:
:param i: 第i行
:param j: 第j列
:return:
"""
# 肯定不共行
# records[0...i-1]需要看，[i...]不需要，因为当前在i行
for row in range(i): # 之前某个x行皇后
if records[row] == j or abs(i - row) == abs(j - records[row]):
return False
return True
print(n_queens(4)) # 2
- 最优解就是上面这个，时间复杂度
O(N^N)，每行N种选择，一共N行 - 但是可以做常数时间优化，但是指标没法优化，利用位运算加速，非常优雅
import time
# 位运算求解
def n_queens2(n: int):
if n < 1:
return 0
limit = int('0b' + '1' * n, 2) # 比如： 5 -> 0b11111
return process2(limit, 0, 0, 0) # limit 可以限制在哪些位可以放皇后，limit永远不变
def process2(limit: int, col_limit: int, left_limit: int, right_limit: int):
"""
例如：
11111
第二位放： 00100
列限制： 00100
左限制： 01000（左移）
右限制： 00010（右移）
求或： 01110
:param limit: 限制
:param col_limit: 列限制
:param left_limit: 左限制
:param right_limit: 右限制
:return:
"""
# base case
if col_limit == limit: # 每次都在在某一列放一个皇后，如果放到跟limit一样，说明存在一种放法
return 1
cnt = 0
can_put_bit = limit & ~(col_limit | left_limit | right_limit) # 求哪些位可以放
while can_put_bit != 0:
most_right_one = can_put_bit & (~can_put_bit + 1)
can_put_bit -= most_right_one # 等于 can_put_bit & (can_put_bit - 1)
cnt += process2(limit,
col_limit | most_right_one,
(left_limit | most_right_one) << 1,
(right_limit | most_right_one) >> 1)
return cnt
for i in range(10, 15):
start = time.time()
n_queens(i)
print(f"n = {i}, n_queens cost {int((time.time() - start) * 1e3)}ms")
start = time.time()
n_queens2(i)
print(f"n = {i}, n_queens2 cost {int((time.time() - start) * 1e3)}ms")
print("\n")
# n = 10, n_queens cost 574ms
# n = 10, n_queens2 cost 39ms
#
# n = 11, n_queens cost 2525ms
# n = 11, n_queens2 cost 133ms
#
# n = 12, n_queens cost 13443ms
# n = 12, n_queens2 cost 736ms
#
# n = 13, n_queens cost 90491ms
# n = 13, n_queens2 cost 3976ms