论暴力的重要性！

经常听人谈起暴力，那暴力到底是什么呢?他有一个明确的定义吗？接下来我们来一探究竟

在算法领域，暴力解法（Brute Force Approach）是一种最直接、最简单但通常也是最效率低下的解决问题的方法。它通过尝试所有可能的解决方案，直到找到正确的解决方案或所有可能性都被尝试过。暴力解法的特点是易于理解和实现，但在处理大规模问题时，往往会因为时间复杂度高而变得不可行。

特点

1. 直接性：暴力解法通过列举所有可能的情况来解决问题。
2. 简单性：实现起来相对简单，不需要复杂的算法或数据结构。
3. 低效性：对大规模数据和问题，暴力解法通常很低效，时间复杂度和空间复杂度可能非常高。

例子

例1：字符串匹配

假设我们有一个文本字符串text和一个模式字符串pattern，需要在text中找到pattern的所有出现位置。暴力解法会尝试将pattern与text的每一个子字符串进行匹配。

def brute_force_string_match(text, pattern):
    n = len(text)
    m = len(pattern)
    positions = []
    
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            positions.append(i)
    
    return positions

text = "abracadabra"
pattern = "abra"
print(brute_force_string_match(text, pattern))  # 输出: [0, 7]

例2：旅行商问题（TSP）

旅行商问题是一类经典的组合优化问题，即给定一组城市和每对城市之间的距离，找到一条经过每个城市一次并返回起点的最短路径。暴力解法会生成所有可能的路径并计算它们的总距离，然后选择最短的路径。

import itertools

def tsp_brute_force(distance_matrix):
    n = len(distance_matrix)
    all_permutations = itertools.permutations(range(n))
    min_distance = float('inf')
    min_path = None
    
    for perm in all_permutations:
        current_distance = 0
        for i in range(n):
            current_distance += distance_matrix[perm[i]][perm[(i + 1) % n]]
        
        if current_distance < min_distance:
            min_distance = current_distance
            min_path = perm
    
    return min_path, min_distance

distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
print(tsp_brute_force(distance_matrix))  # 输出: 最短路径及其距离

优缺点

优点

1. 简单直接：易于实现和理解。
2. 全面性：不会遗漏任何可能的解决方案，能保证找到最优解（如果有）。

缺点

1. 低效：时间复杂度和空间复杂度通常非常高，导致在处理大规模问题时不可行。
2. 不实用：对于大多数实际问题，暴力解法无法在合理时间内给出结果，需要改进。

何时使用

1. 问题规模较小：在处理规模较小的问题时，暴力解法可以快速找到解决方案。
2. 作为基准：可以作为复杂算法的基准，用于验证优化算法的正确性。
3. 探索阶段：在问题的初期探索阶段，可以使用暴力解法来理解问题并找到一些初步的解决方案。

尽管暴力解法在实际应用中往往不高效，但它的简单性和全面性使其在特定情况下仍然有一定的价值。随着问题规模的增大，通常需要更高效的算法来替代暴力解法，如动态规划、贪心算法、分治法等。

实例上线，来看看这道题。暴力有多爽！

​

419.甲板上的战舰[中等]

题目：

给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在甲板 board 上放置的 战舰 的数量。

战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造，其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。

​编辑

输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出：2

示例 2：

输入：board = [["."]]
输出：0

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 是 '.' 或 'X'

题目分析：

         这道题可能题目有点表达不清晰，会让人误以为只有在第1行的某个列和第1列的某行才能算数，其实并不是这个意思。他的意思是每个战舰都要和周围的分开，当他们相连接的时候是被看做一个战舰的，只有被隔开的两个战舰才被认为是两个战舰，然后搜查一共有多少艘战舰。

        最本质的思路就是暴力搜索，遍历一遍看看有几个符合题意的X，统计并返回即可。以下是代码实现：

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        a1,a2,res=len(board),len(board[0]),0  # a1是行  a2是列 res是战舰总数
        for i in range(a1):
            for j in range(a2):
                if (j==0 and board[i][j]=='X' and ((i>0 and board[i-1][j]!='X') or (i==0))) or (j!=0 and board[i][j]=='X' and board[i][j-1]=='.' and ((i>0 and board[i-1][j]!='X') or (i==0))): res+=1
        return res

​编辑

​

编辑

总结：

        这段代码通过遍历二维字符数组中的每个位置，并根据相邻字符的情况，判断该位置是否属于战舰，从而统计出二维字符数组中战舰的数量。以下是具体实现步骤：

1. 首先，获取二维字符数组 board 的行数和列数，分别赋值给变量 a1 和 a2，并初始化战舰总数变量 res 为 0。

2. 然后，使用两层循环遍历整个二维数组 board。外层循环控制行数，内层循环控制列数。

3. 在每次循环中，通过条件判断语句检查当前字符是否为 ‘X’，以及其前一个字符的情况，来判断当前位置是否属于战舰。具体的判断逻辑如下：

   • 如果当前字符在第一列且为 ‘X’，且前一个字符不是 ‘X’（或当前字符在第一行），则将战舰总数 res 增加 1。
   • 如果当前字符不在第一列且为 ‘X’，且当前字符的前一个字符是 ‘.’（表示战舰的左侧没有战舰），并且满足第一个条件（前一个字符不是 'X’或当前字符在第一行），则将战舰总数 res 增加 1。

4. 最后，返回统计得到的战舰总数 res。

   ---

   
   

Control is Power.

​