[面经]阿里游戏一面的算法题

算法题

前言：两天前参加阿里游戏的面试，一面时出了一道面试题。那时我看楞了，好像没做过这种题型，看起来很容易又很难。很容易是，使用O(N^2)就可以解决，难得是，优化时间复杂度。

题目：字符串删除字符（字符可能会有重复，要一起删掉）

思路一（反正面试我没这么写，你们随便看看）

一开始看到题目，思路就遍历字符串，一个个字符比较，然后删除它。
(1) 遍历数组，找到目标字符；
(2) 移动目标字符后面的所有字符，各向前移动复制1位；
(3) 删除最后一位字符(或标识它不可用)；
(4) 重复(1)直至循环结束。

优点(当然有)：容易想出来，代码逻辑简单；
缺点：时间复杂度O(N^2)。

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
public static String deleteChar(String str, char c)
{
    if (str == null || "".equals(str)) return str;
    int len = str.length();
    char[] ca = str.toCharArray();
    for (int i = 0; i < len; i++)
    {
        while (len != 0 && ca[i] == c)
        {
            len--;
            if(len!= i){
                for (int j = i; j < len; j++)
                {
                    ca[j] = ca[j + 1];
                }
            }
            else{
                break;
            }
        }
    }
    if (len == str.length()) return str;
    // java被迫无奈~
    return new String(ca,0, len);
}

思路二(逗比的我的现场解法)

有没有办法一次性将所有字符集合在一起，然后一起删除掉呢？有没有很熟悉呢？快速排序？没错就是它！我们在实现快速排序时用到的关键方法partition的思路！里面比较大和小，我们这里换成比较相等于不想等就Ok啦！对不对！？

优点：时间复杂度：O(N)；
缺点：字符串乱序。

这里的代码我就不写出来了，需要的话，参考快速排序代码。

思路三(机智的我开窍改回来了)

增强版的partition。同样的思路来自于快速排序算法，经典的快速排序算法对付很多重复数的数组效率低，有人发明了改进这一效率的partition。思路是使用三个指针，第一个指针相当于经典快排的第一个指针，后面两个指针相当于经典快排的最后一个指针，只是两个指针间的数都是相等重复的数。

步骤

优点：克服和思路二的缺点，又具有思路二的优点。

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
public static String deleteChar(String str, char c)
{
    if (str == null || "".equals(str)) return str;
    int i = 0;
    int j = 0;
    int len = str.length();
    for (; i < len && str.charAt(i) != c; i++);

    if (i == len) return str;
    // 下面是重点
    char[] ca = str.toCharArray();
    j = i;
    while (j < len)
    {
        while (j < len && ca[j] == c)
        {
            j++;
        }
        if (j >= len) break;
        // 交换
        exch(ca, i++, j);
    }
    // java被迫无奈~
    return new String(ca,0,i);
}