位置：太原达内IT培训学校 > 学校动态 > 太原Java程序员面试字符串算法教程

太原Java程序员面试字符串算法教程

来源：太原达内IT培训学校时间：2022/1/17 16:16:01

　　一、概要
　　本文介绍了有关字符串的算法部分的Java代码实现，算法目录：
　　替换字符串中的空格
　　输入一个字符串，打印出该字符串的所有排列
　　个只出现一次的字符
　　翻转句子
　　计算字符串之间的较短距离
　　“二、代码实现
　　2.1替换字符串中的空格
　　问题描述
　　实现一个函数，将字符串p中的所有空格都替换成为指定的字符串r。
　　解决思路
　　遍历原始的字符串p，统计原先字符串中空格的个数spaceNum。
　　创建一个新的数组n，用于存放替换后的字符串。由于原先字符串中空格也占了一个位置，因此新数组n的长度为p.len+(r.len-1)*spaceNum。
　　对于p从后往前遍历，如果遇到了空格，那么就将需要替换的字符串r中的字符从后往前填入n数组中；如果遇到了非空格，那么就将p中的字符填入n数组中。
　　实现代码
　　运行结果
　　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}的全排列只有一种，因此递归结束，这时候就可以打印出结果。
　　实现代码
　　运行结果
　　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，那么就表示它是次只出现一次的字符。
　　实现代码
　　运行结果
　　2.4翻转句子
　　问题描述
　　翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。例如Iamaoriginalstring翻转后的结果为stringoriginalaamI。
　　解决思路
　　实现过程分为两步：
　　步，将整个句子中的所有字符都翻转
　　第二步，遍历翻转后的句子，对于句子内的每一个单词，将其字符再翻转一次，就能增加单词内字符的顺序不变。翻转单词的时候，通过pStart和pEnd记录每次遇到单词的起止下标，并使用子方法reverseSub对单词中的字符进行翻转。
　　实现代码
　　运行结果为：
　　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也如此。

领取试听课

每天限量名额，先到先得

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/2387/news/477038/违者必究！以上就是太原达内IT培训学校小编为您整理 太原Java程序员面试字符串算法教程的全部内容。