蓝桥杯算法题分享（二）

蓝桥杯算法题分享

本文将继续分享三道经典的蓝桥杯算法题，包括题目描述、解题思路和 Java 代码实现，帮助大家更好地理解算法的应用。对算法感兴趣的朋友可以点开我的主页查看我上周分享的另三道题。

第一题：次数差

题目描述

x 星球有 26 只球队，分别用 a ~ z 的 26 个字母代表。他们总是不停地比赛。

在某一赛段，哪个球队获胜了，就记录下代表它的字母，这样就形成一个长长的串。

国王总是询问：获胜次数最多的和获胜次数最少的有多大差距？（当然，他不关心那些一次也没获胜的，认为他们在怠工罢了）

解题思路

1. 使用一个长度为 26 的数组 arr 记录每个字母的出现次数。
2. 遍历输入字符串，统计各个字母的出现次数。
3. 找出 arr 中非零的最大值和最小值。
4. 计算二者之差并输出结果。

Java 代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        int[] arr = new int[26];
        
        for (int i = 0; i < str.length(); i++) {    
            arr[str.charAt(i) - 'a']++;
        }
        scan.close();
        
        int max = 0, min = Integer.MAX_VALUE;
        for (int count : arr) {
            if (count > 0) {
                max = Math.max(max, count);
                min = Math.min(min, count);
            }
        }
        System.out.println(max - min);
    }
}

第二题：翻硬币

题目描述

小明正在玩一个"翻硬币"的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo;

如果同时翻转左边的两个硬币，则变为：oooo***oooo。

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

解题思路

1. 读取初始状态和目标状态。
2. 遍历字符串，如果当前位置的字符与目标状态不同，则翻转当前位置和相邻位置的硬币。
3. 统计翻转次数，直到初始状态变为目标状态。
4. 输出最小翻转次数。

Java 代码实现

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] arr1 = sc.next().toCharArray();
        char[] arr2 = sc.next().toCharArray();
        int sum = 0;
        
        for(int i = 0; i < arr1.length - 1; i++) {
            if(arr1[i] != arr2[i]) {
                arr1[i] = arr2[i];
                arr1[i + 1] = arr1[i + 1] == '*' ? 'o' : '*';
                sum++;
            }
            if(Arrays.equals(arr1, arr2)) {
                System.out.println(sum);
                break;
            }
        }
    }
}

第三题：特别数的和

题目描述

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n（1 ≤ n ≤ 10⁴）中，所有这样的数的和是多少？

解题思路

1. 遍历 1 到 n 的所有数字。
2. 逐位检查当前数字是否包含 2、0、1 或 9。
3. 如果包含其中任意一个数字，则将该数字加入总和。
4. 输出最终计算出的和。

Java 代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long sum = 0;
        
        for (int i = 1; i <= n; i++) {
            if (containsSpecialDigit(i)) {
                sum += i;
            }
        }
        System.out.println(sum);
        sc.close();
    }

    private static boolean containsSpecialDigit(int n) {
        while (n != 0) {
            int digit = n % 10;
            if (digit == 2 || digit == 0 || digit == 1 || digit == 9) {
                return true;
            }
            n /= 10;
        }
        return false;
    }
}

总结

通过这三道题，我们可以看到不同类型的算法在解决问题时的实际应用。例如，第一题考察了基本的字符串处理与计数统计，第二题涉及模拟与贪心策略，而第三题则涉及遍历和数位分析。在蓝桥杯比赛中，熟练掌握各种算法技巧，并能够灵活运用，是取得好成绩的关键。希望本篇文章能够帮助大家加深理解，并在编程竞赛中不断提升自己的实力！祝愿大家在比赛中取得优异成绩！

原题链接

• 次数差
• 翻硬币
• 特别数的和

欢迎大家在评论区留言讨论，分享你的解题思路和心得体会！