Java求解最近点对问题（含面试大厂题和源码）

最近点对问题（Closest Pair of Points Problem）是计算一个点集内所有点对之间最短距离的问题。这个问题在计算机图形学、地理信息系统、以及许多科学和工程领域中都有应用。

算法思路

1. 暴力方法：对于两个点的集合，暴力方法会计算所有点对之间的距离，然后找出最近的一对。这种方法简单但效率不高，时间复杂度为O(n^2)。

2. 分治方法：分治算法将点集分成两半，分别在两半中找到最近的点对，然后在合并的过程中更新最近点对的距离。这种方法的时间复杂度为O(n log n)。

Java实现

以下是使用分治方法实现最近点对问题的Java代码示例：

import java.awt.*;
import java.util.*;
public class ClosestPair {
    static class Point implements Comparable<Point> {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int compareTo(Point p) {
            return this.x - p.x;
        }
    }

    static class ClosestInfo {
        double minDist;
        Point p1, p2;

        ClosestInfo() {
            minDist = Double.MAX_VALUE;
        }
    }

    static void minDistance(Point[] points, int l, int r, ClosestInfo info) {
        if (l >= r)
            return;

        int mid = (l + r) / 2;
        Point[] left = Arrays.copyOfRange(points, l, mid + 1);
        Point[] right = Arrays.copyOfRange(points, mid + 1, r + 1);

        mergeSort(left);
        mergeSort(right);

        info.minDist = Math.min(info.minDist, distance(points[mid], points[mid + 1]));

        minDistance(left, 0, left.length - 1, info);
        minDistance(right, 0, right.length - 1, info);

        double[] closest = closestInStrip(points, l, r, info.minDist);
        if (closest[0] < info.minDist) {
            info.minDist = closest[0];
            info.p1 = points[(int) closest[1]];
            info.p2 = points[(int) closest[2]];
        }
    }

    static void mergeSort(Point[] points) {
        Arrays.sort(points);
    }

    static double distance(Point p1, Point p2) {
        return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
    }

    static double[] closestInStrip(Point[] points, int l, int r, double minDist) {
        // 这里省略具体实现，它涉及到在一个“条带”区域内查找最近点对
        // 这个函数的实现需要一些几何学和排序的知识
        // ...

        return new double[] {minDist, -1, -1};
    }

    public static void main(String[] args) {
        Point[] points = {new Point(1, 2), new Point(3, 4), new Point(5, 6), new Point(7, 8)};
        Arrays.sort(points); // 按x坐标排序

        ClosestInfo info = new ClosestInfo();
        minDistance(points, 0, points.length - 1, info);

        System.out.println("最近点对之间的距离是 " + info.minDist);
        System.out.println("最近点对是 " + info.p1.x + ", " + info.p1.y + " 和 " + info.p2.x + ", " + info.p2.y);
    }
}

请注意，上面的代码中的closestInStrip函数没有给出具体实现，因为它需要一些额外的几何学知识，并且实现起来相对复杂。这个函数的目的是在一个特定的“条带”区域内查找最近点对，这个区域由分治算法生成，并且其宽度小于已知的最近点对的距离。

在实际应用中，你可能需要查找相关的资料或算法书籍来完成这个函数的实现，或者直接使用现成的库来处理最近点对问题。

1. 两数之和

题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。可以假设每个输入只对应一种答案，但是数组中同一个元素不能使用两次。

源码：

import java.util.HashMap;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("Index: " + result[0] + ", " + result[1]);
    }
}

2. 爬楼梯问题

题目：假设你正在爬楼梯。每次你可以爬1或2个台阶。你有多少种不同的方式爬到第n个台阶？

源码：

public class ClimbingStairs {
    public static int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 2; i < n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println("爬" + n + "个台阶的方式有: " + climbStairs(n));
    }
}

3. 合并两个有序数组

题目：给定两个有序整数数组 nums1 和 nums2，其中 nums1 的长度为 m，nums2 的长度为 n。假设 nums1 的前 m 个元素足够大，可以容纳 nums2 中的所有元素。将 nums2 合并到 nums1 中，使合并后的数组仍然有序。

源码：

public class MergeSortedArray {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }
        // 如果 nums2 有剩余，直接拷贝到 nums1 前面
        while (j >= 0) {
            nums1[k] = nums2[j];
            j--;
            k--;
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int m = 3;
        int[] nums2 = {2, 5, 6};
        int n = 3;
        
        merge(nums1, m, nums2, n);
        
        for (int num : nums1) {
            System.out.print(num + " ");
        }
    }
}

这些题目涵盖了基本的数据结构操作、动态规划和双指针技巧，是准备技术面试时很好的练习材料。在面试中，除了正确实现算法，清晰地表达你的思考过程和代码优化也同样重要。