Rust·算法基础·前缀树·贪心算法

 

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

  • 前缀树
    • 创建前缀树, 查询一个字符串作了多少次前缀,加入了多少次, 删除字符串
  • 贪心算法
    • 注意收集各种贪心策略
    • 获利的最大数值,数据流的中位数, 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
    }