写点什么

2022-11-01:给定一个只由小写字母和数字字符组成的字符串 str。 要求子串必须只含有一个小写字母,数字字符数量随意。 求这样的子串最大长度是多少?

  • 2022-11-01
    北京
  • 本文字数:1462 字

    阅读完需:约 5 分钟

2022-11-01:给定一个只由小写字母和数字字符组成的字符串str。 要求子串必须只含有一个小写字母,数字字符数量随意。 求这样的子串最大长度是多少?

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;}
复制代码


执行结果如下:





左神java代码

发布于: 刚刚阅读数: 3
用户头像

还未添加个人签名 2021-02-15 加入

还未添加个人简介

评论

发布
暂无评论
2022-11-01:给定一个只由小写字母和数字字符组成的字符串str。 要求子串必须只含有一个小写字母,数字字符数量随意。 求这样的子串最大长度是多少?_算法_福大大架构师每日一题_InfoQ写作社区