算法刷题基础知识总结

处理输入输出

Scanner 类可以读取多种类型的数据，包括：

1. nextInt()：读取整数。
2. nextDouble()：读取双精度浮点数。
3. nextLine()：读取整行字符串（包括空格）。
4. next()：读取下一个完整的单词。

常用数据结构

数学知识

数论基础

质数和合数

只有两个正因数（1和它本身）的自然数称为质数。比1大但不是质数的数称为合数。1和0既非质数也非合数。

public static boolean isPrimeNumber(int a){
    // 0 和 1 既不是质数和不是合数
    if (a < 2 ){
        return false;
    }
    for (int i = 2; i < a; i++) {
        if (a % i == 0) {
            return false;
        }
    }
    return true;
}

第二种方式，由于a = b * c，那么b，c一定小于a的平方根；可以说明，a的其他因数的平方一定小于a.

public static boolean isPrimeNumber(int a){
    //0和1既不是质数和不是合数
    if (a < 2 ){
        return false;
    }
    boolean b = true;
    for (int i = 2; i*i < a; i++) {
        if (a % i == 0){
            return false;
        }
    }
    return true;
}

因数/约数

因数是指能够整除一个整数的数。换句话说，如果一个整数 𝑎 被另一个整数 𝑏 除，且结果是一个整数（没有余数），那么 𝑏 就是 𝑎 的因数。

互为质数

互质（又称为 质数 或 互为质数）是指两个或多个整数之间的一种关系：如果它们的最大公约数（GCD）是 1，则称这些整数互质。

判断2个数互为质数: 辗转相除法

可以通过求最大公约数是否为1判断两数互为质数

public static boolean isPrimeNumber(int a ,int b){
    // 辗转相除法
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a == 1 ? true: false;
}

判断N个数互为质数

根据互为质数可以得到，质数的最大公约数是一，那么用哈希表保存各个因数的累计值，除了1以外的因数，其他存在大于1的数，则不互为质数。

public static boolean isPrimeNumberAll(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (num < 2) {
            return false;
        }
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0 && set.contains(i)) {
                return false;
            } else {
                set.add(i);
            }
        }
    }
    return true;
}

根据互质数的定义，可总结出一些规律，利用这些规律能迅速判断一组数是否互质。
（1）两个不相同的质数一定是互质数。如：7和11、17和31是互质数。
（2）两个连续的自然数一定是互质数。如：4和5、13和14是互质数。
（3）相邻的两个奇数一定是互质数。如：5和7、75和77是互质数。
（4）1和其他所有的自然数一定是互质数。如：1和4、1和13是互质数。
（5）两个数中的较大一个是质数，这两个数一定是互质数。如：3和19、16和97是互质数。
（6）两个数中的较小一个是质数，而较大数是合数且不是较小数的倍数，这两个数一定是互质数。如：2和15、7和54是互质数。
（7）较大数比较小数的2倍多1或少1，这两个数一定是互质数。如：13和27、13和25是互质数。

阶乘

阶乘是一个数学概念，通常用符号 𝑛! 表示，代表一个正整数 𝑛 的阶乘。阶乘的定义是将所有正整数从 1 乘到 𝑛 的结果。阶乘只适用于非负整数。

n!=n×(n−1)×(n−2)×…×3×2×1

特殊情况：0!=1（这是一个约定，方便数学运算）

排列与组合

排列是指从 𝑛 个不同元素中选取 𝑟 个元素的不同排列方式。排列考虑了元素的顺序。

n! 表示 𝑛 的阶乘，定义为 𝑛×(𝑛−1) x (𝑛−2) x… x 2x1。𝑟 是选取的元素个数。

组合是指从 𝑛 个不同元素中选取 𝑟 个元素的不同组合方式。组合不考虑元素的顺序。

求排列和组合

如果只需要求数量，可以直接通过代码计算公式即可：

public class PermutationCombination {
    // 计算阶乘
    public static long factorial(int n) {
        if (n == 0) return 1;
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    // 计算排列
    public static long permutation(int n, int r) {
        return factorial(n) / factorial(n - r);
    }

    // 计算组合
    public static long combination(int n, int r) {
        return factorial(n) / (factorial(r) * factorial(n - r));
    }

    public static void main(String[] args) {
        int n = 5; // 总元素个数
        int r = 3; // 选取元素个数

        long permResult = permutation(n, r);
        long combResult = combination(n, r);

        System.out.println("P(" + n + ", " + r + ") = " + permResult);
        System.out.println("C(" + n + ", " + r + ") = " + combResult);
    }
}

如果要求所有的排列或者组合，参考以下程序：

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

public class PermutationAndCombination {

    public static void main(String[] args) {
        // 生成所有排列
        int[] nums = {1, 2, 3}; // 输入数组
        System.out.println("All permutations:");
        List<List<Integer>> permutations = generatePermutations(nums);
        for (List<Integer> perm : permutations) {
            System.out.println(perm);
        }

        // 生成所有组合
        int n = 5; // 总元素个数
        int r = 3; // 选取元素个数
        System.out.println("\nAll combinations:");
        List<List<Integer>> combinations = generateCombinations(n, r);
        for (List<Integer> comb : combinations) {
            System.out.println(comb);
        }
    }

    // 生成所有排列
    public static List<List<Integer>> generatePermutations(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrackPermutations(result, new ArrayList<>(), nums);
        return result;
    }

    private static void backtrackPermutations(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
        if (tempList.size() == nums.length) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (tempList.contains(nums[i])) continue; // 元素已存在，跳过
                tempList.add(nums[i]);
                backtrackPermutations(result, tempList, nums);
                tempList.remove(tempList.size() - 1); // 回溯
            }
        }
    }

    // 生成所有组合
    public static List<List<Integer>> generateCombinations(int n, int r) {
        List<List<Integer>> result = new ArrayList<>();
        backtrackCombinations(result, new ArrayList<>(), 1, n, r);
        return result;
    }

    private static void backtrackCombinations(List<List<Integer>> result, List<Integer> tempList, int start, int n, int r) {
        if (tempList.size() == r) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = start; i <= n; i++) {
                tempList.add(i);
                backtrackCombinations(result, tempList, i + 1, n, r);
                tempList.remove(tempList.size() - 1); // 回溯
            }
        }
    }
}

排序

字典序

字典序（又称字典排列、字典顺序）是一种将字符串（或其他序列）按字母（或元素）顺序排列的方式，类似于在字典中查找单词的顺序。字典序是基于字符的 Unicode 值进行比较的。

在字典序中，字符串的比较通常遵循以下原则：

1. 逐字符比较：从字符串的第一个字符开始，逐个字符进行比较。
2. 字符顺序：如果两个字符串的第一个字符不同，则较小的字符对应的字符串在前。如果第一个字符相同，则比较第二个字符，以此类推。
3. 长度比较：如果一个字符串是另一个字符串的前缀，则较短的字符串排在前面。例如，“apple” 在字典序中排在 “applepie” 之前。

许多编程语言提供了内置的字符串比较功能，通常可以直接使用这些功能来实现字典序的排序。例如，在 Java 中，可以使用 Arrays.sort() 方法对字符串数组进行字典序排序。

String[] words = {"apple", "banana", "apricot", "grape"};
// 按字典序排序
Arrays.sort(words);

两个字符串之间比较：

String a = "apple";
String b = "banana";
// 直接通过compareTo进行比较就是字典序
a.compareTo(b)

Comparator接口

int compare(T o1, T o2)：比较两个对象，返回负整数、零或正整数，以指示第一个对象是否小于、等于或大于第二个对象。

compare(T o1, T o2) 方法的返回值决定了排序的顺序，默认是按升序排列的：

1. 返回负整数：表示 o1 小于 o2，在排序中 o1 会排在 o2 前面。
2. 返回零：表示 o1 等于 o2，它们的位置不变。
3. 返回正整数：表示 o1 大于 o2，在排序中 o1 会排在 o2 后面。