蓝桥杯算法分享：征服三座算法高峰

最近在准备蓝桥杯，遇到了一些比较有意思的算法题，今天我将分享三道来自蓝桥杯的经典算法题，这些题可能对于大佬来说比较简单，但都是我认为比较巧妙的，希望能帮助大家在算法学习的道路上更进一步。代码部分都使用java解决。博客最后附有原题链接。

第一题：三带一

题目描述：

小蓝和小桥玩斗地主，小蓝只剩四张牌了，他想知道是否是“三带一”牌型。
所谓“三带一”牌型，即四张手牌中，有三张牌一样，另外一张不与其他牌相同，换种说法，四张手牌经过重新排列后，可以组成AAAB 型。

解题思路：

“三带一”牌型的特点是四张牌中有三张相同，另一张不同，如果将四张牌按从小到大排序，那么“三带一”牌型只有两种可能：

前三张牌相同，第四张不同（AAAB）
后三张牌相同，第一张不同（BAAA）

如果排序后的牌满足以下任意一种情况，则是“三带一”牌型：

s[0] == s[2] && s[0] != s[3]（AAAB）。
s[1] == s[3] && s[0] != s[3]（BAAA）。

代码实现：

import java.util.Arrays;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int i1 = scan.nextInt();for(int i=0; i<i1 ;i++ ){String str= scan.next();char s []=str.toCharArray();Arrays.sort(s);if (s[0]==s[2] && s[0]!=s[3]){System.out.println("Yes");} else if (s[1]==s[3] && s[0] !=s[3]) {System.out.println("Yes");}else {System.out.println("No");}}scan.close();}
}

第二题：信号覆盖

题目描述：

小蓝负责一块区域的信号塔安装，整块区域是一个长方形区域，建立坐标轴后，西南角坐标为 (0,0)，东南角坐标为 (W,0)，西北角坐标为 (0,H)，东北角坐标为 (W,H)。其中 W, H 都是整数。n 个位置设置了信号塔，每个信号塔可以覆盖以自己为圆心，半径为 R 的圆形（包括边缘）。
为了对信号覆盖的情况进行检查，小蓝打算在区域内的所有横纵坐标为整数的点进行测试，检查信号状态。其中横坐标范围为 0 到 W，纵坐标范围为 0 到 H，总共测试 (W+1)×(H+1) 个点。给定信号塔的位置，请问这 (W+1)×(H+1) 个点中有多少个点被信号覆盖。

解题思路：

问题核心：

遍历所有整数点 (i, j)，其中 i 的范围是 [0, W]，j 的范围是 [0, H]。对于每个点，判断是否在至少一个信号塔的覆盖范围内。

一个点 (i, j) 被信号塔 (x, y) 覆盖的条件是：

$\sqrt{(i - x)^2 + (j - y)^2} \leq R$
为了简化计算，可以比较平方值：

$x)^2 + (j - y)^2} \leq R^2$

代码实现：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int[] X = new int[100];static int[] Y= new int[100];static int r;static int n;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int w = scan.nextInt();int h = scan.nextInt();n = scan.nextInt();r = scan.nextInt();int res = 0;for (int i = 0; i < n; i++) {X[i] = scan.nextInt();Y[i] = scan.nextInt();}for (int i = 0; i <= w; i++) {for (int j = 0; j <= h; j++) {if (check(i, j)) {res++;}}}System.out.println(res);scan.close();}public static boolean check(int i, int j) {for (int k = 0; k < n; k++) {if ((i - X[k]) * (i - X[k]) + (j - Y[k]) * (j - Y[k]) <= r * r) {return true;}}return false;}
}

第三题：寻找 3 个数的最大乘积

题目描述：

实现一个算法在数组中找到 3 个数字的最大乘积。介绍如下：

例如数组 [5, -2, 3, 1, -1, 4] 中 3 个数字的最大乘积为 60。

解题思路：

最大乘积可能来自以下两种情况：

数组中最大的三个数相乘
数组中两个最小的数（可能是负数）与最大的数相乘

所以应当先对数组进行排序，方便找最大值最小值。此时以上两种情况可以表示为：

数组中最大的三个数相乘（max1 = arr[n-1] * arr[n-2] * arr[n-3]）。
数组中两个最小的数（可能是负数）与最大的数相乘（max2 = arr[0] * arr[1] * arr[n-1]）

取 max1 和 max2 中的较大值作为最终结果

代码实现：

import java.util.Scanner;
import java.util.Arrays;public class FindMax {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = scan.nextInt();}Arrays.sort(arr);int max1 = arr[n - 1] * arr[n - 2] * arr[n - 3];int max2 = arr[0] * arr[1] * arr[n - 1];int maxProduct = Math.max(max1, max2);System.out.println(maxProduct);scan.close();}
}

总结：

相信通过以上的分析和代码实现，大家对算法有了更深入的理解。当然，算法学习永无止境，希望大家能够保持热情，不断挑战自我，在算法的海洋中遨游！

原题链接：

三带一
信号覆盖
寻找 3 个数的最大乘积

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

蓝桥杯算法分享：征服三座算法高峰