目录
64. 最小路径和 Minimum Path Sum 🌟🌟
65. 有效数字 Valid Number 🌟🌟🌟
66. 加一 Plus One 🌟
🌟 每日一练刷题专栏 🌟
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
64. 最小路径和 Minimum Path Sum
给定一个包含非负整数的 m x n
网格 grid
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→1→1 的总和最小。
示例 2:
输入:grid = [[1,2,3],[4,5,6]] 输出:12
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
代码1:动态规划
fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut dp = vec![vec![0; n]; m];
dp[0][0] = grid[0][0];
for i in 1..m {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for j in 1..n {
dp[0][j] = dp[0][j-1] + grid[0][j];
}
for i in 1..m {
for j in 1..n {
dp[i][j] = std::cmp::min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
dp[m-1][n-1]
}
fn main() {
let grid1 = vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]];
println!("{}", min_path_sum(grid1));
let grid2 = vec![vec![1, 2, 3], vec![4, 5, 6]];
println!("{}", min_path_sum(grid2));
}
输出:
7
12
代码2:DFS
fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
dfs(&grid, m-1, n-1)
}
fn dfs(grid: &Vec<Vec<i32>>, i: usize, j: usize) -> i32 {
if i == 0 && j == 0 {
return grid[0][0];
}
let mut res = i32::max_value();
let mut left = i32::max_value();
if i > 0 {
res = dfs(grid, i-1, j);
}
if j > 0 {
left = dfs(grid, i, j-1);
}
if res > left {
res = left;
}
res + grid[i][j]
}
fn main() {
let grid1 = vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]];
println!("{}", min_path_sum(grid1));
let grid2 = vec![vec![1, 2, 3], vec![4, 5, 6]];
println!("{}", min_path_sum(grid2));
}
写成嵌套函数:
fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
fn dfs(grid: &Vec<Vec<i32>>, i: usize, j: usize) -> i32 {
if i == 0 && j == 0 {
return grid[0][0];
}
let mut res = i32::max_value();
let mut left = i32::max_value();
if i > 0 {
res = dfs(grid, i-1, j);
}
if j > 0 {
left = dfs(grid, i, j-1);
}
if res > left {
res = left;
}
res + grid[i][j]
}
dfs(&grid, grid.len()-1, grid[0].len()-1)
}
fn main() {
let grid1 = vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]];
println!("{}", min_path_sum(grid1));
let grid2 = vec![vec![1, 2, 3], vec![4, 5, 6]];
println!("{}", min_path_sum(grid2));
}
65. 有效数字 Valid Number
有效数字(按顺序)可以分成以下几个部分:
- 一个 小数 或者 整数
- (可选)一个
'e'
或'E'
,后面跟着一个 整数
小数(按顺序)可以分成以下几个部分:
- (可选)一个符号字符(
'+'
或'-'
) - 下述格式之一:
- 至少一位数字,后面跟着一个点
'.'
- 至少一位数字,后面跟着一个点
'.'
,后面再跟着至少一位数字 - 一个点
'.'
,后面跟着至少一位数字
- 至少一位数字,后面跟着一个点
整数(按顺序)可以分成以下几个部分:
- (可选)一个符号字符(
'+'
或'-'
) - 至少一位数字
部分有效数字列举如下:["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
部分无效数字列举如下:["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]
给你一个字符串 s
,如果 s
是一个 有效数字 ,请返回 true
。
示例 1:
输入:s = "0" 输出:true
示例 2:
输入:s = "e" 输出:false
示例 3:
输入:s = "." 输出:false
提示:
1 <= s.length <= 20
-
s
仅含英文字母(大写和小写),数字(0-9
),加号'+'
,减号'-'
,或者点'.'
。
代码:
fn is_number(s: String) -> bool {
let s = s.trim();
if s.is_empty() {
return false;
}
let mut has_num = false;
let mut has_dot = false;
let mut has_e = false;
for (i, ch) in s.chars().enumerate() {
match ch {
'0'..='9' => {
has_num = true;
}
'.' => {
if has_dot || has_e || i == s.len()-1 || (i == 0 && s.len() == 1) {
return false;
}
has_dot = true;
}
'e' | 'E' => {
if has_e || !has_num || i == s.len()-1 || i == 0 {
return false;
}
has_e = true;
has_num = false;
}
'+' | '-' => {
if i != 0 && (s.chars().nth(i-1) != Some('e') && s.chars().nth(i-1) != Some('E')) {
return false;
}
}
_ => {
return false;
}
}
}
has_num
}
fn main() {
println!("{}", is_number("0".to_string())); // output: true
println!("{}", is_number(" 0.1 ".to_string())); // output: true
println!("{}", is_number("abc".to_string())); // output: false
println!("{}", is_number("1 a".to_string())); // output: false
println!("{}", is_number("2e10".to_string())); // output: true
println!("{}", is_number(" -90e3 ".to_string())); // output: true
println!("{}", is_number(" 1e".to_string())); // output: false
println!("{}", is_number("e3".to_string())); // output: false
println!("{}", is_number(" 6e-1".to_string())); // output: true
println!("{}", is_number(" 99e2.5 ".to_string())); // output: false
println!("{}", is_number("53.5e93".to_string())); // output: true
println!("{}", is_number(" --6 ".to_string())); // output: false
println!("{}", is_number("-+3".to_string())); // output: false
println!("{}", is_number("95a54e53".to_string())); // output: false
}
输出:
true
true
false
false
true
true
false
false
true
false
true
false
false
false
66. 加一 Plus One
给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例 1:
输入:digits = [1,2,3] 输出:[1,2,4] 解释:输入数组表示数字 123。
示例 2:
输入:digits = [4,3,2,1] 输出:[4,3,2,2] 解释:输入数组表示数字 4321。
示例 3:
输入:digits = [0] 输出:[1]
提示:
1 <= digits.length <= 100
0 <= digits[i] <= 9
代码:
fn plus_one(digits: &mut Vec<i32>) -> Vec<i32> {
let n = digits.len();
for i in (0..n).rev() {
if digits[i] < 9 {
digits[i] += 1;
return digits.to_vec();
}
digits[i] = 0;
}
let mut res = vec![0; n+1];
res[0] = 1;
res
}
fn plus_one2(digits: &mut Vec<i32>) -> Vec<i32> {
let n = digits.len();
for i in (0..n).rev() {
if digits[i] < 9 {
digits[i] += 1;
for j in i+1..n {
digits[j] = 0;
}
return digits.to_vec();
}
}
let mut res = vec![0; n+1];
res[0] = 1;
res
}
fn plus_one3(digits: &mut Vec<i32>) -> Vec<i32> {
let mut carry = 0;
let n = digits.len();
digits[n-1] += 1;
for i in (0..n).rev() {
digits[i] += carry;
carry = digits[i] / 10;
digits[i] %= 10;
}
if carry > 0 {
digits.insert(0, 1);
}
digits.to_vec()
}
fn main() {
let mut digits = vec![4, 3, 2, 1];
println!("{:?}", plus_one(&mut digits));
let mut digits = vec![4, 3, 2, 1];
println!("{:?}", plus_one2(&mut digits));
let mut digits = vec![4, 3, 2, 1];
println!("{:?}", plus_one3(&mut digits));
}
输出:
[4, 3, 2, 2]
[4, 3, 2, 2]
[4, 3, 2, 2]
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页: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)暂停更 |
|
文章来源:https://www.toymoban.com/news/detail-472889.html |
Java每日一练 专栏(2023.3.11~2023.5.18)暂停更文章来源地址https://www.toymoban.com/news/detail-472889.html |
到了这里,关于Rust每日一练(Leetday0022) 最小路径和、有效数字、加一的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!