1
2022-11-01:给定一个只由小写字母和数字字符组成的字符串 str。 要求子串必须只含有一个小写字母,数字字符数量随意。 求这样的子串最大长度是多少?
作者:福大大架构师每日一题
- 2022-11-01 北京
本文字数:1462 字
阅读完需:约 5 分钟
2022-11-01:给定一个只由小写字母和数字字符组成的字符串 str。要求子串必须只含有一个小写字母,数字字符数量随意。求这样的子串最大长度是多少?
答案 2022-11-01:
经典的滑动窗口问题。时间复杂度:O(N)。空间复杂度:O(1)。
代码用 rust 编写。代码如下:
use rand::Rng;
fn main() {
let nn: i32 = 100;
let test_time: i32 = 10000;
println!("测试开始");
for _ in 0..test_time {
let n = rand::thread_rng().gen_range(0, nn) + 1;
let str = random_string(n);
let ans1 = right(&str);
let ans2 = zuo(&str);
if ans1 != ans2 {
println!("ans1 = {:?}", ans1);
println!("ans2 = {:?}", ans2);
println!("出错了!");
break;
}
}
println!("测试结束");
}
// 一个绝对正确的暴力方法
fn right(s: &str) -> i32 {
let str = s.as_bytes();
let mut ans = 0;
for i in 0..str.len() as i32 {
for j in i..str.len() as i32 {
if check(str, i, j) {
ans = get_max(ans, j - i + 1);
}
}
}
return ans;
}
fn check(str: &[u8], l: i32, r: i32) -> bool {
let mut letter_number = 0;
for i in l..=r {
if str[i as usize] >= 'a' as u8 && str[i as usize] <= 'z' as u8 {
letter_number += 1;
}
}
return letter_number == 1;
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
// 用窗口
// 时间复杂度O(N)
fn zuo(s: &str) -> i32 {
let str = s.as_bytes();
let n = str.len() as i32;
// 窗口内有几个小写字母了
let mut letters = 0;
// 窗口的右边界
// [left, right)
let mut right = 0;
let mut ans = 0;
// for枚举了每一个窗口的开始位置,0... 1...... 2.....
for left in 0..n {
while right < n {
// right不能越界,一旦越界不用再往右了
if letters == 1 && str[right as usize] >= 'a' as u8 && str[right as usize] <= 'z' as u8
{
break;
}
// letters == 0 str[right]是数字
if str[right as usize] >= 'a' as u8 && str[right as usize] <= 'z' as u8 {
letters += 1;
}
right += 1;
}
// [left.....right)
// [left.....right-1]
if letters == 1 {
ans = get_max(ans, right - left);
}
if str[left as usize] >= 'a' as u8 && str[left as usize] <= 'z' as u8 {
letters -= 1;
}
}
return ans;
}
// 为了测试
const CHARS: [char; 36] = [
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
];
// 为了测试
fn random_string(n: i32) -> String {
let mut ans = String::from("");
for _i in 0..n {
ans.push(CHARS[rand::thread_rng().gen_range(0, 36)]);
}
return ans;
}
复制代码
执行结果如下:
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/67a6c9519748de8d3cc028931】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
福大大架构师每日一题
关注
还未添加个人签名 2021-02-15 加入
还未添加个人简介
评论