- 前缀树
- 创建前缀树, 查询一个字符串作了多少次前缀,加入了多少次, 删除字符串
- 贪心算法
- 注意收集各种贪心策略
- 获利的最大数值,数据流的中位数, 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
- update(N8)
- 从根节点root沿路a走到新节点N2
-
前缀树
#[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 }