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

最近在准备蓝桥杯，遇到了一些比较有意思的算法题，今天我将分享三道来自蓝桥杯的经典算法题，这些题可能对于大佬来说比较简单，但都是我认为比较巧妙的，希望能帮助大家在算法学习的道路上更进一步。代码部分都使用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$

  • 为了简化计算，可以比较平方值：

    ${(i - 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();
    }
}

总结：

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

原题链接：

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