一道算法题，了解一下？

前言

说实话，看到算法题我是慌的，一般我都是直接“对不起，告辞”。但是，今天看到球友分享的智线18年笔试题，试着看了第一道：

image

emmm，好像不怎么难，让我想到了以前做的一道题。

题：求在字符串中找出第一个只出现一次的字符

可以说是非常常见了，实现也比较简单，精髓就在注释的那一行。

    private static char findString(char p[],int length) {
        if (length == 1) {
            return p[0];
        }
        int c[] = new int[256];
        int i;
        char r = p[0];
        for (i = 0; i < 256; i++) {
            c[i] = 0;
        }
        //以p的值作为数组c的下标，c的值表示字符i在p中出现的次数
        for (i=0;i<length;i++) {
            c[p[i]] += 1;
        }
        for (i=0;i<length;i++) {
            if (c[p[i]] == 1) {
                r = p[i];
                break;
            }
        }
        return r;
    }

这道题理解了，那上面求超集就很简单了，思路一样，可以说，求字符个数，是否包含这一类算法题大都可以用这个思路。

判断超集：

    private static boolean isSuperSet(char[] charsOne, char[] charsTwo) {

        if (charsOne.length < charsTwo.length) {
            return false;
        }
        int[] intsOne = toIntArray(charsOne);
        int[] intsTwo = toIntArray(charsTwo);
        for (int i = 0; i < intsTwo.length; i++) {
            if (intsOne[i] < intsTwo[i]) {
                return false;
            }
        }
        return true;
    }

    private static int[] toIntArray(char[] chars) {
        //取字符最大Ascall
        int[] counts = new int[256];
        for (int i = 0; i < counts.length; i++) {
            counts[i] = 0;
        }
        //以aChar的值作为数组counts的下标，counts[aChar]的值表示该字符在chars中出现的次数
        for (char aChar : chars) {
            counts[aChar] += 1;
        }
        return counts;
    }

    public static void main(String[] args) {
        String a = "abbccdd";
        String b = "abcdd";
        System.out.println(isSuperSet(a.toCharArray(), b.toCharArray()));
        String c = "abbccd";
        String d = "abcdd";
        System.out.println(isSuperSet(c.toCharArray(),d.toCharArray()));
    }

最后

当然，智线三道算法题，最后一题还是要告辞的。

image