笔试题—字符串常见的算法题集锦

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/52602327

笔试题—字符串常见的算法题集锦

本篇博客主要讲解以下四个问题

  • KMP算法
  • 字母倒序输出
  • 全排列
  • 全组合

转载请注明原博客地址: http://blog.csdn.net/gdutxiaoxu/article/details/52602327

例子源码下载地址: http://download.csdn.net/detail/gdutxiaoxu/9635393

KMP算法

关于KMP算法的分析,这里就不讲解了,有兴趣的可以参考这篇博客:从头到尾彻底理解KMP

代码如下

package com.xujun.stringfind;

public class KMPFind {

    public static void main(String[] args) {
        String s = "abcbb2abcabx";
        String c = "abca";
        int[] next = new int[s.length() + 1];
        next = getNext(c);
        for (int i = 0; i < next.length; i++) {
            System.out.println("=" + next[i]);
        }
        int find = matchNext(s, c, 0);
        System.out.println("find=" + find);

        int[] nextVal = getNextVal(c);

        for (int i = 0; i < nextVal.length; i++) {
            System.out.println("=" + nextVal[i]);
        }
        int matchNextVal = matchNextVal(s, c, 0);
        System.out.println("matchNextVal=" + matchNextVal);

    }

    /**
     * 注意这里为了保持保持一致性 ,第一个next[0]没有用到
     * 
     * @param c
     * @return
     */
    private static int[] getNextVal(String c) {
        int[] nextVal = new int[c.length() + 1];
        int front = 0;
        int behind = 1;
        nextVal[1] = 0;
        /**
         * c.charAt(front-1)表示前缀字符 ,c.charAt(behind-1)表示后缀字符
         */
        while (behind < c.length()) {
            if (front == 0 || c.charAt(front - 1) == c.charAt(behind - 1)) {
                ++front;
                ++behind;
                if (c.charAt(front - 1) != c.charAt(behind - 1)) {
                    nextVal[behind] = front;
                } else {
                    nextVal[behind] = nextVal[front];
                }
            } else {
                // 前缀索引回溯
                front = nextVal[front];
            }
        }

        return nextVal;
    }

    /**
     * 注意这里为了保持保持一致性 ,第一个next[0]没有用到
     * 
     * @param c
     * @return
     */
    private static int[] getNext(String c) {
        int[] next = new int[c.length() + 1];
        int front = 0;
        int behind = 1;
        next[1] = 0;
        /**
         * c.charAt(front-1)表示前缀字符 c.charAt(behind-1)表示后缀字符
         */
        while (behind < c.length()) {
            if (front == 0 || c.charAt(front - 1) == c.charAt(behind - 1)) {
                ++front;
                ++behind;
                next[behind] = front;
            } else {
                // 前缀 索引回溯
                front = next[front];
            }
        }

        return next;
    }

    public static int matchNextVal(String source, String c, int pos) {

        int i;
        int[] nextVal = getNextVal(c);
        if (pos < 1) {
            i = 1;
        } else {
            i = pos + 1;
        }
        int j = 1; // i控制S,j控制T;
        while (i <= source.length() && j <= c.length()) {
            if (j == 0 || source.charAt(i - 1) == c.charAt(j - 1)) {
                ++i;
                ++j;
            } else {
                j = nextVal[j]; // j退回合适的位置,i值不变
            }
        }
        if (j > c.length())
            return i - c.length() - 1;
        else
            return -1;
    }

    public static int matchNext(String source, String c, int pos) {

        int i;
        int[] next = getNext(c);
        if (pos < 1) {
            i = 1;
        } else {
            i = pos + 1;
        }
        int j = 1; // i控制S,j控制T;
        while (i <= source.length() && j <= c.length()) {
            if (j == 0 || source.charAt(i - 1) == c.charAt(j - 1)) {
                ++i;
                ++j;
            } else {
                j = next[j]; // j退回合适的位置,i值不变
            }
        }
        if (j > c.length())
            return i - c.length() - 1;
        else
            return -1;
    }

}

字符串倒序输出,单词不倒序

题目 对字符串中的所有单词进行倒排。 说明: 1、每个单词是以26个大写或小写英文字母构成,可能含有非法字符 2、非构成单词的字符均视为单词间隔符; 3、要求倒排后的单词间隔符以一个空格表示;如果原字符串中相邻单词间有多个间隔符时,倒排转换后也只允许出现一个空格间隔符; 4、每个单词最长20个字母;

第一种方法

思路解析

  • 1.我们可以采用正则表达式把字符串分隔成为字符串数组
  • 2.接着我们再倒序输出字符串数组
  • 3.在注意最后一个字符串数组,可能是空格
public class ReverseStr2 {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            String[] strArray = str.split("[^a-zA-Z]+");
            for (int i = strArray.length - 1; i >= 2; i--) {
                System.out.print(strArray[i] + ' ');
            }
            // 如果字符串数组的第一个元素是空串,那么下标为1的元素就是最后一个要输出的元素,末尾不要再加空格
            if (strArray[0].length() == 0)
                System.out.println(strArray[1]);
            else
                System.out.println(strArray[1] + ' ' + strArray[0]);
        }
    }

}

第二种方法

思路解析

  • 对输入的字符串进行分析,去掉非法字符,如中文字符,多个空格只保留一个空格等
  • 对字符串进行分组
  • 倒序输出

代码如下

/**
 * Created by xujun on 2016/9/20
 */
public class ReverseStr {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            StringBuilder sb = new StringBuilder();
            String[] a = filter(sc.nextLine()).split(" ");
            sb.append(a[a.length - 1]);
            for (int i = a.length - 2; i >= 0; i--) {
                sb.append(" " + a[i]);
            }

            System.out.println(sb.toString().trim());
        }
    }

    public static String filter(String s) {
        char[] c = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        boolean isFirstSpace=true;
        for (int i = 0; i < c.length; i++) {
            if ((c[i] >= 'a' && c[i] <= 'z') || (c[i] >= 'A' && c[i] <= 'Z')) {
                sb.append(c[i]);
                isFirstSpace=true;
                continue;
            }
            if(isFirstSpace){
                sb.append(' ');
                isFirstSpace=false;
            }


        }
        return sb.toString();
    }
}

字符串全排列

思路分析

可以采用递归的形式

  • 从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,
  • 从而得到所有元素的全排列。以对字符串abc进行全排列为例,我们可以这么做:以abc为例:
  • 固定a,求后面bc的排列:abc,acb,求好后,a和b交换,得到bac
  • 固定b,求后面ac的排列:bac,bca,求好后,c放到第一位置,得到cba
  • 固定c,求后面ba的排列:cba,cab。
public class permutate {  
    public static int total = 0;  
    public static void swap(String[] str, int i, int j)  
    {  
        String temp = new String();  
        temp = str[i];  
        str[i] = str[j];  
        str[j] = temp;  
    }  
    public static void arrange (String[] str, int st, int len)  
    {  
        if (st == len - 1)  
        {  
            for (int i = 0; i < len; i ++)  
            {  
                System.out.print(str[i]+ "  ");  
            }  
            System.out.println();  
            total++;  
        }  
        else  
        {  
            for (int i = st; i < len; i ++)  
            {  
                swap(str, st, i);  
                arrange(str, st + 1, len);  
                swap(str, st, i);  
            }  
        }  

    }  
    /** 
     * @param args 
     */  
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
         String str[] = {"a","b","c"};  
         arrange(str, 0, str.length);  
         System.out.println(total);  
    }  
}

运行以上代码,将可以看到以下输出

a b c d a b d c a c b d a c d b a d c b a d b c b a c d b a d c b c a d b c d a b d c a b d a c c b a d c b d a c a b d c a d b c d a b c d b a d b c a d b a c d c b a d c a b d a c b d a b c 24


全组合

第一种方法

思路解析

基本思路:求全组合,则假设原有元素n个,则最终组合结果是2^n个。

原因是: 用位操作方法:假设元素原本有:a,b,c三个,则1表示取该元素,0表示不取。故去a则是001,取ab则是011.所以一共三位,每个位上有两个选择0,1.所以是2^n个结果。

这些结果的位图值都是0,1,2….2^n。所以可以类似全真表一样,从值0到值2^n依次输出结果:即:

000,001,010,011,100,101,110,111

对应输出组合结果为:

空,a, b ,ab,c,ac,bc,abc.

这个输出顺序刚好跟数字0~2^n结果递增顺序一样,取法的二进制数其实就是从0到2^n-1的十进制数

public static  void Combination( ) {
        /*基本思路:求全组合,则假设原有元素n个,则最终组合结果是2^n个。原因是:
         * 用位操作方法:假设元素原本有:a,b,c三个,则1表示取该元素,0表示不取。故去a则是001,取ab则是011.
         * 所以一共三位,每个位上有两个选择0,1.所以是2^n个结果。
         * 这些结果的位图值都是0,1,2....2^n。所以可以类似全真表一样,从值0到值2^n依次输出结果:即:
         * 000,001,010,011,100,101,110,111 。对应输出组合结果为:
        空,a, b ,ab,c,ac,bc,abc.
        这个输出顺序刚好跟数字0~2^n结果递增顺序一样
        取法的二进制数其实就是从0到2^n-1的十进制数
         * ******************************************************************
         * * 
         * */
        String[] str = {"a" , "b" ,"c"};
        int n = str.length;                                  //元素个数。
        //求出位图全组合的结果个数:2^n
        int nbit = 1<<n;                                     // “<<” 表示 左移:各二进位全部左移若干位,高位丢弃,低位补0。:即求出2^n=2Bit。
        System.out.println("全组合结果个数为:"+nbit);

        for(int i=0 ;i<nbit ; i++) {                        //结果有nbit个。输出结果从数字小到大输出:即输出0,1,2,3,....2^n。
            System.out.print("组合数值  "+i + " 对应编码为: ");
            for(int j=0; j<n ; j++) {                        //每个数二进制最多可以左移n次,即遍历完所有可能的变化新二进制数值了
                int tmp = 1<<j ;        
                if((tmp & i)!=0) {                            //& 表示与。两个位都为1时,结果才为1
                    System.out.print(str[j]);
                }
            }
            System.out.println();
        }
    }

第二种方法

思路解析

n个元素选m个元素的组合问题的实现. 原理如下:

从后往前选取, 选定位置i后, 再在前i-1个里面选取m-1个. 如: 1, 2, 3, 4, 5 中选取3个元素.

  • 1) 选取5后, 再在前4个里面选取2个, 而前4个里面选取2个又是一个子问题, 递归即可;
  • 2) 如果不包含5, 直接选定4, 那么再在前3个里面选取2个, 而前三个里面选取2个又是一个子问题, 递归即可;
  • 3) 如果也不包含4, 直接选取3, 那么再在前2个里面选取2个, 刚好只有两个.
    • 纵向看, 1与2与3刚好是一个for循环, 初值为5, 终值为m.
    • 横向看, 该问题为一个前i-1个中选m-1的递归.

代码如下

package com.xujun.PermutationCombinationHolder;

public final class PermutationCombinationHolder {

    /** 数组元素的全组合 */
    static void combination(char[] chars) {
        char[] subchars = new char[chars.length]; // 存储子组合数据的数组
        // 全组合问题就是所有元素(记为n)中选1个元素的组合, 加上选2个元素的组合...加
        // 上选n个元素的组合的和
        for (int i = 0; i < chars.length; ++i) {
            final int m = i + 1;
            combination(chars, chars.length, m, subchars, m);
        }
    }

    /**
     * n个元素选m个元素的组合问题的实现. 原理如下: 从后往前选取, 选定位置i后, 再在前i-1个里面选取m-1个. 如: 1, 2, 3, 4,
     * 5 中选取3个元素. 1) 选取5后, 再在前4个里面选取2个, 而前4个里面选取2个又是一个子问题, 递归即可; 2) 如果不包含5,
     * 直接选定4, 那么再在前3个里面选取2个, 而前三个里面选取2个又是一个子问题, 递归即可; 3) 如果也不包含4, 直接选取3,
     * 那么再在前2个里面选取2个, 刚好只有两个. 纵向看, 1与2与3刚好是一个for循环, 初值为5, 终值为m. 横向看,
     * 该问题为一个前i-1个中选m-1的递归.
     */
    static void combination(char[] chars, int n, int m, char[] subchars,
            int subn) {
        if (m == 0) { // 出口
            for (int i = 0; i < subn; ++i) {
                System.out.print(subchars[i]);
            }
            System.out.println();
        } else {
            for (int i = n; i >= m; --i) { // 从后往前依次选定一个
                subchars[m - 1] = chars[i - 1]; // 选定一个后
                combination(chars, i - 1, m - 1, subchars, subn); // 从前i-1个里面选取m-1个进行递归
            }
        }
    }

    /** 数组元素的全排列 */
    static void permutation(char[] chars) {
        permutation(chars, 0, chars.length - 1);
    }

    /** 数组中从索引begin到索引end之间的子数组参与到全排列 */
    static void permutation(char[] chars, int begin, int end) {
        if (begin == end) { // 只剩最后一个字符时为出口
            for (int i = 0; i < chars.length; ++i) {
                System.out.print(chars[i]);
            }
            System.out.println();
        } else {
            for (int i = begin; i <= end; ++i) { // 每个字符依次固定到数组或子数组的第一个
                if (canSwap(chars, begin, i)) { // 去重
                    swap(chars, begin, i); // 交换
                    permutation(chars, begin + 1, end); // 递归求子数组的全排列
                    swap(chars, begin, i); // 还原
                }
            }
        }
    }

    static void swap(char[] chars, int from, int to) {
        char temp = chars[from];
        chars[from] = chars[to];
        chars[to] = temp;
    }

    static boolean canSwap(char[] chars, int begin, int end) {
        for (int i = begin; i < end; ++i) {
            if (chars[i] == chars[end]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        final char[] chars = new char[] { 'a', 'b', 'c' };
        permutation(chars);
        System.out.println("===================");
        combination(chars);
    }
}

题外话

  • 已经有20多天没更新博客了,主要是因为家里有事,回家了十来天,最近又在校招,有时候参加宣讲会与招聘,有时候在准备笔试和面试的东西。
  • 现在还没有拿到offer,也是感觉挺可惜的。
  • 接下来更新博客的频率可能会比较不稳定

转载请注明原博客地址: http://blog.csdn.net/gdutxiaoxu/article/details/52602327

例子源码下载地址: http://download.csdn.net/detail/gdutxiaoxu/9635393

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

请问你知道什么是栈吗?

1.1栈的概念及记本操作 栈(stack)又称堆栈,是限制在表的一端进行插入和删除的线性表。其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行...

3138
来自专栏赵俊的Java专栏

快乐数

2333
来自专栏Android知识点总结

01--图解数据结构之数组实现集合

1304
来自专栏个人分享

Scala第一章学习笔记

  面向对象编程是一种自顶向下的程序设计方法。用面向对象方法构造软件时,我们将代码以名词(对象)做切割,每个对象有某种形式的表示服(self/this)、行为(...

1052
来自专栏desperate633

LintCode 比较字符串题目分析代码

比较两个字符串A和B,确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母

561
来自专栏个人随笔

Java 关于集合框架那点事儿

 1.引入集合框架   采用数组存在的一些缺陷:    1.数组长度固定不变,不能很好地适应元素数量动态变化的情况。    2.可通过数组名.length获取数...

29110
来自专栏专注 Java 基础分享

从源码解析LinkedList集合

     上篇文章我们介绍了ArrayList类的基本的使用及其内部的一些方法的实现原理,但是这种集合类型虽然可以随机访问数据,但是如果需要删除中间的元素就...

2025
来自专栏追不上乌龟的兔子

Python中最快的格式化字符串方式

第一种是传承自C语言printf函数的使用%占位符格式化字符串,如'%d' % 100,这种方式严格来说是使用%作为算数运算符进行的二元运算,而且有一个限制是只...

1074
来自专栏java学习

重要通知!小编出新的Java练习题咯!!

正确答案 3月5号公布 一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是( )。 A. import ...

4225
来自专栏书山有路勤为径

合法的出栈序列

poj 1363 Rails 已知从1至n的数字序列,按顺序入栈,每个数字入栈后即可出栈,也可在栈中 停留,等待后面的数字入栈出栈后,该数字再出栈,求该数字序...

812

扫码关注云+社区

领取腾讯云代金券