9.14 去哪儿笔试（开发）（含个人解题思路代码）

如果有更好的思路欢迎在评论区讨论。共勉~

第一题：如果一个数可以整除3，那么它每位数的和一定是3的倍数。

我们记录下来0-9每个数出现了多少次，并记录一下这些数的和 sum。

计算 sum % 3

0: 符合要求，直接输出就好。

1: 需要删除一个 %3 = 1 的数，如果没有就删除两个 %3 = 2的数。

2: 同1。

public String solution1(int[] d) {
    int[] cnt = new int[10];
    int[] modulo = new int[3];
    int sum = 0;
    for (int t : d) {
        ++cnt[t];
        ++modulo[t % 3];
        sum += t;
    }
    int l; // %3 == l的数 删除 r 个
    int r;
    int mod = sum % 3;
    if (mod == 0) {
        l = r = 0;
    } else {
        if (modulo[mod] >= 1) {
            l = mod;
            r = 1;
        } else {
            l = 2 * mod % 3;
            r = 2;
        }
    }
    StringBuffer buffer = new StringBuffer();
    for (int i = 0; i < 10; i++) {
        char ch = (char) (i + '0');
        for (int j = 0; j < cnt[i]; ++j) {
            if (r > 0 && i % 3 == l) {
                --r;
            } else {
                buffer.append(ch);
            }
        }
    }
    // 0000 的情况
    if (buffer.length() > 0 && buffer.charAt(buffer.length() - 1) == '0') {
        buffer = new StringBuffer("0");
    }
    return buffer.reverse().toString();
}

第二题：记录下来所有正数的和 sum。

负数扔到优先队列中（从大到小）从中依次取数，定义一个变量t 记录要选的所有负数的和。

那么选择一个负数带来的收益就是 sum + t(t是负的)。

只需判断 abs(t) 是否小于等于 sum 。

更好的思路：

一个sum记录选择的数的和。每选一个数，带来的收益就是sum。

//笔试时写的
public int solution2(int[] arr) {
    int sum = 0;
    PriorityQueue<Integer> que = new PriorityQueue<>();
    PriorityQueue<Integer> fuQ = new PriorityQueue<>((o1, o2) -> o2 - o1);
    for (int t : arr) {
        if (t >= 0) {
            sum += t;
            que.add(t);
        } else {
            fuQ.add(t);
        }
    }
    int k = 1;
    int ans = 0;
    int t = 0;
    int last = 0;
    while (!fuQ.isEmpty()) {
        t += fuQ.remove();
        if (-t <= sum) {
            ans += t;
            k++;
        }
    }
    while (!que.isEmpty()) {
        t = que.remove();

        ans += t * k;
        k++;
    }
    return ans;
}
// 更好的思路
public static int solution2_2(int[] arr) {
    Arrays.sort(arr);
    int ans = 0;
    int sum = 0;
    for(int i = arr.length - 1; i >= 0 ;i--){
        sum+=arr[i];
        if(sum > 0) ans += sum;
        else break;
    }
    return ans;
}

第三题：我的算法最差应该是 O(n2) 的时间复杂度。

我发现一个规律，半回文串都是 1232123 、 1234321234 这种由两个回文串组成。第一个: 12321 和 32123 。第二个1234321、4321234。

但是长度为4的半回文串不符合上述规律，需单独处理。 if(s[i] == s[i+2] && s[i+1] == s[i+3])

然后利用马拉车算法 (O(n)) 求出 每个下标为中心 的回文串长度。去判断上述规律。 len[i] == len[j] && j - i == len[i]/2 - 2; len[i] 表示以 s[i] 为中心的回文串的长度。

判断最差是O(n2)的算法。

public int solution3(String str) {
    if (str == null || str.length() < 4) return 0;
    StringBuilder sb = new StringBuilder();
    sb.append("$");
    char[] s = str.toCharArray();
    int ans = 0;
    for (int i = 0; i < str.length(); i++) {
        if (i + 3 < str.length())
            if (s[i] == s[i + 2] && s[i + 1] == s[i + 3]) ans++;
        sb.append('#');
        sb.append(s[i]);
    }

    sb.append("#@");
    int n = sb.length();
    int[] p = new int[n];
    int id = 0, mx = 0;
    int idex = 0;
    for (int j = 1; j < n - 1; j++) {
        p[j] = mx > j ? Math.min(p[2 * id - j], mx - j) : 1;
        while (sb.charAt(j + p[j]) == sb.charAt(j - p[j])) {
            p[j]++;
        }
        if (mx < p[j] + j) {
            mx = p[j] + j;
            id = j;
        }
    }
    for (int j = 2; j < n - 1; j += 2) {
        if (p[j] >= 6) {
            int tem = p[j];
            for (int i = j + p[j] - 2; i >= j + 4; i -= 2) {
                if (p[i] >= tem) ans++;
                tem-=2;
            }
        }
    }
    return ans;
}

#去哪儿##笔试题目#