devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

rust OJ实战

作者：羊村懒王 | 2024-02-25 01:22:20

赞

踩

rust OJ实战

目录

力扣 172. 阶乘后的零（递归）

力扣 793. 阶乘函数后 K 个零（递归、二分）

力扣 704. 二分查找（二分）

力扣 275. H 指数 II（二分）

力扣 2300. 咒语和药水的成功对数（二分）

力扣 414. 第三大的数（排序）

力扣 628. 三个数的最大乘积（排序）

力扣 2073. 买票需要的时间（数组）

力扣 1700. 无法吃午餐的学生数量（数组）

力扣 2824. 统计和小于目标的下标对数目（数组）

力扣 581. 最短无序连续子数组（栈）

力扣 1046. 最后一块石头的重量（堆）

力扣 2406. 将区间分为最少组数（堆）

力扣 LCP 23. 魔术排列（双端队列）

力扣 203. 移除链表元素（链表）

力扣 面试题 02.02. 返回倒数第 k 个节点（链表）

力扣 617. 合并二叉树（二叉树DFS）

力扣 面试题 04.02. 最小高度树（二叉树DFS）

力扣 654. 最大二叉树（二叉树DFS）

力扣 2458. 移除子树后的二叉树高度（二叉树DFS）

力扣 297. 二叉树的序列化与反序列化（BFS+字符串）

力扣 2586. 统计范围内的元音字符串数（字符串）

力扣 面试题 01.04. 回文排列（字符串+哈希表）

力扣 697. 数组的度（哈希表）

力扣 350. 两个数组的交集 II（哈希表）

力扣 532. 数组中的 k-diff 数对（哈希表）

力扣 2561. 重排水果（哈希表）

力扣 349. 两个数组的交集（集合）

力扣 2336. 无限集中的最小数字（集合）

力扣 2718. 查询后矩阵的和（集合）

力扣 1823. 找出游戏的获胜者（约瑟夫问题）

力扣 面试题 08.06. 汉诺塔问题（汉诺塔问题）

力扣 2526. 找到数据流中的连续整数（数据流）

力扣 313. 超级丑数（数列DP）

力扣 2609. 最长平衡子字符串（数列DP）

力扣 1039. 多边形三角剖分的最低得分（区间DP）

力扣 321. 拼接最大数（贪心）

力扣 179. 最大数（贪心）

力扣 984. 不含 AAA 或 BBB 的字符串（贪心）

力扣 223. 矩形面积（计算几何）

力扣 684. 冗余连接（并查集）

力扣 685. 冗余连接 II（并查集）

力扣 785. 判断二分图（带权并查集）

力扣 面试题 04.01. 节点间通路（有向图BFS）

力扣 LCP 62. 交通枢纽（有向图）

力扣 LCR 115. 序列重建（拓扑排序）

力扣 172. 阶乘后的零（递归）

阶乘

力扣 793. 阶乘函数后 K 个零（递归、二分）

阶乘

力扣 704. 二分查找（二分）

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。


示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。
  1. impl Solution {
  2.     pub fn search(nums: Vec<i32>, target: i32) -> i32 {
  3.         let res = nums.binary_search(&target);
  4.         match res{
  5.             Ok(x)=>x as i32,
  6.             _=>-1
  7.         }
  8.     }
  9. }

力扣 275. H 指数 II（二分）

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。

请你设计并实现对数时间复杂度的算法解决此问题。

示例 1：

输入：citations = [0,1,3,5,6]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
     由于研究者有3篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3 。

示例 2：

输入：citations = [1,2,100]
输出：2

提示：

  • n == citations.length
  • 1 <= n <= 105
  • 0 <= citations[i] <= 1000
  • citations 按 升序排列
  1. struct SearchData{
  2.     nums:Vec<i32>,
  3. }
  4. impl SearchData{
  5.     fn find(&self, low:usize,high:usize)-> usize{
  6.         let mut low = low;
  7.         let mut high = high;
  8.         if self.check_value(high) == false{
  9.             return high+1;
  10.         }
  11.         if self.check_value(low) == true{
  12.             return low;
  13.         }
  14.         while high - low > 1 {
  15.             let mid = (high + low)/2;
  16.             if self.check_value(mid) == true{
  17.                 high = mid;
  18.             }
  19.             else {
  20.                 low = mid;
  21.             }
  22.         }
  23.         return high;
  24.     }
  25.     fn check_value(&self,x:usize)->bool{
  26.         let y:i32=( self.nums.len()-x)as i32;
  27.         return self.nums[x] >= y;
  28.     }
  29. }
  30. impl Solution {
  31.     pub fn h_index(citations: Vec<i32>) -> i32 {
  32.         let len = citations.len();
  33.         let low:usize =0;
  34.         let high = citations.len() -1;
  35.         let opt=SearchData{nums:citations};
  36.         let ans = (len-opt.find(low,high))as i32;
  37.         return ans;
  38.     }
  39. }

力扣 2300. 咒语和药水的成功对数（二分）

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。

示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。

提示：

  • n == spells.length
  • m == potions.length
  • 1 <= n, m <= 105
  • 1 <= spells[i], potions[i] <= 105
  • 1 <= success <= 1010
  1. struct SearchData{
  2.     nums:Vec<i32>,
  3.     target:i64,
  4. }
  5. impl SearchData{
  6.     fn find(&self, low:usize,high:usize)-> usize{
  7.         let mut low = low;
  8.         let mut high = high;
  9.         if self.check_value(high) == false{
  10.             return high+1;
  11.         }
  12.         if self.check_value(low) == true{
  13.             return low;
  14.         }
  15.         while high - low > 1 {
  16.             let mid = (high + low)/2;
  17.             if self.check_value(mid) == true{
  18.                 high = mid;
  19.             }
  20.             else {
  21.                 low = mid;
  22.             }
  23.         }
  24.         return high;
  25.     }
  26.     fn check_value(&self,x:usize)->bool{
  27.         return self.nums[x] as i64 >= self.target;
  28.     }
  29. }
  30. impl Solution {
  31.     pub fn successful_pairs(spells: Vec<i32>, potions: Vec<i32>, success: i64) -> Vec<i32> {
  32.         let mut potions=potions;
  33.         potions.sort();
  34.         let len = potions.len() as i32;
  35.         let mut opt =SearchData{nums:potions,target:0};
  36.         let mut v=Vec::new();
  37.         for x in spells{
  38.             opt.target = (success + x as i64 -1) / x as i64;
  39.             v.push(len - opt.find(0, len as usize-1)as i32);
  40.         }
  41.         return v;
  42.     }
  43. }

力扣 414. 第三大的数（排序）

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。

示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。

示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

提示：

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？

  1. impl Solution {
  2.     pub fn third_max(nums: Vec<i32>) -> i32 {
  3.         let mut nums=nums;
  4.         nums.sort();
  5.         let mut num=0;
  6.         for i in 0..nums.len(){
  7.             let id = nums.len()-1-i;
  8.             if id==nums.len()-1 || nums[id]!=nums[id+1]{
  9.                 num+=1;
  10.             }
  11.             if(num==3){
  12.                 return nums[id];
  13.             }
  14.         }
  15.         return nums[nums.len()-1];
  16.     }
  17. }

力扣 628. 三个数的最大乘积（排序）

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

输入：nums = [1,2,3]
输出：6

示例 2：

输入：nums = [1,2,3,4]
输出：24

示例 3：

输入：nums = [-1,-2,-3]
输出：-6

提示：

  • 3 <= nums.length <= 104
  • -1000 <= nums[i] <= 1000
  1. impl Solution {
  2.     pub fn maximum_product(nums: Vec<i32>) -> i32 {
  3.         let mut nums=nums;
  4.         nums.sort();
  5.         let mut a = nums[0]*nums[1]*nums[nums.len()-1];
  6.         let b = nums[nums.len()-3]*nums[nums.len()-2]*nums[nums.len()-1];
  7.         if a<b {
  8.             a=b;
  9.         }
  10.         return a;
  11.     }
  12. }

力扣 2073. 买票需要的时间（数组）

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。

给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。

每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到  队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。

返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。

示例 1：

输入：tickets = [2,3,2], k = 2
输出：6
解释： 
- 第一轮，队伍中的每个人都买到一张票，队伍变为 [1, 2, 1] 。
- 第二轮，队伍中的每个都又都买到一张票，队伍变为 [0, 1, 0] 。
位置 2 的人成功买到 2 张票，用掉 3 + 3 = 6 秒。

示例 2：

输入：tickets = [5,1,1,1], k = 0
输出：8
解释：
- 第一轮，队伍中的每个人都买到一张票，队伍变为 [4, 0, 0, 0] 。
- 接下来的 4 轮，只有位置 0 的人在买票。
位置 0 的人成功买到 5 张票，用掉 4 + 1 + 1 + 1 + 1 = 8 秒。

提示：

  • n == tickets.length
  • 1 <= n <= 100
  • 1 <= tickets[i] <= 100
  • 0 <= k < n
  1. impl Solution {
  2.     pub fn time_required_to_buy(tickets: Vec<i32>, k: i32) -> i32 {
  3.         let mut ans=0;
  4.         let k=k as usize;
  5.         for i in 0..tickets.len(){
  6.             if(i<=k){
  7.                 ans+=std::cmp::min(tickets[i],tickets[k]);
  8.             }else{
  9.                 ans+=std::cmp::min(tickets[i],tickets[k]-1);
  10.             }
  11.         }
  12.         return ans;
  13.     }
  14. }

力扣 1700. 无法吃午餐的学生数量（数组）

学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：

  • 如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
  • 否则，这名学生会 放弃这个三明治 并回到队列的尾部。

这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i​​​​​​ 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j​​​​​​ 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。

示例 1：

输入：students = [1,1,0,0], sandwiches = [0,1,0,1]
输出：0 
解释：
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,0,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,0,1,1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [0,1,1]，三明治栈为 sandwiches = [1,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,1,0]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1,0]，三明治栈为 sandwiches = [0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1]，三明治栈为 sandwiches = [1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = []，三明治栈为 sandwiches = []。
所以所有学生都有三明治吃。

示例 2：

输入：students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
输出：3

提示：

  • 1 <= students.length, sandwiches.length <= 100
  • students.length == sandwiches.length
  • sandwiches[i] 要么是 0 ，要么是 1 。
  • students[i] 要么是 0 ，要么是 1 。

思路：

因为学生是可以疯狂旋转的，所以只需要计数就行了。

如果问题是求哪些学生最后没饭吃，那就需要用队列去模拟了。

  1. impl Solution {
  2.     pub fn count_students(students: Vec<i32>, sandwiches: Vec<i32>) -> i32 {
  3.         let mut s1 = 0;
  4.         let mut s0 = 0;
  5.         for i in 0..students.len(){
  6.             if students[i]==0{
  7.                 s0+=1;
  8.             }else{
  9.                 s1+=1;
  10.             }
  11.         }
  12.         let mut ans = students.len() as i32;
  13.         for i in 0..sandwiches.len(){
  14.             if sandwiches[i]==0{
  15.                 if s0==0{
  16.                     return ans;
  17.                 }
  18.                 s0-=1;
  19.             }else{
  20.                 if s1==0{
  21.                     return ans;
  22.                 }
  23.                 s1-=1;
  24.                 
  25.             }
  26.             ans-=1;
  27.         }
  28.         return ans;
  29.     }
  30. }

力扣 2824. 统计和小于目标的下标对数目（数组）

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。

示例 1：

输入：nums = [-1,1,2,3,1], target = 2
输出：3
解释：总共有 3 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target
- (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target 
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target
注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target 。

示例 2：

输入：nums = [-6,2,5,-2,-7,-1,3], target = -2
输出：10
解释：总共有 10 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = -4 < target
- (0, 3) ，0 < 3 且 nums[0] + nums[3] = -8 < target
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = -13 < target
- (0, 5) ，0 < 5 且 nums[0] + nums[5] = -7 < target
- (0, 6) ，0 < 6 且 nums[0] + nums[6] = -3 < target
- (1, 4) ，1 < 4 且 nums[1] + nums[4] = -5 < target
- (3, 4) ，3 < 4 且 nums[3] + nums[4] = -9 < target
- (3, 5) ，3 < 5 且 nums[3] + nums[5] = -3 < target
- (4, 5) ，4 < 5 且 nums[4] + nums[5] = -8 < target
- (4, 6) ，4 < 6 且 nums[4] + nums[6] = -4 < target

提示：

  • 1 <= nums.length == n <= 50
  • -50 <= nums[i], target <= 50
  1. impl Solution {
  2.     pub fn count_pairs(nums: Vec<i32>, target: i32) -> i32 {
  3.         let mut ans = 0;
  4.         for i in 0..nums.len() {
  5.             for j in i+1..nums.len() {
  6.                 if nums[i] + nums[j] < target {
  7.                     ans+=1;
  8.                 }
  9.             }
  10.         }
  11.         return ans;
  12.     }
  13. }

力扣 581. 最短无序连续子数组（栈）

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]
输出：0

示例 3：

输入：nums = [1]
输出：0

提示：

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

  1. impl Solution {
  2.     pub fn find_unsorted_subarray(nums: Vec<i32>) -> i32 {
  3.         let mut id:usize=1;
  4.         let mut s:Vec<i32>=Vec::new();
  5.         s.push(nums[0]);
  6.         let mut flag=true;
  7.         while id<nums.len(){
  8.             while !s.is_empty() && s.last()>Some(&nums[id]){
  9.                 s.pop();
  10.                 flag = false;
  11.             }
  12.             if flag {
  13.                 s.push(nums[id]);
  14.             }
  15.             id=id+1;
  16.         }
  17.         let mut ans=s.len() as i32;
  18.         let mut id:usize=nums.len()-1;
  19.         let mut s:Vec<i32>=Vec::new();
  20.         s.push(nums[id]);
  21.         let mut flag=true;
  22.         while id>0{
  23.             id=id-1;
  24.             while !s.is_empty() && s.last()<Some(&nums[id]){
  25.                 s.pop();
  26.                 flag = false;
  27.             }
  28.             if flag {
  29.                 s.push(nums[id]);
  30.             }
  31.         }
  32.         ans=(nums.len() -s.len()) as i32 - ans;
  33.         if ans < 0 {
  34.             ans =0;
  35.         }
  36.         return ans;
  37.     }
  38. }

力扣 1046. 最后一块石头的重量（堆）

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

提示：

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000
  1. use std::collections::BinaryHeap;
  2. impl Solution {
  3.     pub fn last_stone_weight(stones: Vec<i32>) -> i32 {
  4.         let mut heap = BinaryHeap::from(stones);
  5.         while heap.len() > 1 {
  6.             let mut x = heap.pop().unwrap();
  7.             let mut y = heap.pop().unwrap();
  8.             if x>y{
  9.                 heap.push(x-y);
  10.             }else if x<y{
  11.                 heap.push(y-x);
  12.             }
  13.         }
  14.         if heap.is_empty() {
  15.             return 0;
  16.         }
  17.         return *heap.peek().unwrap();
  18.     }
  19. }

力扣 2406. 将区间分为最少组数（堆）

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。

你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。

请你返回 最少 需要划分成多少个组。

如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。

示例 1：

输入：intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
输出：3
解释：我们可以将区间划分为如下的区间组：
- 第 1 组：[1, 5] ，[6, 8] 。
- 第 2 组：[2, 3] ，[5, 10] 。
- 第 3 组：[1, 10] 。
可以证明无法将区间划分为少于 3 个组。

示例 2：

输入：intervals = [[1,3],[5,6],[8,10],[11,13]]
输出：1
解释：所有区间互不相交，所以我们可以把它们全部放在一个组内。

提示：

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • 1 <= lefti <= righti <= 106
  1. use std::collections::BinaryHeap;
  2. use std::cmp::Reverse;
  3. impl Solution {
  4.     pub fn min_groups(intervals: Vec<Vec<i32>>) -> i32 {
  5.         let mut ans = 0;
  6.         let mut v = intervals;
  7.         v.sort();
  8.         let mut heap=BinaryHeap::new();
  9.         for vi in v{
  10.             if !heap.is_empty(){
  11.                 if *heap.peek().unwrap() > Reverse(vi[0]){
  12.                     heap.pop();
  13.                     heap.push(Reverse(vi[1]));
  14.                     continue;
  15.                 }
  16.             }
  17.             heap.push(Reverse(vi[1]));
  18.             ans+=1;
  19.         }
  20.         return ans;
  21.     }
  22. }

力扣 LCP 23. 魔术排列（双端队列）

秋日市集上，魔术师邀请小扣与他互动。魔术师的道具为分别写有数字 1~N 的 N 张卡牌，然后请小扣思考一个 N 张卡牌的排列 target。

魔术师的目标是找到一个数字 k（k >= 1），使得初始排列顺序为 1~N 的卡牌经过特殊的洗牌方式最终变成小扣所想的排列 target，特殊的洗牌方式为：

  • 第一步，魔术师将当前位于 偶数位置 的卡牌（下标自 1 开始），保持 当前排列顺序 放在位于 奇数位置 的卡牌之前。例如：将当前排列 [1,2,3,4,5] 位于偶数位置的 [2,4] 置于奇数位置的 [1,3,5] 前，排列变为 [2,4,1,3,5]；
  • 第二步，若当前卡牌数量小于等于 k，则魔术师按排列顺序取走全部卡牌；若当前卡牌数量大于 k，则取走前 k 张卡牌，剩余卡牌继续重复这两个步骤，直至所有卡牌全部被取走；

卡牌按照魔术师取走顺序构成的新排列为「魔术取数排列」，请返回是否存在这个数字 k 使得「魔术取数排列」恰好就是 target，从而让小扣感到大吃一惊。

示例 1：

输入：target = [2,4,3,1,5]

输出：true

解释：排列 target 长度为 5，初始排列为：1,2,3,4,5。我们选择 k = 2： 第一次：将当前排列 [1,2,3,4,5] 位于偶数位置的 [2,4] 置于奇数位置的 [1,3,5] 前，排列变为 [2,4,1,3,5]。取走前 2 张卡牌 2,4，剩余 [1,3,5]； 第二次：将当前排列 [1,3,5] 位于偶数位置的 [3] 置于奇数位置的 [1,5] 前，排列变为 [3,1,5]。取走前 2 张 3,1，剩余 [5]； 第三次：当前排列为 [5]，全部取出。 最后，数字按照取出顺序构成的「魔术取数排列」2,4,3,1,5 恰好为 target。

示例 2：

输入：target = [5,4,3,2,1]

输出：false

解释：无法找到一个数字 k 可以使「魔术取数排列」恰好为 target。

提示：

  • 1 <= target.length = N <= 5000
  • 题目保证 target 是 1~N 的一个排列。

思路：

如果k=N-1，不妨设k=N。

于是，要么k不存在，要么k有唯一值，且在第一次交叉洗牌之后就直接确定了k值了。

有了k值之后，后面就只需要用双端队列进行模拟，全部验证一遍即可。

  1.  
  2. use std::collections::VecDeque;
  3. impl Solution {
  4.     pub fn is_magic(target: Vec<i32>) -> bool {
  5.         if target.len() == 1{
  6.             return true;
  7.         }
  8.         let k = Solution::get_magic_k(&target);
  9.         if k < 1 {
  10.             return false;
  11.         }
  12.         let mut q:VecDeque<i32>=VecDeque::new();
  13.         for i in 0..target.len(){
  14.             q.push_back(i as i32 +1);
  15.         }
  16.         let mut id:usize = 0;
  17.         loop{
  18.             let mut q2:VecDeque<i32>=VecDeque::new();
  19.             let mut i:usize = 1;
  20.             while i<q.len(){
  21.                 if let Some(x) = q.get(i){
  22.                     q2.push_back(*x);
  23.                 }
  24.                 i=i+2;
  25.             }
  26.             i=0;
  27.             while i<q.len(){
  28.                 if let Some(x) = q.get(i){
  29.                     q2.push_back(*x);
  30.                 }
  31.                 i=i+2;
  32.             }
  33.             for i in 0..k{
  34.                 if let Some(x) = q2.pop_front(){
  35.                     if x != target[id]{
  36.                         return false;
  37.                     }
  38.                     id+=1;
  39.                 }
  40.                 if q2.is_empty(){
  41.                     return true;
  42.                 }
  43.             }
  44.             q=q2;
  45.         }
  46.         return true;
  47.     }
  48.     pub fn get_magic_k(target: &Vec<i32>) -> usize{
  49.         let mid = target.len()/2;
  50.         for i in 0..target.len(){
  51.             let mut x = i*2+2;
  52.             if i>= mid{
  53.                 x=(i-mid)*2+1;
  54.             }
  55.             if target[i] != x as i32 {
  56.                 return i;
  57.             }
  58.         }
  59.         return target.len();
  60.     }
  61. }

力扣 203. 移除链表元素（链表）

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

  • 列表中的节点数目在范围 [0, 104] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

不用模板：

  1. impl Solution {
  2.     pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
  3.         if head.is_none(){
  4.             return head;
  5.         }
  6.         let mut ans = Box::new(ListNode::new(0));
  7.         let mut p = & mut head.unwrap();        
  8.         let mut pans = & mut ans;
  9.         loop {
  10.             let x = p.val;
  11.             if x != val{
  12.                 pans.next = Some(Box::new(ListNode::new(x)));
  13.                 if let Some(ref mut x) = pans.next{
  14.                     pans=x;
  15.                 }
  16.             }
  17.             if let Some(ref mut x)=p.next{
  18.                 p=x;
  19.             }else{
  20.                 break;
  21.             }
  22.         }
  23.         return ans.next;
  24.     }
  25. }

用链表互转模板：

  1. fn trans_link_list_to_vector(head: Option<Box<ListNode>>)->Vec<i32>{
  2.     let mut v=Vec::new();
  3.     if head.is_none(){
  4.         return v;
  5.     }
  6.     let mut p = & mut head.unwrap();
  7.     v.push(p.val);
  8.     loop{
  9.         if let Some(ref mut x) = p.next {
  10.             v.push(x.val);
  11.             p=x;
  12.         }else{
  13.             break;
  14.         }
  15.     }
  16.     return v;
  17. }
  18. fn trans_vector_to_link_list(v:Vec<i32>)-> Option<Box<ListNode>> {
  19.     let mut ans = Box::new(ListNode::new(0));
  20.     let mut p =&mut ans;
  21.     for i in 0..v.len() {
  22.         p.next = Some(Box::new(ListNode::new(v[i])));
  23.         if let Some(ref mut x) = p.next{
  24.             p=x;
  25.         }
  26.     }
  27.     return ans.next;
  28. }
  29.  
  30.  
  31. impl Solution {
  32.     pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
  33.         let v = trans_link_list_to_vector(head);
  34.         let mut v2=Vec::new();
  35.         for i in 0..v.len(){
  36.             if v[i]!=val{
  37.                 v2.push(v[i]);
  38.             }
  39.         }
  40.         return trans_vector_to_link_list(v2);
  41.     }
  42. }

力扣 面试题 02.02. 返回倒数第 k 个节点（链表）

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4

说明：

给定的 k 保证是有效的。

用模板：

  1. fn trans_link_list_to_vector(head: Option<Box<ListNode>>)->Vec<i32>{
  2.     let mut v=Vec::new();
  3.     if head.is_none(){
  4.         return v;
  5.     }
  6.     let mut p = & mut head.unwrap();
  7.     v.push(p.val);
  8.     loop{
  9.         if let Some(ref mut x) = p.next {
  10.             v.push(x.val);
  11.             p=x;
  12.         }else{
  13.             break;
  14.         }
  15.     }
  16.     return v;
  17. }
  18. impl Solution {
  19.     pub fn kth_to_last(head: Option<Box<ListNode>>, k: i32) -> i32 {
  20.         let v = trans_link_list_to_vector(head);
  21.         return v[v.len()-k as usize];
  22.     }
  23. }

力扣 617. 合并二叉树（二叉树DFS）

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

提示：

  • 两棵树中的节点数目在范围 [0, 2000] 内
  • -104 <= Node.val <= 104
  1. use std::rc::Rc;
  2. use std::cell::RefCell;
  3.  
  4.  
  5. impl Solution {
  6.     pub fn merge_trees(root1: Option<Rc<RefCell<TreeNode>>>, root2: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
  7.         if root1.is_none() {
  8.             return root2;
  9.         }
  10.         if root2.is_none() {
  11.             return root1;
  12.         }
  13.         let nod1 = root1.unwrap();
  14.         let nod2 = root2.unwrap();
  15.         let mut nod = TreeNode::new(nod1.borrow_mut().val + nod2.borrow_mut().val);
  16.         nod.left = Solution::merge_trees(nod1.borrow_mut().left.clone(),nod2.borrow_mut().left.clone());
  17.         nod.right = Solution::merge_trees(nod1.borrow_mut().right.clone(),nod2.borrow_mut().right.clone());
  18.         return Some(Rc::new(RefCell::new(nod)));
  19.     }
  20. }

力扣 面试题 04.02. 最小高度树（二叉树DFS）

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

          0 
         / \ 
       -3   9 
       /   / 
     -10  5 
  1.  
  2. use std::rc::Rc;
  3. use std::cell::RefCell;
  4. impl Solution {
  5.     pub fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
  6.         if nums.is_empty(){
  7.             return None;
  8.         }
  9.         return Solution::dfs(&nums,0,nums.len()-1);
  10.     }
  11.     pub fn dfs(nums: &Vec<i32>,low:usize,high:usize) -> Option<Rc<RefCell<TreeNode>>> {
  12.         let mid = (low+high)/2;
  13.         let mut nod = TreeNode::new(nums[mid]);
  14.         if low < mid{
  15.             nod.left = Solution::dfs(nums,low,mid-1);
  16.         }if mid < high{
  17.             nod.right = Solution::dfs(nums,mid+1,high);
  18.         }
  19.         return Some(Rc::new(RefCell::new(nod)));
  20.     }
  21. }

力扣 654. 最大二叉树（二叉树DFS）

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • nums 中的所有整数 互不相同
  1. use std::rc::Rc;
  2. use std::cell::RefCell;
  3. impl Solution {
  4.     pub fn construct(nums: &Vec<i32>, low:usize, high:usize) -> Option<Rc<RefCell<TreeNode>>> {
  5.         let mut id=low;
  6.         for i in low..=high{
  7.             if nums[id] < nums[i]{
  8.                 id=i;
  9.             }
  10.         }
  11.         let mut r = TreeNode::new(nums[id]);
  12.         if low <id{
  13.             r.left = Solution::construct(nums,low,id-1);
  14.         }
  15.         if id < high{
  16.             r.right = Solution::construct(nums,id+1,high);
  17.         }
  18.         Some(Rc::new(RefCell::new(r)))
  19.     }
  20.     pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
  21.         Solution::construct(&nums,0,nums.len()-1)
  22.     }
  23. }

力扣 2458. 移除子树后的二叉树高度（二叉树DFS）

给你一棵 二叉树 的根节点 root ，树中有 n 个节点。每个节点都可以被分配一个从 1 到 n 且互不相同的值。另给你一个长度为 m 的数组 queries 。

你必须在树上执行 m 个 独立 的查询，其中第 i 个查询你需要执行以下操作：

  • 从树中 移除 以 queries[i] 的值作为根节点的子树。题目所用测试用例保证 queries[i] 不 等于根节点的值。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是执行第 i 个查询后树的高度。

注意：

  • 查询之间是独立的，所以在每个查询执行后，树会回到其 初始 状态。
  • 树的高度是从根到树中某个节点的 最长简单路径中的边数 。

示例 1：

输入：root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
输出：[2]
解释：上图展示了从树中移除以 4 为根节点的子树。
树的高度是 2（路径为 1 -> 3 -> 2）。

示例 2：

输入：root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
输出：[3,2,3,2]
解释：执行下述查询：
- 移除以 3 为根节点的子树。树的高度变为 3（路径为 5 -> 8 -> 2 -> 4）。
- 移除以 2 为根节点的子树。树的高度变为 2（路径为 5 -> 8 -> 1）。
- 移除以 4 为根节点的子树。树的高度变为 3（路径为 5 -> 8 -> 2 -> 6）。
- 移除以 8 为根节点的子树。树的高度变为 2（路径为 5 -> 9 -> 3）。

提示：

  • 树中节点的数目是 n
  • 2 <= n <= 105
  • 1 <= Node.val <= n
  • 树中的所有值 互不相同
  • m == queries.length
  • 1 <= m <= min(n, 104)
  • 1 <= queries[i] <= n
  • queries[i] != root.val
  1.  
  2. use std::cmp::max;
  3. use std::rc::Rc;
  4. use std::cell::RefCell;
  5. use std::collections::HashMap;
  6. impl Solution {
  7.     pub fn tree_queries(root: Option<Rc<RefCell<TreeNode>>>, queries: Vec<i32>) -> Vec<i32> {
  8.         let mut m:HashMap<i32,i32>=HashMap::new();
  9.         Solution::max_deep(root.clone(), &mut m);
  10.         let mut m2:HashMap<i32,i32>=HashMap::new();
  11.         Solution::dfs(root.clone(), 0, 0, &mut m, &mut m2);
  12.         let mut ans = Vec::new();
  13.         for x in queries {
  14.             if let Some(p) = m2.get_mut(&x){
  15.                 ans.push(*p - 1);
  16.             }
  17.         }
  18.         return ans;
  19.     }
  20.     pub fn max_deep(root: Option<Rc<RefCell<TreeNode>>>,m:&mut HashMap<i32,i32>)->i32{
  21.         if root.is_none(){
  22.             return 0;
  23.         }
  24.         let r = root.clone().unwrap();
  25.         let x1 = Solution::max_deep(r.borrow_mut().left.clone(),m);
  26.         let x2 = Solution::max_deep(r.borrow_mut().right.clone(),m);
  27.         let mut s= max(x1,x2) + 1;
  28.         m.insert(r.borrow_mut().val, s);
  29.         return s;
  30.     }
  31.     pub fn dfs(root: Option<Rc<RefCell<TreeNode>>>,fa_deep:i32,fa_ans:i32,m:&mut HashMap<i32,i32>, m2:&mut HashMap<i32,i32>){
  32.         if root.is_none(){
  33.             return;
  34.         }
  35.         let r = root.clone().unwrap();
  36.         let left = r.borrow_mut().left.clone();
  37.         let right = r.borrow_mut().right.clone();
  38.         m2.insert(r.borrow_mut().val, fa_ans);
  39.         let deep = fa_deep + 1;
  40.         let mut right_ans=0;
  41.         if right.is_some(){
  42.             if let Some(p) = m.get_mut(&right.clone().unwrap().borrow_mut().val){
  43.                 right_ans = *p;
  44.             }
  45.         }
  46.         let mut left_ans=0;
  47.         if left.is_some(){
  48.             if let Some(p) = m.get_mut(&left.clone().unwrap().borrow_mut().val){
  49.                 left_ans = *p;
  50.             }
  51.         }
  52.         Solution::dfs(left, deep, max(deep + right_ans,fa_ans), m, m2);    
  53.         Solution::dfs(right, deep, max(deep + left_ans,fa_ans), m, m2);
  54.     }
  55. }

力扣 297. 二叉树的序列化与反序列化（BFS+字符串）

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

提示：

  • 树中结点数在范围 [0, 104] 内
  • -1000 <= Node.val <= 1000

c++代码：

  1.  
  2.  
  3. class Codec {
  4. public:
  5.     vector<int> serialize(TreeNode* root, int error) {
  6.         queue<TreeNode*>q;
  7.         q.push(root);
  8.         vector<int>ans;
  9.         while (!q.empty()) {
  10.             auto p = q.front();
  11.             q.pop();
  12.             if (p == nullptr) {
  13.                 ans.push_back(error);
  14.                 continue;
  15.             }
  16.             ans.push_back(p->val);
  17.             q.push(p->left);
  18.             q.push(p->right);
  19.         }
  20.         return ans;
  21.     }
  22.     TreeNode* deserialize(vector<int>v, int error) {
  23.         int id = 0;
  24.         TreeNode* root = nullptr;
  25.         queue<TreeNode**>q;
  26.         q.push(&root);
  27.         while (!q.empty()) {
  28.             auto p = q.front();
  29.             q.pop();
  30.             int val = v[id++];
  31.             if (val != error) {
  32.                 *p = new TreeNode(val);
  33.                 q.push(&((*p)->left));
  34.                 q.push(&((*p)->right));
  35.             }
  36.         }
  37.         return root;
  38.     }
  39.     // Encodes a tree to a single string.
  40.     string serialize(TreeNode* root) {
  41.         auto v = serialize(root, 123456);
  42.         string s;
  43.         for (auto x : v)s += to_string(x) + " ";
  44.         return s;
  45.     }
  46.  
  47.     // Decodes your encoded data to tree.
  48.     TreeNode* deserialize(string data) {
  49.         auto v = stringSplit(data);
  50.         vector<int>vals;
  51.         for (auto s : v)vals.push_back(atoi(s.data()));
  52.         return deserialize(vals, 123456);
  53.     }
  54. };

rust代码：

  1.  
  2. use std::rc::Rc;
  3. use std::cell::RefCell;
  4. use std::collections::VecDeque;
  5. fn string_to_int(v:& Vec<char>)->i32{
  6.     let mut id :usize=0;
  7.     let mut flag:i32 = 1;
  8.     if v[id] == '-' {
  9.         id+=1;
  10.         flag = -1;
  11.     }
  12.     let mut s:i32 = 0;
  13.     while id < v.len() {
  14.         s = s * 10 + v[id].to_digit(10).unwrap() as i32;
  15.         id+=1;
  16.     }
  17.     return s*flag;
  18. }
  19.  
  20. struct Codec {
  21. }
  22. impl Codec {
  23.     fn new() -> Self {
  24.         Codec{}
  25.     }
  26.     fn serialize_(root: Option<Rc<RefCell<TreeNode>>>, error: i32)->Vec<i32> {
  27.         let mut q=VecDeque::new();
  28.         q.push_back(root.clone());
  29.         let mut ans = Vec::new();
  30.         while q.len() > 0{
  31.             let p = q.pop_front().unwrap();
  32.             if p.is_none() {
  33.                 ans.push(error);
  34.                 continue;
  35.             }
  36.             let r = p.clone().unwrap();
  37.             ans.push(r.borrow_mut().val);
  38.             q.push_back(r.borrow_mut().left.clone());
  39.             q.push_back(r.borrow_mut().right.clone());
  40.         }
  41.         return ans;
  42.     }
  43.     fn deserialize_(v:Vec<i32>, error:i32) ->Option<Rc<RefCell<TreeNode>>>{
  44.         if v[0]==error {
  45.             return None;
  46.         }
  47.         let mut id:usize = 0;
  48.         let val = v[id];
  49.         id+=1;
  50.         let root = Some(Rc::new(RefCell::new(TreeNode::new(val))));
  51.         let mut q=VecDeque::new();
  52.         q.push_back(root.clone());
  53.         while q.len() > 0 {
  54.             let p = q.pop_front().unwrap();
  55.             let r = p.clone().unwrap();
  56.             let val = v[id];
  57.             id+=1;
  58.             if val != error {
  59.                 r.borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(val))));
  60.                 q.push_back(r.borrow_mut().left.clone());
  61.             }
  62.             let val = v[id];
  63.             id+=1;
  64.             if val != error {
  65.                 r.borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(val))));
  66.                 q.push_back(r.borrow_mut().right.clone());
  67.             }
  68.         }
  69.         root
  70.     }
  71.     fn serialize(&mut self, root: Option<Rc<RefCell<TreeNode>>>) -> String {
  72.         let v = Codec::serialize_(root, 123456);
  73.         let mut s = String::from("");
  74.         for x in v {
  75.             s += &x.to_string();
  76.             s+=" ";
  77.         }
  78.         return s;
  79.     }
  80. 	
  81.     fn deserialize(&self, data: String) -> Option<Rc<RefCell<TreeNode>>> {
  82.         let v:Vec<char>=data.chars().collect();
  83.         let mut v2=Vec::new();
  84.         let mut vx = Vec::new();
  85.         for x in v {
  86.             if x == ' ' {
  87.                 vx.push(string_to_int(&v2));
  88.                 v2.clear();
  89.             }else{
  90.                 v2.push(x);
  91.             }
  92.         }        
  93.         return Codec::deserialize_(vx, 123456);
  94.     }
  95. }

力扣 2586. 统计范围内的元音字符串数（字符串）

给你一个下标从 0 开始的字符串数组 words 和两个整数：left 和 right 。

如果字符串以元音字母开头并以元音字母结尾，那么该字符串就是一个 元音字符串 ，其中元音字母是 'a'、'e'、'i'、'o'、'u' 。

返回 words[i] 是元音字符串的数目，其中 i 在闭区间 [left, right] 内。

示例 1：

输入：words = ["are","amy","u"], left = 0, right = 2
输出：2
解释：
- "are" 是一个元音字符串，因为它以 'a' 开头并以 'e' 结尾。
- "amy" 不是元音字符串，因为它没有以元音字母结尾。
- "u" 是一个元音字符串，因为它以 'u' 开头并以 'u' 结尾。
在上述范围中的元音字符串数目为 2 。

示例 2：

输入：words = ["hey","aeo","mu","ooo","artro"], left = 1, right = 4
输出：3
解释：
- "aeo" 是一个元音字符串，因为它以 'a' 开头并以 'o' 结尾。
- "mu" 不是元音字符串，因为它没有以元音字母开头。
- "ooo" 是一个元音字符串，因为它以 'o' 开头并以 'o' 结尾。
- "artro" 是一个元音字符串，因为它以 'a' 开头并以 'o' 结尾。
在上述范围中的元音字符串数目为 3 。

提示：

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 10
  • words[i] 仅由小写英文字母组成
  • 0 <= left <= right < words.length
  1. impl Solution {
  2.     pub fn vowel_char(c:char)->bool{
  3.         match c{
  4.             'a'=>true,
  5.             'e'=>true,
  6.             'i'=>true,
  7.             'o'=>true,
  8.             'u'=>true,
  9.             _=>false
  10.         }
  11.     }
  12.     pub fn vowel_strings(words: Vec<String>, left: i32, right: i32) -> i32 {
  13.         let mut ans =0;
  14.         for i in left..=right {
  15.             let v:Vec<char>=words[i as usize].chars().collect();
  16.             if Solution::vowel_char(v[0]) {
  17.                 if Solution::vowel_char(v[v.len()-1]) {
  18.                     ans+=1;
  19.                 }
  20.             }
  21.         }        
  22.         return ans;
  23.     }
  24. }

力扣 面试题 01.04. 回文排列（字符串+哈希表）

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

回文串不一定是字典当中的单词。

示例1：

输入："tactcoa"
输出：true（排列有"tacocat"、"atcocta"，等等）
  1. use std::collections::HashMap;
  2. impl Solution {
  3.     pub fn can_permute_palindrome(s: String) -> bool {
  4.         let c:Vec<char>=s.chars().collect();
  5.         let mut m=HashMap::new();
  6.         for x in c{
  7.             if let Some(p)=m.get_mut(&x){
  8.                 *p+=1;
  9.             }else{
  10.                 m.insert(x,1);
  11.             }
  12.         }
  13.         let mut s=0;
  14.         for pair in m{
  15.             s+=pair.1 % 2;
  16.         }
  17.         return s<2;
  18.     }
  19. }

力扣 697. 数组的度（哈希表）

给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1：

输入：nums = [1,2,2,3,1]
输出：2
解释：
输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
连续子数组里面拥有相同度的有如下所示：
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。

示例 2：

输入：nums = [1,2,2,3,1,4,2]
输出：6
解释：
数组的度是 3 ，因为元素 2 重复出现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。

提示：

  • nums.length 在 1 到 50,000 范围内。
  • nums[i] 是一个在 0 到 49,999 范围内的整数。
  1. use std::collections::HashMap;
  2. use std::cmp::min;
  3. use std::cmp::max;
  4. impl Solution {
  5.     pub fn find_shortest_sub_array(nums: Vec<i32>) -> i32 {
  6.         let mut m=HashMap::new();
  7.         let mut left=HashMap::new();
  8.         let mut right=HashMap::new();
  9.         let mut max_num = 1;
  10.         for i in 0..nums.len(){
  11.             if let Some(p) = m.get_mut(&nums[i]){
  12.                 *p += 1;
  13.                 max_num = max(max_num, *p)
  14.             }else{
  15.                 m.insert(nums[i], 1);
  16.             }
  17.             if let Some(p) = left.get_mut(&nums[i]){
  18.                 if let Some(p) = right.get_mut(&nums[i]){
  19.                     *p=i as i32;
  20.                 }
  21.             }else{
  22.                 left.insert(nums[i], i as i32);
  23.                 right.insert(nums[i], i as i32);
  24.             }
  25.         }
  26.  
  27.         let mut ans = nums.len() as i32;
  28.         for i in 0..nums.len(){
  29.             if let Some(p) = m.get_mut(&nums[i]){
  30.                 if *p == max_num{
  31.                     let leftid = *(left.get_mut(&nums[i]).unwrap());
  32.                     let rightid = *(right.get_mut(&nums[i]).unwrap());
  33.                     ans=min(ans,rightid-leftid+1);
  34.                 }
  35.             }
  36.         }
  37.         return ans;
  38.     }
  39. }

力扣 350. 两个数组的交集 II（哈希表）

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

进阶：

  • 如果给定的数组已经排好序呢？你将如何优化你的算法？
  • 如果 nums1 的大小比 nums2 小，哪种方法更优？
  • 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
  1.  
  2. use std::collections::HashMap;
  3. impl Solution {
  4.     pub fn intersect(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
  5.         let mut m = HashMap::new();
  6.         for i in 0..nums1.len() {
  7.             if let Some(p) = m.get_mut(&nums1[i]){
  8.                 *p+=1;
  9.             }else{
  10.                 m.insert(nums1[i],1);
  11.             }
  12.         }
  13.         let mut ans = Vec::new();
  14.         for i in 0..nums2.len() {
  15.             if let Some(p) = m.get_mut(&nums2[i]){
  16.                 if *p>0 {
  17.                     ans.push(nums2[i]);
  18.                 }
  19.                 *p-=1;
  20.             }
  21.         }
  22.         ans
  23.     }
  24. }

力扣 532. 数组中的 k-diff 数对（哈希表）

给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。

k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件：

  • 0 <= i, j < nums.length
  • i != j
  • |nums[i] - nums[j]| == k

注意，|val| 表示 val 的绝对值。

示例 1：

输入：nums = [3, 1, 4, 1, 5], k = 2
输出：2
解释：数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个 1 ，但我们只应返回不同的数对的数量。

示例 2：

输入：nums = [1, 2, 3, 4, 5], k = 1
输出：4
解释：数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5) 。

示例 3：

输入：nums = [1, 3, 1, 5, 4], k = 0
输出：1
解释：数组中只有一个 0-diff 数对，(1, 1) 。

提示：

  • 1 <= nums.length <= 104
  • -107 <= nums[i] <= 107
  • 0 <= k <= 107
  1. use std::collections::HashSet;
  2. use std::collections::HashMap;
  3. impl Solution {
  4.     pub fn find_pairs(nums: Vec<i32>, k: i32) -> i32 {
  5.         let mut ans=0;
  6.         if k > 0 {
  7.             let mut s = HashSet::new();
  8.             for x in nums{
  9.                 s.insert(x);
  10.             }
  11.             let s2=s.clone();
  12.             for x in s2{
  13.                 if s.contains(&(x-k)){
  14.                     ans+=1;
  15.                 }
  16.             }
  17.         }else{
  18.             let mut s = HashMap::new();
  19.             for x in nums{
  20.                 if let Some(p) = s.get_mut(&x){
  21.                     if *p == 1{
  22.                         ans+=1;
  23.                     }
  24.                     *p+=1;                    
  25.                 }else{
  26.                     s.insert(x, 1);
  27.                 }
  28.             }
  29.         }
  30.         return ans;
  31.     }
  32. }

力扣 2561. 重排水果（哈希表）

你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的交换成本。为了让两个果篮中水果的数量相等。为此，可以根据需要多次执行下述操作：

  • 选中两个下标 i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
  • 交换的成本是 min(basket1i,basket2j) 。

根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。

返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。

示例 1：

输入：basket1 = [4,2,2,2], basket2 = [1,4,1,2]
输出：1
解释：交换 basket1 中下标为 1 的水果和 basket2 中下标为 0 的水果，交换的成本为 1 。此时，basket1 = [4,1,2,2] 且 basket2 = [2,4,1,2] 。重排两个数组，发现二者相等。

示例 2：

输入：basket1 = [2,3,4,1], basket2 = [3,2,5,1]
输出：-1
解释：可以证明无法使两个果篮相等。

提示：

  • basket1.length == bakste2.length
  • 1 <= basket1.length <= 105
  • 1 <= basket1i,basket2i <= 109
  1. use std::collections::BTreeMap;
  2. use std::cmp::min;
  3. impl Solution {
  4.     pub fn min_cost(basket1: Vec<i32>, basket2: Vec<i32>) -> i64 {
  5.         let mut s=BTreeMap::new();
  6.         for x in basket1{
  7.             if let Some(p) =s.get_mut(&x){
  8.                 *p+=1;
  9.             }
  10.             else{
  11.                 s.insert(x, 1);
  12.             }
  13.         }
  14.         for x in basket2{
  15.             if let Some(p) =s.get_mut(&x){
  16.                 *p-=1;
  17.             }
  18.             else{
  19.                 s.insert(x, -1);
  20.             }
  21.         }
  22.         let mut ans=0;
  23.         let mut num=0;
  24.         let mut mins = 1000000000;
  25.         for (x,n) in s.iter(){
  26.             if n%2==1{
  27.                 return -1;
  28.             }
  29.             num+=i32::abs(*n);
  30.             mins=min(mins,*x);
  31.         }
  32.         num/=4;
  33.         for (x,n) in s{
  34.             if n%2==0{
  35.                 let y=min(x,mins*2) as i64;
  36.                 if i32::abs(n)/2 >= num {
  37.                     ans+=y * num as i64;
  38.                     return ans;
  39.                 }else{
  40.                     num-=i32::abs(n)/2;
  41.                     ans+=y * i32::abs(n) as i64 /2;
  42.                 }
  43.             }
  44.         }
  45.         0
  46.     }
  47. }

力扣 349. 两个数组的交集（集合）

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000
  1. use std::collections::HashSet;
  2. impl Solution {
  3.     pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
  4.         let mut m = HashSet::new();
  5.         for i in 0..nums1.len() {
  6.             m.insert(nums1[i]);
  7.         }
  8.         let mut m2 = HashSet::new();
  9.         for i in 0..nums2.len() {
  10.             if m.contains(&nums2[i]){
  11.                 m2.insert(nums2[i]);
  12.             }
  13.         }
  14.         let mut ans = Vec::new();
  15.         for x in m2{
  16.             ans.push(x);
  17.         }
  18.         ans
  19.     }
  20. }

力扣 2336. 无限集中的最小数字（集合）

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。

实现 SmallestInfiniteSet 类：

  • SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
  • int popSmallest() 移除 并返回该无限集中的最小整数。
  • void addBack(int num) 如果正整数 num 不 存在于无限集中，则将一个 num 添加 到该无限集最后。

示例：

输入
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
输出
[null, null, 1, 2, 3, null, 1, 4, 5]

解释
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2);    // 2 已经在集合中，所以不做任何变更。
smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。
smallestInfiniteSet.addBack(1);    // 将 1 添加到该集合中。
smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中，
                                   // 且 1 是最小的整数，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。

提示：

  • 1 <= num <= 1000
  • 最多调用 popSmallest 和 addBack 方法 共计 1000 次
  1. use std::collections::HashSet;
  2. struct SmallestInfiniteSet {
  3.     s:HashSet<i32>
  4. }
  5. impl SmallestInfiniteSet {
  6.  
  7.     fn new() -> Self {
  8.         SmallestInfiniteSet{s:HashSet::new()}
  9.     }
  10.     
  11.     fn pop_smallest(&mut self) -> i32 {
  12.         for i in 1..12345{
  13.             if !self.s.contains(&i){
  14.                 self.s.insert(i);
  15.                 return i;
  16.             }
  17.         }
  18.         0
  19.     }
  20.     
  21.     fn add_back(&mut self, num: i32) {
  22.         if self.s.contains(&num){
  23.             self.s.remove(&num);
  24.         }
  25.     }
  26. }

力扣 2718. 查询后矩阵的和（集合）

给你一个整数 n 和一个下标从 0 开始的 二维数组 queries ，其中 queries[i] = [typei, indexi, vali] 。

一开始，给你一个下标从 0 开始的 n x n 矩阵，所有元素均为 0 。每一个查询，你需要执行以下操作之一：

  • 如果 typei == 0 ，将第 indexi 行的元素全部修改为 vali ，覆盖任何之前的值。
  • 如果 typei == 1 ，将第 indexi 列的元素全部修改为 vali ，覆盖任何之前的值。

请你执行完所有查询以后，返回矩阵中所有整数的和。

示例 1：

输入：n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
输出：23
解释：上图展示了每个查询以后矩阵的值。所有操作执行完以后，矩阵元素之和为 23 。

示例 2：

输入：n = 3, queries = [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]
输出：17
解释：上图展示了每一个查询操作之后的矩阵。所有操作执行完以后，矩阵元素之和为 17 。

提示：

  • 1 <= n <= 104
  • 1 <= queries.length <= 5 * 104
  • queries[i].length == 3
  • 0 <= typei <= 1
  • 0 <= indexi < n
  • 0 <= vali <= 105
  1. use std::collections::HashSet;
  2. impl Solution {
  3.     pub fn matrix_sum_queries(n: i32, queries: Vec<Vec<i32>>) -> i64 {
  4.         let mut rnum=Vec::new();
  5.         rnum.resize(queries.len(),0);
  6.         let mut cnum=Vec::new();
  7.         cnum.resize(queries.len(),0);
  8.         let mut rm = HashSet::new();
  9.         let mut cm = HashSet::new();
  10.         let mut id = queries.len() -1;
  11.         loop{
  12.             if queries[id][0] == 0{
  13.                 rm.insert(queries[id][1]);
  14.             }else{
  15.                 cm.insert(queries[id][1]);
  16.             }
  17.             rnum[id]=rm.len();
  18.             cnum[id]=cm.len();
  19.             if id==0{
  20.                 break;
  21.             }
  22.             id-=1;
  23.         }
  24.         let mut ans:i64=0;
  25.         for i in 0..queries.len(){
  26.             if i+1 < queries.len(){
  27.                 if queries[i][0] == 0 && rnum[i]==rnum[i+1]{
  28.                     continue;
  29.                 }
  30.                 if queries[i][0] == 1 && cnum[i]==cnum[i+1]{
  31.                     continue;
  32.                 }
  33.             }
  34.             if queries[i][0] == 0{
  35.                 ans+=queries[i][2] as i64 *(n-cnum[i] as i32) as i64;
  36.             }else{
  37.                 ans+=queries[i][2] as i64 *(n-rnum[i] as i32) as i64;
  38.             }
  39.             
  40.         }
  41.         return ans;
  42.     }
  43. }

力扣 1823. 找出游戏的获胜者（约瑟夫问题）

约瑟夫问题

力扣 面试题 08.06. 汉诺塔问题（汉诺塔问题）

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

示例1:

 输入：A = [2, 1, 0], B = [], C = []
 输出：C = [2, 1, 0]

示例2:

 输入：A = [1, 0], B = [], C = []
 输出：C = [1, 0]

提示:

  1. A中盘子的数目不大于14个。
  1. impl Solution {
  2.     pub fn hanota(a: &mut Vec<i32>, b: &mut Vec<i32>, c: &mut Vec<i32>) {
  3.         *c=a.clone();
  4.         *a=Vec::new();
  5.     }
  6. }

力扣 2526. 找到数据流中的连续整数（数据流）

给你一个整数数据流，请你实现一个数据结构，检查数据流中最后 k 个整数是否 等于 给定值 value 。

请你实现 DataStream 类：

  • DataStream(int value, int k) 用两个整数 value 和 k 初始化一个空的整数数据流。
  • boolean consec(int num) 将 num 添加到整数数据流。如果后 k 个整数都等于 value ，返回 true ，否则返回 false 。如果少于 k 个整数，条件不满足，所以也返回 false 。

示例 1：

输入：
["DataStream", "consec", "consec", "consec", "consec"]
[[4, 3], [4], [4], [4], [3]]
输出：
[null, false, false, true, false]

解释：
DataStream dataStream = new DataStream(4, 3); // value = 4, k = 3 
dataStream.consec(4); // 数据流中只有 1 个整数，所以返回 False 。
dataStream.consec(4); // 数据流中只有 2 个整数
                      // 由于 2 小于 k ，返回 False 。
dataStream.consec(4); // 数据流最后 3 个整数都等于 value， 所以返回 True 。
dataStream.consec(3); // 最后 k 个整数分别是 [4,4,3] 。
                      // 由于 3 不等于 value ，返回 False 。

提示：

  • 1 <= value, num <= 109
  • 1 <= k <= 105
  • 至多调用 consec 次数为 105 次。
  1. struct DataStream {
  2.     x:i32,
  3.     n:i32,
  4.     num:i32,
  5. }
  6.  
  7. /**
  8.  * `&self` means the method takes an immutable reference.
  9.  * If you need a mutable reference, change it to `&mut self` instead.
  10.  */
  11. impl DataStream {
  12.  
  13.     fn new(value: i32, k: i32) -> Self {
  14.         return DataStream{x:value,n:k,num:0};
  15.     }
  16.     
  17.     fn consec(&mut self, num: i32) -> bool {
  18.         if num == self.x{
  19.             self.num=self.num+1;
  20.         }else{
  21.             self.num=0;
  22.         }
  23.         return self.num>=self.n;
  24.     }
  25. }

力扣 313. 超级丑数（数列DP）

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

示例 1：

输入：n = 12, primes = [2,7,13,19]
输出：32 
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

示例 2：

输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。

提示：

  • 1 <= n <= 105
  • 1 <= primes.length <= 100
  • 2 <= primes[i] <= 1000
  • 题目数据 保证 primes[i] 是一个质数
  • primes 中的所有值都 互不相同 ，且按 递增顺序 排列

思路：

假设超级丑数的无穷集合是A，那么形如{A*primes[i]}的 primes.length个集合的并集就等于 A-{1}

也就是说，求A的过程，可以看做从primes.length个有序数组中依次挑选数构成有序数组的过程。

  1. impl Solution {
  2.     pub fn nth_super_ugly_number(n: i32, primes: Vec<i32>) -> i32 {
  3.         let mut n = n as usize;
  4.         let mut ugs = Vec::from([1i64]);
  5.         let mut ids=Vec::new();
  6.         ids.resize(primes.len(), 0usize);
  7.         while ugs.len() < n{
  8.             let mut min_id = 0;
  9.             for i in 1..primes.len(){
  10.                 if ugs[ids[i]] * (primes[i] as i64) == *ugs.last().unwrap(){
  11.                     ids[i]+=1;
  12.                 }
  13.                 if ugs[ids[i]] * (primes[i] as i64) < ugs[ids[min_id]] * (primes[min_id] as i64){
  14.                     min_id = i;
  15.                 }
  16.             }
  17.             ugs.push(ugs[ids[min_id]]*primes[min_id] as i64);
  18.             ids[min_id]+=1;
  19.         }
  20.         return ugs[n-1] as i32;
  21.     }
  22. }

时间复杂度：O（n * primes.length）

用优先队列可以进一步优化时间复杂度。

力扣 2609. 最长平衡子字符串（数列DP）

给你一个仅由 0 和 1 组成的二进制字符串 s 。  

如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。 

返回  s 中最长的平衡子字符串长度。

子字符串是字符串中的一个连续字符序列。

示例 1：

输入：s = "01000111"
输出：6
解释：最长的平衡子字符串是 "000111" ，长度为 6 。

示例 2：

输入：s = "00111"
输出：4
解释：最长的平衡子字符串是 "0011" ，长度为  4 。

示例 3：

输入：s = "111"
输出：0
解释：除了空子字符串之外不存在其他平衡子字符串，所以答案为 0 。

提示：

  • 1 <= s.length <= 50
  • '0' <= s[i] <= '1'
  1. use std::cmp::min;
  2. use std::cmp::max;
  3. fn vector_reverse<T:Clone> (v:&Vec<T>)->Vec<T>{
  4.     let mut ans = Vec::new();
  5.     let mut i = v.len();
  6.     loop {
  7.         if i==0{
  8.             break;
  9.         }
  10.         i-=1;
  11.         ans.push(v[i].clone());
  12.     }
  13.     return ans;
  14. }
  15. impl Solution {
  16.     pub fn find_the_longest_balanced_substring(s: String) -> i32 {
  17.         let v:Vec<char> = s.chars().collect();
  18.         let rv = vector_reverse(&v);
  19.         let mut n = 0;
  20.         let mut nv=Vec::new();
  21.         for i in 0..v.len(){
  22.             if v[i]=='0'{
  23.                 n+=1;
  24.             }else{
  25.                 n=0;
  26.             }
  27.             nv.push(n);
  28.         }
  29.         let mut ans =0;
  30.         for i in 0..rv.len()-1{
  31.             if rv[i]=='1'{
  32.                 n+=1;
  33.             }else{
  34.                 n=0;
  35.             }
  36.             ans = max(ans, min(n, nv[v.len()-2-i]));
  37.         }
  38.         return ans*2;
  39.     }
  40. }

力扣 1039. 多边形三角剖分的最低得分（区间DP）

你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。

假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。

返回 多边形进行三角剖分后可以得到的最低分 。
 

示例 1：

输入：values = [1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。

示例 2：

输入：values = [3,7,4,5]
输出：144
解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。

示例 3：

输入：values = [1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。

提示：

  • n == values.length
  • 3 <= n <= 50
  • 1 <= values[i] <= 100
  1. use std::cmp::min;
  2. use std::collections::HashMap;
  3.  
  4. impl Solution {
  5.     pub fn min_score_triangulation(values: Vec<i32>) -> i32 {
  6.         let mut m:HashMap<(usize, usize, usize),i32>=HashMap::new();
  7.         return Solution::dp(&values,0,1,values.len()-1,& mut m);
  8.     }
  9.     pub fn dp(values: &Vec<i32>, p:usize,low:usize,high:usize,m:& mut HashMap<(usize, usize, usize), i32>) -> i32 {
  10.         if (low + 1 == high){
  11.             return values[p]*values[low]*values[high];
  12.         }
  13.         if let Some(p) = m.get_mut(&(p,low,high)){
  14.             return *p;
  15.         }
  16.         let mut ans = Solution::dp(values,low,low+1,high,m)+values[p]*values[low]*values[high];
  17.         for i in low+1..high{
  18.             ans = min(ans, Solution::dp(values,p,low,i,m)+Solution::dp(values,p,i,high,m));
  19.         }
  20.         m.insert((p,low,high),ans);
  21.         return ans;
  22.     }
  23. }

力扣 321. 拼接最大数（贪心）

字典序

力扣 179. 最大数（贪心）

字典序

力扣 984. 不含 AAA 或 BBB 的字符串（贪心）

给定两个整数 a 和 b ，返回 任意 字符串 s ，要求满足：

  • s 的长度为 a + b，且正好包含 a 个 'a' 字母与 b 个 'b' 字母；
  • 子串 'aaa' 没有出现在 s 中；
  • 子串 'bbb' 没有出现在 s 中。

示例 1：

输入：a = 1, b = 2
输出："abb"
解释："abb", "bab" 和 "bba" 都是正确答案。

示例 2：

输入：a = 4, b = 1
输出："aabaa"

提示：

  • 0 <= a, b <= 100
  • 对于给定的 a 和 b，保证存在满足要求的 s 
  1. impl Solution {
  2.     pub fn str_without3a3b(a: i32, b: i32) -> String {
  3.         let mut ca='a';
  4.         let mut cb='b';
  5.         let mut a=a;
  6.         let mut b=b;
  7.         if a<b{
  8.             let c=b;
  9.             b=a;
  10.             a=c;
  11.             ca='b';
  12.             cb='a';
  13.         }
  14.         let len = (a as usize +1)/2 ;
  15.         let mut v=Vec::new();
  16.         v.resize(len,Vec::new());
  17.         for i in 0..a{
  18.             v[(i as i32 % len as i32)as usize].push(ca);
  19.         }
  20.         for i in 0..b{
  21.             v[(i as i32 % len as i32)as usize].push(cb);
  22.         }
  23.         let mut vans=Vec::new();
  24.         for x in v{
  25.             for c in x{
  26.                 vans.push(c);
  27.             }
  28.         }
  29.         return vans.into_iter().collect();
  30.     }
  31. }

力扣 223. 矩形面积（计算几何）

给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形，请你计算并返回两个矩形覆盖的总面积。

每个矩形由其 左下 顶点和 右上 顶点坐标表示：

  • 第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
  • 第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。

示例 1：

Rectangle Area

输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出：45

示例 2：

输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
输出：16

提示：

  • -104 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 104
  1. use std::cmp::min;
  2. use std::cmp::max;
  3. impl Solution {
  4.     fn compute_len(a1:i32,a2:i32,b1:i32,b2:i32)->i32 {
  5.         let c1=max(a1,b1);
  6.         let c2=min(a2,b2);
  7.         if c1 >= c2 {
  8.             return 0;
  9.         }
  10.         return c2-c1;
  11.     }
  12.     pub fn compute_area(ax1: i32, ay1: i32, ax2: i32, ay2: i32, bx1: i32, by1: i32, bx2: i32, by2: i32) -> i32 {
  13.         let mut s1 = (ax2-ax1)*(ay2-ay1);
  14.         let mut s2 = (bx2-bx1)*(by2-by1);
  15.         return s1 + s2 - Solution::compute_len(ax1,ax2,bx1,bx2) * Solution::compute_len(ay1,ay2,by1,by2);
  16.     }
  17. }

力扣 684. 冗余连接（并查集）

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

示例 1：

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

示例 2：

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

提示:

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ai < bi <= edges.length
  • ai != bi
  • edges 中无重复元素
  • 给定的图是连通的 
  1. struct Union{
  2.     fa:Vec<usize>,
  3. }
  4. impl Union{
  5.     fn find(& mut self,x:usize)->usize{
  6.         if self.fa[x] == x{
  7.             return x;
  8.         }
  9.         Union::find(self,self.fa[x]);
  10.         self.fa[x] = self.fa[self.fa[x]];
  11.         return self.fa[x];
  12.     }
  13.     fn in_same(& mut self,x:usize,y:usize)->bool{
  14.         return Union::find(self,x) == Union::find(self,y);
  15.     }
  16.     fn merge(& mut self,x:usize,y:usize)->(){
  17.         Union::find(self,x);
  18.         let fax = self.fa[x];
  19.         self.fa[fax] = y;
  20.     }
  21. }
  22. impl Solution {
  23.     pub fn find_redundant_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
  24.         let mut fa=Vec::new();
  25.         for i in 0..edges.len(){
  26.             fa.push(i);
  27.         }
  28.         let mut opt = Union{fa:fa};
  29.         for v in edges{
  30.             if opt.in_same(v[0]as usize -1 , v[1] as usize -1){
  31.                 return v;
  32.             }
  33.             opt.merge(v[0] as usize -1, v[1] as usize -1);
  34.         }
  35.         return Vec::new();
  36.     }
  37. }

力扣 685. 冗余连接 II（并查集）

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1：

输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]

示例 2：

输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出：[4,1]

提示：

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ui, vi <= n

思路：

分3种情况讨论

分别是：

（1）有双父亲的节点，没有有向环，2个父亲删掉一个即可

（2）有双父亲的节点，有有向环，删掉环中的父亲即可

（3）没有双父亲的节点，有有向环，删掉环中的任意一条边即可，这种情况下问题和力扣 684. 冗余连接等价。

  1. struct Union{
  2.     fa:Vec<usize>,
  3. }
  4. impl Union{
  5.     fn find(& mut self,x:usize)->usize{
  6.         if self.fa[x] == x{
  7.             return x;
  8.         }
  9.         Union::find(self,self.fa[x]);
  10.         self.fa[x] = self.fa[self.fa[x]];
  11.         return self.fa[x];
  12.     }
  13.     fn in_same(& mut self,x:usize,y:usize)->bool{
  14.         return Union::find(self,x) == Union::find(self,y);
  15.     }
  16.     fn merge(& mut self,x:usize,y:usize)->(){
  17.         Union::find(self,x);
  18.         let fax = self.fa[x];
  19.         self.fa[fax] = y;
  20.     }
  21. }
  22. impl Solution {
  23.     pub fn find_redundant_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
  24.         let mut fa=Vec::new();
  25.         for i in 0..edges.len(){
  26.             fa.push(i);
  27.         }
  28.         let mut opt = Union{fa:fa};
  29.         for v in edges{
  30.             if opt.in_same(v[0]as usize -1 , v[1] as usize -1){
  31.                 return v;
  32.             }
  33.             opt.merge(v[0] as usize -1, v[1] as usize -1);
  34.         }
  35.         return Vec::new();
  36.     }
  37.     pub fn find_redundant_directed_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
  38.         let mut fa=Vec::new();
  39.         fa.resize(edges.len()+1, 0);
  40.         let mut double_fa = Vec::new();
  41.         for i in 0..edges.len(){
  42.             let x = edges[i][0];
  43.             let y = edges[i][1];
  44.             if fa[y as usize] != 0{
  45.                 double_fa.push(y);
  46.                 double_fa.push(fa[y as usize]);
  47.                 double_fa.push(x);
  48.             }else{
  49.                 fa[y as usize] = x;
  50.             }
  51.         }
  52.         if double_fa.is_empty(){
  53.             return Solution::find_redundant_connection(edges);
  54.         }
  55.         let y = double_fa[0];
  56.         let x = double_fa[1];
  57.         let mut r = x;
  58.         for i in 0..edges.len(){
  59.             r = fa[r as usize];
  60.             if r == y{
  61.                 return Vec::from([x,y]);
  62.             }
  63.         }
  64.         return Vec::from([double_fa[2],y]);
  65.     }
  66. }

力扣 785. 判断二分图（带权并查集）

二分图

力扣 面试题 04.01. 节点间通路（有向图BFS）

节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。

示例1:

 输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
 输出：true

示例2:

 输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
 输出 true

提示：

  1. 节点数量n在[0, 1e5]范围内。
  2. 节点编号大于等于 0 小于 n。
  3. 图中可能存在自环和平行边。
  1. use std::collections::HashMap;
  2. use std::collections::VecDeque;
  3. impl Solution {
  4.     pub fn find_whether_exists_path(n: i32, graph: Vec<Vec<i32>>, start: i32, target: i32) -> bool {
  5.         let mut m_next = HashMap::new();
  6.         for i in 0..n{
  7.             m_next.insert(i, Vec::new());
  8.         }
  9.         for v in graph{
  10.             if let Some(p) = m_next.get_mut(&v[0]){
  11.                 (*p).push(v[1]);
  12.             }
  13.         }
  14.         let mut v = Vec::from([start]);
  15.         let mut m=HashMap::new();
  16.         let mut deq=VecDeque::new();
  17.         for i in 0..v.len(){
  18.             m.insert(v[i], 1);
  19.             deq.push_back(v[i]);
  20.         }
  21.         loop {
  22.             if deq.is_empty(){
  23.                 break;
  24.             }
  25.             let id = deq.pop_front().unwrap();
  26.             for i in m_next.get_mut(&id).unwrap(){
  27.                 if *i==target{
  28.                     return true;
  29.                 }
  30.                 if m.get_mut(&i) == None{
  31.                     v.push(*i);
  32.                     m.insert(*i, 1);
  33.                     deq.push_back(*i);
  34.                 }
  35.             }
  36.         }
  37.         return false;
  38.     }
  39. }

力扣 LCP 62. 交通枢纽（有向图）

为了缓解「力扣嘉年华」期间的人流压力，组委会在活动期间开设了一些交通专线。path[i] = [a, b] 表示有一条从地点 a通往地点 b 的 单向 交通专线。 若存在一个地点，满足以下要求，我们则称之为 交通枢纽：

  • 所有地点（除自身外）均有一条 单向 专线 直接 通往该地点；
  • 该地点不存在任何 通往其他地点 的单向专线。

请返回交通专线的 交通枢纽。若不存在，则返回 -1。

注意：

  • 对于任意一个地点，至少被一条专线连通。

示例 1：

输入：path = [[0,1],[0,3],[1,3],[2,0],[2,3]]

输出：3

解释：如下图所示： 地点 0,1,2 各有一条通往地点 3 的交通专线， 且地点 3 不存在任何通往其他地点的交通专线。

image.png

示例 2：

输入：path = [[0,3],[1,0],[1,3],[2,0],[3,0],[3,2]]

输出：-1

解释：如下图所示：不存在满足 交通枢纽 的地点。

image.png

提示：

  • 1 <= path.length <= 1000
  • 0 <= path[i][0], path[i][1] <= 1000
  • path[i][0] 与 path[i][1] 不相等
  1. use std::cmp::max;
  2. impl Solution {
  3.     pub fn transportation_hub(path: Vec<Vec<i32>>) -> i32 {
  4.         let mut m = 0;
  5.         for i  in 0..path.len(){
  6.             m=max(m,max(path[i][0],path[i][1]));
  7.         }
  8.         let n = m as usize + 1;
  9.         let mut ins = Vec::new();
  10.         let mut outs = Vec::new();
  11.         ins.resize(n,0);
  12.         outs.resize(n,0);
  13.         for v in path{
  14.             outs[v[0] as usize]+=1;
  15.             ins[v[1] as usize]+=1;
  16.         }
  17.         for i in 0..n{
  18.             if ins[i] == n-1 && outs[i]==0{
  19.                 return i as i32;
  20.             }
  21.         }
  22.         return -1;
  23.     }
  24. }

力扣 LCR 115. 序列重建（拓扑排序）

拓扑排序

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/137496
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号