使用 Java 泛型在竞争性编程中高效编码

2025 年 1 月 6 日 | 阅读 9 分钟

Java 泛型是一种可以在竞争性编程中有效使用的概念，用于编写最优和可重用的代码。泛型使您能够声明类或接口，以及带有类型参数的方法，这些参数可以在实例化或调用期间被具体类型替换。

竞争性编程中常用的函数

1. Java 中的 Pair（对）

Pair（对）是一种常用的数据类型，在编程时使用，它只包含两个连接在一起的值。在 Java 中，尽管作为一个面向对象的语言，其标准库中没有内置的 Pair 类，但在竞争性编程中创建和使用 Pair 非常简单且非常方便。

文件名: Pairs.java

import java.util.*;
// Generic Pair class
class Pair<K, V> {
    private K key;
    private V value;
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    public K getKey() {
        return key;
    }
    public void setKey(K key) {
        this.key = key;
    }
    public V getValue() {
        return value;
    }
    public void setValue(V value) {
        this.value = value;
    }
    @Override
    public String toString() {
        return "(" + key + ", " + value + ")";
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair<?, ?> pair = (Pair<?, ?>) o;
        if (!key.equals(pair.key)) return false;
        return value.equals(pair.value);
    }
    @Override
    public int hashCode() {
        int result = key.hashCode();
        result = 31 * result + value.hashCode();
        return result;
    }
}
public class Pairs {
    public static void main(String[] args) {
        // List to store pairs of String and Integer
        List<Pair<String, Integer>> list = new ArrayList<>();
        list.add(new Pair<>("Apple", 3));
        list.add(new Pair<>("Banana", 2));
        list.add(new Pair<>("Cherry", 1));
        // Sort the list by the integer value in the pairs
        Collections.sort(list, Comparator.comparing(Pair::getValue));
        // Print the sorted list
        for (Pair<String, Integer> pair : list) {
            System.out.println(pair);
        }
    }
}

输出

(Cherry, 1)
(Banana, 2)
(Apple, 3)

2. 模运算下的快速幂

直接计算大幂可能导致溢出且计算成本高昂。快速幂（也称为平方求幂）是一种以 O(logn) 时间复杂度快速计算幂的方法。当与模运算结合时，它在涉及大数的题目中尤其有用。

文件名: FastExponentiation.java

public class FastExponentiation {
    // Function to perform fast exponentiation with modulo
    public static long powerMod(long base, long exp, long mod) {
        if (mod == 1) return 0; // Since anything mod 1 is 0
        long result = 1;
        base = base % mod; // Handle the initial base case
        while (exp > 0) {
            // If exp is odd, multiply the base with result
            if ((exp % 2) == 1) {
                result = (result * base) % mod;
            }
            // Now exp must be even, so we halve it
            exp = exp >> 1; // Equivalent to exp /= 2
            base = (base * base) % mod; // Square the base
        }
        return result;
    }
    public static void main(String[] args) {
        long base1 = 2;
        long exp1 = 10;
        long mod1 = 1000000007; // A large prime commonly used in competitive programming
        long base2 = 5;
        long exp2 = 20;
        long mod2 = 1000000007;
        long base3 = 7;
        long exp3 = 13;
        long mod3 = 1000000007;
        System.out.println("Result 1: " + powerMod(base1, exp1, mod1)); // Expected: 1024
        System.out.println("Result 2: " + powerMod(base2, exp2, mod2)); // Expected: 953674316
        System.out.println("Result 3: " + powerMod(base3, exp3, mod3)); // Expected: 968890104
    }
}

输出

Result 1: 1024
Result 2: 430973056
Result 3: 889009735

3. 使用费马小定理计算 nCr

在竞争性编程中，高效计算组合数（nCr）至关重要，尤其是在处理大数和模运算时。费马小定理为高效处理此问题提供了一种优雅的方法。

文件名: CombinationsUsingFermat.java

public class CombinationsUsingFermat {
    static final int MOD = 1000000007;
    // Function to compute x^y under modulo MOD
    static long power(long x, long y, long p) {
        long result = 1;
        x = x % p;
        while (y > 0) {
            if ((y & 1) == 1)
                result = (result * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return result;
    }
    // Function to compute nCr % p using Fermat's Little Theorem
    static long nCrModP(int n, int r, int p) {
        if (r == 0 || r == n)
            return 1;
        long[] fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++)
            fact[i] = fact[i - 1] * i % p;
        long numerator = fact[n];
        long denominator = (fact[r] * fact[n - r]) % p;
        return (numerator * power(denominator, p - 2, p) % p) % p;
    }
    public static void main(String[] args) {
        int n = 10;
        int r = 2;
        System.out.println("Result 1: " + nCrModP(n, r, MOD));
        n = 20;
        r = 4;
        System.out.println("Result 2: " + nCrModP(n, r, MOD));
    }
}

输出

Result 1: 45
Result 2: 4845

4. 二项式系数（迭代）

二项式系数表示从 n 个元素的集合中选择 k 个元素的组合数，而不考虑选择的顺序。它是组合学中的基本概念，在概率、统计和数学的各个领域都有应用。

文件名: BinomialCoefficient.java

public class BinomialCoefficient {
    // Function to compute nCr using an iterative approach
    public static long binomialCoefficient(int n, int k) {
        if (k > n - k) {
            k = n - k; // Since C(n, k) = C(n, n-k)
        }
        long result = 1;
        for (int i = 0; i < k; i++) {
            result *= (n - i);
            result /= (i + 1);
        }
        return result;
    }
    public static void main(String[] args) {
        // Test cases
        int n1 = 5, k1 = 2;
        System.out.println("Binomial Coefficient C(" + n1 + ", " + k1 + ") = " + binomialCoefficient(n1, k1));
        int n2 = 10, k2 = 3;
        System.out.println("Binomial Coefficient C(" + n2 + ", " + k2 + ") = " + binomialCoefficient(n2, k2));
        int n3 = 50, k3 = 25;
        System.out.println("Binomial Coefficient C(" + n3 + ", " + k3 + ") = " + binomialCoefficient(n3, k3));
    }
}

输出

Binomial Coefficient C(5, 2) = 10
Binomial Coefficient C(10, 3) = 120
Binomial Coefficient C(50, 25) = 126410606437752

5. 模运算

模运算是一种整数算术系统，其中数字在达到称为模数的特定值时会“回绕”。给定一个正整数 n，称为模数，如果两个整数 a 和 b 的差 a-b 是 n 的整数倍，则称它们模 n 同余。关系式写为：a≡b(modn)。这意味着当 a 除以 n 时，它得到的余数与 b 除以 n 时得到的余数相同。

文件名: ModularArithmetic.java

public class ModularArithmetic {
    // Function for modular addition
    public static int modAdd(int a, int b, int mod) {
        return (a % mod + b % mod) % mod;
    }
    // Function for modular subtraction
    public static int modSubtract(int a, int b, int mod) {
        return (a % mod - b % mod + mod) % mod;
    }
    // Function for modular multiplication
    public static int modMultiply(int a, int b, int mod) {
        return (int)((long)a * b % mod);
    }
    // Function for modular exponentiation using exponentiation by squaring
    public static long modExponentiation(long base, long exp, long mod) {
        long result = 1;
        base = base % mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % mod;
            }
            exp = exp >> 1;
            base = (base * base) % mod;
        }
        return result;
    }
    // Function for modular inverse using Fermat's Little Theorem
    public static long modInverse(long a, long mod) {
        return modExponentiation(a, mod - 2, mod);
    }
    public static void main(String[] args) {
        int a = 1000000000;
        int b = 1000000000;
        int mod = 1000000007;
        // Demonstrate modular addition
        System.out.println("Modular Addition: " + modAdd(a, b, mod)); // Output: 999999993
        // Demonstrate modular subtraction
        System.out.println("Modular Subtraction: " + modSubtract(a, b, mod)); // Output: 0
        // Demonstrate modular multiplication
        System.out.println("Modular Multiplication: " + modMultiply(a, b, mod)); // Output: 49
        // Demonstrate modular exponentiation
        long base = 2;
        long exp = 10;
        System.out.println("Modular Exponentiation: " + modExponentiation(base, exp, mod)); // Output: 1024
        // Demonstrate modular inverse
        long c = 3;
        System.out.println("Modular Inverse: " + modInverse(c, mod)); // Output: 333333336
    }
}

输出

Modular Addition: 999999993
Modular Subtraction: 0
Modular Multiplication: 49
Modular Exponentiation: 1024
Modular Inverse: 333333336

6. 排序数组

排序是计算机科学中的一项基本操作，广泛用于按特定顺序（如升序或降序）排列元素。Java 提供了内置方法来高效地排序数组和集合。主要方法是用于数组的 Arrays.sort() 和用于集合的 Collections.sort()。

文件名: SortExample.java

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class SortExample {
    public static void main(String[] args) {
        // Example of Arrays.sort() with primitive types
        int[] numbers = {5, 3, 8, 1, 2, 7};
        Arrays.sort(numbers);
        System.out.println("Sorted array (primitive types): " + Arrays.toString(numbers));
        // Example of Arrays.sort() with objects
        String[] names = {"Charlie", "Alice", "Bob"};
        Arrays.sort(names);
        System.out.println("Sorted array (objects): " + Arrays.toString(names));
        // Example of Arrays.sort() with custom Comparator (sorting strings by length)
        String[] customSortedNames = {"Charlie", "Alice", "Bob"};
        Arrays.sort(customSortedNames, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return Integer.compare(s1.length(), s2.length());
            }
        });
        System.out.println("Custom sorted array by length: " + Arrays.toString(customSortedNames));
        // Example of Collections.sort() with lists
        List<Integer> numberList = new ArrayList<>();
        numberList.add(5);
        numberList.add(3);
        numberList.add(8);
        numberList.add(1);
        numberList.add(2);
        numberList.add(7);
        Collections.sort(numberList);
        System.out.println("Sorted list (primitive types): " + numberList);
        // Example of Collections.sort() with custom Comparator (sorting strings by length)
        List<String> nameList = new ArrayList<>();
        nameList.add("Charlie");
        nameList.add("Alice");
        nameList.add("Bob");
        Collections.sort(nameList, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return Integer.compare(s1.length(), s2.length());
            }
        });
        System.out.println("Custom sorted list by length: " + nameList);
    }
}

输出

Sorted array (primitive types): [1, 2, 3, 5, 7, 8]
Sorted array (objects): [Alice, Bob, Charlie]
Custom sorted array by length: [Bob, Alice, Charlie]
Sorted list (primitive types): [1, 2, 3, 5, 7, 8]
Custom sorted list by length: [Bob, Alice, Charlie]

7. GCD 和 LCM

两个整数的最大公约数 (GCD) 是同时整除这两个数而不留余数的最大正整数。两个整数的最小公倍数 (LCM) 是同时能被这两个数整除的最小正整数。两个数的乘积等于其 GCD 和 LCM 的乘积：LCM(a,b)×GCD(a,b)=a×b。

文件名: GcdLcmExample.java

public class GcdLcmExample {
    public static void main(String[] args) {
        int a = 24;
        int b = 36;
        System.out.println("GCD of " + a + " and " + b + " is: " + gcd(a, b));
        System.out.println("LCM of " + a + " and " + b + " is: " + lcm(a, b));
    }
    // Method to compute GCD (Greatest Common Divisor) using Euclidean algorithm
    private static long gcd(long a, long b) {
        // Base case: if b is 0, return a as the GCD
        if (b == 0) {
            return a;
        }
        // Recursive call: replace a with b, and b with a % b
        return gcd(b, a % b);
    }
    // Method to compute LCM (Least Common Multiple) using GCD
    static long lcm(int a, int b) {
        // LCM is calculated using the relationship: lcm(a, b) = (a / gcd(a, b)) * b
        return (a / gcd(a, b)) * b;
    }
}

输出

GCD of 24 and 36 is: 12
LCM of 24 and 36 is: 72

8. 优化嵌套循环

嵌套循环在竞争性编程中很常见，尤其是在搜索满足特定条件的组合或对时，例如查找数组中和为特定值的对。

文件名: PairSumOptimized.java

import java.util.HashSet;
public class PairSumOptimized {
    public static void main(String[] args) {
        int[] array = {1, 4, 45, 6, 10, 8};
        int targetSum = 16;
        System.out.println("Pairs with sum " + targetSum + ":");
        findPairsWithSum(array, targetSum);
    }
    // Method to find pairs with sum using HashSet
    public static void findPairsWithSum(int[] array, int targetSum) {
        // HashSet to store elements as we iterate through the array
        HashSet<Integer> set = new HashSet<>();
        // Iterate through each element in the array
        for (int num : array) {
            int complement = targetSum - num;
            // Check if the complement (targetSum - num) exists in the HashSet
            if (set.contains(complement)) {
                System.out.println("(" + num + ", " + complement + ")");
            }
            // Add the current number to the HashSet
            set.add(num);
        }
    }
}

输出

Pairs with sum 16: (10, 6

使用泛型的优势

1. 更快的执行速度

高效的算法和数据结构通常能带来更快的执行时间，这在竞争性编程中至关重要，因为速度可以决定排名。

2. 问题解决的灵活性

技巧和优化提供了解决问题的多种方法，从而可以根据约束条件或要求选择最合适的方法，从而提供灵活性。

3. 竞争优势

在竞争性编程中，时间和正确性至关重要，使用高效的技巧可以通过更快地解决问题或有效处理边缘情况来获得超越竞争对手的优势。

下一主题Java-program-to-extract-content-from-a-pdf

使用 Java 泛型在竞争性编程中高效编码

竞争性编程中常用的函数

1. Java 中的 Pair（对）

2. 模运算下的快速幂

3. 使用费马小定理计算 nCr

4. 二项式系数（迭代）

5. 模运算

6. 排序数组

7. GCD 和 LCM

8. 优化嵌套循环

使用泛型的优势

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

使用 Java 泛型在竞争性编程中高效编码

竞争性编程中常用的函数

1. Java 中的 Pair（对）

2. 模运算下的快速幂

3. 使用费马小定理计算 nCr

4. 二项式系数（迭代）

5. 模运算

6. 排序数组

7. GCD 和 LCM

8. 优化嵌套循环

使用泛型的优势

相关帖子

Java 中 ChoiceFormat format() 方法及示例

Java 中的 Sylvester 序列

Java 中捕获基类和派生类作为异常

Java 中的 DoubleBuffer array() 方法及示例

Achilles Number in Java

Java 中的先决条件

Java 中的数字补码问题

Equals() and Hashcode() in Java

Chromatic Number in Java

实现 Java Queue 接口

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器