蓝桥杯算法题分享（二）

蓝桥杯算法题分享

本文将继续分享三道经典的蓝桥杯算法题，包括题目描述、解题思路和 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;}
}

---

总结

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

---

原题链接

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

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