0°

面试算法知识梳理二:字符串算法第一部分

内容预览:
  • 始发于微信公众号: 程序员小乐 分享编程技能、互联网技术、生活感悟、...~
  • 对于上面的任意一种情况,经过划分后A和B的长度都会减少,那么最终必然...~
  • 乐乐有话说 人性有一个弱点,你越在意什么,什么就越折磨你~

始发于微信公众号: 程序员小乐

分享编程技能、互联网技术、生活感悟、打造干货分享平台,将总结的技术、心得、经验分享给大家,这里不只限于技术!还有职场心得、生活感悟、以及面经点击上方 “杨守乐” ,选择“置顶公众号”,第一时间送达!


 一、概要


本文介绍了有关字符串的算法第一部分的Java代码实现,算法目录:

  • 替换字符串中的空格

  • 输入一个字符串,打印出该字符串的所有排列

  • 第一个只出现一次的字符

  • 翻转句子

  • 计算字符串之间的最短距离

 二、代码实现


2.1 替换字符串中的空格

问题描述

实现一个函数,将字符串p中的所有空格都替换成为指定的字符串r。

解决思路

  • 遍历原始的字符串p,统计原先字符串中空格的个数spaceNum。

  • 创建一个新的数组n,用于存放替换后的字符串。由于原先字符串中空格也占了一个位置,因此新数组n的长度为p.len + (r.len – 1) * spaceNum。

  • 对于p 从后往前遍历,如果 遇到了空格,那么就将需要替换的字符串r中的字符 从后往前 填入n数组中;如果 遇到了非空格,那么就将p中的字符填入n数组中。


实现代码


class Untitled {
   static char[] replaceSpace(char p[], char r[], int pLen, int rLen){
       int spaceNum = 0;
       int i;
       for(i = 0; i < pLen; i++){
           if(p[i] == ' ')
               spaceNum += (rLen-1);
       }
       int nLen = pLen+spaceNum;
       char n[] = new char[nLen+1];
       i = nLen-1;
       int j = pLen-1;
       while(i >= 0 && j >= 0){
           if (p[j] == ' ') {
               for (int k = rLen-1; k >= 0; k--)
                   n[i--] = r[k];
           } else {
               n[i--] = p[j];
           }
           j--;
       }
       n[nLen] = 0;
       return n;
   }
   public static void main(String[] args) {
       char[] source = "I am sentence with space".toCharArray();
       char[] replace = "%20".toCharArray();
       char[] result = replaceSpace(source, replace, source.length, replace.length);
       System.out.println(result);
   }
}

运行结果

I%20am%20sentence%20with%20space

2.2 输入一个字符串,打印出该字符串的所有排列

问题描述

输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

解决思路

这是一个 递归问题,求一个长度为n的字符串的全排列的方法为:

  • n[0..n.len-1]全排列的计算方法为:将n[0]位置的字符分别和n[1..n.len-1]的每一个字符串交换,n[0]和交换后的n[1..n.len – 1]的全排列进行组合。我们将字符串{s}的全排列表示为{s},那么对于abc来说,其全排列{abc},就等于是a + {bc}、b + {ac},c + {ba}。

  • 以此类推,n[1..n.len – 1]的全排列,则是将n[1]分别和n[2..n.len – 1]的每一个字符串交换,再求出交换后的n[2..len – 1]的全排列,递归结束的条件为n[i..n.len – 1]只有一个字符,例如,bc的全排列为b + {c}、c + {b},而{c}和{b}的全排列只有一种,因此递归结束,这时候就可以打印出结果。


实现代码


class Untitled {
   static void permutationStr(char p[], int depth, int length){
       if (depth == length) {
           System.out.println(p);
           return;
       }
       char c;
       for (int i = depth; i < length; i++){
           c = p[depth]; p[depth] = p[i]; p[i] = c;
           permutationStr(p, depth+1, length);
           c = p[depth]; p[depth] = p[i]; p[i] = c;
       }
   }
   public static void main(String[] args) {
       char[] source = "abc".toCharArray();
       permutationStr(source, 0, source.length);
   }
}

运行结果

abc
acb
bac
bca
cba
cab

2.3 第一个只出现一次的字符

问题描述

在字符串中找出第一个只出现一次的字符。如输入abaccdeff,则输出b,要求时间复杂度为O(n)。

解决思路

这里需要采用 以空间换时间 的思想,也就是创建一个足够大的数组c,这里为256,然后对原始的数组p进行两次遍历:

  • 第一次 从头开始 遍历p,以p的值作为数组c的下标,并将c中对应位置的值加1,也就是说c[Integer.valueOf(i)]的值表示的是字符i在p中出现的次数。这和HashMap的原理有些类似,只不过是将查找的key值直接简化成为了value的整型值。

  • 第二次 从头开始 遍历p,查找数组c对应位置该值是否为1,如果为1,那么就表示它是第一次只出现一次的字符。

实现代码

class Untitled {
   static char firstNotRepeat(char p[], int len){
       if (len == 1)
           return p[0];
       int c[] = new int[256];
       int i;
       char r = p[0];
       for (i = 0; i < 256; i++)
           c[i] = 0;
       for (i = 0; i < len; i++)
           c[p[i]] += 1;
       for (i = 0; i < len; i++) {
           if (c[p[i]] == 1) {
               r = p[i];
               break;
           }
       }
       return r;
   }
   public static void main(String[] args) {
       char[] source = "abaccdeff".toCharArray();
       char c = firstNotRepeat(source, source.length);
       System.out.println(c);
   }
}

运行结果

b

2.4 翻转句子

问题描述

翻转句子中单词的顺序,但单词内字符的顺序不变,句子中单词以空格符隔开。例如I am a original string翻转后的结果为string original a am I。

解决思路

实现过程分为两步:

  • 第一步,将整个句子中的所有字符都翻转

  • 第二步,遍历翻转后的句子,对于句子内的每一个单词,将其字符再翻转一次,就能保证单词内字符的顺序不变。翻转单词的时候,通过pStart和pEnd记录每次遇到单词的起止下标,并使用子方法reverseSub对单词中的字符进行翻转。

实现代码

class Untitled {
   static void reverseSub(char p[], int start, int end){
       char c;
       int i = start;
       int j = end;
       while(i < j){
           c = p[i]; p[i] = p[j]; p[j] = c;
           i++; j--;
       }
   }
   static void reverseSentence(char p[], int length){
       //首先翻转整个具体的所有字符。
       reverseSub(p, 0, length-1);
       int pStart = 0;
       int pEnd = 0;
       //从头开始遍历,寻找句子中的单词,pStart和pEnd分别表示单词的起止下标。
       while(pStart < length && pEnd < length){
           if(p[pStart] == ' '){
               pStart++;
               pEnd++;
           } else if (p[pEnd] == ' ' || p[pEnd] == '
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论