优秀的网站建设推荐,超炫的网站模板,可信赖的商城网站建设,龙华app网站制作目录
13. 罗马数字转整数 Roman to Integer #x1f31f;
14. 最长公共前缀 Longest Common Prefix #x1f31f;
15. 三数之和 3Sum #x1f31f;#x1f31f;
#x1f31f; 每日一练刷题专栏 #x1f31f;
Rust每日一练 专栏
Golang每日一练 专栏
Python每日…
目录
13. 罗马数字转整数 Roman to Integer
14. 最长公共前缀 Longest Common Prefix
15. 三数之和 3Sum 每日一练刷题专栏
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C每日一练 专栏
Java每日一练 专栏 13. 罗马数字转整数 Roman to Integer
罗马数字包含以下七种字符: I V X LCD 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如 罗马数字 2 写做 II 即为两个并列的 1 。12 写做 XII 即为 X II 。 27 写做 XXVII, 即为 XX V II 。
通常情况下罗马数字中小的数字在大的数字的右边。但也存在特例例如 4 不写做 IIII而是 IV。数字 1 在数字 5 的左边所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况
I 可以放在 V (5) 和 X (10) 的左边来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边来表示 400 和 900。
给定一个罗马数字将其转换成整数。
示例 1:
输入: s III
输出: 3
示例 2:
输入: s IV
输出: 4
示例 3:
输入: s IX
输出: 9
示例 4:
输入: s LVIII
输出: 58
解释: L 50, V 5, III 3.示例 5:
输入: s MCMXCIV
输出: 1994
解释: M 1000, CM 900, XC 90, IV 4.提示
1 s.length 15s 仅含字符 (I, V, X, L, C, D, M)题目数据保证 s 是一个有效的罗马数字且表示整数在范围 [1, 3999] 内题目所给测试用例皆符合罗马数字书写规则不会出现跨位等情况。IL 和 IM 这样的例子并不符合题目要求49 应该写作 XLIX999 应该写作 CMXCIX 。关于罗马数字的详尽书写规则可以参考 罗马数字(链接略) 。
代码
use std::collections::HashMap;fn roman_to_int(s: String) - i32 {let mut roman HashMap::new(); // 使用哈希表记录符号和对应的整数值roman.insert(I, 1);roman.insert(V, 5);roman.insert(X, 10);roman.insert(L, 50);roman.insert(C, 100);roman.insert(D, 500);roman.insert(M, 1000);let mut lastint 0; // 上一次处理的整数值let mut total 0; // 当前的总和for c in s.chars().rev() {let num roman.get(c).unwrap(); // 获取当前符号对应的整数值if *num lastint {total - num;} else {total num;}lastint *num;}total
}fn main() {println!({}, roman_to_int(String::from(IX)));println!({}, roman_to_int(String::from(LVIII)));println!({}, roman_to_int(String::from(MCMXCIV)));
}输出
9 58 1994 14. 最长公共前缀 Longest Common Prefix
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀返回空字符串 。
示例 1
输入strs [flower,flow,flight]
输出fl示例 2
输入strs [dog,racecar,car]
输出
解释输入不存在公共前缀。提示
1 strs.length 2000 strs[i].length 200strs[i] 仅由小写英文字母组成
代码
fn longest_common_prefix(strs: VecString) - String {if strs.is_empty() {return String::new();}let mut prefix strs[0].clone();for str in strs.iter().skip(1) {while !str.starts_with(prefix) {prefix.pop();if prefix.is_empty() {return String::new();}}}prefix
}fn main() {let strs1 vec![flower, flow, flight].iter().map(|x| x.to_string()).collect();let strs2 vec![dog, racecar, car].iter().map(|x| x.to_string()).collect();println!({}, longest_common_prefix(strs1)); // flprintln!({}, longest_common_prefix(strs2)); //
}输出
fl //空
说明
将第一个字符串作为公共前缀的初始值从第二个字符串开始依次与公共前缀进行比较。 如果当前字符串不是以公共前缀开头则将公共前缀缩短一个字符继续比较。 如果公共前缀已经为空则说明不存在公共前缀返回空字符串。 15. 三数之和 3Sum
给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 a,b,c使得 a b c 0请你找出所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例 1
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]示例 2
输入nums []
输出[]示例 3
输入nums [0]
输出[]提示
0 nums.length 3000-10^5 nums[i] 10^5
代码1
fn three_sum(nums: Veci32) - VecVeci32 {let mut nums nums;let n nums.len();let mut res Vec::new();nums.sort(); // 升序排序for i in 0..n {if i 0 nums[i] nums[i - 1] {continue; // 跳过重复的元素}let mut l i 1;let mut r n - 1;while l r {let sum nums[i] nums[l] nums[r];if sum 0 {res.push(vec![nums[i], nums[l], nums[r]]);while l r nums[l] nums[l 1] {l 1; // 去除重复的元素}while l r nums[r] nums[r - 1] {r - 1; // 去除重复的元素}l 1;r - 1;} else if sum 0 {l 1;} else {r - 1;}}}res
}fn main() {let nums1 vec![-1, 0, 1, 2, -1, -4];let nums2: Veci32 vec![];let nums3 vec![0];println!({:?}, three_sum(nums1)); // [[-1, -1, 2], [-1, 0, 1]]println!({:?}, three_sum(nums2)); // []println!({:?}, three_sum(nums3)); // []
}代码2
fn three_sum(nums: Veci32) - VecVeci32 {let mut nums nums;let n nums.len();let mut res Vec::new();nums.sort(); // 升序排序for i in 0..n {if i 0 nums[i] nums[i - 1] {continue; // 跳过重复的元素}let mut k n - 1;let target -nums[i];let mut j i 1;while j n {if j i 1 nums[j] nums[j - 1] {j 1;continue; // 跳过重复的元素}while j k nums[j] nums[k] target {k - 1; // 移动右指针}if j k {break;}if nums[j] nums[k] target {res.push(vec![nums[i], nums[j], nums[k]]);}j 1;}}res
}fn main() {let nums1 vec![-1, 0, 1, 2, -1, -4];let nums2: Veci32 vec![];let nums3 vec![0];println!({:?}, three_sum(nums1)); // [[-1, -1, 2], [-1, 0, 1]]println!({:?}, three_sum(nums2)); // []println!({:?}, three_sum(nums3)); // []
}输出
[[-1 -1 2] [-1 0 1]] [] [] 每日一练刷题专栏
✨ 持续努力奋斗做强刷题搬运工 点赞你的认可是我坚持的动力 收藏你的青睐是我努力的方向
✎ 评论你的意见是我进步的财富
☸ 主页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暂停更
