头像

官渡酒徒




离线:1天前


最近来访(5)
用户头像
我是sun
用户头像
算法小爱
用户头像
心向远方
用户头像
我要出去乱说
用户头像
zombotany

活动打卡代码 AcWing 790. 数的三次方根

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(in);
        double n = Double.parseDouble(br.readLine());
        double l = -10000;
        double r = 10000;
        while(r - l > 1e-8) { // 精度值高2位
            double mid = (l + r) / 2;
            if(mid * mid * mid >= n) {
                r = mid;  // 不需要加1,减1
            } else {
                l = mid;
            }
        }
        System.out.println(String.format("%.6f", l));
    }
}


活动打卡代码 AcWing 789. 数的范围

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        while(q-- > 0) {
            int k = sc.nextInt();
            int l = 0, r = n - 1;
            while(l < r) {
                int mid = l + r >> 1;
                if(a[mid] >= k) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            int left = l;
            if(a[left] != k) {
                System.out.println("-1 -1");
                continue;
            }
            l = 0;
            r = n - 1;
            while(l < r) {
                int mid = l + r + 1 >> 1;
                if(a[mid] <= k) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            System.out.println(left + " " + l);
        }
    }
}


活动打卡代码 AcWing 788. 逆序对的数量

import java.io.*;
import java.util.*;

public class Main {
    static int[] tmp = new int[100010];

    static long mergeSort(int[] a, int l, int r) {
        if(l >= r)
            return 0;
        int mid = l + r >> 1;
        long left = mergeSort(a, l, mid);
        long right = mergeSort(a, mid + 1, r);
        int i = l, j = mid + 1;
        int k = 0;
        long res = 0;
        while(i <= mid && j <= r) {
            if(a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                tmp[k++] = a[j++];
                res += (mid - i + 1);
            }
        }
        while(i <= mid) {
            tmp[k++] = a[i++];
        }
        while(j <= r) {
            tmp[k++] = a[j++];
        }
        for(i = l, j = 0; i <= r; i++, j++) {
            a[i] = tmp[j];
        }
        return res + left + right;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        System.out.println(mergeSort(a, 0, n - 1));
    }
}


活动打卡代码 AcWing 787. 归并排序

import java.io.*;
import java.util.*;

public class Main {
    static int[] t = new int[100010];

    static void mergeSort(int[] a, int l, int r) {
        if(l >= r) return;
        int mid = l + r >> 1;
        mergeSort(a, l, mid);
        mergeSort(a, mid + 1, r);
        int i = l, j = mid + 1;
        int k = 0;
        while(i <= mid && j <= r) {
            if(a[i] <= a[j]) {
                t[k++] = a[i++];
            } else {
                t[k++] = a[j++];
            }
        }
        while(i <= mid)
            t[k++] = a[i++];
        while(j <= r)
            t[k++] = a[j++];
        for(i = l, j = 0; i <= r; i++, j++) {
            a[i] = t[j];
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        mergeSort(a, 0, n - 1);
        for(int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }
    }
}


活动打卡代码 AcWing 786. 第k个数

import java.io.*;
import java.util.*;

public class Main {
    static int quickSelect(int[] arr, int l, int r, int k) {
        if(l >= r) {
            return arr[l];
        }
        int x = arr[l];
        int i = l, j = r;
        while(i < j) {
            while(i < j && arr[j] >= x) j--;
            arr[i] = arr[j];
            while(i < j && arr[i] <= x) i++;
            arr[j] = arr[i];
        }
        arr[i] = x;
        if(i == k) {
            return x;
        } else if(k < i) {
            return quickSelect(arr, l, i - 1, k);
        } else {
            return quickSelect(arr, i + 1, r, k);
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(quickSelect(arr, 0, n - 1, k - 1));
    }
}


活动打卡代码 AcWing 785. 快速排序

import java.io.*;
import java.util.*;

public class Main {
    static void quickSort(int[] a, int l, int r) {
        if(l >= r) {
            return;
        }
        int i = l - 1;
        int j = r + 1;
        int t = a[l];
        while(i < j) {
            i++;
            j--;
            while(a[i] < t) i++;
            while(a[j] > t) j--;
            if(i < j) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
        quickSort(a, l, j);
        quickSort(a, j + 1, r);
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        quickSort(arr, 0, n - 1);
        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}



要么是最长的,否则一定是次长的

(KMP) $O(n)$

参考自y总: https://www.acwing.com/video/3420/
和Y总不同的点在于最后求解答案的那一步。 Y总是循环判断next[j] = k是否曾经在内部的某个i出现过。
我的结论是, 如果最长的公共前后缀不是答案,那么答案一定是次长的。
因为次长的是最长的后缀,而最长的前后缀在s头部出现过,它的后缀相当于在s的 内部

时间复杂度

参考文献

JAVA 代码

import java.io.*;
import java.util.*;

public class Main {
    static boolean kmp(String s, String p) {
        int n = s.length(), m = p.length();
        int[] ne = new int[m];
        for(int i = 1, j = 0; i < m; i++) {
            while(j > 0 && p.charAt(i) != p.charAt(j)) j = ne[j - 1];
            if(p.charAt(i) == p.charAt(j)) j++;
            ne[i] = j;
        }
        for(int i = 0, j = 0; i < n; i++) {
            while(j > 0 && s.charAt(i) != p.charAt(j)) j = ne[j - 1];
            if(s.charAt(i) == p.charAt(j)) j++;
            if(j == m)
                return true;
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0) {
            String tmp = sc.next();
            String s = " " + tmp;
            int n = tmp.length();
            int[] ne = new int[n + 1];
            for(int i = 2, j = 0; i <= n; i++) {
                while(j > 0 && s.charAt(i) != s.charAt(j + 1)) j = ne[j];
                if(s.charAt(i) == s.charAt(j + 1)) j++;
                ne[i] = j;
            }

            StringBuilder t = new StringBuilder(tmp);
            if(t.length() <= 2) {
                System.out.println("not exist");
                continue;
            }
            t.deleteCharAt(0);
            t.deleteCharAt(t.length() - 1);
            int first = ne[n];
            if(first == 0) {
                System.out.println("not exist");
                continue;
            }
            boolean flag = kmp(t.toString(), s.substring(1, first + 1));
            if(flag) {
                System.out.println(s.substring(1, first + 1));
            } else {
                int second = ne[first];
                if(second == 0) {
                    System.out.println("not exist");
                } else {
                    System.out.println(s.substring(1, second + 1));
                }
            }
        }
    }
}


活动打卡代码 AcWing 125. 耍杂技的牛

官渡酒徒
1个月前
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for(int i = 0; i < n; i++) {
            int w = sc.nextInt();
            int s = sc.nextInt();
            arr[i] = new int[]{w, s};
        }
        Arrays.sort(arr, (a, b) -> {
            return a[0] + a[1] - b[0] - b[1];
        });
        long res = Long.MIN_VALUE;
        long sum = 0;
        for(int i = 0; i < n; i++) {
            res = Math.max(res, sum - arr[i][1]);
            sum += arr[i][0];
        }
        System.out.println(res);
    }
}


活动打卡代码 AcWing 104. 货仓选址

官渡酒徒
1个月前
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        long res = 0;
        for(int i = 0; i < n; i++) {
            res += Math.abs(arr[n / 2] - arr[i]);
        }
        System.out.println(res);
    }
}


活动打卡代码 AcWing 913. 排队打水

官渡酒徒
1个月前
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        long res = 0;
        for(int i = 0; i < n; i++) {
            res += (long)arr[i] * (n - 1 - i);
        }
        System.out.println(res);
    }
}