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;
}