数位递增的数

方法一：逐位比较法

• 从右向左逐位比较相邻数字
• 如果发现左边数字大于右边数字，立即返回false
• 时间复杂度：O(d)，d为数字位数

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数。
        int n = scanner.nextInt();
        int count = 0;
        for (int i = 1; i <= n; i++) {
            int num = i;
            int right = num % 10;
            num /= 10;
            // 先标记为数位递增
            boolean isIncreasing = true;
            while (num > 0) {
                int left = num % 10; // 最后一位数
                // 发现大于了, 说明不是数位递增
                if (left > right) {
                    isIncreasing = false;
                }
                right = left;
                num /= 10;
            }
            if (isIncreasing) {
                count++;
            }
        }
        System.out.println(count);
    }
}

用函数的话会更加直观, 可以发现不满足条件立即返回，提高效率

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数。
        int n = scanner.nextInt();
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (isIncreasing(i)) {
                count++;
            }
        }
        System.out.println(count);
    }

    private static boolean isIncreasing(int num) {
        int right = num % 10;
        num /= 10;
        while (num > 0) {
            int left = num % 10; // 最后一位数
            // 发现大于了, 说明不是数位递增
            if (left > right) {
                return false;
            }
            right = left;
            num /= 10;
        }
        return true;
    }
}

方法二：字符串排序法

• 将数字转为字符串并排序
• 比较排序前后字符串是否相同
• 时间复杂度：O(d log d)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数。
        int n = scanner.nextInt();
        int count = 0;
        for (int i = 1; i <= n; i++) {
            // 比较排序后的字符串和原字符串是否一致
            // 先将数字转成字符串
            String str = Integer.toString(i);
            // 将字符串转成字符数组, 方便排序
            char[] chars = str.toCharArray();
            // 排序
            Arrays.sort(chars);
            // 排序后的字符串
            String sortedStr = new String(chars);
            // 如果排序后的字符串和原字符串一致, 则数位递增
            if (str.equals(sortedStr)) {
                count++;
            }
        }
        System.out.println(count);
    }
}

好数

位置标记法

• 用 pos变量记录当前位置（从个位开始为1）
• 奇数位：pos % 2 == 1 且 digit % 2 == 1
• 偶数位：pos % 2 == 0 且 digit % 2 == 0

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int cnt = 0;
        // 枚举1到N的所有数字
        for (int i = 1; i <= n; i++) {
            if (isGoodNum(i)) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    private static boolean isGoodNum(int num) {
        // 取出每个数字
        int pos = 1; // 从个位开始，位置编号为1（奇数位）
        while (num > 0) {
            int digit = num % 10; // 取出当前位的数字
            // 如果奇数位是偶数, 或者偶数位是奇数, 则不是好数
            if ((pos % 2 == 1 && digit % 2 == 0) || (pos % 2 == 0 && digit % 2 == 1)) {
                return false;
            }
            num /= 10; // 去掉当前位
            pos++; // 位置编号加1
        }
        return true; // 如果所有位都符合条件, 则是好数
    }
}

校门外的树

数组标记法

• 创建长度为L+1的布尔数组来模拟这条道路
• 初始所有位置标记为true或者1（有树）
• 遍历每个区间，将对应位置标记为false或者0（移除）
• 最后统计true的数量

关键点在于用数组来模拟这条道路, 数组的每个元素下标相当于横坐标, 元素值这里可以用来指代有没有种树

用1代表有树, 用0代表没树

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int L = scanner.nextInt();
        int M = scanner.nextInt();
        int[] trees = new int[L + 1];
        // 0到L都种有树
        for (int i = 0; i <= L; i++) {
            trees[i] = 1;
        }
        while (M-- > 0) { // 循环M次
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            // 从start到end, 把树移除
            for (int i = start; i <= end; i++) {
                trees[i] = 0; // 重复移除也没关系, 最终结果仍然是0
            }
        }
        int count = 0;
        for (int i = 0; i <= L; i++) {
            if (trees[i] == 1) {
                count++;
            }
        }
        System.out.println(count);
    }
}

用true和false可能更直观理解

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int L = scanner.nextInt();
        int M = scanner.nextInt();
        boolean[] trees = new boolean[L + 1];
        // 0到L都种有树
        for (int i = 0; i <= L; i++) {
            trees[i] = true;
        }
        while (M-- > 0) { // 循环M次
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            // 从start到end, 把树移除
            for (int i = start; i <= end; i++) {
                trees[i] = false; // 重复移除也没关系, 最终结果仍然是false
            }
        }
        int count = 0;
        for (int i = 0; i <= L; i++) {
            if (trees[i]) {
                count++;
            }
        }
        System.out.println(count);
    }
}

多次出现的数

向上取整公式: (a + b - 1) / b

核心思想：先“加一点”，让结果刚好能被向下取整成我们想要的“向上”结果

加一个比b小1的数，只要余数不是0就会使答案加一

• b - 1 是“最大可能的余数”（因为余数只能是 1 到 b-1）
• 加上 b-1 相当于说：“只要还有剩的，我就假装它快够一整袋了”，这样整数除法就会自动多算一个。

方法一：HashMap计数法

• 使用HashMap记录每个数字出现的次数
• 当某个数字的次数达到目标值时立即返回
• 时间复杂度：O(n)，空间复杂度：O(n)

用数组实现的思路(但不能通过本题):

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        // (a+(b-1))/b, 即a/b向上取整
        int target = (2 * n + 2) / 3;
        int[] cnt = new int[100005];
        for (int i = 1; i <= n; i++) {
            // 对于每个数字num, 将其累计数量
            int num = scanner.nextInt();
            cnt[num]++;
            // 如果某个数字出现的次数大于等于target, 则该数字就是要找的
            if (cnt[num] >= target) {
                System.out.println(num);
                return;
            }
        }
    }
}

过不了是因为数太大了, 最大是10^9, 所以我们可以用HashMap来代替数组实现相同的功能

HashMap

🌟 想象一下：你是个小卖部老板，要记账

你不需要给每一个可能的商品编号都准备一页纸。

你只在有人买了某个商品时，才在本子上写一笔：

商品编号	卖了多少个
1001	3
2005	1
3007	2

这个“记账本”就是 HashMap！

HashMap 就是一个“名字 → 数量”的映射工具。

• Key（键）：你要统计的东西，比如“数字 3”
• Value（值）：它出现的次数，比如“3 次”

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        // (a+(b-1))/b, 即a/b向上取整
        int target = (2 * n + 2) / 3;
        HashMap<Integer, Integer> cnt = new HashMap<>(); // 一个映射, key是数字, value是数量
        for (int i = 1; i <= n; i++) {
            // 对于每个数字num, 将其累计数量
            int num = scanner.nextInt();
            cnt.put(num, cnt.getOrDefault(num, 0) + 1); // cnt[num]++;
            // 如果某个数字出现的次数大于等于target, 则该数字就是要找的
            if (cnt.get(num) >= target) { // if (cnt[num] >= target)
                System.out.println(num);
                return;
            }
        }
    }
}

1. 查某个数字现在出现几次？

cnt.get(num) // 查 num 出现了多少次

但如果这个数字还没记过账，get 会返回 null，会出错！

所以要用：

cnt.getOrDefault(num, 0)

👉 意思是：“如果没记过，就当它是 0 次”

2. 给某个数字加 1 次

cnt.put(num, cnt.getOrDefault(num, 0) + 1);

👉 拆解：

• 先查 num 现在是几次（没记过就当 0）
• 加 1
• 再存回去

就像你在记账本上：

“哦，3 又卖了一个，现在是 4 个了！”

摩尔投票法

是什么？

一种专门用来找“超级多数元素” 的聪明算法，特点是：

• 时间 O(n)：只遍历一遍数组
• 空间 O(1)：只用几个变量，不额外开大数组或 HashMap

特别适合面试和竞赛！

💡 核心思想（同归于尽吧!）：

想象一场“武林大会”，所有人拿着自己的门派牌子（数字），比如 3, 3, 1, 2, 3

规则是：

• 遇到不同门派的人 → 两人同归于尽（抵消）
• 遇到相同门派的人 → 收纳入队，组队继续打

如果某个门派的人数 超过一半以上（比如这里超过 2/3），那最后活下来的一定是他们的人！

因为题目说：“有个数出现 ≥ ⌈2n/3⌉ 次”，说明它超级多！

就像一个门派有 70% 的人，其他所有门派加起来才 30%，怎么打都赢！

所以我们可以用“投票抵消”的方式，找出这个“隐藏大佬”。

步骤:

• 使用候选人和计数变量
• 遍历数组，通过抵消的方式找到出现次数最多的元素
• 时间复杂度：O(n)，空间复杂度：O(1)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int candidate = -1; // 候选人的位置
        int count = 0; // 候选人的门派有几个人
        for (int i = 0; i < n; i++) {
            int num = scanner.nextInt(); // 来个人比划比划
            if (count == 0) {
                candidate = num; // 宗门无人, 你来当老大
            }
            if (num == candidate) {
                // 咱俩一伙的, 收纳入队
                count++;
            } else {
                // 咱俩不是一伙的, 派出一个人和他同归于尽
                count--;
            }
        }
        // 最后活着的人是最多的那个数字
        System.out.println(candidate);
    }
}

排序

核心思路: 先排序 → 再遍历，统计连续相同数字的个数

想象你有一堆乱序的数字：

[1, 2, 3, 3, 3, 3, 4, 3, 3, 3]

你把它们从小到大排好：

[1, 2, 3, 3, 3, 3, 3, 3, 3, 4]

现现在相同的数字都“抱在一起”(相邻)了！并且他们占了超过一半的位置，所以，中间那个位置（中位数）一定被它占据！

结论：中位数一定是 x

直接返回中间的数字

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        // 先读取进来所有的数
        int[] nums = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            nums[i] = scanner.nextInt();
        }
        // 排序! O(n log n)
        Arrays.sort(nums, 1, n + 1); // 对编号1-n的数字进行排序

        // 取中间的中位数, 就是目标数字
        System.out.println(nums[(1 + n) / 2]);
    }
}

计算鞍点

解题思路（分三步走）

1. 先读入 5×5 的矩阵
2. 对每一行，找出最大值的位置
3. 检查这个最大值，是不是它所在列的最小值
4. 如果是，输出它；如果都不是，输出 not found

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 鞍点指的是矩阵中的一个元素，它是所在行的最大值，并且是所在列的最小值
        // 定义矩阵
        int[][] matrix = new int[6][6];

        // 读入矩阵
        for (int i = 1; i <= 5; i++) {
            for (int j = 1; j <= 5; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        // 开始找鞍点
        boolean found = false;  // 标记是否找到鞍点

        // 遍历每一行
        for (int i = 1; i <= 5; i++) {
            // 第一步：找第 i 行的最大值 和 它的列号
            int maxInRow = matrix[i][1];  // 假设第一个最大
            int colIndex = 1;             // 记录最大值在第几列

            for (int j = 2; j <= 5; j++) {
                if (matrix[i][j] > maxInRow) {
                    maxInRow = matrix[i][j];
                    colIndex = j;
                }
            }

            // 现在 maxInRow 是第 i 行最大值, 位于第 colIndex 列
            // 第二步：检查它是不是第 colIndex 列的最小值
            int minInCol = matrix[1][colIndex];  // 先假设第一行这个列的值最小

            for (int k = 2; k <= 5; k++) {
                if (matrix[k][colIndex] < minInCol) {
                    minInCol = matrix[k][colIndex];
                }
            }

            // 第三步：判断 maxInRow(当前行的最大值) 是否等于 minInCol(对应列的最小值)
            // 注意：不是值相等，而是“这个元素”既是行最大，又是列最小
            if (maxInRow == minInCol) {
                // 输出鞍点所在的行、列及其值
                System.out.println(i + " " + colIndex + " " + maxInRow);
                found = true;  // 标记为找到鞍点
                break;  // 找到一个就可以停了
            }
        }
        // 如果没找到
        if (!found) {
            System.out.println("not found");
        }
    }
}

题目说“每行只有一个最大值，每列只有一个最小值”，所以不会有并列，不用担心“多个最大值”，一旦找到一个鞍点就可以停止