18年春招美团笔试题

发表于 | 分类于 | 阅读次数

一共两道题，相对其他公司的笔试来说是最简单的了

  1. 字符串距离
    给出两个相同长度的由字符a和b构成的字符串，定义它们的距离为对应位置不同的字符的数量，如串”aab”和串”aba”的距离为2，串”ba”与”aa”的距离为1。
    下面给出两个字符串S与T，其中S的长度不小于T的长度，我们用|S|代表S的长度，|T|代表T的长度，那么在S中一共有|S|-|T|+1个与T长度相同的子串，现在你需要计算T串与这些|S|-|T|+1个子串的距离的和

  2. 数字字符
    在十进制表示中，任意一个正整数都可以用字符’0’-‘9’表示出来，但是当这些字符每种字符的数量是有限的时候，可能有些正整数就无法表示出来了，比如你有两个’1’，一个’2’，那么你能表示出来11,12,121等等，但是无法表示出10，122，200等，现在你手上拥有一些字符，它们都是’0’-‘9’的字符，你可以选出其中一些字符然后将它们组合成一个数字，那么你所无法组成的最小正整数是多少？

这两道题可以说非常简单了，就是优化的问题

字符串距离

题目说的非常清楚了，字符串S长度大于字符串T，在S中一共有|S|-|T|+1个与T长度相同的子串，那么直接比较这些串就可以了，立马就写了如下函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public  static int distance(String s,String t){
    int res=0;
    for(int i=0;i<s.length();i++){
        if(s.charAt(i)!=t.charAt(i))res++;
    }
    return res;
}
public static int theAllDistance(String s,String t){
    int res=0;
    int ls=s.length();
    int lt=t.length();
    for(int i=0;i<=ls-lt;i++){
        res+=distance(s.substring(i,lt+i),t);
    }
    return res;
}
public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
    String s,t;
    s=scanner.next();
    t=scanner.next();
    scanner.close();
    System.out.println(theAllDistance(s,t));
}

其实这个函数复杂度还是有点高的，因为没有利用前面比较的信息，肯定是有优化的方法的，但是牛客网上通过了，我也就没想了。

数字字符

这道题也是按照题目直接出思路，找最小的正整数，那我就从1开始遍历，直到找到一个不能表示的正数就是题目要求的结果了，具体的，先将给定的字符串转为字符数组，并排序，然后将遍历的数字也转为字符数组，并排序，然后查看遍历的字符数组是否是给定的字符数组的子集。
于是写下如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static boolean getTheNumber(char[] chars,char[] cs){
    int k=0;
    for(int j=0;j<cs.length;j++){
        while (k<chars.length&&chars[k]<cs[j])k++;
        if((k<chars.length&&chars[k]!=cs[j])||k==chars.length)return false;
        k++;
    }
    return true;
}
public static int getMinNumber(char[]chars){
    int i=1;
    while (true){
        char[] cs=Integer.toString(i).toCharArray();
        Arrays.sort(cs);
        if(getTheNumber(chars,cs))i++;
        else return i;
    }
}
public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
    String s;
    s=scanner.next();
    char[] chars=s.toCharArray();
    Arrays.sort(chars);
    System.out.println(getMinNumber(chars));
}

非常暴力了，然后牛客网显示时间复杂度过大，后面我就开始找规律，如下：
字符’1’-‘9’如果没有被包含，就返回没有包含的最小的字符表示的数字
没有包含’0’就返回数字10
如果已经包含了’0’-‘9’这10个字符，那么在1-100内的数字中，主要看11，22，33，44，..100这样的数字了，也就是对应的数字必须出现两次
1-100也满足了，就要看101-1000的情况，同样的，需要看111，222，333，444，…1000的情况…
于是发现的规律就是统计数字的个数，从1开始遍历到10（对应到0），每次都将对应的字符中的个数减少1，判断减少后的个数是否大于等于0，如果不满足，则找到该数字（该数字是由对应字符对应次数组成），返回。
这样子就将时间复杂度从上面的方法降到了lgn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//返回有k+1个i组成的数字
public static int getNum(int i,int k){
    String si=String.valueOf(i);
    String res="";
    for(int j=0;j<k;j++){
        res+=si;
    }
    return Integer.parseInt(res+si);
}
public static int getMinNumber(char[]chars){
    int [] nums=new int[10];//统计各个数字出现的次数
    for(int i=0;i<chars.length;i++){
        nums[chars[i]-'0']++;
    }
    int i=1;
    int k=0;
    while(true){
        if(i==10){
            i=0;
            k++;
        }
        nums[i]--;
        if(nums[i]<0)return getNum(i,k);
        i++;
    }
}
public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
    String s;
    s=scanner.next();
    char[] chars=s.toCharArray();
    Arrays.sort(chars);
    System.out.println(getMinNumber(chars));
}

如果觉得有帮助，给我打赏吧！