Rust每日一练(Leetday0015) 字符串相乘、通配符匹配、跳跃游戏II-LMLPHP

目录

43. 字符串相乘 Multiply Strings  🌟🌟

44. 通配符匹配 Wildcard Matching  🌟🌟🌟

45. 跳跃游戏 II Jump Game II  🌟🌟

🌟 每日一练刷题专栏 🌟

Rust每日一练 专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏


43. 字符串相乘 Multiply Strings

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示:

  • 1 <= num1.length, num2.length <= 200
  • num1 和 num2 只能由数字组成。
  • num1 和 num2 都不包含任何前导零,除了数字0本身。

代码:

fn multiply(num1: String, num2: String) -> String {
    if num1 == "0" || num2 == "0" {
        return String::from("0");
    }
    let (m, n) = (num1.len(), num2.len());
    let mut ans_arr: Vec<i32> = vec![0; m+n];
    let num1_bytes = num1.as_bytes();
    let num2_bytes = num2.as_bytes();
    for i in (0..m).rev() {
        let x = (num1_bytes[i] - b'0') as i32;
        for j in (0..n).rev() {
            let y = (num2_bytes[j] - b'0') as i32;
            ans_arr[i + j + 1] += x * y;
        }
    }
    for i in (1..m+n).rev() {
        ans_arr[i - 1] += ans_arr[i] / 10;
        ans_arr[i] %= 10;
    }
    let mut idx = 0;
    while idx < m+n && ans_arr[idx] == 0 {
        idx += 1;
    }
    let ans_bytes: Vec<u8> = ans_arr[idx..].iter().map(|x| (*x as u8) + b'0').collect();
    String::from_utf8(ans_bytes).unwrap()
}

fn main() {
    println!("{}", multiply(String::from("123"), String::from("456")));
}

输出:

56088


44. 通配符匹配 Wildcard Matching

给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串(包括空字符串)。

两个字符串完全匹配才算匹配成功。

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3:

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

输入:
s = "acdcb"
p = "a*c?b"
输出: false

代码:

fn is_match(s: &str, p: &str) -> bool {
    let (mut si, mut pi) = (0, 0);
    let (mut s_si, mut p_si) = (0, 0);
    let s_bytes = s.as_bytes();
    let p_bytes = p.as_bytes();
    while si < s_bytes.len() {
        if pi < p_bytes.len() && (s_bytes[si] == p_bytes[pi] || p_bytes[pi] == b'?') {
            si += 1;
            pi += 1;
        } else if pi < p_bytes.len() && p_bytes[pi] == b'*' {
            s_si = si;
            p_si = pi;
            pi += 1;
        } else if p_si == usize::MAX {
            return false;
        } else {
            s_si += 1;
            si = s_si;
            pi = p_si + 1;
        }
    }
    while pi < p_bytes.len() && p_bytes[pi] == b'*' {
        pi += 1;
    }
    pi == p_bytes.len()
}

fn main() {
    println!("{}", is_match("aa", "*"));
    println!("{}", is_match("adceb", "*a*b"));
    println!("{}", is_match("acdcd", "a*c?b"));
}

输出:

true
true
false


45. 跳跃游戏 II Jump Game II

给你一个非负整数数组 nums ,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000

代码:

fn jump(nums: Vec<i32>) -> i32 {
    let (mut end, mut max_pos, mut steps) = (0, 0, 0);
    for i in 0..nums.len()-1 {
        max_pos = max(max_pos, i + nums[i] as usize);
        if i == end {
            end = max_pos;
            steps += 1;
        }
    }
    steps
}

fn max(a: usize, b: usize) -> usize {
    if a > b {
        a
    } else {
        b
    }
}

fn main() {
    println!("{}", jump(vec![2, 3, 1, 1, 4]));
    println!("{}", jump(vec![2, 3, 0, 1, 4]));
}

输出:

2
2


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力! 

🌟 收藏,你的青睐是我努力的方向! 

评论,你的意见是我进步的财富!  

 主页:https://hannyang.blog.csdn.net/

05-30 09:20