Rust每日一练(Leetday0010) 子串下标、两数相除、串联子串

简介: Rust每日一练(Leetday0010) 子串下标、两数相除、串联子串

28. 找出字符串中第一个匹配项的下标 Find-the-index-of-the-first-occurrence-in-a-string


给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回  -1 。



说明:实现 strStr() 函数。对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strStr() 以及 Java 的 indexOf() 定义相符。

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。


示例 1:

输入:haystack = "hello", needle = "ll"

输出:2


示例 2:

输入:haystack = "aaaaa", needle = "bba"

输出:-1


提示:

   1 <= haystack.length, needle.length <= 10^4

   haystack 和 needle 仅由小写英文字符组成



代码1:

fn str_str(haystack: String, needle: String) -> i32 {
    let n = haystack.len();
    let m = needle.len();
    if m == 0 {
        return 0;
    }
    if n < m {
        return -1;
    }
    for i in 0..=n-m {
        if haystack[i..i+m] == needle {
            return i as i32;
        }
    }
    return -1;
}
fn main() {
    let haystack = "hello".to_string();
    let needle = "ll".to_string();
    println!("{}", str_str(haystack, needle));
    let haystack = "aaaaa".to_string();
    let needle = "bba".to_string();
    println!("{}", str_str(haystack, needle));
}


输出:

2

-1

代码2:

fn str_str(haystack: String, needle: String) -> i32 {
    let mut i = 0_usize;
    loop {
        let mut j = 0_usize;
        loop {
            if j == needle.len() {
                return i as i32;
            }
            if i + j == haystack.len() {
                return -1;
            }
            if needle.as_bytes()[j] != haystack.as_bytes()[i+j] {
                break;
            }
            j += 1;
        }
        i += 1;
    }
}
fn main() {
    let haystack = "hello".to_string();
    let needle = "ll".to_string();
    println!("{}", str_str(haystack, needle));
    let haystack = "aaaaa".to_string();
    let needle = "bba".to_string();
    println!("{}", str_str(haystack, needle));
}


另: Rust语言有现成的字符串方法 haystack.find(&needle)

fn main() {
    let haystack = "hello".to_string();
    let needle = "ll".to_string();
    println!("{:?}", haystack.find(&needle));
    let haystack = "aaaaa".to_string();
    let needle = "bba".to_string();
    println!("{:?}", haystack.find(&needle));
}



29. 两数相除 Divide Two Integers



给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。


返回被除数 dividend 除以除数 divisor 得到的商。


整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2


示例 1:

输入: dividend = 10, divisor = 3

输出: 3

解释: 10/3 = truncate(3.33333..) = truncate(3) = 3


示例 2:

输入: dividend = 7, divisor = -3

输出: -2

解释: 7/-3 = truncate(-2.33333..) = -2


提示:

   被除数和除数均为 32 位有符号整数。

   除数不为 0。

   假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2^31,  2^31 − 1]。本题中,如果除法结果溢出,则返回 2^31 − 1。


代码:

pub fn divide(dividend: i32, divisor: i32) -> i32 {
    // 处理特殊情况
    if dividend == std::i32::MIN && divisor == -1 {
        return std::i32::MAX;
    }
    if divisor == 1 {
        return dividend;
    }
    if divisor == -1 {
        return -dividend;
    }
    // 处理符号
    let mut res = 0;
    let mut sign = 1;
    if (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) {
        sign = -1;
    }
    let mut a = abs(dividend);
    let b = abs(divisor);
    // 计算商
    while a >= b {
        let (mut temp, mut tb) = (1, b);
        while a >= (tb << 1) {
            tb <<= 1;
            temp <<= 1;
        }
        res += temp;
        a -= tb;
    }
    res * sign
}
fn abs(x: i32) -> i32 {
    if x < 0 {
        -x
    } else {
        x
    }
}
fn main() {
    println!("{}", divide(10, 3));
    println!("{}", divide(7, -3));
}


输出:

3

-2


30. 串联所有单词的子串 Substring-with-concatenation-of-all-words


给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。


注意子串要与 words 中的单词完全匹配,中间不能有其他字符 ,但不需要考虑 words 中单词串联的顺序。


示例 1:

输入:s = "barfoothefoobarman", words = ["foo","bar"]

输出:[0,9]

解释:

从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。



输出的顺序不重要, [9,0] 也是有效答案。


示例 2:

输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]

输出:[]


示例 3:

输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

输出:[6,9,12]


提示:

   1 <= s.length <= 10^4

   s 由小写英文字母组成

   1 <= words.length <= 5000

   1 <= words[i].length <= 30

   words[i] 由小写英文字母组成


代码1:  暴力枚举

pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
    let n = s.len();
    let m = words.len();
    if n == 0 || m == 0 {
        return Vec::new();
    }
    let word_len = words[0].len();
    let mut ans = Vec::new();
    for i in 0..=n - m * word_len {
        let mut j = 0;
        let mut used = vec![false; m];
        while j < m {
            let word = &s[i + j * word_len..i + j * word_len + word_len];
            let mut k = 0;
            while k < m {
                if !used[k] && word == &words[k] {
                    used[k] = true;
                    break;
                }
                k += 1;
            }
            if k == m {
                break;
            }
            j += 1;
        }
        if j == m {
            ans.push(i as i32);
        }
    }
    ans
}
fn main() {
    let s = String::from("barfoothefoobarman");
    let words = vec![String::from("foo"), String::from("bar")];
    println!("{:?}", find_substring(s, words));
    let s = String::from("wordgoodgoodgoodbestword");
    let words = vec![
        String::from("word"),
        String::from("good"),
        String::from("best"),
        String::from("word"),
    ];
    println!("{:?}", find_substring(s, words));
    let s = String::from("barfoofoobarthefoobarman");
    let words = vec![String::from("bar"), String::from("foo"), String::from("the")];
    println!("{:?}", find_substring(s, words));
}




输出:

[0, 9]

[]

[6, 9, 12]

代码2: 滑动窗口

use std::collections::HashMap;
pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
    let n = s.len();
    let m = words.len();
    if n == 0 || m == 0 {
        return vec![];
    }
    let word_len = words[0].len();
    let mut cnt = HashMap::new();
    for word in words {
        *cnt.entry(word).or_insert(0) += 1;
    }
    let mut ans = Vec::new();
    for i in 0..word_len {
        let mut left = i;
        let mut right = i;
        let mut window = HashMap::new();
        while right + word_len <= n {
            let word = &s[right..right + word_len];
            right += word_len;
            if *cnt.get(word).unwrap_or(&0) == 0 {
                left = right;
                window.clear();
            } else {
                *window.entry(word.to_string()).or_insert(0) += 1;
                while *window.get(word).unwrap_or(&0) > *cnt.get(word).unwrap_or(&0) {
                    let d_word = &s[left..left + word_len];
                    left += word_len;
                    *window.entry(d_word.to_string()).or_insert(0) -= 1;
                }
                if right - left == word_len * m {
                    ans.push(left as i32);
                }
            }
        }
    }
    ans
}
fn main() {
    let s = String::from("barfoothefoobarman");
    let words = vec![String::from("foo"), String::from("bar")];
    println!("{:?}", find_substring(s, words));
    let s = String::from("wordgoodgoodgoodbestword");
    let words = vec![
        String::from("word"),
        String::from("good"),
        String::from("best"),
        String::from("word"),
    ];
    println!("{:?}", find_substring(s, words));
    let s = String::from("barfoofoobarthefoobarman");
    let words = vec![String::from("bar"), String::from("foo"), String::from("the")];
    println!("{:?}", find_substring(s, words));
}


代码3:滑动窗口

use std::collections::HashMap;
pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
    let n = s.len();
    let m = words.len();
    if n == 0 || m == 0 {
        return vec![];
    }
    let word_len = words[0].len();
    let mut cnt = HashMap::new();
    for word in &words {
        *cnt.entry(word.to_string()).or_insert(0) += 1;
    }
    let mut ans = Vec::new();
    for i in 0..word_len {
        let mut left = i;
        let mut right = i;
        let mut window = HashMap::new();
        let mut count = 0;
        while right + word_len <= n {
            let word = &s[right..right + word_len];
            right += word_len;
            if cnt.get(word).cloned().unwrap_or(0) == 0 {
                left = right;
                window.clear();
                count = 0;
            } else {
                *window.entry(word.to_string()).or_insert(0) += 1;
                count += 1;
                while window.get(word).cloned().unwrap_or(0) > cnt.get(word).cloned().unwrap_or(0) {
                    let d_word = &s[left..left + word_len];
                    left += word_len;
                    *window.entry(d_word.to_string()).or_insert(0) -= 1;
                    count -= 1;
                }
                if count == m {
                    ans.push(left as i32);
                }
            }
        }
    }
    ans
}
fn main() {
    let s = String::from("barfoothefoobarman");
    let words = vec![String::from("foo"), String::from("bar")];
    println!("{:?}", find_substring(s, words));
    let s = String::from("wordgoodgoodgoodbestword");
    let words = vec![
        String::from("word"),
        String::from("good"),
        String::from("best"),
        String::from("word"),
    ];
    println!("{:?}", find_substring(s, words));
    let s = String::from("barfoofoobarthefoobarman");
    let words = vec![String::from("bar"), String::from("foo"), String::from("the")];
    println!("{:?}", find_substring(s, words));
}

代码4: 滑动窗口

use std::collections::HashMap;
pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
    let n = s.len();
    let m = words.len();
    if n == 0 || m == 0 {
        return vec![];
    }
    let word_len = words[0].len();
    let mut cnt = HashMap::new();
    for word in &words {
        *cnt.entry(word.to_string()).or_insert(0) += 1;
    }
    let mut ans = Vec::new();
    for i in 0..word_len {
        let mut left = i;
        let mut right = i;
        let mut window = HashMap::new();
        let mut count = 0;
        while right + word_len <= n {
            let word = &s[right..right + word_len];
            right += word_len;
            if cnt.get(word).cloned().unwrap_or(0) == 0 {
                left = right;
                window.clear();
                count = 0;
            } else {
                *window.entry(word.to_string()).or_insert(0) += 1;
                count += 1;
                while window.get(word).cloned().unwrap_or(0) > cnt.get(word).cloned().unwrap_or(0) {
                    let d_word = &s[left..left + word_len];
                    left += word_len;
                    *window.entry(d_word.to_string()).or_insert(0) -= 1;
                    count -= 1;
                }
                if count == m {
                    ans.push(left as i32);
                }
            }
            if right - left == word_len * (m + 1) {
                let d_word = &s[left..left + word_len];
                left += word_len;
                *window.entry(d_word.to_string()).or_insert(0) -= 1;
                count -= 1;
            }
        }
    }
    ans
}
fn main() {
    let s = String::from("barfoothefoobarman");
    let words = vec![String::from("foo"), String::from("bar")];
    println!("{:?}", find_substring(s, words));
    let s = String::from("wordgoodgoodgoodbestword");
    let words = vec![
        String::from("word"),
        String::from("good"),
        String::from("best"),
        String::from("word"),
    ];
    println!("{:?}", find_substring(s, words));
    let s = String::from("barfoofoobarthefoobarman");
    let words = vec![String::from("bar"), String::from("foo"), String::from("the")];
    println!("{:?}", find_substring(s, words));
}


目录
相关文章
|
Java Go C++
Rust每日一练(Leetday0031) 解码方法、复原 IP 地址
Rust每日一练(Leetday0031) 解码方法、复原 IP 地址
122 0
Rust每日一练(Leetday0031) 解码方法、复原 IP 地址
|
Java Go Rust
Rust每日一练(Leetday0030) 合并有序数组、格雷编码、子集II
Rust每日一练(Leetday0030) 合并有序数组、格雷编码、子集II
168 0
Rust每日一练(Leetday0030) 合并有序数组、格雷编码、子集II
|
算法 Java Go
Rust每日一练(Leetday0029) 柱状图、最大矩形、扰乱字符串
Rust每日一练(Leetday0029) 柱状图、最大矩形、扰乱字符串
107 0
Rust每日一练(Leetday0029) 柱状图、最大矩形、扰乱字符串
|
Rust Java Go
Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II
Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II
120 0
Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II
|
Java Go C++
Rust每日一练(Leetday0026) 最小覆盖子串、组合、子集
Rust每日一练(Leetday0026) 最小覆盖子串、组合、子集
102 0
Rust每日一练(Leetday0026) 最小覆盖子串、组合、子集
|
算法 Java Go
Rust每日一练(Leetday0025) 矩阵置零、搜索二维矩阵、颜色分类
Rust每日一练(Leetday0025) 矩阵置零、搜索二维矩阵、颜色分类
126 0
Rust每日一练(Leetday0025) 矩阵置零、搜索二维矩阵、颜色分类
|
Java Go C++
Rust每日一练(Leetday0024) 爬楼梯、简化路径、编辑距离
Rust每日一练(Leetday0024) 爬楼梯、简化路径、编辑距离
169 0
Rust每日一练(Leetday0024) 爬楼梯、简化路径、编辑距离
|
Java Go C++
Rust每日一练(leetDay0023) 二进制求和、左右对齐、平方根
Rust每日一练(leetDay0023) 二进制求和、左右对齐、平方根
138 0
Rust每日一练(leetDay0023) 二进制求和、左右对齐、平方根
|
Java Go C++
Rust每日一练(Leetday0022) 最小路径和、有效数字、加一
Rust每日一练(Leetday0022) 最小路径和、有效数字、加一
140 0
Rust每日一练(Leetday0022) 最小路径和、有效数字、加一
|
Python Rust Java
Rust每日一练(Leetday0020) 最后单词的长度、螺旋矩阵II、排列序列
Rust每日一练(Leetday0020) 最后单词的长度、螺旋矩阵II、排列序列
161 0
Rust每日一练(Leetday0020) 最后单词的长度、螺旋矩阵II、排列序列