动力节点口口相传的Java黄埔军校
Java程序员面试字符串算法教程
2019-09-09 来源:动力节点



  一、概要


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


  替换字符串中的空格


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


  第一个只出现一次的字符


  翻转句子


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


  “二、代码实现


  2.1替换字符串中的空格


  问题描述


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


  解决思路


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


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


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


  实现代码


image.png

  运行结果

image.png

  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}的全排列只有一种,因此递归结束,这时候就可以打印出结果。


  实现代码

image.png

  运行结果

image.png

  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,那么就表示它是第一次只出现一次的字符。


  实现代码

image.png

  运行结果

image.png

  2.4翻转句子


  问题描述


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


  解决思路


  实现过程分为两步:


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


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


  实现代码

image.png

  运行结果为:

image.png

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


  问题描述


  假设我们有两个字符串A和B,那么如果想要将字符串A通过以下三种操作变换成B:删除、新增和修改,操作步骤的次数就称为字符串A和B之间的距离。


  现在给定两个字符串,求这两个字符串之间的最短距离。


  解决思路


  首先,我们需要先明确一个前提条件:如果A的长度为0,那么A和B之间的距离就为B的长度,反之对于B也如此。


  下面,我们在来看普通的情况,假如A[0]和B[0]相同,那么A和B之间的距离就为A[1..A.len-1]和B[1..B.len-1]之间的距离;假如A[0]和B[0]不相同,那么想要让A和B相同,执行的操作有以下几种:


  删除A的第一个字符,然后计算A[1..A.len-1]和B[0..B.len-1]的距离


  删除B的第一个字符,然后计算A[0..A.len-1]和B[1..B.len-1]的距离


  修改A的第一个字符为B的第一个字符,然后计算A[1..A.len-1]和B[1..B.len-1]的距离


  修改B的第一个字符为A的第一个字符,然后计算A[1..A.len-1]和B[1..B.len-1]的距离


  增加A的第一个字符到B第一个字符之前,然后计算A[1..A.len-1]和B[0…B.len-1]的距离


  增加B的第一个字符到A第一个字符之前,然后计算A[0…A,len-1]和B[1..B.len-1]的距离


  对于以上这六种情况,其实最终都可以归纳为经过一次操作,再加上剩下部分的操作次数,那么我们的接下来的工作就是求出剩下部分的操作部分的最小值。对于上面的任意一种情况,经过划分后A和B的长度都会减少,那么最终必然会达到我们在一开始谈到的前提条件:如果A的长度为0,那么A和B之间的距离就为B的长度,反之对于B也如此。

  实现代码

image.png

  运行结果:

image.png

  以上就是动力Java培训机构小编介绍的“Java程序员面试字符串算法教程”的内容,希望对大家有帮助,如有疑问,请在线咨询,有专业老师随时为你服务。


  



开班信息

同类文章

微信搜索“动力节点Java学院“或扫二维码

关注官方微信免费领学习资料

动力节点Java培训机构,行业口碑最好的Java培训机构。

立即抢名额