目錄
73. 矩陣置零 Set Matrix Zeroes??????
74. 搜索二維矩陣 Search A 2d-Matrix??????
75. 顏色分類 Sort Colors??????
?? 每日一練刷題專欄???
Rust每日一練 專欄
Golang每日一練 專欄
Python每日一練 專欄
C/C++每日一練 專欄
Java每日一練 專欄
73. 矩陣置零 Set Matrix Zeroes
給定一個?m?x?n?的矩陣，如果一個元素為?0?，則將其所在行和列的所有元素都設為?0?。請使用原地算法。
示例 1：
輸入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 輸出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
輸入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 輸出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示：
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-2^31?<= matrix[i][j] <= 2^31?- 1
進階：
- 一個直觀的解決方案是使用 ?
O(mn)?的額外空間，但這并不是一個好的解決方案。 - 一個簡單的改進方案是使用?
O(m+n)?的額外空間，但這仍然不是最好的解決方案。 - 你能想出一個僅使用常量空間的解決方案嗎？
代碼1：
fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
let m = matrix.len();
let n = matrix[0].len();
let mut row = vec![false; m];
let mut col = vec![false; n];
for i in 0..m {
for j in 0..n {
if matrix[i][j] == 0 {
row[i] = true;
col[j] = true;
}
}
}
for i in 0..m {
for j in 0..n {
if row[i] || col[j] {
matrix[i][j] = 0;
}
}
}
}
fn main() {
let mut matrix = vec![vec![1, 1, 1], vec![1, 0, 1], vec![1, 1, 1]];
set_zeroes(&mut matrix);
println!("{:?}", matrix);
matrix = vec![vec![0, 1, 2, 0], vec![3, 4, 5, 2], vec![1, 3, 1, 5]];
set_zeroes(&mut matrix);
println!("{:?}", matrix);
}
輸出：
[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
?代碼2：
fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
let m = matrix.len();
let n = matrix[0].len();
let mut row0 = false;
let mut col0 = false;
for i in 0..m {
for j in 0..n {
if matrix[i][j] == 0 {
if i == 0 {
row0 = true;
}
if j == 0 {
col0 = true;
}
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for i in 1..m {
for j in 1..n {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0;
}
}
}
if row0 {
for j in 0..n {
matrix[0][j] = 0;
}
}
if col0 {
for i in 0..m {
matrix[i][0] = 0;
}
}
}
fn main() {
let mut matrix = vec![vec![1, 1, 1], vec![1, 0, 1], vec![1, 1, 1]];
set_zeroes(&mut matrix);
println!("{:?}", matrix);
matrix = vec![vec![0, 1, 2, 0], vec![3, 4, 5, 2], vec![1, 3, 1, 5]];
set_zeroes(&mut matrix);
println!("{:?}", matrix);
}74. 搜索二維矩陣 Search A 2d-Matrix
編寫一個高效的算法來判斷?m x n?矩陣中，是否存在一個目標值。該矩陣具有如下特性：
- 每行中的整數(shù)從左到右按升序排列。
- 每行的第一個整數(shù)大于前一行的最后一個整數(shù)。
示例 1：
輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 輸出：true
示例 2：
輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 輸出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-10^4?<= matrix[i][j], target <= 10^4
代碼1：
fn search_matrix(matrix: &Vec<Vec<i32>>, target: i32) -> bool {
let m = matrix.len();
let n = matrix[0].len();
let mut l = 0;
let mut r = m * n - 1;
while l <= r {
let mid = (l + r) >> 1;
if matrix[mid / n][mid % n] == target {
return true;
} else if matrix[mid / n][mid % n] < target {
l = mid + 1;
} else {
r = mid - 1;
}
}
false
}
fn main() {
let matrix = vec![vec![1, 3, 5, 7], vec![10, 11, 16, 20], vec![23, 30, 34, 60]];
println!("{}", search_matrix(&matrix, 3));
println!("{}", search_matrix(&matrix, 13));
}輸出：
true
false
代碼2：
fn search_matrix(matrix: &Vec<Vec<i32>>, target: i32) -> bool {
let m = matrix.len();
let n = matrix[0].len();
let (mut l, mut r) = (0, m - 1);
while l <= r {
let mid = (l + r) >> 1;
if matrix[mid][0] == target {
return true;
} else if matrix[mid][0] < target {
l = mid + 1;
} else {
r = mid - 1;
}
}
let row = r;
let (mut l, mut r) = (0, n - 1);
while l <= r {
let mid = (l + r) >> 1;
if matrix[row][mid] == target {
return true;
} else if matrix[row][mid] < target {
l = mid + 1;
} else {
r = mid - 1;
}
}
false
}
fn main() {
let matrix = vec![vec![1, 3, 5, 7], vec![10, 11, 16, 20], vec![23, 30, 34, 60]];
println!("{}", search_matrix(&matrix, 3));
println!("{}", search_matrix(&matrix, 13));
}75. 顏色分類 Sort Colors
給定一個包含紅色、白色和藍色、共?n?個元素的數(shù)組?nums，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列。
我們使用整數(shù)?0、?1?和?2?分別表示紅色、白色和藍色。
必須在不使用庫的sort函數(shù)的情況下解決這個問題。
示例 1：
輸入：nums = [2,0,2,1,1,0] 輸出：[0,0,1,1,2,2]
示例 2：
輸入：nums = [2,0,1] 輸出：[0,1,2]
提示：
n == nums.length1 <= n <= 300-
nums[i]?為?0、1?或?2
進階：
- 你可以不使用代碼庫中的排序函數(shù)來解決這道題嗎？
- 你能想出一個僅使用常數(shù)空間的一趟掃描算法嗎？
?代碼1：
fn sort_colors(nums: &mut Vec<i32>) {
let mut count = vec![0; 3];
for &num in nums.iter() {
count[num as usize] += 1;
}
let mut index = 0;
for i in 0..3 {
for _ in 0..count[i] {
nums[index] = i as i32;
index += 1;
}
}
}
fn main() {
let mut nums = vec![2, 0, 2, 1, 1, 0];
sort_colors(&mut nums);
println!("{:?}", nums);
nums = vec![2, 0, 1];
sort_colors(&mut nums);
println!("{:?}", nums);
}代碼2：
fn sort_colors(nums: &mut Vec<i32>) {
let mut index = 0;
for i in 0..nums.len() {
if nums[i] == 0 {
nums.swap(i, index);
index += 1;
}
}
for i in index..nums.len() {
if nums[i] == 1 {
nums.swap(i, index);
index += 1;
}
}
}
fn main() {
let mut nums = vec![2, 0, 2, 1, 1, 0];
sort_colors(&mut nums);
println!("{:?}", nums);
nums = vec![2, 0, 1];
sort_colors(&mut nums);
println!("{:?}", nums);
}代碼3：
fn sort_colors(nums: &mut Vec<i32>) {
let (mut left, mut right) = (0, nums.len() - 1);
let mut i = 0;
while i <= right {
if nums[i] == 0 {
nums.swap(i, left);
left += 1;
i += 1;
} else if nums[i] == 2 {
nums.swap(i, right);
right -= 1;
} else {
i += 1;
}
}
}
fn main() {
let mut nums = vec![2, 0, 2, 1, 1, 0];
sort_colors(&mut nums);
println!("{:?}", nums);
nums = vec![2, 0, 1];
sort_colors(&mut nums);
println!("{:?}", nums);
}輸出：
[0, 0, 1, 1, 2, 2]
[0, 1, 2]
?? 每日一練刷題專欄???
? 持續(xù)，努力奮斗做強刷題搬運工！
?? 點贊，你的認可是我堅持的動力！?
???收藏，你的青睞是我努力的方向！?
? 評論，你的意見是我進步的財富！??
??主頁：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）暫停更文章來源地址http://www.zghlxwxcb.cn/news/detail-512309.html |
文章來源：http://www.zghlxwxcb.cn/news/detail-512309.html到了這里，關(guān)于Rust每日一練(Leetday0025) 矩陣置零、搜索二維矩陣、顏色分類的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
