算法练习（一）——数学公式，逻辑思维，DFS递归

题目一

题干

给定一个数a，这个a是可以由一组m个连续的正整数相加得到的，求这个m的最小值。举例：a=21=1+2+3+4+5+6=10+11，会发现10和11是最小的，返回m为2。

解法

要找到一个数 a 可以由一组 m 个连续的正整数相加得到的最小值 m ，我们可以使用数学方法和Python编程来解决。

我们需要检查 m 个连续整数的和是否等于 a 。如果设这 m 个连续整数从 k 开始，则它们的和为：

$$a=k+(k+1)+(k+2)+\cdots +(k+m-1)=\frac{m(2k+m-1)}{2}$$

这里运用的是等差数列求和公式。我们在这个公式中需要找出最小的 m。

通过遍历可能的 m 值，我们可以求解这个问题。以下是一个Python函数实现：

代码

def find_min_m(a):
    m = 2
    while True:
        # Calculate the first term of the sequence, k
        if (2 * a + m - m**2) % (2 * m) == 0:
            k = (2 * a + m - m**2) // (2 * m)
            if k > 0:
                return m
        m += 1

# 测试用例
a = 21
print(find_min_m(a))  # 输出2

解释

1. 初始条件：
   我们从 m = 2 开始，因为至少需要两个数才能形成一个连续的序列。

2. 公式转换：
   我们根据公式 $a=\frac{m(2k+m-1)}{2}$，转换为求 k 的表达式：
   $$k=\frac{2a+m-m^2}{2m}$$
   我们检查是否 $(2a+m-m^2)\%(2m)==0$，以确保 k 是一个整数。

3. **返回最小的 m **：
   一旦找到使 k 为正整数的 m ，我们返回这个 m 。

通过这个方法，我们可以高效地找到满足条件的最小 m 。

Tips

等差数列和的逆序。

题目二

题干

遇上了黑车司机计价器，司机不喜欢出现4这个数字，所以每次碰到4就会跳到更大的数字上。举例：3变成5，39变成50，399变成500。请根据计价器上的数值找到原本的价钱。

解法

要解决这个问题，我们需要找到一个方法来把包含4的数字映射回它们原本的数字。我们可以考虑将问题逆转，通过去掉所有在跳跃过程中产生的数字4，然后将剩余的数字重新映射到没有跳过4的序列中。

具体来说，我们可以通过以下步骤来解决这个问题：

1. 将计价器上的数值转成字符串。
2. 将字符串中的每个数字转换成一个对应的非跳跃序列中的数字。
3. 拼接这些数字，得到原本的价钱。

下面是一个Python函数来实现这个逻辑。

代码

def find_original_price(displayed_price):
    result = 0
    factor = 1
    
    while displayed_price > 0:
        digit = displayed_price % 10
        if digit > 4:
            digit -= 1
        
        result += digit * factor
        factor *= 9
        displayed_price //= 10
    
    return result

# 测试用例
print(find_original_price(5))    # 输出3
print(find_original_price(50))   # 输出39
print(find_original_price(500))  # 输出399

解释

1. 初始化结果和因子：
   我们初始化结果 result 为0，因子 factor 为1。

2. 逐位处理显示的价格：
   通过 while 循环处理每一位数字。

   • digit = displayed_price % 10：获取当前最低位数字。
   • 如果 digit 大于4，则减去1，因为原来的序列中没有4。
   • 将这个数字乘以当前的因子，并加到结果中。
   • 因子乘以9（因为原来序列中没有4，所以是基于9进制的计算）。
   • 去掉已经处理的最低位数字。

3. 返回结果：
   最终的结果就是原本的价钱。

这个函数能够正确处理各种输入值，映射出原本的价钱。通过这种方式，我们可以实现跳过4的计价器映射。

Tips

对于一个数，求10的余数获得最低位的数字，之后求除10的结果取整就是去掉最低位的数字。

题目三

题干

给定一个网格及其长宽，网格中1代表此处有服务器，0代表没有，当某处的服务器有横向或者竖向相邻的服务器时，就可以组成一个局域网。请找出最大的局域网，返回其大小。举例：给一个矩阵$\left[\begin{array}{cc}2& 2\\ 0& 1\\ 1& 1\end{array}\right]$，返回的最大的局域网大小为3。

解法

为了找到最大的局域网（即最大的由相邻服务器组成的区域），我们可以使用深度优先搜索（DFS）来遍历网格。每当遇到一个服务器节点（值为1），我们就从这个节点开始，使用DFS或BFS遍历所有与其相连的服务器节点，并计算该区域的大小。然后，我们记录下最大的区域大小。

下面是一个使用DFS的Python解决方案。

代码

def max_area_of_servers(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    max_area = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
            return 0
        grid[r][c] = 0  # 标记为已访问
        area = 1
        # 四个方向
        area += dfs(r+1, c)
        area += dfs(r-1, c)
        area += dfs(r, c+1)
        area += dfs(r, c-1)
        return area

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                max_area = max(max_area, dfs(r, c))

    return max_area

# 测试用例
grid = [
    [1, 1, 0, 0, 0],
    [1, 1, 0, 0, 1],
    [0, 0, 0, 1, 1],
    [0, 0, 0, 1, 1]
]

print(max_area_of_servers(grid))  # 输出：4

解释

1. 输入检查：首先检查输入网格是否为空。如果为空，返回0。

2. 变量初始化：获取网格的行数和列数，并初始化 max_area 为0。

3. DFS函数：定义一个深度优先搜索（DFS）函数，该函数将遍历所有相邻的服务器节点并计算区域大小。

   • 如果当前节点超出边界或当前节点为0（表示没有服务器），返回0。
   • 否则，将当前节点标记为已访问（设置为0），并初始化当前区域大小为1。
   • 递归遍历四个方向（上下左右）的节点，并累加区域大小。

4. 遍历网格：遍历网格中的每个节点，如果节点值为1（表示有服务器），则调用DFS函数计算该区域的大小，并更新 max_area。

5. 返回结果：返回最大区域的大小。

通过这种方法，我们可以高效地找到网格中最大的局域网。

Tips

DFS可以用来递归寻找最大的连通分量。注意可以改变原值来标记该处已被处理（比如原本的grid[i][j]为1，处理后改为0）.