搜狗2016校園招聘之程式設計題解析-大資料開發

解題思路：

1. 使用JDK中的Point2D類，該類定義了坐标系空間中的一個點
2. Point2D是一個抽象類，但是在該類内部定義了靜态的Double類，并且Double繼承自Point2D
3. 可以通過Double的構造方法來執行個體化空間中的某個點
4. 将所有的輸入資料全部執行個體化并存放在一個Point2D.Double的數組中
5. 對該數組進行暴力破解，計算其中任意兩個點之間的距離，時間複雜度為 O(n2) ，并保留下最小的兩個點的編号，且編号小的在前

Java算法實作：

import java.awt.geom.Point2D;
import java.util.Scanner;
/**
 * Description:
 * 測試資料
 * 3
 * 1.0 1.0002
 * 3.03 3.023
 * 0.0 -0.001
 * Closest points: 0, 2
 * Process finished with exit code 0
 * 
 *
 */
public class Main {

    static int[] getClosest(Point2D.Double[] points) {
        int[] result = new int[2];
        double distance = Double.MAX_VALUE;
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                if (i != j) {
                    double distance1 = points[i].distance(points[j]);
                    if (distance1 < distance) {
                        distance = distance1;
                        if (i < j) {
                            result[0] = i;
                            result[1] = j;
                        } else {
                            result[0] = j;
                            result[i] = i;
                        }
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Point2D.Double[] points;
        Scanner input = new Scanner(System.in);
        {
            int n = input.nextInt();
            input.nextLine();
            points = new Point2D.Double[n];
            for (int i = 0; i < n; ++i) {
                double x = input.nextDouble();
                double y = input.nextDouble();
                input.nextLine();
                points[i] = new Point2D.Double(x, y);
            }
        }
        int[] result = getClosest(points);
        System.out.printf("Closest points: %d, %d\n", result[0], result[1]);
    }
}
           

解題思路：

1. 利用僞随機特性，隻要時間種子一樣且上限一樣，其實随機數每次都會産生相同的數
2. 既然要求還原，那麼我們從後往前執行對應的操作即可
3. 使用一個額外的棧來存儲所産生的随機數
4. 在亂序操作中，是将随機數對應的元素與最後一個元素進行交換，那麼還原的時候，就要從第一個元素開始與最後産生的那個随機數對應的元素進行交換，依次類推，直到棧空即可

Java算法實作：

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;

/**
 * ClassName:Main
 * Description:輸入資料
 * 12312 3 1 2 3
 * Success!
 */


public class Main {
    static Stack<Integer> s = new Stack<Integer>();

    static void shuffle(int a[], int seed) {
        int n = a.length;
        Random random = new Random(seed);
        for (; n > 1; n--) {
            int r = random.nextInt(n);
            int tmp = a[n - 1];
            a[n - 1] = a[r];
            a[r] = tmp;
        }
    }

    static void restore(int a[], int seed) {
        int n = a.length;
        Random random = new Random(seed);
        int temp = n;
        for (; temp > 1; temp--) {
            int r = random.nextInt(temp);
            s.add(r);
        }
        for (int i = 0; i < n; i++) {
            if (!s.isEmpty()) {
                int r = s.pop();
                int tmp = a[i + 1];
                a[i + 1] = a[r];
                a[r] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        int seed, n, i;
        int[] a, b;
        Scanner input = new Scanner(System.in);
        {
            seed = input.nextInt();
            n = input.nextInt();
            a = new int[n];
            for (i = 0; i < n; ++i)
                a[i] = input.nextInt();
        }
        b = Arrays.copyOf(a, a.length);
        shuffle(a, seed);
        restore(a, seed);
        for (i = 0; i < n; i++) {
            if (a[i] != b[i])
                break;
        }
        if (i == n)
            System.out.printf("Success!\n");
        else
            System.out.printf("Failed!\n");
    }
}
           

僅供參考！！！