算法
发布时间：2019-10-29 发布网站：大佬教程 code.js-code.com
大佬教程收集整理的这篇文章主要介绍了字符串类的算法题，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
1、将0-1串进行排序，你可以交换任意两个位置，问最少交换多少次？（用快速排序的思想）
answer=0( i=0,j=len-1;i<j;++i,--{
((i++);++i));
((i--j;
);--j);
(i<++
2、删除所有的a，并复制所有的b（字符数组足够大）
1>先删除a，可以利用原来的字符串空间
n=0,numb=0( i=0;a[i];++{
(s[i]!='a'{
s[n++]=(s[i]=='b'{
++numb;
}
}
2>复制b，技巧：倒着复制
newLength=n+numb;
s[newLength]
=0<span style="color: #000000">;
<span style="color: #0000ff">for(<span style="color: #0000ff">int i=newLength-1,j=n-1;j>
=0;--<span style="color: #000000">j)
{
s[i--]=<span style="color: #000000">s[j];
<span style="color: #0000ff">if(s[j]=='b'<span style="color: #000000">){
s[i--]='b'<span style="color: #000000">;
}
}
3、一个字符串只包含*和数字，请把字符串内所有的*都放在开头
方法一：数字的相对顺序会变
( i=0,j=0;j{
<span style="color: #0000ff">if(s[j]=='*'<span style="color: #000000">)
swap(s[i++<span style="color: #000000">],s[j])
}
方法二：数字的相对顺序不变
j=n-1<span style="color: #0000ff">for(<span style="color: #0000ff">int i=n-1;i>
=0;--<span style="color: #000000">i)
{
<span style="color: #0000ff">if<span style="color: #000000">(isdigit(s[i]))
s[j--]=<span style="color: #000000">s[i];
}
<span style="color: #0000ff">for(;j>=0;--<span style="color: #000000">j){
s[j]='*'<span style="color: #000000">;
}
4、给定两个串a,b,问b是否是a的子串的变位词，例如输入a=Hello,b=lel,lle,ello都是true,但是b=elo是false，
解题思想：
滑动窗口的思想，动态维护一个窗口，例如b的长度为3，我们考察a[0..2],a[1..3],a[2..4]是否和b是变位词。
用一个hash，基于字符串的特性，用一个[0..255]或[0..65535]的数组，在这，暂且认为它们都是小写英文字母，用[0-25]来表示b中的每个单词出现的次数
用nonZero来存出现不同字母的个数，num[]来存每个字母出现的个数
1>先遍历一下b，存b中的不同字母的个数nonZero，和每个字母出现的个数num[];
nonZero=0( i=0;i{
<span style="color: #0000ff">if(++num[b[i]-'a']==1<span style="color: #000000">)
++<span style="color: #000000">nonZero;
}
2>再遍历a[0..lenb-1],用b中的次数减去a中的一个窗口内字符种类，如果结果全是0，则找到这样的子串，注意：num[]的含义变为字符种类差。
( i=0;i{
<span style="color: #0000ff">int c=a[i]-'a'<span style="color: #000000">;
--<span style="color: #000000">num[c];
<span style="color: #0000ff">if(num[c]=
=0<span style="color: #000000">)
{
<span style="color: #008000">//<span style="color: #008000">b与a中的该字母个数差为0，正好，可以将nonZero减1了
--<span style="color: #000000">nonZero;
}<span style="color: #0000ff">else <span style="color: #0000ff">if(num[c]==-1<span style="color: #000000">)
{
<span style="color: #008000">//<span style="color: #008000">这种情况不是b中没有这个字母，就是a中该字母个数比b中要多
++<span style="color: #000000">nonZero;
}
}
<span style="color: #0000ff">if(nonZero=
=0<span style="color: #000000">)
<span style="color: #0000ff">return <span style="color: #0000ff">true;
3>a窗口滑动右移
i=lenb;
新窗口：a[i-lenb+1..i]
旧窗口：a[i-lenb..i-1]
需要去掉a[i-lenb],加入a[i]
<div class="cnblogs_code">
( i=lenb;i{
c=a[i-lenb]-'a'++(num[c]==1{
++ (num[c]==0{
--<span style="color: #000000">nonZero;
}
<span style="color: #008000"> //<span style="color: #008000">加入新窗口的最后一个字母，因为中间的字母与旧窗口重叠。
c=a[i]-'a'<span style="color: #000000">;
--<span style="color: #000000">num[c];
<span style="color: #0000ff">if(num[c]==0<span style="color: #000000">){
--<span style="color: #000000">nonZero;
}<span style="color: #0000ff">else <span style="color: #0000ff">if(num[c]==-1<span style="color: #000000">){
++<span style="color: #000000">nonZero;
}
<span style="color: #0000ff">if(nonZero==0<span style="color: #000000">)
<span style="color: #0000ff">return <span style="color: #0000ff">true<span style="color: #000000">;
}
