[面经]CVTE的两道笔试编程题

算法题

晚上状态有点不好，然后就仓促参加笔试了。前面很多道选择题，真是坑，都是多选（混杂了多道单选）。下面就说说笔试题的两道编程题吧。其实我做的时候也是挺紧张的，随意符合题意的做完提交，也没加以优化，其实如果时间允许，我也是蛮想优化下的，不过这 场笔试不是看你优化得有多好，而是看你做对了没。

第一道题：字符数组的循环右移问题

题目要求：将N个字符的数组，循环右移K位。时间复杂度O(N)。
现场思路：

  1. k可以小于N，大于N，等于N，按照这几种请况分析。首先我们必须知道，当N=dK（d=0,1,2..）时，字符数组循环右移后，字符数组中字符位置不变。有了这个“突破口”我们就能将K>N转化成K<=N来解，这样缩小了判断的范围。
  2. 接下来我们只需要分析K<N的情况就可以了。由于需要修改原来数组，题目没要求限制使用的空间复杂度，这里，我就偷了个懒，申请了一个O(N)的字符数组，保存原来的数组中字符及其位置，然后就可以大胆的随意修改原来的数组了。for循环遍历复制数组，然后让当前数组下标(i+K)%length，这里+K就将字符右移了K位，%length让右移循环了。
  3. 整理一下上面的思路，OK，写代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
public static void solution(int[] arr, int length, int shiftStep)
{
    if(arr==null||length==0) return;
    int count=shiftStep%length;
    if(count==0) return;
    int[] copy=new int[length];
    for(int i=0;i<length;i++){
        copy[i]=arr[i];
    }
    for(int i=0;i<length;i++){
        arr[(i+count)%length]=copy[i];
    }
}

第二道题：字符串去重问题

题目要求：删除小写字母字符串中重复字符。如果可以，优先删除重复字符中排在比他小字符前面的字符。 比如，输入：bbcacdww；输出：bacdw
现场思路：一开始，我本来在想这个问题的最优解，排除使用“暴破”。想了一阵子，可能是太紧张了，思路不开。时间快到了，被迫是用“暴破”。然而“暴破”也不是那么容易的，orz。

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
37
38
39
40
41
42
43
public static String solution(String s)
{
    if(s==null||"".equals(s)) return s;

    StringBuilder sb = new StringBuilder(s);
    int i = 0;
    while (i < sb.length())
    {
        char temp = sb.charAt(i);
        boolean isR = false; // 是否有重复的字符在i的前面
        boolean isFront = true; // 要删除后面的重复字符?true删除后面的重复字符:false删除前面的重复字符
        int j = i + 1;
        while (j < sb.length())
        {
            if (isFront && sb.charAt(j) < temp)
            {
                isFront = false;
            }
            if (sb.charAt(j) == temp)
            {
                if (isFront)
                {
                    sb.deleteCharAt(j);
                    continue;
                }
                else
                {
                    isR = true;
                }
            }
            j++;
        }
        if (isR)
        {
            sb.deleteCharAt(i);
        }
        else
        {
            i++;
        }
    }
    return sb.toString();
}

总结： 算法题还是要有针对性的刷题，然后从中提取解法和经验。