字符串类的算法题

发布时间:2019-10-29 发布网站:大佬教程
大佬教程收集整理的这篇文章主要介绍了字符串类的算法题大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。

1、将0-1串进行排序,你可以交换任意两个位置,问最少交换多少次?(用快速排序的思想)

answer=0( i=0,j=len-1;i((i++ ((i-- (i<++

2、删除所有的a,并复制所有的b(字符数组足够大)

  1>先删除a,可以利用原来的字符串空间

n=0,numb=0( i=0;a[i];++(s[i]!='a'++]=(s[i]=='b'++

  2>复制b,技巧:倒着复制

newLength=n+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">;
}

5、单词翻转

  while(i

例1: I'm a student变为student a I'm

方法:先将整个句子翻转,tneduts a m'I

  再将每个单词单独翻转,student a I'm

例2:字符串循环移位 abcd

  bcda,cdab,dabc

 思路: 长度为n,移动m次,相当于移动m%n次

  将前m%n翻转,再将后n-m%n翻转,最后总体翻转一下

 

  

  

大佬总结

以上是大佬教程为你收集整理的字符串类的算法题全部内容,希望文章能够帮你解决字符串类的算法题所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ群:277859234,请注明来意。
猜你在找的算法相关文章