高级算法考试复习笔记

public class MinDiff {

    public static int findMinDiff(int[] arr) {
        int n = arr.length;
        int minDiff = Integer.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int diff = Math.abs(arr[i] - arr[j]);
                if (diff < minDiff) {
                    minDiff = diff;
                }
            }
        }
        
        return minDiff;
    }

    public static void main(String[] args) {
        int[] arr = {3, 8, 15, 17};
        System.out.println("The minimum difference is: " + findMinDiff(arr));
    }
}

import java.util.ArrayList;
import java.util.List;

public class ConvexHull {

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

    // 计算向量 (o -> a) 和 (o -> b) 的叉积
    public static int crossProduct(Point o, Point a, Point b) {
        return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
    }

    public static List<Point> convexHull(Point[] points) {
        int n = points.length;
        if (n < 3) return List.of(points);
        
        List<Point> hullPoints = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                boolean allLeft = true;
                boolean allRight = true;
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j) continue;
                    int cp = crossProduct(points[i], points[j], points[k]);
                    if (cp > 0) {
                        allRight = false;
                    } else if (cp < 0) {
                        allLeft = false;
                    }
                    if (!(allLeft || allRight)) break;
                }
                if (allLeft || allRight) {
                    if (!hullPoints.contains(points[i])) hullPoints.add(points[i]);
                    if (!hullPoints.contains(points[j])) hullPoints.add(points[j]);
                }
            }
        }
        
        return hullPoints;
    }

    public static void main(String[] args) {
        Point[] points = {
            new Point(0, 0),
            new Point(1, 1),
            new Point(2, 2),
            new Point(3, 0),
            new Point(0, 3),
            new Point(3, 3)
        };
        
        List<Point> hull = convexHull(points);
        System.out.println("Points in the convex hull:");
        for (Point p : hull) {
            System.out.println("(" + p.x + ", " + p.y + ")");
        }
    }
}

public class MergeSort {

    public static void mergeSort(int[] array) {
        if (array.length < 2) {
            return;
        }
        int mid = array.length / 2;
        int[] left = new int[mid];
        int[] right = new int[array.length - mid];

        System.arraycopy(array, 0, left, 0, mid);
        System.arraycopy(array, mid, right, 0, array.length - mid);

        mergeSort(left);
        mergeSort(right);
        merge(array, left, right);
    }

    private static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                array[k++] = left[i++];
            } else {
                array[k++] = right[j++];
            }
        }
        while (i < left.length) {
            array[k++] = left[i++];
        }
        while (j < right.length) {
            array[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(array);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

public class QuickSort {

    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pi = partition(array, low, high);
            quickSort(array, low, pi - 1);
            quickSort(array, pi + 1, high);
        }
    }

    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                swap(array, i, j);
            }
        }
        swap(array, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        int[] array = {10, 7, 8, 9, 1, 5};
        int n = array.length;
        quickSort(array, 0, n - 1);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

import java.util.Arrays;
import java.util.Comparator;

public class ClosestPair {

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

    public static double closestPair(Point[] points) {
        Point[] px = points.clone();
        Arrays.sort(px, Comparator.comparingInt(p -> p.x));
        Point[] py = points.clone();
        Arrays.sort(py, Comparator.comparingInt(p -> p.y));
        return closestPairRec(px, py);
    }

    private static double closestPairRec(Point[] px, Point[] py) {
        int n = px.length;
        if (n <= 3) {
            return bruteForce(px);
        }

        int mid = n / 2;
        Point midPoint = px[mid];

        Point[] pxLeft = Arrays.copyOfRange(px, 0, mid);
        Point[] pxRight = Arrays.copyOfRange(px, mid, n);

        Point[] pyLeft = Arrays.stream(py).filter(p -> p.x <= midPoint.x).toArray(Point[]::new);
        Point[] pyRight = Arrays.stream(py).filter(p -> p.x > midPoint.x).toArray(Point[]::new);

        double dLeft = closestPairRec(pxLeft, pyLeft);
        double dRight = closestPairRec(pxRight, pyRight);
        double d = Math.min(dLeft, dRight);

        Point[] strip = Arrays.stream(py).filter(p -> Math.abs(p.x - midPoint.x) < d).toArray(Point[]::new);
        return Math.min(d, stripClosest(strip, d));
    }

    private static double bruteForce(Point[] points) {
        double minDist = Double.MAX_VALUE;
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                double dist = distance(points[i], points[j]);
                if (dist < minDist) {
                    minDist = dist;
                }
            }
        }
        return minDist;
    }

    private static double stripClosest(Point[] strip, double d) {
        double minDist = d;
        for (int i = 0; i < strip.length; i++) {
            for (int j = i + 1; j < strip.length && (strip[j].y - strip[i].y) < minDist; j++) {
                double dist = distance(strip[i], strip[j]);
                if (dist < minDist) {
                    minDist = dist;
                }
            }
        }
        return minDist;
    }

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

    public static void main(String[] args) {
        Point[] points = { new Point(2, 3), new Point(12, 30), new Point(40, 50), new Point(5, 1), new Point(12, 10), new Point(3, 4) };
        System.out.println("The smallest distance is " + closestPair(points));
    }
}

#include<bits/stdc++.h>
using namespace std;
#define Double long double 
const int MAXN = 1e6 + 10;
struct Point{
    Double x,y;
    Double rad;
    Point(Double x=0,Double y=0):x(x),y(y){}
    void read(){
        scanf("%Lf %Lf",&x,&y);
        //rad = atan2(y,x);
    }
};

typedef vector<Point> Polygon;
typedef Point Vector;

inline Vector operator - (Vector A,Vector B){
    return Vector(A.x - B.x , A.y - B.y);
}

inline Double Dot(Vector A,Vector B){
    return A.x * B.x + A.y * B.y;
}

inline Double Length(Vector A){
    return sqrt(Dot(A , A));
}

inline Double Cross(Vector A,Vector B){
    return A.x * B.y - A.y * B.x;
}

int N;
Point points[MAXN];
Polygon convex;

bool cmpByX(Point A,Point B){
    if(A.x != B.x) return A.x < B.x;
    else return A.y < B.y;
}

void findConvex(Point A,Point B,vector<Point> p){
    if(!p.size()) return;
    Point C = p[0];
    vector<Point> l;
    vector<Point> r;
    for(auto P:p){
        if(Cross(B-A,P-A) > Cross(B-A,C-A)) C = P;
    }
    for(auto P:p){
        if(Cross(C-A,P-A) > 0) l.push_back(P);
        if(Cross(B-C,P-C) > 0) r.push_back(P);
    }
    findConvex(A,C,l);
    convex.push_back(C);
    findConvex(C,B,r);
}

Double getPolygonPerimeter(Polygon polygon){
    Double ret = 0;
    for(int i = 0;i < polygon.size(); i++){
        ret += Length(polygon[(i + 1) % polygon.size()] - polygon[i]);
    }
    return ret;
}

void solve(){
    scanf("%d",&N);
    for(int i = 1; i <= N; i++) points[i].read();
    sort(points + 1,points + 1 + N,cmpByX);
    vector<Point> l;
    vector<Point> r;
    Point A = points[1];
    Point B = points[N];
    for(int i = 2;i <= N - 1; i++){
        if(Cross(B - A,points[i] - A) > 0) l.push_back(points[i]);
        if(Cross(B - A,points[i] - A) < 0) r.push_back(points[i]);
    }
    convex.push_back(A);
    findConvex(A,B,l);
    convex.push_back(B);
    findConvex(B,A,r);
    printf("%.2Lf\n",getPolygonPerimeter(convex));
}

int main(){
    solve();
}

import java.util.Arrays;
import java.util.Stack;

public class ConvexHull {

    static class Point implements Comparable<Point> {
        int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Point p) {
            return this.x != p.x ? this.x - p.x : this.y - p.y;
        }
    }

    public static Point[] convexHull(Point[] points) {
        Arrays.sort(points);
        Stack<Point> lower = new Stack<>();
        for (Point p : points) {
            while (lower.size() >= 2 && cross(lower.get(lower.size() - 2), lower.get(lower.size() - 1), p) <= 0) {
                lower.pop();
            }
            lower.push(p);
        }

        Stack<Point> upper = new Stack<>();
        for (int i = points.length - 1; i >= 0; i--) {
            Point p = points[i];
            while (upper.size() >= 2 && cross(upper.get(upper.size() - 2), upper.get(upper.size() - 1), p) <= 0) {
                upper.pop();
            }
            upper.push(p);
        }

        lower.pop();
        upper.pop();
        Point[] hull = new Point[lower.size() + upper.size()];
        int k = 0;
        for (Point p : lower) hull[k++] = p;
        for (Point p : upper) hull[k++] = p;
        return hull;
    }

    private static int cross(Point o, Point a, Point b) {
        return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
    }

    public static void main(String[] args) {
        Point[] points = { new Point(0, 3), new Point(2, 3), new Point(1, 1), new Point(2, 1), new Point(3, 0), new Point(0, 0), new Point(3, 3) };
        Point[] hull = convexHull(points);
        System.out.println("The points in the convex hull are:");
        for (Point p : hull) {
            System.out.println("(" + p.x + ", " + p.y + ")");
        }
    }
}

public class KMP {

    public static int[] computeLPSArray(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int length = 0;
        int i = 1;
        lps[0] = 0;

        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static void KMPSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] lps = computeLPSArray(pattern);

        int i = 0;
        int j = 0;
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }

            if (j == m) {
                System.out.println("Found pattern at index " + (i - j));
                j = lps[j - 1];
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        KMPSearch(text, pattern);
    }
}

public class Fibonacci {

    // 使用数组存储子问题的解
    public static int fibDP(int n) {
        if (n <= 1) {
            return n;
        }
        int[] f = new int[n + 1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }

    // 使用两个变量优化空间复杂度
    public static int fibOptimized(int n) {
        if (n <= 1) {
            return n;
        }
        int a = 0, b = 1, c;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci number using DP: " + fibDP(n));
        System.out.println("Fibonacci number using optimized DP: " + fibOptimized(n));
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ActivitySelection {

    static class Activity {
        int start;
        int end;

        Activity(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static List<Activity> selectActivities(Activity[] activities) {
        Arrays.sort(activities, (a1, a2) -> a1.end - a2.end);
        List<Activity> result = new ArrayList<>();

        int lastEndTime = -1;
        for (Activity activity : activities) {
            if (activity.start >= lastEndTime) {
                result.add(activity);
                lastEndTime = activity.end;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 4),
            new Activity(3, 5),
            new Activity(0, 6),
            new Activity(5, 7),
            new Activity(3, 9),
            new Activity(5, 9),
            new Activity(6, 10),
            new Activity(8, 11),
            new Activity(8, 12),
            new Activity(2, 14),
            new Activity(12, 16)
        };

        List<Activity> selectedActivities = selectActivities(activities);
        System.out.println("Selected activities:");
        for (Activity activity : selectedActivities) {
            System.out.println("Activity: (" + activity.start + ", " + activity.end + ")");
        }
    }
}

import java.util.*;

public class KruskalMST {

    static class Edge implements Comparable<Edge> {
        int src, dest, weight;

        public int compareTo(Edge compareEdge) {
            return this.weight - compareEdge.weight;
        }
    }

    static class Subset {
        int parent, rank;
    }

    int V, E;
    Edge[] edges;

    KruskalMST(int v, int e) {
        V = v;
        E = e;
        edges = new Edge[E];
        for (int i = 0; i < e; ++i) {
            edges[i] = new Edge();
        }
    }

    int find(Subset[] subsets, int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
        return subsets[i].parent;
    }

    void union(Subset[] subsets, int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);

        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }

    void KruskalMST() {
        Edge[] result = new Edge[V];
        int e = 0;
        int i = 0;
        for (i = 0; i < V; ++i)
            result[i] = new Edge();

        Arrays.sort(edges);

        Subset[] subsets = new Subset[V];
        for (i = 0; i < V; ++i)
            subsets[i] = new Subset();

        for (int v = 0; v < V; ++v) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }

        i = 0;

        while (e < V - 1) {
            Edge next_edge = edges[i++];
            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);

            if (x != y) {
                result[e++] = next_edge;
                union(subsets, x, y);
            }
        }

        System.out.println("Following are the edges in the constructed MST");
        for (i = 0; i < e; ++i)
            System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
    }

    public static void main(String[] args) {
        int V = 4;
        int E = 5;
        KruskalMST graph = new KruskalMST(V, E);

        graph.edges[0].src = 0;
        graph.edges[0].dest = 1;
        graph.edges[0].weight = 10;

        graph.edges[1].src = 0;
        graph.edges[1].dest = 2;
        graph.edges[1].weight = 6;

        graph.edges[2].src = 0;
        graph.edges[2].dest = 3;
        graph.edges[2].weight = 5;

        graph.edges[3].src = 1;
        graph.edges[3].dest = 3;
        graph.edges[3].weight = 15;

        graph.edges[4].src = 2;
        graph.edges[4].dest = 3;
        graph.edges[4].weight = 4;

        graph.KruskalMST();
    }
}