0
0

Rust每日一练(Leetday0012) 首末位置、插入位置、有效数独

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. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 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

🌟 每日一练刷题专栏 🌟

✨持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

✎ 评论，你的意见是我进步的财富！

☸ 主页：https://hannyang.blog.csdn.net/

Rust每日一练 专栏

（2023.5.16~）更新中...

Golang每日一练 专栏

（2023.3.11~）更新中...

Python每日一练 专栏

（2023.2.18~2023.5.18）暂停更

C/C++每日一练 专栏

（2023.2.18~2023.5.18）暂停更

Java每日一练 专栏

（2023.3.11~2023.5.18）暂停更

标签： golang leetcode 二分算法
本文转载自: https://blog.csdn.net/boysoft2002/article/details/130892726
版权归原作者 Hann Yang 所有， 如有侵权，请联系我们删除。
登录后发布评论

“Rust每日一练(Leetday0012) 首末位置、插入位置、有效数独”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

【保姆级教程】实操 Linux 磁盘管理：硬盘选型 & 分区挂载

通过visual studio进行dump文件调试和分析

开源低代码平台-Microi吾码-V8函数列表-后端

rabbitMQ

web渗透测试漏洞复现：Springboot Actuator未授权漏洞复现

如何给SaaS应用做安全

【软件测试】自动化常用函数

文章导航