剑客
关注科技互联网

编程之法-字符串

字符串的旋转

题:abcedf –> edfabc

1.蛮力移位

原理:将后一个位置的字符向前移动,第一个字符放置在最后的位置上。 即分三步完成 bcedfa –> cedfab –> edfabc

2. 三步反转

拆分为两段即 abc 与 edf,对他俩分别进行反转得到 cbafde;再对整个进行反转,得到结果

练习:单词翻转 “I am a student.“ –> “student. a am I”. 思路:按空格分隔,分别进行反转,再整理反转。

字符串的包含。

题:a: “ABCD”, b:“BAD” 则包含为true;

若b 是 ”BCE", 为 false;
若b 是 “AA", 为true. 即字符串b 中出现的字符都必须按在 a 中出现。

1.蛮力轮询

2.排序后轮询

排序使用快排,需要 O(mlogm) + O(nlogn), 线性扫描需要 O(m+n)次操作。

3.素数相乘

原理:利用素数相乘取余数的结果来判断,是否存在。(若是余数为0,表示存在,若是余数不为0,则表示不存在)

分步: 1.将 a 中出现的字符对应到 26 个素数当中,并相乘得到结果 2.遍历 b 中的字符,取得相应的素数,与上一步乘积的结果,取余进行判断。

现实不可行:前16个素数相乘的结果会超出 long 能表示的结果。

4.位运算法

原理:将 a 中的字符存至 hash 表中,b 来进行获取判断。 位运算:先用一个 int 来表示最终的结果,因为 Int 为32位,完全满足 26 个字符的要求,对 a 中的字符,对应 26 个字符的顺序进行移位放置 a 中。 即 hash |= (1 << a[i] – ‘A’) 再进行 b 中判断的时候,直接进行相与,即可得到结果。

字符串的全排列

1.递归实现

2.字典序排列

原理:起点字典序最小的排列 1 ~ n 如 ”12345“;终点 n ~ 1, 如 ”54321“。 执行过程就是获取比当前字典序大的下一个排列。

举例: 21543, 1. 获得第一个升序的数字为 1 2. 比 1 大,并在 1 右边的最小一个数自,得到 3 3. 它俩交换,得到 23541, 4. 翻转 541 ,得到 23145.

两种解法的都一共有 n! 种情况,复杂度为 O(n!)。

练习

1. 字典序的所有排列

如 “ab”, 任意排列为 aa, ab, ba,bb。

采用递归的思想,当字符的个数为 2 时,输出结果。

2. 字符的所有组合

输入 “abc”, 组合有 a,b,c,ab,ac,bc,abc

3.序列的打印

(a),(b),© (a,b),(a,c)(b,c) (a,b,c)

字符串转成整数

“123” –> 123

乘以进制10

其他问题:溢出,正负

回文判断

1. 两头往中间

2. 中间往两头

练习 1. 链表回文 2. 栈回文

最长回文子串

中心扩展法

需要考虑奇数还是偶数

Manacher 算法

将字符串间隔添加特殊字符,变为一个长度为奇数长度的新的字符串。 如 S[i]: # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 # 得 P[i]: 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1 其中 P[i] 来记录为字符 S[i] 为中心的最长回文子串向左或向右扩张的长度(包括 S[i])

一个利用中间变量特殊技巧,增加两个变量 id 和 mx, id 表示最大回文子串中心的位置,mx 为 id + P[id], 即最大回文子串的右边界。会得到一个重要的结论: 如果 mx > i, 那么 P[i] >= min(P[2 * id -i], mx – i)。

参考资料

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址