今天360的笔试题，100 / 55
第一道题：看了一圈感觉和大家的思路不一样，描述一下我的思路：
从(0, 0)到(m, n)，每当(i, j)上的柱子被计算进来之后，有三处变化：
①增加了柱子的表面积（柱子高度为h(i, j)，即h(i, j) * 4 + 2）；
②减掉两倍的min(h(i, j), h(i - 1, j))，即当前柱子和上一层相邻柱子中较低的那个柱子的高度的两倍；
②减掉两倍的min(h(i, j), h(i, j - 1))，即当前柱子和左边一列相邻柱子中较低的那个柱子的高度的两倍；
代码：
private static int solve(int[][] counts, int rows, int columns){
int[][] results = new int[rows][columns];
for (int i = 0; i < rows; i++){
for (int j = 0; j < columns; j++){
int upCovered = 0, leftCovered = 0;
if (i - 1 >= 0) {
upCovered = Math.min(counts[i][j], counts[i - 1][j]);
results[i - 1][j] -= upCovered;
}
if (j - 1 >= 0) {
leftCovered = Math.min(counts[i][j], counts[i][j - 1]);
results[i][j - 1] -= leftCovered;
}
results[i][j] = counts[i][j] * 4 + 2 - upCovered - leftCovered;
}
}
int result = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
result += results[i][j];
}
}
return result;
} 今天又看了看代码，发现那个results数组是没有必要的，空间复杂度可以降到O(1)。
private static int solve(int[][] counts, int rows, int columns) {
int result = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
int upCovered = 0, leftCovered = 0;
if (i - 1 >= 0) {
upCovered = Math.min(counts[i][j], counts[i - 1][j]);
}
if (j - 1 >= 0) {
leftCovered = Math.min(counts[i][j], counts[i][j - 1]);
}
result += counts[i][j] * 4 + 2 - upCovered * 2 - leftCovered * 2;
}
}
return result;
} 第二道题：先统计第一个数组和第二个数组的“词频”作为各个数字的“库存”，然后凑最高的mod值，减掉相应的“库存”
代码：
//first和second就是两个数组的“词频”，比如 4 4 4 1 1 和 0 1 2 3 4对应 first = {0,2,0,0,3},second = {1,1,1,1,1}
private static int[] solve(int bitCount, int system, int[] first, int[] second) {
int[] result = new int[bitCount];
for (int i = 0; i < bitCount; i++) {
int tmp = 0, i1 = 0, i2 = 0;
for (int p = 0; p < bitCount; p++) {
if (first[p] != 0) {
for (int q = 0; q < bitCount; q++) {
if (second[q] != 0) {
int mod = (p + q) % system;
if (mod > tmp) {
tmp = mod;
i1 = p;
i2 = q;
}
}
}
}
}
result[i] = tmp;
first[i1]--;
second[i2]--;
}
return result;
} 这道题自己不很满意，首先代码格式很丑，其次复杂度太高，考虑了一下，主要是bitCount这个值，如果是个1万进制数，那么每个用例O(n ^ 3)就是万亿级别的计算量，不超时才怪。 目前想到一种O(n ^ 2)的，还没有实现。