LeetCode 笔记
Sep 15, 2021
- 1. 两数之和
- 2. 两数相加
- 3. 无重复字符的最长子串
- 4. 寻找两个正序数组的中位数
- 5. 最长回文子串
- 6. Z 字形变换
- 7. 整数反转
- 8. 字符串转换整数 (atoi)
- 9. 回文数
- 11. 盛最多水的容器
- 12. 整数转罗马数字
- 13. 罗马数字转整数
- 14. 最长公共前缀
- 15. 三数之和
- 16. 最接近的三数之和
- 17. 电话号码的字母组合
- 18. 四数之和
- 19. 删除链表的倒数第 N 个结点
- 20. 有效的括号
- 21. 合并两个有序链表
- 22. 括号生成
- 36. 有效的数独
- 58. 最后一个单词的长度
- 162. 寻找峰值
- 187. 重复的 DNA 序列
- 212. 单词搜索 II
- 414. 第三大的数
- 434. 字符串中的单词数
- 524. 通过删除字母匹配到字典里最长单词
- 650. 只有两个键的键盘
- 704. 二分查找
大学时间已过半，迫于生计，最近开始做 LeetCode。我准备在这段时间里做完“热题 HOT 100”，另外尽量每天都做“每日一题”。使用的语言是 Rust，尽量写出最优的算法（如果我能理解的话）。之前没怎么做过题，所以写出的算法可能很垃圾，但还是记录一下方便以后查看。
1. 两数之和
以前做题太少了，最开始看到这题，想都没想就直接写了个暴力遍历：
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut result = Vec::new();
nums.iter().enumerate()
.for_each(|(a_idx, a)|
nums[a_idx + 1..].iter().enumerate()
.filter(|(_, b)| *b == &(target - a))
.for_each(|(b_idx, _)| result = vec![a_idx as i32, (a_idx + b_idx + 1) as i32]));
result
}
}
就是从这个数组创建一个带元素下标迭代器，然后遍历，对于其中的每个元素，再创建一个这个数组的 slice（包含前一次迭代还没遍历到的元素），用这个新迭代器遍历剩下的元素找到与前一个迭代器当前元素匹配的元素。
不出所料跑出了 48ms 的“好”成绩。嗯，这很不 Rust。
看了别人的题解才反应过来，应该用字典法才对：
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = HashMap::with_capacity(nums.len());
for (idx_a, n) in nums.iter().enumerate() {
if let Some(idx_b) = map.get(&(target - n)) {
return vec![*idx_b as i32, idx_a as i32];
} else {
map.insert(n, idx_a);
}
}
Vec::new()
}
}
2. 两数相加
对两个单链表做加法，输出新链表。
由于 Rust 所有权的设定，链表本身可以看作是一个递归数据结构，节点的读写比较麻烦，指针操作比较复杂，我开始写的时候逻辑非常混乱，到处都是编译器报错，直到看到了别人的题解中提到的“状态机”：
impl Solution {
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut head = None;
let mut tail = &mut head;
// 分别对应(链表 1, 链表2, 当前遍历到的两节点之和（只取个位数）, 进位)
let mut pattern = (l1, l2, 0, 0);
loop {
pattern = match pattern {
(Some(l1), Some(l2), _, carry) => {
let sum = l1.val + l2.val + carry;
if sum < 10 {
(l1.next, l2.next, sum, 0)
} else {
(l1.next, l2.next, sum - 10, 1)
}
}
(Some(list), None, _, carry) | (None, Some(list), _, carry) => {
let sum = list.val + carry;
if sum < 10 {
(list.next, None, sum, 0)
} else {
(list.next, None, sum - 10, 1)
}
}
(None, None, _, carry) => {
if carry != 0 {
(None, None, 1, 0)
} else {
break;
}
}
};
*tail = Some(Box::new(ListNode::new(pattern.2)));
tail = &mut tail.as_mut().unwrap().next;
}
head
}
}
这样用模式匹配写出的代码思路非常清晰。对指针的操作：
最开始将 head 初始化为 None 是为了和循环中每次初始化新节点时的状态对应，同时创建 head 的可变引用 tail。每次 loop 结束时，pattern 通过模式匹配都得到了需要创建的新节点的数据，只需要把节点放进 tail 中，然后将 tail 指向节点的 next，也就是下一个节点。每次循环结束时 tail 永远是末尾节点的 next 值的可变引用，也就是 None。
更新 tail 时，由于 tail 是 head 的可变引用，只需要解引用 tail 把值设置成新创建的节点。
下一步是将 tail 更新为指向当前节点的 next。tail 是一个指向可变 next 的可变的引用 ，也就是说 tail 指向的数据可变，tail 本身也可变（就是可以更新 tail 指向的地址）。tail 目前是一个 &Option<Box<ListNode>>，通过调用 Option 的 as_mut() 方法，可以在不消耗自身的前提下得到一个 Option<&mut Box<ListNode>>，然后把这个 Option unwrap()，就得到了内部节点的 Box 指针。Box 指针有 Deref 强制转换，所以可以直接当作其内部的数据进行处理，内部数据 ListNode 的 next 就是 tail 需要指向的值。由于 tail 是指向可变 next 的可变的引用，所以其指向的内部数据也要可变，所以要在赋值时在等号右边加上 &mut 标识。
3. 无重复字符的最长子串
这道题很简单，可以直接看出是通过“滑动窗口“求结果的。
在其它语言中可以直接用两个指针来指向窗口的开始处和结束处，但是在 Rust 中不可以直接这样做，不过类似地，可以创建字串的两个没有所有权的带下标的迭代器，后续的操作和用指针非常类似。
但是我准备换种方法。同样的“滑动窗口“思路，可以用一个队列作为窗口，顺便还能起到字典的作用。
每读入一个新字符，从窗口后部 push 进新字符，并检查窗口中是否已经有这个字符，如果有，就从前部一直 pop 到这个字符被移出。在整个过程中窗口的最大长度就是最长子串长度。
use std::collections::VecDeque;
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let mut sub = VecDeque::new();
let mut max_len: usize = 0;
for letter in s.chars() {
if sub.contains(&letter) {
while let Some(front_of_sub) = sub.pop_front() {
if front_of_sub == letter {
break;
}
}
}
sub.push_back(letter);
if sub.len() > max_len {
max_len = sub.len();
}
}
max_len as i32
}
}
4. 寻找两个正序数组的中位数
题目要求算法的时间复杂度最好是 O(log(m+n))，包含 log 十有八九就是要用二分法。
但是首先实现一下双指针带顺序地拼接数组的方法，可以用到“状态机”：
impl Solution {
pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
let mut nums = Vec::with_capacity(nums1.len() + nums2.len());
let mut nums1_iter = nums1.iter();
let mut nums2_iter = nums2.iter();
let mut pattern = (nums1_iter.next(), nums2_iter.next());
loop {
pattern = match pattern {
(Some(num1), Some(num2)) => {
if num1 < num2 {
nums.push(num1);
(nums1_iter.next(), Some(num2))
} else {
nums.push(num2);
(Some(num1), nums2_iter.next())
}
}
(Some(num1), None) => {
nums.push(num1);
(nums1_iter.next(), None)
}
(None, Some(num2)) => {
nums.push(num2);
(None, nums2_iter.next())
}
(None, None) => break
};
}
if nums.len() % 2 == 0 {
(nums[nums.len() / 2 - 1] + nums[nums.len() / 2]) as f64 / 2.0
} else {
*nums[nums.len() / 2] as f64
}
}
}
这样的算法的时间复杂度和空间复杂度都是 O(m+n)，不符合题目要求，所以只能用二分法。
二分法的思路是 官方解法思路 的实现，都是用一条“分割线”将两个数组分别分开，由于中位数是两个数组长度之和的一半，所以用二分法查找较短的数组，效率最高。与“官方解法”不同的是对超出数组下标范围的处理二分查找时用了双开区间，而不是“官方解法”中的半开半闭。
时间复杂度是 O(log(min(m, n))) 优于题目要求的 O(log(m+n))，空间复杂度是常数 O(1)。
impl Solution {
pub fn find_median_sorted_arrays(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> f64 {
// 使用较短数组决定二分位置
if nums1.len() > nums2.len() {
std::mem::swap(&mut nums1, &mut nums2);
}
// 确定中位数分割线左侧元素个数，总元素个数为奇数时中位数处在分割线左侧
let total_left = (nums1.len() + nums2.len() + 1) / 2;
// 以 nums1 为标准设置二分指针，左右边界开区间
let mut left = 0;
let mut right = nums1.len();
let mut mid = left + (right - left + 1) / 2;
// 分割线左侧元素个数
let mut nums1_left = mid;
let mut nums2_left = total_left - nums1_left;
// 处于分界线左右
enum IndexPos {
Left,
Right,
}
// 防止数组为空值或只有一个元素，处理 get() 方法返回的 Result
fn get_elem_in_vec(vec: &Vec<i32>, idx: usize, pos: IndexPos) -> i32 {
*vec.get(idx).unwrap_or_else(|| match pos {
IndexPos::Left => &i32::MIN,
IndexPos::Right => &i32::MAX,
})
}
while left as i32 <= right as i32 {
// 分割线左侧元素个数
nums1_left = mid;
nums2_left = total_left - nums1_left;
if get_elem_in_vec(&nums1, nums1_left - 1, IndexPos::Left)
<= get_elem_in_vec(&nums2, nums2_left, IndexPos::Right)
&& get_elem_in_vec(&nums1, nums1_left, IndexPos::Right)
>= get_elem_in_vec(&nums2, nums2_left - 1, IndexPos::Left)
{
// nums1 分割线左侧元素小于 nums2 右侧元素且nums1 分割线右侧元素大于 nums2 左侧元素，查找成功
break;
} else if get_elem_in_vec(&nums1, nums1_left - 1, IndexPos::Left)
> get_elem_in_vec(&nums2, nums2_left, IndexPos::Right)
{
// nums1 分割线左侧元素大于 nums2 右侧元素，区间左移
right = mid - 1;
} else if get_elem_in_vec(&nums1, nums1_left, IndexPos::Right)
< get_elem_in_vec(&nums2, nums2_left - 1, IndexPos::Left)
{
// nums1 分割线右侧元素小于 nums2 左侧元素，区间右移
left = mid + 1;
}
// 更新分割线位置
mid = left + (right - left + 1) / 2;
}
// 获取中位数
if (nums1.len() + nums2.len()) % 2 == 0 {
// 长度为偶数，取左侧最大值与右侧最小值之平均数
let left_max = std::cmp::max(
get_elem_in_vec(&nums1, nums1_left - 1, IndexPos::Left),
get_elem_in_vec(&nums2, nums2_left - 1, IndexPos::Left),
);
let right_min = std::cmp::min(
get_elem_in_vec(&nums1, nums1_left, IndexPos::Right),
get_elem_in_vec(&nums2, nums2_left, IndexPos::Right),
);
(left_max + right_min) as f64 / 2.0
} else {
// 长度为奇数，取左侧最大值
std::cmp::max(
get_elem_in_vec(&nums1, nums1_left - 1, IndexPos::Left),
get_elem_in_vec(&nums2, nums2_left - 1, IndexPos::Left),
) as f64
}
}
}
理论上讲，Vec 的 get() 是 O(1) 的，所以用 get() 得到 Option 再进行处理，对时间复杂度没有影响。
但实际运行时，不知为何这样做的效果不如直接 nums.insert(0, i32::MIN) 和 nums.push(i32::MAX)。insert() 方法对数组头部插入元素的时间复杂度是 O(n)，但是却跑出了内存占用更少的成绩... 玄学
5. 最长回文子串
先将整个字符串转为 Vec<bytes> 方便处理。
回文字符串去掉收尾字符还是回文字符串，所以回文字符串长度有两种可能：奇数和偶数。这两种情况在遍历时都必须考虑，如果出现如“baaaab”这样的字符串，如果只考虑奇数，最长子串就成了 “aaa”。
use std::collections::VecDeque;
impl Solution {
pub fn longest_palindrome(s: String) -> String {
let mut longest = VecDeque::new();
let s = s.into_bytes();
for (idx, letter) in s.iter().enumerate() {
let mut current_even_len = VecDeque::new();
let mut current_odd_len = VecDeque::new();
current_odd_len.push_back(*letter);
let mut offset_even_len = 0;
let mut offset_odd_len = 1;
loop {
let mut can_be_even_len = true;
let mut can_be_odd_len = true;
if can_be_even_len
&& idx.checked_sub(offset_even_len).is_some()
&& idx + offset_even_len + 1 < s.len()
&& s[idx - offset_even_len] == s[idx + offset_even_len + 1]
{
current_even_len.push_front(s[idx - offset_even_len]);
current_even_len.push_back(s[idx + offset_even_len + 1]);
offset_even_len += 1;
} else {
can_be_even_len = false;
}
if can_be_odd_len
&& idx.checked_sub(offset_odd_len).is_some()
&& idx + offset_odd_len < s.len()
&& s[idx - offset_odd_len] == s[idx + offset_odd_len]
{
current_odd_len.push_front(s[idx - offset_odd_len]);
current_odd_len.push_back(s[idx + offset_odd_len]);
offset_odd_len += 1;
} else {
can_be_odd_len = false;
}
if !can_be_even_len && !can_be_odd_len {
if current_even_len.len() > longest.len() {
longest = current_even_len;
}
if current_odd_len.len() > longest.len() {
longest = current_odd_len;
}
break;
}
}
}
longest.into_iter().map(|c| c as char).collect::<String>()
}
}
6. Z 字形变换
这道题思路很简单，以面向过程的思想可以写出：
impl Solution {
pub fn convert(s: String, num_rows: i32) -> String {
if num_rows > 1 {
let mut rows = vec![Vec::new(); num_rows as usize];
let divisor = num_rows * 2 - 2;
for (idx, byte) in s.into_bytes().into_iter().enumerate() {
let row = num_rows - 1 - (idx as i32 % divisor - num_rows + 1).abs();
rows[row as usize].push(byte);
}
rows.into_iter()
.flatten()
.map(|c| c as char)
.collect::<String>()
} else {
s
}
}
}
这样写没有任何问题，只是代码中的 as 转换太多了，而且代码还不够“亮眼”，因为我在题解中看到了另一种方法：
impl Solution {
pub fn convert(s: String, num_rows: i32) -> String {
let num_rows = num_rows as usize;
let mut rows = vec![Vec::new(); num_rows];
let row_idx = (0..num_rows).chain((1..num_rows - 1).rev()).cycle();
row_idx
.zip(s.chars())
.for_each(|(row_idx, c)| rows[row_idx].push(c));
rows.into_iter().flatten().collect::<String>()
}
}
将 (0..num_rows) 和 (1..num_rows - 1).rev() 两个迭代器拼接后用 .cycle() 使其无限循环，这不就是目标行数吗😂
感谢惰性的迭代器和“零成本抽象”😂
7. 整数反转
可以用转换成 String 再反转的方法，这么做简单是简单，但就没有做题的意义了，而且应该不是最优解法：
impl Solution {
pub fn reverse(x: i32) -> i32 {
x.abs()
.to_string()
.chars()
.rev()
.collect::<String>()
.parse::<i32>()
.unwrap_or(0)
* x.signum()
}
}
常规做法是用 checked_*() 方法：
impl Solution {
pub fn reverse(x: i32) -> i32 {
let mut x_abs = x.abs();
let mut result_abs: i32 = 0;
while x_abs != 0 {
if let Some(n) = result_abs.checked_mul(10) {
result_abs = n;
} else {
result_abs = 0;
break;
}
if let Some(n) = result_abs.checked_add(x_abs % 10) {
result_abs = n;
} else {
result_abs = 0;
break;
}
x_abs /= 10;
}
result_abs * x.signum()
}
}
8. 字符串转换整数 (atoi)
用迭代器遍历字符，判断是不是数字字符，然后计算并检查溢出。其中检查溢出和上一题神似：
impl Solution {
pub fn my_atoi(s: String) -> i32 {
let mut s_iter = s.chars().skip_while(|c| c == &' ');
let mut result_abs = 0;
let mut signum: i32 = 1;
match s_iter.next() {
Some(c) if c == '+' => (),
Some(c) if c == '-' => signum = -1,
Some(c) if c >= '0' && c <= '9' => result_abs = c as i32 - 48,
_ => return 0,
}
while let Some(c) = s_iter.next() {
if c >= '0' && c <= '9' {
if let Some(n) = result_abs.checked_mul(10) {
result_abs = n;
} else {
return if signum.is_positive() {
i32::MAX
} else {
i32::MIN
};
}
if let Some(n) = result_abs.checked_add(c as i32 - 48) {
result_abs = n;
} else {
return if signum.is_positive() {
i32::MAX
} else {
i32::MIN
};
}
} else {
break;
}
}
result_abs * signum
}
}
9. 回文数
题目中说不要转换成字符串，换句话说就是不要用堆上内存，因为一般非常数空间复杂度的算法才会用到堆。
可以将整个数反转，因为是回文数所以不会溢出，官方题解中说会溢出我觉得不太对。不过我还是用了官方题解中的“反转一半”方法：
impl Solution {
pub fn is_palindrome(x: i32) -> bool {
if !x.is_negative() && (x % 10 != 0 || x == 0) {
let mut left = x;
let mut right = 0;
while left >= right {
right = right * 10 + left % 10;
if right == left || right == left / 10 {
return true;
}
left /= 10;
}
}
false
}
}
11. 盛最多水的容器
说实话刚开始根本没有想到双指针法，直到看了题解。
use std::cmp;
impl Solution {
pub fn max_area(height: Vec<i32>) -> i32 {
let mut left = 0;
let mut right = height.len() - 1;
let mut max = cmp::min(height[left], height[right]) * (right - left) as i32;
while left < right {
if height[left] <= height[right] {
left += 1;
} else {
right -= 1;
}
max = max.max(cmp::min(height[left], height[right]) * (right - left) as i32);
}
max
}
}
这个双指针法比较难理解，重点在于，向内移动较长的挡板时，面积 一定 会变小，所以移动较短的挡板可以将所有比初始状态面积大的情况遍历到。
12. 整数转罗马数字
数据规模只有 1~3999，那直接无脑手写了。
impl Solution {
pub fn int_to_roman(mut num: i32) -> String {
let thousands = num / 1000;
num %= 1000;
let hundreds = num / 100;
num %= 100;
let tens = num / 10;
let ones = num % 10;
let mut result = String::new();
for _ in 0.. thousands {
result.push('M');
}
match hundreds {
9 => result.push_str("CM"),
n if n < 9 && n > 4 => {
result.push('D');
for _ in 0..n - 5 {
result.push('C');
}
}
4 => result.push_str("CD"),
n => {
for _ in 0..n {
result.push('C');
}
}
}
match tens {
9 => result.push_str("XC"),
n if n < 9 && n > 4 => {
result.push('L');
for _ in 0..n - 5 {
result.push('X');
}
}
4 => result.push_str("XL"),
n => {
for _ in 0..n {
result.push('X');
}
}
}
match ones {
9 => result.push_str("IX"),
n if n < 9 && n > 4 => {
result.push('V');
for _ in 0..n - 5 {
result.push('I');
}
}
4 => result.push_str("IV"),
n => {
for _ in 0..n {
result.push('I');
}
}
}
result
}
}
13. 罗马数字转整数
十一放假，做几道简单题吧。
impl Solution {
pub fn roman_to_int(s: String) -> i32 {
fn byte_to_num(byte: u8) -> i32 {
match byte {
b'I' => 1,
b'V' => 5,
b'X' => 10,
b'L' => 50,
b'C' => 100,
b'D' => 500,
b'M' => 1000,
_ => 0,
}
}
let mut s_iter = s.into_bytes().into_iter();
let prev = s_iter.next();
let current = s_iter.next();
let mut result = byte_to_num(prev.unwrap());
let mut pattern = (prev, current);
while let (Some(prev), Some(current)) = pattern {
if byte_to_num(prev) >= byte_to_num(current) {
result += byte_to_num(current);
} else {
result += byte_to_num(current) - 2 * byte_to_num(prev);
}
pattern = (Some(current), s_iter.next());
}
result
}
}
14. 最长公共前缀
之所以在大多数涉及到 String 的题中都将 String 转成 [byte] 而不是 [char]，是因为 .into_bytes() 可以直接消耗掉 String，没有多余的 Copy 操作，从而性能更好。
impl Solution {
pub fn longest_common_prefix(strs: Vec<String>) -> String {
let mut longest = strs
.get(0)
.map_or_else(|| Vec::new(), |s| s.bytes().collect::<Vec<u8>>());
for s in strs.into_iter().skip(1) {
let s_length = s.len();
let mut s_iter = s.into_bytes().into_iter();
let mut longest_iter = longest.iter().enumerate();
while let (Some(byte_current), Some((idx, byte_longest))) =
(s_iter.next(), longest_iter.next())
{
if &byte_current != byte_longest {
for _ in 0..longest.len() - idx {
longest.pop();
}
break;
}
}
if longest.len() > s_length {
for _ in 0..longest.len() - s_length {
longest.pop();
}
}
}
longest.into_iter().map(|b| b as char).collect()
}
}
15. 三数之和
这道题很坑，主要是很容易超时。我最早的想法是照搬“两数之和”的解法，两次遍历数组，第二次遍历的时候查询字典中是否有合法的数字对，并把第一次和第二次正在遍历数组成数字对入字典，时间复杂度可以达到 O(n ^ 2)。所有的去重靠的都是 HashSet 和入字典前的排序。然而这方法就没有运行成功过，每次都是超时，我甚至手写了 Hasher：
use std::{
cmp,
collections::{HashMap, HashSet},
};
impl Solution {
pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut result = HashSet::with_hasher(BuildQuickHasher);
let mut map = HashMap::with_capacity_and_hasher(nums.len(), BuildQuickHasher);
for (idx_a, a) in nums.iter().enumerate() {
for (idx_b, b) in nums.iter().enumerate() {
if idx_a != idx_b {
let sum = map
.entry(*a + *b)
.or_insert(HashSet::with_hasher(BuildQuickHasher));
sum.insert((cmp::min(idx_a, idx_b), cmp::max(idx_a, idx_b)));
if let Some(sum) = map.get(&-b) {
for pair in sum {
if idx_b != pair.0 && idx_b != pair.1 {
let mut set = vec![nums[pair.0], nums[pair.1], *b];
if set[0] > set[1] {
set.swap(0, 1);
}
if set[1] > set[2] {
set.swap(1, 2);
}
if set[0] > set[1] {
set.swap(0, 1);
}
result.insert(set);
}
}
}
}
}
}
result.into_iter().collect()
}
}
pub struct QuickHasher(u64);
impl std::hash::Hasher for QuickHasher {
fn write(&mut self, bytes: &[u8]) {
let QuickHasher(mut hash) = *self;
for byte in bytes.iter() {
hash = hash ^ (*byte as u64);
hash = hash.wrapping_mul(0x100000001b3);
}
*self = QuickHasher(hash);
}
fn finish(&self) -> u64 {
self.0
}
}
pub struct BuildQuickHasher;
impl std::hash::BuildHasher for BuildQuickHasher {
type Hasher = QuickHasher;
fn build_hasher(&self) -> QuickHasher {
QuickHasher(0)
}
}
上面的问题在于哈希表的效率，看了题解之后才发现原来排序后可以更有效率地用双指针法。用标准库的快排算法，最差也只需要 O(n * log(n)) 时间，不会影响到总体的时间复杂度，所以可以很好地简化问题。
impl Solution {
pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut result: Vec<Vec<i32>> = Vec::new();
if nums.len() < 3 {
return result;
}
nums.sort_unstable();
let mut a = 0;
let (mut b, mut c) = (1, nums.len() - 1);
while nums[a] <= 0 && a + 2 < nums.len() {
while b < c {
if nums[a] + nums[b] + nums[c] == 0 {
result.push(vec![nums[a], nums[b], nums[c]]);
}
if nums[b] + nums[c] > -nums[a] {
c -= 1;
while c >= b && nums[c] == nums[c + 1] {
c -= 1;
}
} else {
b += 1;
while b <= c && nums[b] == nums[b - 1] {
b += 1;
}
}
}
a += 1;
while a + 1 < nums.len() && nums[a] == nums[a - 1] {
a += 1;
}
b = a + 1;
c = nums.len() - 1;
}
result
}
}
还可以进一步优化：剪枝。在循环开始时就判断本次循环是不是已经没有可能得到结果，从而减少循环次数。不过这道题剪不剪枝对最后的运行时长影响不大。
impl Solution {
pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut result: Vec<Vec<i32>> = Vec::new();
if nums.len() < 3 {
return result;
}
nums.sort_unstable();
let mut a = 0;
let (mut b, mut c) = (1, nums.len() - 1);
while nums[a] <= 0 && a + 2 < nums.len() {
if nums[a] + nums[a + 1] + nums[a + 2] > 0 {
break;
}
if nums[a] + nums[nums.len() - 2] + nums[nums.len() - 1] < 0 {
a += 1;
while a + 1 < nums.len() && nums[a] == nums[a - 1] {
a += 1;
}
b = a + 1;
c = nums.len() - 1;
continue;
}
while b < c {
if nums[a] + nums[b] + nums[b + 1] > 0 {
break;
}
if nums[a] + nums[b] + nums[nums.len() - 1] < 0 {
b += 1;
while b <= c && nums[b] == nums[b - 1] {
b += 1;
}
continue;
}
if nums[a] + nums[b] + nums[c] == 0 {
result.push(vec![nums[a], nums[b], nums[c]]);
}
if nums[b] + nums[c] > -nums[a] {
c -= 1;
while c >= b && nums[c] == nums[c + 1] {
c -= 1;
}
} else {
b += 1;
while b <= c && nums[b] == nums[b - 1] {
b += 1;
}
}
}
a += 1;
while a + 1 < nums.len() && nums[a] == nums[a - 1] {
a += 1;
}
b = a + 1;
c = nums.len() - 1;
}
result
}
}
16. 最接近的三数之和
这道题和上一道题简直一模一样，唯一的区别就是不能“剪枝”：
impl Solution {
pub fn three_sum_closest(mut nums: Vec<i32>, target: i32) -> i32 {
nums.sort_unstable();
let mut a = 0;
let (mut b, mut c) = (1, nums.len() - 1);
let mut closest = nums[a] + nums[b] + nums[c];
while a + 2 < nums.len() {
while b < c {
if (nums[a] + nums[b] + nums[c] - target).abs() < (closest - target).abs() {
closest = nums[a] + nums[b] + nums[c];
}
if nums[b] + nums[c] == target - nums[a] {
return target;
} else if nums[b] + nums[c] < target - nums[a] {
b += 1;
while b <= c && nums[b] == nums[b - 1] {
b += 1;
}
} else if nums[b] + nums[c] > target - nums[a] {
c -= 1;
while c >= b && nums[c] == nums[c + 1] {
c -= 1;
}
}
}
a += 1;
while a + 1 < nums.len() && nums[a] == nums[a - 1] {
a += 1;
}
b = a + 1;
c = nums.len() - 1;
}
closest
}
}
17. 电话号码的字母组合
这道题有 DFS 和 BFS 两种解法，我最开始想到的是 BFS，遍历字符，每次遍历都把结果的 Vec 中原本的各 String 复制数字对应字母个数 - 1 次，然后加上当前正在遍历的数字对应的字母：
impl Solution {
pub fn letter_combinations(digits: String) -> Vec<String> {
fn digit_to_chars(digit: u8) -> &'static [char] {
match digit {
b'2' => &['a', 'b', 'c'],
b'3' => &['d', 'e', 'f'],
b'4' => &['g', 'h', 'i'],
b'5' => &['j', 'k', 'l'],
b'6' => &['m', 'n', 'o'],
b'7' => &['p', 'q', 'r', 's'],
b'8' => &['t', 'u', 'v'],
b'9' => &['w', 'x', 'y', 'z'],
_ => unreachable!(),
}
}
let mut result = if !digits.is_empty() {
vec!["".to_string()]
} else {
return Vec::new();
};
for digit in digits.into_bytes().into_iter() {
let original_length = result.len();
let mut chars = digit_to_chars(digit).into_iter();
let first_char = chars.next().unwrap();
while let Some(char) = chars.next() {
for idx in 0..original_length {
let mut combination = result[idx].clone();
combination.push(*char);
result.push(combination);
}
}
for idx in 0..original_length {
result[idx].push(*first_char);
}
}
result
}
}
然后是 DFS 解法。说实话我对递归的理解还不太够，所以所以写出这个递归的回溯花了不少时间：
impl Solution {
pub fn letter_combinations(digits: String) -> Vec<String> {
fn digit_to_chars(digit: u8) -> &'static [char] {
match digit {
b'2' => &['a', 'b', 'c'],
b'3' => &['d', 'e', 'f'],
b'4' => &['g', 'h', 'i'],
b'5' => &['j', 'k', 'l'],
b'6' => &['m', 'n', 'o'],
b'7' => &['p', 'q', 'r', 's'],
b'8' => &['t', 'u', 'v'],
b'9' => &['w', 'x', 'y', 'z'],
_ => unreachable!(),
}
}
fn backtrack(
idx: usize,
digits: &Vec<u8>,
combination: &mut String,
result: &mut Vec<String>,
) {
if idx == digits.len() {
result.push(combination.clone());
return;
}
for char in digit_to_chars(digits[idx]) {
combination.push(*char);
backtrack(idx + 1, digits, combination, result);
combination.pop();
}
}
if digits.is_empty() {
return Vec::new();
}
let digits = digits.into_bytes();
let mut result = Vec::new();
backtrack(0, &digits, &mut String::new(), &mut result);
result
}
}
18. 四数之和
这题就是 15. 三数之和 的翻版，唯一的区别就是剪枝对结果的影响很大。剪枝前要跑 24ms，剪枝后直接变成 0ms：
impl Solution {
pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut result: Vec<Vec<i32>> = Vec::new();
if nums.len() < 3 {
return result;
}
nums.sort_unstable();
let mut a = 0;
let (mut b, mut c) = (1, nums.len() - 1);
while nums[a] <= 0 && a + 2 < nums.len() {
if nums[a] + nums[a + 1] + nums[a + 2] > 0 {
break;
}
if nums[a] + nums[nums.len() - 2] + nums[nums.len() - 1] < 0 {
a += 1;
while a + 1 < nums.len() && nums[a] == nums[a - 1] {
a += 1;
}
b = a + 1;
c = nums.len() - 1;
continue;
}
while b < c {
if nums[a] + nums[b] + nums[b + 1] > 0 {
break;
}
if nums[a] + nums[b] + nums[nums.len() - 1] < 0 {
b += 1;
while b <= c && nums[b] == nums[b - 1] {
b += 1;
}
continue;
}
if nums[a] + nums[b] + nums[c] == 0 {
result.push(vec![nums[a], nums[b], nums[c]]);
}
if nums[b] + nums[c] > -nums[a] {
c -= 1;
while c >= b && nums[c] == nums[c + 1] {
c -= 1;
}
} else {
b += 1;
while b <= c && nums[b] == nums[b - 1] {
b += 1;
}
}
}
a += 1;
while a + 1 < nums.len() && nums[a] == nums[a - 1] {
a += 1;
}
b = a + 1;
c = nums.len() - 1;
}
result
}
}
19. 删除链表的倒数第 N 个结点
这道题本身不难，然而用 Rust 写的话就不容易了。
一般来说，看到这种题首先想到的都是双指针法，然而由于 Rust 借用检查器的原因，想要同时有两个指针指向链表中的节点，要么得用 unsafe，要么就得把节点复制。
还是做题太少，我完全没有想到可以用回溯来做这道题，直到看到题解。
impl Solution {
pub fn remove_nth_from_end(mut head: Option<Box<ListNode>>, mut n: i32) -> Option<Box<ListNode>> {
fn backtrack(mut head: Option<Box<ListNode>>, n: &mut i32) -> Option<Box<ListNode>> {
match head.take() {
None => None,
Some(mut node) => {
let next = backtrack(node.next.take(), n);
*n -= 1;
if n == &0 {
next
} else {
node.next = next;
Some(node)
}
},
}
}
backtrack(head, &mut n)
}
}
利用递归，先把链表遍历到底，编程语言利用栈来实现递归，所以这一步事实上是把每个节点都拆开，依次压入栈中，然后再重新拼接成链表，同时从底部倒数 n 次，经过第 n 个元素时直接跳过。
20. 有效的括号
这是道简单题，然而我在最开始做的时候思路居然错了... 还好在提交之前就发现了。
用栈存储每个未闭合的括号，遇到右括号时检查有没有不匹配的未关闭的左括号。
impl Solution {
pub fn is_valid(s: String) -> bool {
let mut stack = Vec::new();
for byte in s.into_bytes().into_iter() {
match byte {
b'(' | b'{' | b'[' => stack.push(byte),
b')' => if stack.is_empty() || stack.pop().unwrap() != byte - 1 {
return false;
}
b'}' | b']' => if stack.is_empty() || stack.pop().unwrap() != byte - 2 {
return false;
}
_ => unreachable!()
}
}
stack.is_empty()
}
}
21. 合并两个有序链表
有了做 两数相加 的经验，这道题就简单了，思路几乎一模一样：
impl Solution {
pub fn merge_two_lists(mut l1: Option<Box<ListNode>>, mut l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut head = None;
let mut tail = &mut head;
let mut pattern = (l1, l2);
loop {
pattern = match pattern {
(Some(l1), Some(l2)) => {
if l1.val < l2.val {
*tail = Some(l1);
let l1 = tail.as_mut().unwrap().next.take();
tail = &mut tail.as_mut().unwrap().next;
(l1, Some(l2))
} else {
*tail = Some(l2);
let l2 = tail.as_mut().unwrap().next.take();
tail = &mut tail.as_mut().unwrap().next;
(Some(l1), l2)
}
}
(Some(list), None) | (None, Some(list)) => {
*tail = Some(list);
let list = tail.as_mut().unwrap().next.take();
tail = &mut tail.as_mut().unwrap().next;
(list, None)
}
_ => break,
}
}
head
}
}
22. 括号生成
不像 17. 电话号码的字母组合，由于有括号个数和闭合的限制，用 BFS 写起来非常复杂，用回溯应该是最简单的。（终于能一气呵成写出个能用的递归算法了）
impl Solution {
pub fn generate_parenthesis(n: i32) -> Vec<String> {
fn backtrack(
result: &mut Vec<String>,
path: &mut String,
generated: i32,
depth: i32,
n: i32,
) {
if generated == n && depth == 0 {
result.push(path.clone());
return;
}
if generated < n {
path.push('(');
backtrack(result, path, generated + 1, depth + 1, n);
path.pop();
}
if depth > 0 {
path.push(')');
backtrack(result, path, generated, depth - 1, n);
path.pop();
}
}
let mut result = Vec::new();
backtrack(&mut result, &mut String::new(), 0, 0, n);
result
}
}
36. 有效的数独
这题简单，不过可以考虑优化的地方很多。第一眼看这题，想到的肯定是用哈希表。
最开始我的做法是先把整个数独遍历一遍，把每个数作为键，Vec<位置> 作为值放进哈希表，然后再遍历哈希表验证每个数字都没有不合法的位置。
刚写了几行突然发现，验证位置合法这项操作可以直接整合进第一次遍历数独的时候就做啊，然后就改成了第一次遍历的时候顺便检查位置。
写完之后看了一下别人的题解，发现还有一个能优化的地方：由于只有 1～9 这九个数字，可以把哈希表换成定长数组，用数字的 char 减去 49 作为下标。在 Rust 中，元素超过 15 个之前，用 Vec 的 contains() 速度比哈希表快，所以换成数组可以变快一点。
最终结果是 0ms 执行时间 2MB 内存，不知道为什么内存消耗比较大，可能是因为初始化 Vec 的时候指定分配 9 个单元的内存。
impl Solution {
pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
let mut map: [Used; 9] = Default::default();
for (idx_row, row) in board.iter().enumerate() {
for (idx_col, cell) in row.iter().enumerate() {
if *cell != '.' {
let digit = *cell as usize - 49;
if map[digit].row.contains(&idx_row) // 横向检查
|| map[digit].col.contains(&idx_col) // 纵向检查
|| map[digit]
.zone
.contains(&(idx_row / 3, idx_col / 3)) // 区域检查
{
return false;
}
map[digit].push(idx_row, idx_col); // 位置合法，入字典
}
}
}
true
}
}
struct Used {
row: Vec<usize>,
col: Vec<usize>,
zone: Vec<(usize, usize)>,
}
impl Default for Used {
fn default() -> Self {
Self {
row: Vec::with_capacity(9),
col: Vec::with_capacity(9),
zone: Vec::with_capacity(9),
}
}
}
impl Used {
fn push(&mut self, row: usize, col: usize) {
self.row.push(row);
self.col.push(col);
self.zone.push((row / 3, col / 3));
}
}
58. 最后一个单词的长度
这道题的思路很简单，难点在于优化。看到题解中很多人用 trim 清理掉末尾空格后用 split() 根据空格分割字符串，这实际上是性能最差的方法。用字符串生成迭代器后反向遍历的性能更好，其中，转换为 byte 比转换为 char 后遍历的性能更佳。另外，在生成迭代器时，应该用带 into 的方法消耗所有权，因为后面不需要再用到这个字符串，这样就不会在内存中无用地做 Copy 操作了。
impl Solution {
pub fn length_of_last_word(s: String) -> i32 {
s.into_bytes()
.into_iter()
.rev()
.skip_while(|b| b == &b' ')
.take_while(|b| b != &b' ')
.count() as i32
}
}
162. 寻找峰值
我能想到的解法有滑动窗口和二分查找法。只有二分查找法能达到要求的时间复杂度 O(log n)。
滑动窗口，用长度为 3 的队列作为窗口，预填入 i32::MIN，遍历到末尾时也是与 i32::MIN 比较，用小于等于号比较。
use std::collections::VecDeque;
impl Solution {
pub fn find_peak_element(nums: Vec<i32>) -> i32 {
let mut queue = VecDeque::with_capacity(3);
queue.push_back(i32::MIN);
queue.push_back(i32::MIN);
queue.push_back(i32::MIN);
for (idx, num) in nums.iter().enumerate() {
queue.pop_front();
queue.push_back(*num);
if queue[1] > queue[0] && queue[1] >= queue[2] {
return idx as i32 - 1;
}
}
queue.pop_front();
queue.push_back(i32::MIN);
if queue[1] > queue[0] && queue[1] >= queue[2] {
return nums.len() as i32 - 1;
}
0
}
}
二分查找的关键点在于：如果当前位置比其左（右）侧元素小，那么峰值一定在其左（右）侧。根据这个条件就能确定二分区间：
impl Solution {
pub fn find_peak_element(nums: Vec<i32>) -> i32 {
let mut left = 0;
let mut right = nums.len() - 1;
let mut mid = left + (right - left) / 2;
while left as i32 <= right as i32 {
if &nums[mid] >= nums.get(mid - 1).unwrap_or(&i32::MIN)
&& &nums[mid] >= nums.get(mid + 1).unwrap_or(&i32::MIN)
{
break;
} else if &nums[mid] <= nums.get(mid + 1).unwrap_or(&i32::MIN) {
left = mid + 1;
} else if &nums[mid] <= nums.get(mid - 1).unwrap_or(&i32::MIN) {
right = mid - 1;
}
mid = left + (right - left) / 2;
}
mid as i32
}
}
187. 重复的 DNA 序列
用字典。这道题的关键在于优化，首先 String 的 into_bytes() 是 O(1) 的，而 chars().collect() 是 O(n) 的，所以一般来讲只要题目后续不再需要原 String，最好都将其转为 &[u8]；还有就是 HashMap 空间的预分配，在预分配前要跑 12ms，8MB 内存，预分配后直接变成了 4ms，5MB 内存。
use std::collections::HashMap;
impl Solution {
pub fn find_repeated_dna_sequences(s: String) -> Vec<String> {
if s.len() <= 10 {
return Vec::new();
}
let s = s.into_bytes();
let mut map = HashMap::<_, u16>::with_capacity(s.len());
for sub in s.windows(10) {
*map.entry(sub).or_insert(0) += 1;
}
map.into_iter()
.filter(|(_, count)| count > &1)
.map(|(sub, _)| sub.into_iter().map(|b| *b as char).collect::<String>())
.collect()
}
}
212. 单词搜索 II
这道题的有一个限制“同一个单元格内的字母在一个单词中不允许被重复使用”，然而我在写之前没有注意到这个限制，写完之后发现提交总是过不了。不论怎么改都一样。我在设计算法的时候就没有考虑到记录已经使用过的格子，所以最后变得这么麻烦。
我的思路是 字典 + 深度优先 + 周围单元格迭代：
首先将整个二维的 Vec 遍历一次，生成一个字典 HashMap<char, Vec<(usize, usize)>>，然后在将需要查找的单词转成 Vec<char>，用下标作为指针，逐个检查字母。
BFS 用队列，DFS 用栈，所以初始化一个栈用来存放待检查的单元格。在字典中查询单词首字母的位置，将其全部压入待检查栈。
循环出栈，对于每个出栈的位置，从字典中找到记录当前单词指针的下一个字母所在位置的 Vec<(usize, usize)>，然后用自实现的 Around 迭代器遍历当前位置周围的单元格，检查是否在刚才得到的 Vec 中，是的话就将它压入待检查栈。
目前还是没有解决同一单元格被多次使用的问题，已经卡在这里一整天了... 先暂时搁置，记录一下这个不完善的版本：
use std::collections::HashMap;
impl Solution {
pub fn find_words(board: Vec<Vec<char>>, words: Vec<String>) -> Vec<String> {
let board_size = (board.len(), board[0].len());
let mut map = HashMap::with_capacity(board_size.0 * board_size.1);
for (idx_row, row) in board.iter().enumerate() {
for (idx_col, cell) in row.iter().enumerate() {
let c = map.entry(*cell).or_insert(Vec::new());
c.push((idx_row, idx_col));
}
}
let mut result = Vec::new();
for word in words {
let mut found_word = false;
let word_chars: Vec<char> = word.chars().collect();
let mut current_ptr = 0;
if let Some(first_pos) = map.get(&word_chars[current_ptr]) {
// 初始化栈，用来存储(字母下标，位置坐标)
let mut pos_stack = Vec::new();
// 将首字母位置全部入栈
first_pos
.iter()
.for_each(|p| pos_stack.push((current_ptr, *p)));
// 当前正在遍历的位置
let mut current_pos = pos_stack.pop().unwrap().1;
loop {
// 是否在本次循环中找到下一个字符的位置
let mut found_next_char_pos = false;
// 下一个字符
let next_char = word_chars.get(current_ptr + 1);
match next_char {
// 当前位置在倒数第二个字母及之前
Some(next_char) => {
// 验证 map 中是否有下一个字母
if let Some(next_char_pos) = map.get(&next_char) {
// map 中有下一个字母，遍历当前位置的周围格
for arnd_pos in Around::from(¤t_pos, &board_size) {
// 若周围格内是下一个字母且未在单词已使用字母 list 中，入栈
if next_char_pos.contains(&arnd_pos) {
found_next_char_pos = true;
pos_stack.push((current_ptr + 1, arnd_pos));
}
}
} else {
// map 中没有下一个字母，匹配失败，跳出循环
break;
}
}
// 当前位置在倒数第一个字母
None => {
found_word = true;
break;
}
}
// 还有可遍历的位置
if let Some(next_pos) = pos_stack.pop() {
// 更新当前指针位置
if !found_next_char_pos {
current_ptr = next_pos.0;
} else {
current_ptr += 1;
}
current_pos = next_pos.1;
} else {
if next_char.is_none() {
found_word = true;
}
break;
}
}
if found_word {
result.push(word);
}
}
}
result
}
}
struct Around {
arnd_pos: [(i8, i8); 4],
offset: usize,
board_size: (i8, i8),
}
impl Around {
fn from(pos: &(usize, usize), board_size: &(usize, usize)) -> Self {
let (row, col) = (pos.0 as i8, pos.1 as i8);
Self {
arnd_pos: [
(row - 1, col),
(row, col + 1),
(row + 1, col),
(row, col - 1),
],
offset: 0,
board_size: (board_size.0 as i8, board_size.1 as i8),
}
}
}
impl Iterator for Around {
type Item = (usize, usize);
fn next(&mut self) -> Option<Self::Item> {
for (idx, (row, col)) in self.arnd_pos[self.offset..].iter().enumerate() {
if row >= &0 && col >= &0 && row < &self.board_size.0 && col < &self.board_size.1 {
self.offset += idx + 1;
return Some((*row as usize, *col as usize));
}
}
None
}
}
414. 第三大的数
很简单的一道每日一题。
impl Solution {
pub fn third_max(nums: Vec<i32>) -> i32 {
let mut max = (None, None, None);
for num in nums {
if max.0.is_none() || num > max.0.unwrap() {
max = (Some(num), max.0, max.1);
} else if (max.1.is_none() || num > max.1.unwrap()) && num < max.0.unwrap() {
max = (max.0, Some(num), max.1);
} else if (max.2.is_none() || num > max.2.unwrap())
&& (max.1.is_some() && num < max.1.unwrap())
{
max = (max.0, max.1, Some(num));
}
}
max.2.unwrap_or(max.0.unwrap())
}
}
434. 字符串中的单词数
简单题，几乎不用动脑：
impl Solution {
pub fn count_segments(s: String) -> i32 {
let mut result = 0;
let mut s_iter = s.into_bytes().into_iter();
let mut pattern = (b' ', s_iter.next());
loop {
pattern = match pattern {
(last_char, Some(current_char)) => {
if last_char == b' ' && current_char != b' ' {
result += 1;
}
(current_char, s_iter.next())
}
_ => break,
};
}
result
}
}
524. 通过删除字母匹配到字典里最长单词
我的做法是“双指针”法，用迭代器作为指针，分别遍历查找字串和目标字串：
impl Solution {
pub fn find_longest_word(s: String, dictionary: Vec<String>) -> String {
let mut longest = String::from("");
for word in dictionary {
let mut word_chars = word.chars();
let mut s_chars = s.chars();
let mut found_word = true;
while let Some(word_char) = word_chars.next() {
let mut found_letter = false;
while let Some(s_char) = s_chars.next() {
if word_char == s_char {
found_letter = true;
break;
}
}
if !found_letter {
found_word = false;
break;
}
}
if found_word {
if word.len() > longest.len() {
longest = word;
} else if word.len() == longest.len() {
let mut letter_of_word = word.chars();
let mut letter_of_longest = longest.chars();
while let (Some(letter_of_word), Some(letter_of_longest)) =
(letter_of_word.next(), letter_of_longest.next())
{
if (letter_of_word as u8) > (letter_of_longest as u8) {
break;
} else if (letter_of_word as u8) < (letter_of_longest as u8) {
longest = word;
break;
}
}
}
}
}
longest
}
}
（貌似并没有用到题目中提到的“删除”，毕竟在 String 中删除元素开销很大而且很麻烦）
650. 只有两个键的键盘
这道题可以比较容易地从数学角度找到规律：将给出的目标 n 因式分解然后把结果相加就做完了。重点在于因式分解的过程和对边缘数据的处理。
impl Solution {
pub fn min_steps(n: i32) -> i32 {
let mut result = Vec::new();
let mut m = n;
for i in 2..=m {
while n != i {
if m % i == 0 {
result.push(i);
m = m / i;
} else {
break;
}
}
}
if n == 1 {
0
} else {
if result.is_empty() {
n
} else {
result.iter().sum()
}
}
}
}
704. 二分查找
最简单的二分查找，然而由于用 Rust 所以有些坑需要注意。
首先是猴子也会的直接调用 Vec<T> 的 binary_search()，只要 T 是实现过 Ord trait 的类型就都能用：
impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
nums
.binary_search(&target)
.map_or_else(|_| -1, |idx| idx as i32);
}
}
然而不手写算法的话做题就没什么卵用了。题中说 Vec 中的每个元素都是唯一的，所以这题可以用直接二分和查询左（右）边界二分。
首先是直接二分，用闭区间表示搜索区域。与 C/C++ 不同，Rust 的默认下标类型是 usize，所以在右边界向左移动时，right = mid - 1 可能会导致 usize 变为 -1，也就是溢出了。然而溢出为没有关系，在循环起始的时候把左右边界的 usize 转成 i32 判断就好：
use std::cmp::Ordering;
impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
let mut left = 0;
let mut right = nums.len() - 1;
while left as i32 <= right as i32 {
let mid = left + (right - left) / 2;
match nums[mid].cmp(&target) {
Ordering::Equal => return mid as i32,
Ordering::Less => left = mid + 1,
Ordering::Greater => right = mid - 1,
}
}
-1
}
}
左边界二分法由于右边界是开区间，没有了上面的问题，只需要在最后判断一下有没有越界和有没有目标就好：
use std::cmp::Ordering;
impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
let mut left = 0;
let mut right = nums.len();
let mut mid = left + (right - left) / 2;
while left < right {
match nums[mid].cmp(&target) {
Ordering::Equal => right = mid,
Ordering::Less => left = mid + 1,
Ordering::Greater => right = mid,
}
mid = left + (right - left) / 2;
}
if left >= nums.len() || nums[left] != target {
-1
} else {
left as i32
}
}
}
取中点时用 left + (right - left) / 2 是为了防止 left + right 太大溢出，不过在这道题里没用。