34. 查找元素的首末位置 Find-first-and-last-position-of-element-in-sorted-array 🌟🌟
原标题：在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9
代码：二分法
对于查找左边界，设置一个变量 left，初始值为 -1，表示目标值在数组中不存在。然后用二分法查找目标值，如果找到目标值，就更新 left 的值，并继续在左半边查找，直到找到最左边的目标值。对于查找右边界，设置另一个变量 right，初始值为 -1，然后用类似的方法查找目标值的右边界。 最后，判断 left 是否等于 -1，如果是，说明目标值在数组中不存在，直接返回 [-1, -1]。 否则，返回 [left, right]。
fn search_range(nums: &[i32], target: i32) -> [i32; 2] { let (mut left, mut right) = (-1, -1); if nums.len() ==0 { return [left, right] } // 查找左边界 let (mut l, mut r) = (0, nums.len() - 1); while l <= r { let mid = l + (r - l) / 2; if nums[mid] == target { left = mid as i32; r = mid - 1; } else if nums[mid] > target { r = mid - 1; } else { l = mid + 1; } } // 如果左边界没找到，直接返回 if left == -1 { return [-1, -1]; } // 查找右边界 let (mut l, mut r) = (0, nums.len() - 1); while l <= r { let mid = l + (r - l) / 2; if nums[mid] == target { right = mid as i32; l = mid + 1; } else if nums[mid] > target { r = mid - 1; } else { l = mid + 1; } } [left, right] } fn main() { let nums = vec![5, 7, 7, 8, 8, 10]; println!("{:?}", search_range(&nums, 8)); println!("{:?}", search_range(&nums, 6)); let nums: Vec<i32> = Vec::new(); println!("{:?}", search_range(&nums, 0)); }
输出：
[3, 4]
[-1, -1]
[-1, -1]
35. 搜索插入位置 Search Insert Position 🌟
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为 无重复元素 的 升序 排列数组
-10^4 <= target <= 10^4
代码：
用二分法查找目标值，如果找到目标值，就返回其索引；如果目标值不在数组中，就返回它应该插入的位置。
具体实现：用两个指针 l 和 r，分别指向数组的左边界和右边界。然后用二分法查找目标值。每次查找时，取中间位置 mid，然后将目标值与 nums[mid] 进行比较。如果相等，就返回 mid；如果目标值小于 nums[mid]，就将右边界 r 更新为 mid-1；如果目标值大于 nums[mid]，就将左边界 l 更新为 mid+1。最后，如果目标值不在数组中，就返回左边界 l。
fn search_insert(nums: &[i32], target: i32) -> usize { let (mut l, mut r) = (0, nums.len() - 1); while l <= r { let mid = l + (r - l) / 2; if nums[mid] == target { return mid; } else if nums[mid] > target { r = mid - 1; } else { l = mid + 1; } } l } fn main() { let nums = vec![1, 3, 5, 6]; println!("{}", search_insert(&nums, 5)); println!("{}", search_insert(&nums, 2)); println!("{}", search_insert(&nums, 7)); }
输出：
2
1
4
36. 有效的数独 Valid Sudoku 🌟🌟
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。
示例 1：
输入：board = [["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]] 输出：true
示例 2：
输入：board =
[["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'
代码：
用三个数组来表示行、列、小九宫： rows、cols 和 boxs。
其中，rows[i][num] 表示第 i 行是否出现过数字 num，
cols[j][num] 表示第 j 列是否出现过数字 num，
boxs[k][num] 表示第 k 个子数独是否出现过数字 num。
遍历数独每一个位置，如果该位置为数字，则判断该数字在当前位置所在的行、列、小九宫中是否已经出现过。如果已经出现过，则该数独无效；否则，将其记录在对应的数组中。
use std::collections::HashSet; fn is_valid_sudoku(board: &[Vec<char>]) -> bool { let mut rows = vec![HashSet::new(); 9]; let mut cols = vec![HashSet::new(); 9]; let mut boxes = vec![HashSet::new(); 9]; for i in 0..9 { for j in 0..9 { if board[i][j] == '.' { continue; } let num = board[i][j]; if rows[i].contains(&num) || cols[j].contains(&num) || boxes[(i / 3) * 3 + j / 3].contains(&num) { return false; } rows[i].insert(num); cols[j].insert(num); boxes[(i / 3) * 3 + j / 3].insert(num); } } true } fn main() { let board = vec![ vec!['5', '3', '.', '.', '7', '.', '.', '.', '.'], vec!['6', '.', '.', '1', '9', '5', '.', '.', '.'], vec!['.', '9', '8', '.', '.', '.', '.', '6', '.'], vec!['8', '.', '.', '.', '6', '.', '.', '.', '3'], vec!['4', '.', '.', '8', '.', '3', '.', '.', '1'], vec!['7', '.', '.', '.', '2', '.', '.', '.', '6'], vec!['.', '6', '.', '.', '.', '.', '2', '8', '.'], vec!['.', '.', '.', '4', '1', '9', '.', '.', '5'], vec!['.', '.', '.', '.', '8', '.', '.', '7', '9'], ]; println!("{}", is_valid_sudoku(&board)); let board = vec![ vec!['8', '3', '.', '.', '7', '.', '.', '.', '.'], vec!['6', '.', '.', '1', '9', '5', '.', '.', '.'], vec!['.', '9', '8', '.', '.', '.', '.', '6', '.'], vec!['8', '.', '.', '.', '6', '.', '.', '.', '3'], vec!['4', '.', '.', '8', '.', '3', '.', '.', '1'], vec!['7', '.', '.', '.', '2', '.', '.', '.', '6'], vec!['.', '6', '.', '.', '.', '.', '2', '8', '.'], vec!['.', '.', '.', '4', '1', '9', '.', '.', '5'], vec!['.', '.', '.', '.', '8', '.', '.', '7', '9'], ]; println!("{}", is_valid_sudoku(&board)); }
输出：
true
false
