携程笔试记录
1题 交通拥塞路段。浮点数比较大小可能出现问题，最好转换成整数比较
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = sc.nextInt();
}
// 窗口范围[k,n], 平均值最大，次之窗口最宽
int[] preSum = new int[n + 1];
for (int i = 1; i<= n; ++i) {
preSum[i] = preSum[i-1] + arr[i-1]; // preSum[i] = sum(arr[1..i))
}
long sum = 0;
int st = 0, ed = 0; // avg = sum / (ed - st)
for (int i = 0; i <= n - k; ++i) {
for (int j = i + k; j <= n; ++j) {
long tmpSum = preSum[j] - preSum[i];
if (sum * (j - i) < tmpSum * (ed - st) // sum/(ed-st) < tmpSum/(j-i)
|| sum * (j - i) == tmpSum * (ed - st) && (j - i) > (ed - st)) {
sum = tmpSum;
ed = j;
st = i;
}
}
}
System.out.println(st + " " + (ed - 1));
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int[][] changeCount = {
{0, 4, 3, 3, 4, 3, 2, 3, 1, 2},
{4, 0, 5, 3, 2, 5, 6, 1, 5, 4},
{3, 5, 0, 2, 5, 4, 3, 4, 2, 3},
{3, 3, 2, 0, 3, 2, 3, 2, 2, 1},
{4, 2, 5, 3, 0, 3, 4, 3, 3, 2},
{3, 5, 4, 2, 3, 0, 1, 4, 2, 1},
{2, 6, 3, 3, 4, 1, 0, 5, 1, 2},
{3, 1, 4, 2, 3, 4, 5, 0, 4, 3},
{1, 5, 2, 2, 3, 2, 1, 4, 0, 1},
{2, 4, 3, 1, 2, 1, 2, 3, 1, 0},
{6, 2, 5, 5, 4, 5, 6, 3, 7, 6},
};
Scanner sc = new Scanner(System.in);
String s = sc.next();
StringBuilder cache = new StringBuilder();
for (int d = 1; d <= s.length(); ++d) { // 宽度
cache.append(work(s, d, changeCount)).append(" ");
}
if (cache.length() > 0) {
cache.deleteCharAt(cache.length() - 1);
}
System.out.println(cache);
}
private static int work(String s, int d, int[][] changeCount) {
int count = 0;
for (int i = 0; i < d; ++i) {
count += changeCount[10][s.charAt(i) - '0'];
}
for (int i = 0; i < s.length() - d; ++i) { // 第i天 变化数
for (int j = i + 1; j <= i + d; ++j) {
count += changeCount[s.charAt(j-1) - '0'][s.charAt(j) - '0'];
}
}
return count;
}
}
/*
说明：
所有测试数据正确率为 45%！
可以尝试再次完善代码，并调试，争取全部AC通过
温馨提示：有时候，申请大的全局数组会导致超时，如果有此类情况，请检查您的全局数组是否超过题目要求的内存大小。
排除这个错误后，再检查别的情况引起的超时错误：例如死循环、循环结束条件错误等，或者需要更好的算法！
*/ 打表代码import java.util.Arrays;
public class Main {
public static void main(String[] args) {
init();
for (int i = 0; i < changeCount.length; ++i) {
System.out.println(Arrays.toString(changeCount[i]));
}
}
static int[][] ligths = new int[][]{
// 0 1 2 3 4 5 6
{1, 1, 1, 1, 1, 1, 0}, // 0
{0, 0, 0, 0, 1, 1, 0}, // 1
{1, 0, 1, 1, 0, 1, 1}, // 2
{1, 0, 0, 1, 1, 1, 1}, // 3
{0, 1, 0, 0, 1, 1, 1}, // 4
{1, 1, 0, 1, 1, 0, 1}, // 5
{1, 1, 1, 1, 1, 0, 1}, // 6
{1, 0, 0, 0, 1, 1, 0}, // 7
{1, 1, 1, 1, 1, 1, 1}, // 8
{1, 1, 0, 1, 1, 1, 1}, // 9
};
static final int[][] changeCount = new int[11][10];;
static void init() {
for (int i = 0; i <= 9; ++i) {
for (int j = i + 1; j <= 9; ++j) {
changeCount[i][j] = changeCount[j][i] = calc(i, j);
}
}
changeCount[10] = new int[]{6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
}
private static int calc(int num1, int num2) {
int count = 0;
for (int i = 0; i < 7; ++i) {
count += ligths[num1][i] ^ ligths[num2][i];
}
return count;
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int[][] changeCount = {
{0, 4, 3, 3, 4, 3, 2, 3, 1, 2},
{4, 0, 5, 3, 2, 5, 6, 1, 5, 4},
{3, 5, 0, 2, 5, 4, 3, 4, 2, 3},
{3, 3, 2, 0, 3, 2, 3, 2, 2, 1},
{4, 2, 5, 3, 0, 3, 4, 3, 3, 2},
{3, 5, 4, 2, 3, 0, 1, 4, 2, 1},
{2, 6, 3, 3, 4, 1, 0, 5, 1, 2},
{3, 1, 4, 2, 3, 4, 5, 0, 4, 3},
{1, 5, 2, 2, 3, 2, 1, 4, 0, 1},
{2, 4, 3, 1, 2, 1, 2, 3, 1, 0},
{6, 2, 5, 5, 4, 5, 6, 3, 7, 6},
};
Scanner sc = new Scanner(System.in);
String s = sc.next();
StringBuilder cache = new StringBuilder();
for (int d = 1; d <= s.length(); ++d) { // 宽度
cache.append(work(s, d, changeCount)).append(" ");
}
if (cache.length() > 0) {
cache.deleteCharAt(cache.length() - 1);
}
System.out.println(cache);
}
private static int work(String s, int d, int[][] changeCount) {
int totalCount = 0;
for (int i = 0; i < d; ++i) {
totalCount += changeCount[10][s.charAt(i) - '0'];
}
if (d == s.length()) {
return totalCount;
}
int count = 0;
for (int j = 1; j <= d; ++j) {
count += changeCount[s.charAt(j - 1) - '0'][s.charAt(j) - '0'];
}
totalCount += count;
for (int j = 2; j < s.length() - d; ++j) {
count += - changeCount[s.charAt(j-1) - '0'][s.charAt(j) - '0'] + changeCount[s.charAt(j+d-1) - '0'][s.charAt(j+d) - '0'];
totalCount += count;
}
return totalCount;
}
}
3 题 时间复杂度得O(nlogn)，哎
