Juconcurrent 学而不思则罔,思而不学则殆。

关于char数组的三个算法题


前言

针对char数组我们可以创造很多算法题,有一些是有现成的算法来实现(比如排序、查找等等),有一些却是需要我们具有机灵和应变的能力。

这里,我们罗列几个关于char数组的题目,然后给出实现思路和代码。希望通过对这些题目的分析,将我们固有的、僵化的思想给稍微活络一下,以纪念我们逝去的青春。

1. 给定一个char数组,找出重复次数最多的char元素

这个题目有很多实现的方式,比如我们可以通过jdk集合类来进行实现,但是效率并不会很高。

这里给出一种不需要额外集合和类库的实现方式。

/**
 * 给定一个char数组,找出重复次数最多的char元素
 */
private static void getCharWhichCountIsMax() {
    // 输入char数组
    char[] chars = "acbcbacccdaaaaaaaaaaaaaaaaaaaaaaaaccccccccccccccebb".toCharArray();
    char tmp;

    // 将char数组进行排序
    for (int i = 0; i < chars.length; i++) {
        for (int j = i + 1; j < chars.length; j++) {
            if (chars[i] > chars[j]) {
                tmp = chars[j];
                chars[j] = chars[i];
                chars[i] = tmp;
            }
        }
    }

    // 对排序后的char数组进行长度最大的获取
    char a = ' ';
    int aSize = 0;
    char b = ' ';
    int bSize = 0;
    for (int i = 0; i < chars.length - 1; i++) {
        if (chars[i] == chars[i + 1]) {
            b = chars[i];
            bSize++;
        } else {
            if (bSize > aSize) {
                a = b;
                aSize = bSize;
            }
            b = chars[i + 1];
            bSize = 0;
        }
    }
    System.out.println(a);
}

2. 给定一个char数组,去掉里面的重复元素

去掉重复元素,首先需要判断哪些元素是属于重复的。怎么判断呢?我首先想到的是能否借鉴jdk集合类库来辅助我们完成功能呢?答案是肯定的,但是它的效率(时间和空间)是值得思考的。

这儿仍然给出一种比较好的实现方式。

/**
 * 给定一个char数组,去掉里面的重复元素
 */
private static void dropRepeatableChar() {
    char[] chars = "hello world this is myself".toCharArray();
    // 实现的思路为,遍历整个char数组,将不重复的数据进行交换和前移
    int unRepeatIdx = 0;
    for (int i = 0; i < chars.length; i++) {
        boolean isRepeat = false;
        for (int j = 0; j < unRepeatIdx + 1; j++) {
            if (chars[j] == chars[i]) {
                isRepeat = true;
                break;
            }
        }
        if (!isRepeat) {
            unRepeatIdx++;
            chars[unRepeatIdx] = chars[i];
        }
    }

    // 将不重复的char进行输出
    for (int i = 0; i < unRepeatIdx; i++) {
        System.out.print(chars[i]);
    }
    System.out.println();
}

3. 给定一个char数组,里面的单词使用空格进行分离,将空格分离的单词进行反向输出

这个题目就稍微难一点,咋一看,貌似需要对每个数组元素进行移动,但是怎么个移动法会使移动的效率更高呢?

最简单的方式是先将整个char数组进行反转,再将char数组里面的每个单词进行反转,就能达到我们想要的效果了。思路很简单,那么怎么实现这个算法呢?我们来看一看java代码。

/**
 * 给定一个char数组,里面的单词使用空格进行分离,将空格分离的单词进行反向输出
 * 比如char数组为:hello world this is myself
 * 我们需要得到新的char数组为:myself is this world hello
 */
private static void letWordsInverseOutput() {
    char[] chars = "hello world this is myself".toCharArray();
    char tmp;

    // 先将整个数组进行反转
    for (int i = 0; i < chars.length / 2; i++) {
        tmp = chars[i];
        chars[i] = chars[chars.length - i - 1];
        chars[chars.length - i - 1] = tmp;
    }

    // 再将数组里面的每个单词进行反转
    int start = 0;
    int end;
    for (int i = 0; i <= chars.length; i++) {
        if (i == chars.length || chars[i] == ' ') {
            end = i - 1;
            if (end < 0) {
                continue;
            }
            int k = 0;
            for (int j = start; j <= (start + end) / 2; j++) {
                tmp = chars[j];
                chars[j] = chars[end - k];
                chars[end - k] = tmp;
                k++;
            }
            start = i + 1;
        }
    }
    System.out.println(chars);
}

总结

在实现之前,别人问我这些问题时,我需要绞尽脑汁地想实现方式,但想出的思路不一定是一个好的方式,甚至有时候想不出一个能解决问题的方式,这就很尴尬了。但是一旦我们实现了这些问题,再回过头来看,我们发现这些实现竟然如此简单,甚至还非常高效!

因此,当看一个问题时,我们需要从一个不同的、多维度的视角来看,往往能看到和常人不一样的东西,做人和做事也是一样。

谨以此文献给思路狭隘的自己!


Content