8.18阿里笔试个人题解思路
以下均为个人解题思路，仅供参考！
第一题
两步：1）找到非对角点的那一个点，设为（x0, y0), 另外两个对角点为（x1, y1), (x2, y2)，求 (x, y);
2) 有关系，y = y1 + y2 - y0; x = x1 + x2 - x0;
代码如下：
import java.util.Scanner;
public class Solution1 {
public static void main(String[] args) {
/**
* 两步：
* 1）找到非对角点的那一个点，设为（x0, y0), 另外两个对角点为（x1, y1), (x2, y2)，求 (x, y);
* 2) 有关系，y = y1 + y2 - y0; x = x1 + x2 - x0;
*/
Scanner sc = new Scanner(System.in);
int[][] ins = new int[3][2];
for (int i = 0; i < 3; i++) {
ins[i][0] = sc.nextInt();
ins[i][1] = sc.nextInt();
}
// Handle
handle(ins);
}
private static void handle(int[][] ins) {
// 1 找出非对角线上的点
for(int i = 0; i < 3; i ++){
swap(ins, 0, i);
if(isValid(ins))
break;
}
// 2 利用公式计算
int x = ins[1][0] + ins[2][0] - ins[0][0];
int y = ins[1][1] + ins[2][1] - ins[0][1];
System.out.println(x + " " + y);
}
// 如果某个点与其他两个点的距离一样，那么说明该点是输入中的非对角点
private static boolean isValid(int[][] ins) {
int x1 = (int)(Math.pow((ins[0][0] - ins[1][0]), 2) + Math.pow((ins[0][1] - ins[1][1]), 2));
int x2 = (int)(Math.pow((ins[0][0] - ins[2][0]), 2) + Math.pow((ins[0][1] - ins[2][1]), 2));
return x1 == x2;
} private static void swap(int[][] ins, int a, int b){
int[] temp = ins[a];
ins[a] = ins[b];
ins[b] = temp;
}
} 第二题
1) 数据处理， 将人工通道和天然通道合并为代码中的 `channels`, 不可达的点专门用数组表示，问题就变得简单了
2）使用`used`数组表示，是否之前到达过该点，如果到达过，则返回；
3）这就是简单的回溯算法了；
public class Solution2 {
private static int rst = Integer.MAX_VALUE;
/* 示例
6 2 2 0
9 1 6 3 6
2 5 1
3 6 2
1 5 3
6 5 9
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// int examples = sc.nextInt();
// sc.nextLine();
for (int i = 0; i < 1; i++) {
int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt(), p = sc.nextInt();
sc.nextLine();
int[] costs = new int[n - 1];
for (int j = 0; j < n - 1; j++) {
costs[j] = sc.nextInt();
}
sc.nextLine();
int[][] channels = new int[m * 2 + k][3];
int[][] arts = new int[m][3];
int j = 0;
for (; j < m * 2 + k ;j += 2) {
channels[j][0] = sc.nextInt();
channels[j][1] = sc.nextInt();
channels[j][2] = sc.nextInt();
channels[j + 1][0] = channels[j][1];
channels[j + 1][1] = channels[j][0];
channels[j + 1][2] = channels[j][2];
sc.nextLine();
}
int[][] nature = new int[k][3];
for (; j < m * 2 + k; j++) {
nature[j][0] = sc.nextInt();
nature[j][1] = sc.nextInt();
nature[j][2] = sc.nextInt();
sc.nextLine();
}
int[] cannot = new int[n];
for (int x = 0; x < p; x++) {
cannot[sc.nextInt() - 1] = -1;
}
int[] used = new int[n]; // 是否已经达到过该点
for (int x = 0; x < channels.length; x++) {
System.out.println(Arrays.toString(channels[x]));
}
System.out.println("cannot = " + Arrays.toString(cannot));
handle(costs, channels, cannot, n, used, 1, 0);
System.out.println(rst == Integer.MAX_VALUE ? -1 : rst);
rst = Integer.MAX_VALUE;
}
}
private static void handle(int[] costs, int[][] channels, int[] cannot, int n, int[] used, int next, int total) {
if (used[next - 1] == 1 || cannot[next - 1] == -1)
return;
if (next == n) {
rst = Math.min(rst, total);
return;
}
used[next - 1] = 1;
handle(costs, channels, cannot, n, used, next + 1, total + costs[next - 1]);
used[next - 1] = 0;
for (int i = 0; i < channels.length; i++) {
if(channels[i][0] == next){
used[next - 1] = 1;
handle(costs, channels, cannot, n, used, channels[i][1], total + channels[i][2]);
used[next - 1] = 0;
}
}
}
}
全部评论
(2) 回帖