本文共 3431 字，大约阅读时间需要 11 分钟。

模拟年份的天干和地支判断

2020年是庚子年，0000年是庚申年。通过对年份取模运算，我们可以利用天干和地支的周期性规律来判断任意年份的天干和地支。

通过以上方法，我们可以编写一个简单的程序来判断任意年份的天干和地支。

程序示例：

import java.util.Scanner;
public class Main {
    static final String[] TIAN = {"geng", "xin", "ren", "gui", "jia", "yi", "bing", "ding", "wu", "ji"};
    static final String[] DI = {"shen", "you", "xu", "hai", "zi", "chou", "yin", "mao", "chen", "si", "wu", "wei"};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int year = sc.nextInt();
        System.out.println(TIAN[year % 10] + DI[year % 12]);
    }
}

完全背包问题

给定N个蒸笼，每个蒸笼的包子数量分别为A1, A2,...,An，且这些数的最大公约数d > 1。通过裴蜀定理，我们可以确定无法被d整除的数也无法被所有A_i整除。

解决方案：

• 使用动态规划，记录能否凑成每个数量。
• 优化为一维数组，减少空间复杂度。

程序示例：

import java.util.Scanner;
public class Main {
    static final int N = 110, M = 10010;
    static int[] a = new int[N];
    static boolean[] f = new boolean[M];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            d = gcd(d, a[i]);
        }
        if (d != 1) {
            System.out.println("INF");
        } else {
            f[0] = true;
            for (int i = 1; i <= n; i++) {
                for (int j = a[i]; j < M; j++) {
                    f[j] |= f[j - a[i]];
                }
            }
            int res = 0;
            for (int i = 0; i < M; i++) {
                if (!f[i]) {
                    res++;
                }
            }
            System.out.println(res);
        }
    }
    private static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}

找最小数的约数个数

编写一个函数，计算给定数的约数个数。通过暴力方法逐个检查，直到找到约数个数为100的最小数。

程序示例：

public class Main {
    public static void main(String[] args) {
        System.out.println(45360);
    }
}

广度优先搜索

在字符串中找到最短路径，允许字符跳跃。

程序示例：

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
    static int l;
    static int[] dx = {1, -1, 2, -2, 3, -3};
    static String a = "";
    static String b = "";
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        a = in.next();
        b = in.next();
        l = a.length();
        System.out.println(bfs());
    }
    private static int bfs() {
        Queue
   
     q = new LinkedList<>();
        q.offer(a);
        HashMap
    
      dist = new HashMap<>();
        dist.put(a, 0);
        while (!q.isEmpty()) {
            StringBuilder t = new StringBuilder(q.poll());
            int dis = dist.get(t.toString());
            if (t.toString().equals(b)) {
                return dis;
            }
            int pos = t.indexOf("*");
            for (int i = 0; i < 6; i++) {
                int nx = pos + dx[i];
                if (nx >= 0 && nx < l) {
                    char x = t.charAt(pos);
                    char y = t.charAt(nx);
                    t.setCharAt(pos, y);
                    t.setCharAt(nx, x);
                    if (!dist.containsKey(t.toString())) {
                        dist.put(t.toString(), dis + 1);
                        q.offer(t.toString());
                    }
                }
            }
        }
        return -1;
    }
}
    
   

转载地址：http://jkhfk.baihongyu.com/