Leetcode 2431.最小偶倍数

 

给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。

示例 1：

输入：n = 5
输出：10
解释：5 和 2 的最小公倍数是 10 。

示例 2：

输入：n = 6
输出：6
解释：6 和 2 的最小公倍数是 6 。注意数字会是它自身的倍数。

提示：

• 1 <= n <= 150

我的答案：

 

一、信息

1.给我一个正整数n

2.返回2和n的最小公倍数

二、分析

1.条件1和条件2已经很明显的告诉我此次的目的在于求解n的最小公倍数。

三、步骤

第一步输入一个正整数

第二步求解n的最小公倍数

第三步输出

四、问题出现了

1.该如何求解一个正整数的最小公倍数？

求解两个正整数的最小公倍数（LCM，Least Common Multiple）通常需要先求出这两数的最大公约数（GCD，Greatest Common Divisor）。求解 GCD 有很多方法，其中较为普遍的是使用欧几里得算法。

首先，提供两个正整数的 GCD 的求解方法：

**欧几里得算法**：

假设有两个非负整数 \(a\) 和 \(b\) 且 \(a ≥ b\)，如果 \(b = 0\)，则 \(a\) 是两数的最大公约数。否则，\(a\) 和 \(b\) 的最大公约数是 \(b\) 和 \(a\%b\) 的最大公约数。

使用 Python，这个算法可以这样表示：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

当我们有了 GCD 后，可以使用以下关系求 LCM：

{LCM}(a, b) = {|a \times b|}{\text{GCD}(a, b)}

这里是因为两数之积等于它们的最大公约数和最小公倍数的积。

再次使用 Python，这个关系可以这样表示：

def lcm(a, b):
    return abs(a*b) // gcd(a, b)

如果你需要求三个或更多数字的 LCM，可以这样做：

1. 先求前两个数字的 LCM。
2. 使用得到的 LCM 和下一个数字再求 LCM。
3. 重复上述过程，直到处理完所有数字。

例如，要求三个数字的 LCM，可以这样：

\[ \text{LCM}(a, b, c) = \text{LCM}(\text{LCM}(a, b), c) \]

这种方法可以扩展到任意数量的数字。

五、算法实现

我的答案：

思考过程：

对于算法和数学问题，一个明确、系统化的思考过程是非常重要的。以下是面对此类问题时常用的思考步骤，以刚刚的问题为例：

### 1. **理解问题**:
首先，确保我完全理解了问题及其要求。
- 这个问题要我做什么？
  *找出2和一个给定的正整数n的最小公倍数（LCM）。*

### 2. **列出已知条件**:
明确已知的信息和限制。
- n是一个正整数。
- 1 <= n <= 150

### 3. **考虑简单案例和特殊情况**:
这有助于发现问题的模式。
- 当n=1时，LCM是什么？
- 当n是奇数时，它和2的GCD是多少？
- 当n是偶数时，情况会如何变化？

### 4. **引入已知概念和公式**:
如果与您熟悉的概念或技巧相关，请引入它们。
- 了解到两数的LCM可以由它们的GCD推出。
- 使用欧几里得算法来找GCD。

### 5. **逻辑推理**:
在已知信息的基础上进行推理。
- 2是素数，只与偶数有GCD大于1。
- 因此，对于奇数n，GCD(2, n) = 1，而对于偶数n，GCD(2, n) = 2。

### 6. **形成算法或解决方案**:
基于上述分析，将解决方案明确并转化为算法。
- 如果n是偶数，返回n。
- 如果n是奇数，返回2*n。

### 7. **测试算法**:
使用一些示例输入来验证我的答案。
- 当n=5(奇数)时，输出应为10。
- 当n=6(偶数)时，输出应为6。

### 8. **优化** (如果可能和必要的话):
重新审视我的解决方案，考虑是否有更高效、简洁的方法。
- 在这个特定问题中，我们发现了一个简化的方法，不需要真正计算GCD。

### 9. **总结**:
回顾整个问题和解决方案，总结学到的内容和遇到的难点。

这样的思考过程不仅可以帮助解决当前的问题，还可以培养面对未来问题时的解决思路和方法。

**分析**:
1. **问题描述**: 题目要求我们找到2和任意给定的正整数`n`的最小公倍数。
2. **已知条件**: `1 <= n <= 150`，这是一个有界的问题，所以我们可以保证我们的算法在合理的时间内完成。

**推理**:
1. **GCD与LCM的关系**: 我们知道两个数字的乘积是它们的最大公约数（GCD）和最小公倍数（LCM）的乘积。数学上，这可以表示为：a×b=GCD(a,b)×LCM(a,b)

。由此我们可以得到：LCM(a,b)=a×bGCD(a,b)

LCM(a,b)=a×bGCD(a,b)

。
2. **求GCD**: 对于两个数字，存在多种方法求GCD，但其中最经典的方法是欧几里得算法（也称为辗转相除法）。
3. **求2和n的GCD**: 因为2是一个素数，它只与偶数共有GCD大于1（即GCD为2），与奇数的GCD为1。

**演绎**:
1. 如果`n`是偶数，则GCD(2,n)=2

，所以LCM(2,n)=n

LCM(2,n)=n

。
2. 如果`n`是奇数，则GCD(2,n)=1

GCD(2,n)=1

，所以LCM(2,n)=2×n

LCM(2,n)=2×n

。

根据上述推理，我们可以得到一个简单的算法：
- 如果`n`是偶数，则LCM是`n`。
- 如果`n`是奇数，则LCM是`2 * n`。

这种分析、推理和演绎的过程对于解决问题至关重要。它不仅帮助我们理解问题的核心，还为我们提供了一个有效的求解方法。

英雄师傅答案：

暴力破解法：
C++:

int smallestEvenMultiple(int n){
    for(int i=1;;++i){
        if(i%2==0&&i%n==0){
            return i;
        }
    }
    return -1;
}

Leetcode官方题解：

方法一：数学
思路与算法

对于任意两个正整数 nnn，mmm 的最小公倍数为 n×mgcd⁡(n,m)\frac{n \times m}{\gcd(n, m)} 
gcd(n,m)
n×m
​
 ，其中 gcd⁡(n,m)\gcd(n, m)gcd(n,m) 为 nnn 和 mmm 的最大公约数。

现在题目给出一个正数 nnn，需要返回 222 和 nnn 的最小公倍数，又因为任意正偶数与 222 的最大公约数为 222，任意正奇数与 222 的最大公约数为 111。所以当 nnn 为偶数时直接返回 nnn，否则返回 2×n2 \times n2×n 即可。

作者：力扣官方题解
C：

int smallestEvenMultiple(int n) {
    return n % 2 == 0 ? n : 2 * n;
}

C++:

class Solution {
public:
    int smallestEvenMultiple(int n) {
        return n % 2 == 0 ? n : 2 * n;
    }
};
 

JAVA：
 

class Solution {
    public int smallestEvenMultiple(int n) {
        return n % 2 == 0 ? n : 2 * n;
    }
}
 

 总结：

题目“最小偶倍数”主要是要我们找出给定正整数 nn 和数字 2 之间的最小公倍数。以下是从这个问题中我们可以学到的内容和可能犯的错误：

### **学习内容**：

1. **数学知识的应用**：
   - 这个问题需要我们知道如何求两个数的最小公倍数。这引导我们回想和应用基础数学知识。

2. **编程技巧**：
   - 简化问题。我们知道2是偶数，所以只有当 nn 是奇数时，它和2的最小公倍数是 2×n2×n。当 nn 是偶数时，它本身就是最小公倍数。

3. **代码优化**：
   - 由于问题特点，我们不需要使用复杂算法来计算最小公倍数。根据 nn 的奇偶性，我们可以迅速确定答案。

### **常见错误**：

1. **过度复杂化**：
   - 有些人可能会使用标准算法来计算最小公倍数，例如先找出两个数字的最大公约数，然后再根据此求最小公倍数。而在这特定问题中，这是不必要的。

2. **不考虑边界条件**：
   - 如果忽视了当 nn 是1或2的情况，可能会导致不正确的输出。

3. **逻辑错误**：
   - 可能错误地假设当 nn 是奇数时，其和2的最小公倍数是 nn，而当 nn 是偶数时是 2×n2×n，这与实际情况恰恰相反。

总的来说，这个题目提醒我们在解决问题时要注意问题的特点和简化，而不是机械地应用公式或算法。同时，它也强调了在编写代码时要考虑到所有可能的边界条件。