首页 > 8.18阿里笔试题解思路参考
头像
CoderHell
发布于 2021-08-18 10:45
+ 关注

8.18阿里笔试题解思路参考

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) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐