2019-01-01

喵星之旅-阴险的布谷鸟-暴力枚举

简介

暴力枚举，也称为穷举法或暴力求解，是一种简单朴素的算法思想。其基本思想是对问题的所有可能情况进行逐一尝试，并从中找到符合条件的解决方案。这种算法通常通过循环或递归实现，其时间复杂度与问题规模成指数级关系。因此，对于较大规模的问题，暴力枚举可能并不适用，但对于一些小规模问题，它往往是可行的。

在实现上，暴力枚举算法通常采用循环或递归的方式。循环实现通常是嵌套多层循环，逐个枚举每个可能的情况，并在内层循环中对每种情况进行检查。递归实现则是将问题分解为更小的子问题，逐层递归求解，直到找到符合条件的解。

具体的暴力枚举解法包括循环枚举和子集枚举等。循环枚举类似于模拟，将所有的情况依次罗列出来，然后判断是否可行，并累加得到答案。子集枚举则是通过组合数的方法，从给定的集合中选取特定数量的元素，然后遍历所有可能的状态，找到满足条件的解。

需要注意的是，暴力枚举虽然简单直接，但在处理大规模问题时可能会导致计算量巨大，效率较低。因此，在实际应用中，需要根据问题的规模和特点，选择合适的算法进行优化。例如，可以通过剪枝、分治、变换枚举对象等方式来减少不必要的计算，提高算法的效率。

优点：
1.能举出所有情况，保证解为正确解。
2.能解决许多用其他算法难以解决的问题。
3.便于思考与编程。

主要实现步骤

例题

题目

给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。

如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个好三元组。

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c

其中 |x| 表示 x 的绝对值。

返回好三元组的数量。

提示：

3 <= arr.length <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000

示例

示例 1：

输入：arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
输出：4
解释：一共有 4 个好三元组：[(3,0,1), (3,0,1), (3,1,1), (0,1,1)] 。

示例 2：

输入：arr = [1,1,2,2,3], a = 0, b = 0, c = 1
输出：0
解释：不存在满足所有条件的三元组。

解答

public int countGoodTriplets(int[] arr, int a, int b, int c) {
    int n = arr.length, cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = j + 1; k < n; ++k) {
                if (Math.abs(arr[i] - arr[j]) <= a && Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {
                    ++cnt;
                }
            }
        }
    }
    return cnt;
}