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.lengthn == grid[i].length1 <= m, n <= 2000 <= 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 <= 20s仅含英文字母（大写和小写），数字（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 <= 1000 <= 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）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
