目錄

34. 查找元素的首末位置 Find-first-and-last-position-of-element-in-sorted-array??????

35. 搜索插入位置 Search Insert Position????

36. 有效的數(shù)獨 Valid Sudoku??????

?? 每日一練刷題專欄???

Rust每日一練 專欄

Golang每日一練 專欄

Python每日一練 專欄

C/C++每日一練 專欄

Java每日一練 專欄

34. 查找元素的首末位置 Find-first-and-last-position-of-element-in-sorted-array??????

原標題：在排序數(shù)組中查找元素的第一個和最后一個位置

給定一個按照升序排列的整數(shù)數(shù)組?nums，和一個目標值?target。找出給定目標值在數(shù)組中的開始位置和結束位置。

如果數(shù)組中不存在目標值?target，返回?[-1, -1]。

進階：

• 你可以設計并實現(xiàn)時間復雜度為?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?是一個非遞減數(shù)組
• -10^9?<= target?<= 10^9

代碼：二分法

對于查找左邊界，設置一個變量 left，初始值為 -1，表示目標值在數(shù)組中不存在。然后用二分法查找目標值，如果找到目標值，就更新 left 的值，并繼續(xù)在左半邊查找，直到找到最左邊的目標值。對于查找右邊界，設置另一個變量 right，初始值為 -1，然后用類似的方法查找目標值的右邊界。 最后，判斷 left 是否等于 -1，如果是，說明目標值在數(shù)組中不存在，直接返回 [-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????

給定一個排序數(shù)組和一個目標值，在數(shù)組中找到目標值，并返回其索引。如果目標值不存在于數(shù)組中，返回它將會被按順序插入的位置。

請必須使用時間復雜度為?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?為?無重復元素?的?升序?排列數(shù)組
• -10^4?<= target <= 10^4

代碼：

用二分法查找目標值，如果找到目標值，就返回其索引；如果目標值不在數(shù)組中，就返回它應該插入的位置。
具體實現(xiàn)：用兩個指針 l 和 r，分別指向數(shù)組的左邊界和右邊界。然后用二分法查找目標值。每次查找時，取中間位置 mid，然后將目標值與 nums[mid] 進行比較。如果相等，就返回 mid；如果目標值小于 nums[mid]，就將右邊界 r 更新為 mid-1；如果目標值大于 nums[mid]，就將左邊界 l 更新為 mid+1。最后，如果目標值不在數(shù)組中，就返回左邊界 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. 有效的數(shù)獨 Valid Sudoku??????

請你判斷一個?9 x 9?的數(shù)獨是否有效。只需要?根據(jù)以下規(guī)則?，驗證已經(jīng)填入的數(shù)字是否有效即可。

1. 數(shù)字?1-9?在每一行只能出現(xiàn)一次。
2. 數(shù)字?1-9?在每一列只能出現(xiàn)一次。
3. 數(shù)字?1-9?在每一個以粗實線分隔的?3x3?宮內(nèi)只能出現(xiàn)一次。（請參考示例圖）

注意：

• 一個有效的數(shù)獨（部分已被填充）不一定是可解的。
• 只需要根據(jù)以上規(guī)則，驗證已經(jīng)填入的數(shù)字是否有效即可。
• 空白格用?'.'?表示。

示例 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
解釋：除了第一行的第一個數(shù)字從 5 改為 8 以外，空格內(nèi)其他數(shù)字均與 示例1 相同。 但由于位于左上角的 3x3 宮內(nèi)有兩個 8 存在, 因此這個數(shù)獨是無效的。

提示：

• board.length == 9
• board[i].length == 9
• board[i][j]?是一位數(shù)字（1-9）或者?'.'

代碼：

用三個數(shù)組來表示行、列、小九宮： rows、cols 和 boxs。
其中，rows[i][num] 表示第 i 行是否出現(xiàn)過數(shù)字 num，
cols[j][num] 表示第 j 列是否出現(xiàn)過數(shù)字 num，
boxs[k][num] 表示第 k 個子數(shù)獨是否出現(xiàn)過數(shù)字 num。
遍歷數(shù)獨每一個位置，如果該位置為數(shù)字，則判斷該數(shù)字在當前位置所在的行、列、小九宮中是否已經(jīng)出現(xiàn)過。如果已經(jīng)出現(xiàn)過，則該數(shù)獨無效；否則，將其記錄在對應的數(shù)組中。

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

?? 每日一練刷題專欄???

? 持續(xù)，努力奮斗做強刷題搬運工！

?? 點贊，你的認可是我堅持的動力！?

???收藏，你的青睞是我努力的方向！?

? 評論，你的意見是我進步的財富！??

??主頁：https://hannyang.blog.csdn.net/

到了這里，關于Rust每日一練(Leetday0012) 首末位置、插入位置、有效數(shù)獨的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！