当前位置: 首页 > article >正文

算法刷题基础知识总结

文章目录

  • 处理输入输出
  • 常用数据结构
  • 数学知识
    • 数论基础
      • 质数和合数
      • 因数/约数
      • 互为质数
    • 阶乘
    • 排列与组合
  • 排序
    • 字典序
    • Comparator接口

处理输入输出

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−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 后面。

http://www.kler.cn/a/372585.html

相关文章:

  • MFC工控项目实例二十七添加产品参数
  • ffmpeg视频滤镜:添加边框-drawbox
  • 单例模式 — 设计模式
  • 数据结构---顺序表
  • 【Python各个击破】numpy
  • 8. 性能指标
  • 逆变器前级倍压方案【工作日志】
  • 未来生活中的AI电脑是怎样的
  • 2023 春季测试 题解
  • 论坛系统测试报告
  • Postgresql源码(137)执行器参数传递与使用
  • 大语言模型(LLM)快速理解
  • DOM---鼠标事件类型(移入移出)
  • 基于Unet卷积神经网络的脑肿瘤MRI分割
  • LinkedList和链表(下)
  • 豆包,攻克数字是个什么工具?《GKData-挖掘数据的无限可能》(数据爬虫采集工具)
  • Ceph 存储系统全解
  • TMUX1308PWR规格书 数据手册 具有注入电流控制功能的 5V 双向 8:1单通道和 4:1 双通道多路复用器芯片
  • Android平台RTSP|RTMP播放器高效率如何回调YUV或RGB数据?
  • asp.net core 跨域配置不起作用的原因
  • 【Java多线程】9 Java 的并发性能优化
  • 如何将钉钉付款单数据集成到MySQL数据库
  • Kafka 客户端工具使用分享【offsetexplorer】
  • Resnet搭建介绍及代码撰写详解(总结6)
  • Java Condition 目录
  • 如何在Linux系统中使用Zabbix进行监控