前缀树和贪心算法

前缀树

前缀树（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，此方案不行
    - 只能按最早截止时间优先
贪心算法的在笔试时的解题套路
- 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

前缀树和贪心算法

datetime:2024/1/21 14:18

author:nzb

前缀树和贪心算法

前缀树

例子:

贪心算法

会议室问题

金条切分

获得的最大钱数

n皇后问题

results matching ""

No results matching ""