写点什么

2022-12-10:给你一个由小写字母组成的字符串 s ,和一个整数 k 如果满足下述条件,则可以将字符串 t 视作是 理想字符串 : t 是字符串 s 的一个子序列。 t 中每两个 相邻 字母在字

  • 2022-12-10
    北京
  • 本文字数:2843 字

    阅读完需:约 9 分钟

2022-12-10:给你一个由小写字母组成的字符串 s ,和一个整数 k 如果满足下述条件,则可以将字符串 t 视作是 理想字符串 : t 是字符串 s 的一个子序列。 t 中每两个 相邻 字母在字

2022-12-10:给你一个由小写字母组成的字符串 s ,和一个整数 k 如果满足下述条件,则可以将字符串 t 视作是 理想字符串 :t 是字符串 s 的一个子序列。t 中每两个 相邻 字母在字母表中位次的绝对差值小于或等于 k 。返回 最长 理想字符串的长度。字符串的子序列同样是一个字符串,并且子序列还满足:可以经由其他字符串删除某些字符(也可以不删除)但不改变剩余字符的顺序得到。注意:字母表顺序不会循环例如,'a' 和 'z' 在字母表中位次的绝对差值是 25,而不是 1 。


答案 2022-12-10:


二维动态规划的解。N 为字符串长度,E 为字符集大小,K 为差值要求。时间复杂度 O(NE)。空间复杂度 O(NE)。


一维动态规划从左往右递推版。N 为字符串长度,E 为字符集大小,K 为差值要求。时间复杂度 O(N*K)。空间复杂度 O(E)。


从左往右递推 + 线段树优化。N 为字符串长度,E 为字符集大小,K 为差值要求。时间复杂度 O(N * logE)。空间复杂度 O(E)。


代码用 rust 编写。代码如下:


use std::iter::repeat;fn main() {    let s = "acfgbd";    let k = 2;    let ans = longest_ideal_string1(s, k);    println!("ans = {}", ans);    let ans = longest_ideal_string2(s, k);    println!("ans = {}", ans);    let ans = longest_ideal_string3(s, k);    println!("ans = {}", ans);}
// 二维动态规划的解// N为字符串长度,E为字符集大小,K为差值要求// 时间复杂度O(N*E)// 空间复杂度O(N*E)fn longest_ideal_string1(s: &str, k: i32) -> i32 { let ss: Vec<char> = s.chars().collect(); let n = s.len() as i32; let mut arr: Vec<i32> = repeat(0).take(n as usize).collect(); for i in 0..n { arr[i as usize] = ss[i as usize] as i32 - 'a' as i32; } let mut dp: Vec<[i32; 27]> = repeat([-1; 27]).take(n as usize).collect(); return f(&mut arr, 0, 26, k, &mut dp);}fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T { if a > b { a } else { b }}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T { if a < b { a } else { b }}
// 数组s中所有的值都在0~25对应a~z// 当前在s[i...]选择数字, 并且前一个数字是p// 如果p<26,说明选择的前一个数字是p// 如果p==26,说明之前没有选过任何数字// 返回在前一个数字是p的情况下,在s[i...]上选择数字,最长理想子序列能是多长// dp仅仅是缓存结构,暴力递归改动态规划常规技巧fn f(s: &mut Vec<i32>, i: i32, p: i32, k: i32, dp: &mut Vec<[i32; 27]>) -> i32 { if i == s.len() as i32 { return 0; } if dp[i as usize][p as usize] != -1 { return dp[i as usize][p as usize]; } let p1 = f(s, i + 1, p, k, dp); let mut p2 = 0; if (p == 26 || i32::abs(s[i as usize] - p) <= k) { p2 = 1 + f(s, i + 1, s[i as usize], k, dp); } let ans = get_max(p1, p2); dp[i as usize][p as usize] = ans; return ans;}
// 一维动态规划从左往右递推版// N为字符串长度,E为字符集大小,K为差值要求// 时间复杂度O(N*K)// 空间复杂度O(E)fn longest_ideal_string2(s: &str, k: i32) -> i32 { let mut dp: [i32; 26] = [0; 26]; let mut c = 0; let mut l = 0; let mut r = 0; let mut pre = 0; let mut ans = 0; let ss: Vec<char> = s.chars().collect(); for i in 0..ss.len() { c = ss[i as usize] as i32 - 'a' as i32; l = get_max(c - k, 0); r = get_min(c + k, 25); pre = 0; for j in l..=r { pre = get_max(pre, dp[j as usize]); } dp[c as usize] = 1 + pre; ans = get_max(ans, dp[c as usize]); } return ans;}
// 从左往右递推 + 线段树优化// N为字符串长度,E为字符集大小,K为差值要求// 时间复杂度O(N * logE)// 空间复杂度O(E)fn longest_ideal_string3(s: &str, k: i32) -> i32 { let ss: Vec<char> = s.chars().collect(); // 0 0 0 // 1(a) 2(b) ... 26(z) let mut st = SegmentTree::new(26); let mut c = 0; let mut pre = 0; let mut ans = 0; for i in 0..ss.len() { // i s.charAt(i) // a 1 // b 2 // z 26 c = ss[i as usize] as i32 - 'a' as i32 + 1; // 2 k = 3 // 1 2 3 4 5 6 7 // l = Math.max(c - k, 1) // r = Math.min(c + k, 26) pre = st.max(get_max(c - k, 1), get_min(c + k, 26)); ans = get_max(ans, 1 + pre); st.update(c, 1 + pre); } return ans;}
struct SegmentTree { n: i32, max: Vec<i32>,}
impl SegmentTree { fn new(maxSize: i32) -> Self { let max: Vec<i32> = repeat(0).take(((maxSize + 1) << 2) as usize).collect(); SegmentTree { n: maxSize + 1, max, } } fn update(&mut self, index: i32, c: i32) { self.update0(index, index, c, 1, self.n, 1); }
fn max(&mut self, left: i32, right: i32) -> i32 { return self.max0(left, right, 1, self.n, 1); }
fn pushUp(&mut self, rt: i32) { self.max[rt as usize] = get_max( self.max[(rt << 1) as usize], self.max[(rt << 1 | 1) as usize], ); }
fn update0(&mut self, L: i32, R: i32, C: i32, l: i32, r: i32, rt: i32) { if L <= l && r <= R { self.max[rt as usize] = C; return; } let mid = (l + r) >> 1; if (L <= mid) { self.update0(L, R, C, l, mid, rt << 1); } if (R > mid) { self.update0(L, R, C, mid + 1, r, rt << 1 | 1); } self.pushUp(rt); }
fn max0(&mut self, L: i32, R: i32, l: i32, r: i32, rt: i32) -> i32 { if L <= l && r <= R { return self.max[rt as usize]; } let mut mid = (l + r) >> 1; let mut ans = 0; if (L <= mid) { ans = get_max(ans, self.max0(L, R, l, mid, rt << 1)); } if R > mid { ans = get_max(ans, self.max0(L, R, mid + 1, r, rt << 1 | 1)); } return ans; }}
复制代码


执行结果如下:





左神java代码

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

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

还未添加个人简介

评论

发布
暂无评论
2022-12-10:给你一个由小写字母组成的字符串 s ,和一个整数 k 如果满足下述条件,则可以将字符串 t 视作是 理想字符串 : t 是字符串 s 的一个子序列。 t 中每两个 相邻 字母在字_算法_福大大架构师每日一题_InfoQ写作社区