前缀树
- 创建前缀树, 查询一个字符串作了多少次前缀，加入了多少次, 删除字符串
贪心算法
- 注意收集各种贪心策略
- 获利的最大数值,数据流的中位数, N皇后问题

前缀树

对于字符串[“abc”, “bck”, “abd”, “ace”]把它们挂在一棵树上
- 从根节点root沿路a走到新节点N2
  - 有：直接走
  - 无：新建路a再走
  - 同时更新节点状态update(root)
    - root.pass++
    - root.end = 0
- 在节点N2沿路b走到新节点N5
  - 有：直接走
  - 无：新建路b再走到新节点
  - update(N2)
    - N2.pass ++
    - N2.end = 0
- 在N5沿路c走到新节点N8
  - 有：直接走
  - 无：新建路c再走
  - update(N5)
    - N5.pass++
    - N5.end = 0
- 在节点N8，”abc”已经完
  - update(N8)
    - N8.pass++
    - N8.end = 1

前缀树

#[derive(Debug)]
struct TrieNode {
    pass: u32,
    end: u32,
    nexts: HashMap<char, RefNode>,
}

impl TrieNode {
    fn new() -> Self {
        Self {
            pass: 0, end: 0,
            nexts: HashMap::new(),
        }
    }
}

#[derive(Debug)]
struct RefNode(Rc<RefCell<TrieNode>>);
impl RefNode {
    fn new() -> Self {
        Self(Rc::new(RefCell::new(TrieNode::new())))
    }

    fn insert(&self, s: &str) {
      let mut node: RefNode = RefNode(self.0.clone());
      node.0.borrow_mut().pass += 1;
      s.chars().for_each(|c| {
          let next = RefNode(
              node.0.borrow_mut()
                  .nexts.entry(c)
                  .or_insert(RefNode::new())
                  .0.clone(),
          );
          next.0.borrow_mut().pass += 1;
          node = next;
      });
      node.0.borrow_mut().end += 1;
      
  }
}

查询一个字符串加入了多少次
- 找到这个字符串的终点
- 返回对应的node.end

算法实现

fn search(&self, s: &str) -> u32 {
    if s == "" {
        return self.0.borrow().end;
    }

    let mut node: RefNode = RefNode(self.0.clone());
    for c in s.chars() {
        if node.0.borrow().nexts.get(&c).is_none() {
            return 0;
        }
        let next = node.0.borrow().nexts.get(&c).unwrap().0.clone();
        node = RefNode(next);
    }

    let x = node.0.borrow().end;
    x
}

查询一个字符串作了多少次前缀
- 返回node.pass

实现

fn prefix_num(&self, s: &str) -> u32 {
    if s == "" {
        return self.0.borrow().pass;
    }

    let mut node = RefNode(self.0.clone());
    for c in s.chars() {
        if node.0.borrow().nexts.get(&c).is_none() {
            return 0;
        }
        let next = node.0.borrow().nexts.get(&c).unwrap().0.clone();
        node = RefNode(next);
    }

    let x = node.0.borrow().pass;
    x
}

删除字符串
- 先判断是否存在这个字符串
- 然后沿路node.pass–
- 当node.pass==0时，删除节点及后面的节点
- 因为rust语言特性，删除节点其后链接的节点将自动删除

算法实现

  fn delete(&mut self, s: &str) {
    if self.search(s) == 0 {
        println!("未加入过字符串{}，直接退出", s);
        return;
    }

    let mut node: RefNode = RefNode(self.0.clone());
    node.0.borrow_mut().pass -= 1;
    for c in s.chars() {
        let next = node.0.borrow().nexts.get(&c).unwrap().0.clone();
        next.borrow_mut().pass -= 1;
        if next.borrow().pass == 0 {
            // 删除这个节点，其后面的节点会自动析构
            node.0.borrow_mut().nexts.remove(&c);
            return;
        }
        node = RefNode(next);
    }
    node.0.borrow_mut().end -= 1;
}

贪心算法

思想

在某种策略下，优先选择最符合该策略的样本而得到最终答案的方法
不从整体上考虑最优
得到的是在某种意义上的局部最优解

应用

会议安排

一些项目要占用会议室，给出每个项目使用的起终时间，安排会议日程，使会议室使用次数最多
可采用的贪心策略
- 开始时间最早
- 持续时间最短
- 结束时间最早
采用策略3【结束时间最早】

算法实现

fn best_arrange(programs: &mut Vec<Program>, timepoint: u32) -> u32 {
    programs.sort();
    let mut res = 0u32;
    let mut timepoint = timepoint;
    programs.iter().for_each(|p| {
        if timepoint <= p.start {
            res += 1;
            timepoint = p.end;
        }
    });
    res
}

信心算法的套路
- 实现不靠贪心策略的暴力全排列解法
- 排出想到的贪心策略
- 用暴力解法和对数器，验证每个贪心策略
注意收集各种贪心策略

贪心策略在实现时用到的技巧

根据某策略建立一个比较器来排序
根据某策略建立一个比较器来组成堆

切金条

一块金条切两半需要花费和长度一样的铜板，长为20的金条无论怎么切都需花费20，一群人想整分金条，怎么分花费最少？

给定数组[10, 20, 30]
- 表示3个人，整块金条长度为60
- 金条要分成3部分：10， 20， 30
- 分法1
  - 若先分成30/30，花费60
  - 再分成10/20，花费30
  - 共花90
- 分法2
  - 先分成10/50, 花60
  - 再分20/30，花50
  - 共花110
输入一个数组[2, 3, 4, 7, 9, 2]，得到最小代价
算法
- 把所有数放入最小堆[2,2, 3, 4, 7, 9]
- 取出2个数[2, 2]做组合4
- 把结合4放回最小堆[3, 4, 4, 7, 9]
- 取出2个数[3, 4]->7
- 放回最小堆[4, 7, 7, 9]
- 取出2个数[4, 7] -> 11
- 施加最小堆[7, 9, 11]
- 取出2个数[7, 9] -> 16
- 放回最小堆[11, 16]
- 取出2个数[11, 16] -> 27
- 最后所有组合的和就是最小代价

实现

fn less_money(arr: &Vec<i32>) -> i32 {
    let mut min_heap = BinaryHeap::new();
    arr.iter().for_each(|l| min_heap.push(*l));
    let mut sum = 0;
    while min_heap.len() > 1 {
        sum += (min_heap.pop().unwrap() + min_heap.pop().unwrap());
        min_heap.push(sum);
    }
    sum
}

获利的最大数值

输入正数数组costs，正数数组profits，正数k，正数m
- costs[i]：i号项目的花费
- profits[i]：i号项目的纯利
- k：串行的最多项目数
- m：初始资金
说明
- 每做完一个项目，可以马上获利资金，支持下一个项目
算法
- 把所有项目中花费最小的放到最小堆
- 把所有<=m的项目放到最大堆中
- 从最大堆中选出利润最大的项目
- 循环

数据流的中位数

准备最大堆和最小堆
第1个数入最大堆
新数
- <= 最大堆顶，入最大堆
- > 最大堆顶，入最小堆
当两个堆的size相差2时
- 多的弹出放到少的堆
使小的1/2数放在最大堆
大的1/2数放在最小堆
堆项就是中位数

算法实现

fn middle(nums: Vec<i32>) -> f32 {
    let mut min_heap = BinaryHeap::new();
    let mut max_heap = BinaryHeap::new();
    max_heap.push(nums[0]);

    nums[1..].iter().for_each(|num| {
        if num <= max_heap.peek().unwrap() {
            max_heap.push(*num);
        } else {
            min_heap.push(Reverse(*num));
        }
        if max_heap.len() + 2 == min_heap.len() {
            let Reverse(num) = min_heap.pop().unwrap();
            max_heap.push(num);
        } else if min_heap.len() + 2 == max_heap.len() {
            min_heap.push(Reverse(max_heap.pop().unwrap()))
        }
    });
    if nums.len() % 2 == 0 {
        return *max_heap.peek().unwrap() as f32;
    } else {
        let m1 = *max_heap.peek().unwrap();
        let Reverse(m2) = min_heap.peek().unwrap();
        return (m1 as f32 + *m2 as f32) / 2.0;
    }
}

N皇后问题

在NxN的棋盘上，摆N个皇后，不同行、列和对角
给定N后返回N个皇后有多少种摆法

算法实现

fn queen_is_valid(record: &mut Vec<usize>, line: usize, row:usize) -> bool {
  for line_fixed in 0..line {
      if record[line_fixed] == row 
        || (record[line_fixed] as i32 - row as i32).abs() 
          == (line_fixed as i32- line as i32).abs() {
          return false;
      }
  }
  true
}

// 有多少种摆法
fn queen_pos(line: usize, record: &mut Vec<usize>, n: usize) -> u32 {
    if line == n {
        return 1;
    }
    let mut res: u32 = 0;
    for row in 0..n {
        if queen_is_valid(record, line, row) {
            record[line] = row;
            res += queen_pos(line+1, record, n);
        }
    }
    res
}

fn nqueens(num: usize) -> u32 {
    let mut record: Vec<usize> = vec![0;num];
    let res = queen_pos(0, &mut record, num);
    res
}

上篇Rust·算法·图

下篇Rust·算法基础·暴力递归