Steven's BlogAppearance
每天一道Rust-LeetCode(2019-08-18)
坚持每天一道题,刷题学习Rust.
题目描述
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 示例 1 :
输入: num = "1432219", k = 3 输出: "1219" 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。 示例 2 :
输入: num = "10200", k = 1 输出: "200" 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。 示例 3 :
输入: num = "10", k = 2 输出: "0" 解释: 从原数字移除所有的数字，剩余为空就是0。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-k-digits 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
思路: 贪心算法,每次移除一个,都让其最小,这样可以保证连续移除多位后,仍然是最小. 移除权重尽可能大的那个位置 比如1432219 ,为什么先移除4而不移除9,4虽然小于9,但是其权重大 假设n1=4,位置=1,n2=9,位置=6 那么n2的相比较权重是,n1的则是4*10^(6-1-1) 因此移除4而不是移除9
解题过程
rust
struct Solution;
impl Solution {
pub fn remove_kdigits(num: String, k: i32) -> String {
let mut num = num;
if k <= 0 {
return num;
}
let mut selPos = 0;
let bytes = num.as_bytes();
let mut selNum = bytes[0];
//移除一个让这个字符串尽可能小的数字
for i in 1..bytes.len() {
if i - selPos == 1 && bytes[i] >= selNum {
selPos = i;
selNum = bytes[i];
}
}
num.remove(selPos);
while num.len() > 0 {
if num.as_bytes()[0] != '0' as u8 {
break;
}
num.remove(0);
}
//除非没有可移除的,否则都应该继续
if num.len() == 0 {
return String::from("0");
}
return Solution::remove_kdigits(num, k - 1);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_remove_kdigits() {
assert_eq!("1219", Solution::remove_kdigits(String::from("1432219"), 3));
assert_eq!("200", Solution::remove_kdigits(String::from("10200"), 1));
assert_eq!("0", Solution::remove_kdigits(String::from("10"), 2));
assert_eq!("11", Solution::remove_kdigits(String::from("112"), 1));
}
}
一点感悟
使用rust确实能让思路更清晰,编译通过,结果就对了.
其他
欢迎关注我的github,本项目文章所有代码都可以找到.