Rust每日一练(Leetday0002) 中位数、回文子串、Z字形变换

2023-05-29 78

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Rust每日一练(Leetday0002) 中位数、回文子串、Z字形变换

4. 寻找两个正序数组的中位数 Median of two sorted arrays

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]

输出：2.00000

解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]

输出：2.50000

解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-10^6 <= nums1[i], nums2[i] <= 10^6

代码：

fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
    let mut nums = Vec::with_capacity(nums1.len() + nums2.len());
    let (mut i, mut j) = (0, 0);
    while i < nums1.len() && j < nums2.len() {
        if nums1[i] < nums2[j] {
            nums.push(nums1[i]);
            i += 1;
        } else {
            nums.push(nums2[j]);
            j += 1;
        }
    }
    while i < nums1.len() {
        nums.push(nums1[i]);
        i += 1;
    }
    while j < nums2.len() {
        nums.push(nums2[j]);
        j += 1;
    }
    let n = nums.len();
    if n % 2 == 0 {
        (nums[n/2-1] + nums[n/2]) as f64 / 2.0
    } else {
        nums[n/2] as f64
    }
}
fn main() {
    let nums1 = vec![1, 3];
    let nums2 = vec![2];
    println!("{:?}", find_median_sorted_arrays(nums1, nums2));
    let nums1 = vec![1, 2];
    let nums2 = vec![3, 4];
    println!("{:?}", find_median_sorted_arrays(nums1, nums2));
}

输出：

2.0

2.5

5. 最长回文子串 Longest Palindromic Substring

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"

输出："bab"

解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"

输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

代码：

fn longest_palindrome(s: String) -> String {
    let n = s.len();
    let s: Vec<char> = s.chars().collect();
    let mut dp = vec![vec![false; n]; n];
    let mut max_len = 1;
    let mut start = 0;
    for i in 0..n {
        dp[i][i] = true;
    }
    for j in 1..n {
        for i in 0..j {
            if s[i] != s[j] {
                dp[i][j] = false;
            } else {
                if j - i < 3 {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i+1][j-1];
                }
            }
            if dp[i][j] && j - i + 1 > max_len {
                max_len = j - i + 1;
                start = i;
            }
        }
    }
    s[start..start+max_len].iter().collect()
}
fn main() {
    let s = String::from("babad");
     println!("{:?}", longest_palindrome(s));
    let s = "cbbd".to_string();
     println!("{:?}", longest_palindrome(s));
}

输出：

bab

6. Z字形变换 Zigzag Conversion

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P A H N

A P L S I I G

Y I R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3

输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4

输出："PINALSIGYAHRPI"

解释：

P I N

A L S I G

Y A H R

P I

示例 3：

输入：s = "A", numRows = 1

输出："A"

提示：

1 <= s.length <= 1000

s 由英文字母（小写和大写）、',' 和 '.' 组成

1 <= numRows <= 1000

代码：

fn convert(s: String, num_rows: i32) -> String {
    if num_rows == 1 {
        return s;
    }
    let mut res = vec!["".to_string(); num_rows as usize];
    let mut index = 0;
    let mut flag = 1;
    for c in s.chars() {
        res[index as usize].push(c);
        if index == num_rows - 1 {
            flag = -1;
        }
        if index == 0 {
            flag = 1;
        }
        index += flag;
    }
    res.join("")
}
fn main() {
    let s = String::from("PAYPALISHIRING");
    let num_rows = 3;
    println!("{}", convert(s, num_rows));
    let s = String::from("PAYPALISHIRING");
    let num_rows = 4;
    println!("{}", convert(s, num_rows));
    let s = String::from("A");
    let num_rows = 1;
    println!("{}", convert(s, num_rows));
}