Rust每日一练(Leetday0022) 最小路径和、有效数字、加一

这篇具有很好参考价值的文章主要介绍了Rust每日一练(Leetday0022) 最小路径和、有效数字、加一。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Rust每日一练(Leetday0022) 最小路径和、有效数字、加一

目录

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:

Rust每日一练(Leetday0022) 最小路径和、有效数字、加一

输入: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

有效数字(按顺序)可以分成以下几个部分:

  1. 一个 小数 或者 整数
  2. (可选)一个 'e' 或 'E' ,后面跟着一个 整数

小数(按顺序)可以分成以下几个部分:

  1. (可选)一个符号字符('+' 或 '-'
  2. 下述格式之一:
    1. 至少一位数字,后面跟着一个点 '.'
    2. 至少一位数字,后面跟着一个点 '.' ,后面再跟着至少一位数字
    3. 一个点 '.' ,后面跟着至少一位数字

整数(按顺序)可以分成以下几个部分:

  1. (可选)一个符号字符('+' 或 '-'
  2. 至少一位数字

部分有效数字列举如下:["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每日一练(Leetday0022) 最小路径和、有效数字、加一

Rust每日一练 专栏

(2023.5.16~)更新中...

Rust每日一练(Leetday0022) 最小路径和、有效数字、加一

Golang每日一练 专栏

(2023.3.11~)更新中...

Rust每日一练(Leetday0022) 最小路径和、有效数字、加一

Python每日一练 专栏

(2023.2.18~2023.5.18)暂停更

Rust每日一练(Leetday0022) 最小路径和、有效数字、加一

C/C++每日一练 专栏

(2023.2.18~2023.5.18)暂停更

Rust每日一练(Leetday0022) 最小路径和、有效数字、加一

Java每日一练 专栏

(2023.3.11~2023.5.18)暂停更文章来源地址https://www.toymoban.com/news/detail-472889.html

到了这里,关于Rust每日一练(Leetday0022) 最小路径和、有效数字、加一的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Rust每日一练(Leetday0031) 解码方法、复原 IP 地址

    目录 91. 解码方法  Decode Ways  🌟🌟 93. 复原 IP 地址 Restore IP Addresses  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 一条包含字母  A-Z  的消息通过以下映射进行了  编码  : 要  解码  已编码的消息,所有

    2024年02月09日
    浏览(37)
  • Golang每日一练(leetDay0116) 路径交叉、回文对

    目录 335. 路径交叉 Self-crossing  🌟🌟🌟 336. 回文对 Palindrome Pairs  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给你一个整数数组  distance   。 从  X-Y  平面上的点  (0,0)  开始,先向北

    2024年02月12日
    浏览(38)
  • Rust每日一练(Leetday0025) 矩阵置零、搜索二维矩阵、颜色分类

    目录 73. 矩阵置零 Set Matrix Zeroes  🌟🌟 74. 搜索二维矩阵 Search A 2d-Matrix  🌟🌟 75. 颜色分类 Sort Colors  🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给定一个  m  x  n  的矩阵,如果一个元

    2024年02月11日
    浏览(62)
  • Rust每日一练(Leetday0029) 柱状图、最大矩形、扰乱字符串

    目录 84. 柱状图中最大的矩形 Largest-rectangle-in-histogram  🌟🌟🌟 85. 最大矩形 Maximal Rectangle  🌟🌟🌟 87. 扰乱字符串 Scramble String  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给定  n

    2024年02月09日
    浏览(48)
  • Rust每日一练(Leetday0020) 最后单词的长度、螺旋矩阵II、排列序列

    目录 58. 最后一个单词的长度 Length of Last Word  🌟 59. 螺旋矩阵 II Spiral Matrix II  🌟🌟 60. 排列序列 Permutation Sequence  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给你一个字符串  s ,由

    2024年02月10日
    浏览(50)
  • Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏

    目录 289. 生命游戏 Game Of Life  🌟🌟 292. Nim 游戏 Nim Game  🌟 299. 猜数字游戏 Bulls and Cows  🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 生命游戏   是英国数学家约翰·何顿·康威在 1970 年发

    2024年02月09日
    浏览(38)
  • Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II

    目录 79. 单词搜索 Word Search  🌟🌟 80. 删除有序数组中的重复项 II Remove-duplicates-from-sorted-array-II  🌟🌟 81. 搜索旋转排序数组 II Search-in-rotated-sorted-array-II  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给定一

    2024年02月08日
    浏览(43)
  • Golang每日一练(leetDay0052) 寻找旋转排序数组中的最小值I\II

    目录 153. 寻找旋转排序数组中的最小值 Find Minimum In Rotated Sorted Array  🌟🌟 154. 寻找旋转排序数组中的最小值 II Find Minimum In Rotated Sorted Array II  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 已知一个长度为

    2024年02月16日
    浏览(38)
  • Golang每日一练(leetDay0114) 矩阵中的最长递增路径、按要求补齐数组

    目录 329. 矩阵中的最长递增路径 Longest Increasing Path In A Matrix  🌟🌟 330. 按要求补齐数组 Patching Array  🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给定一个  m x n  整数矩阵  matrix  ,找出

    2024年02月12日
    浏览(48)
  • C/C++每日一练(20230314) 移动数组元素、搜索二维矩阵、三角形最小路径和

    目录 1. 移动数组中的元素 2. 搜索二维矩阵 3. 三角形最小路径和 🌟 每日一练刷题专栏 🌟 Golang 每日一练 专栏 C/C++ 每日一练 ​专栏 Python 每日一练 专栏 Java 每日一练 专栏 将一维数组中的元素循环左移 k 个位置 输入: 第 1 行是一维数组元素的个数 n (数组大小) 第 2 行是

    2024年02月13日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包