LeetCode 1006. 笨阶乘——每日一题

爱被打了一巴掌 2022-11-15 11:58 131阅读 0赞

**上一篇博客：[LeetCode 61. 旋转链表——每日一题][LeetCode 61.]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 1006. 笨阶乘][LeetCode 1006.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  示例 1
     *  示例 2
     *  提示
 *  题解
 *   *  暴力算法
     *  解题代码
     *  数学方法
     *  解题代码

# 题目信息 #

## 题目描述 ##

通常，正整数 `n` 的阶乘是所有小于或等于 n 的正整数的乘积。例如，`factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1`。

相反，我们设计了一个笨阶乘 `clumsy`：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(\*)，除法(/)，加法(+)和减法(-)。

例如，`clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1`。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。

另外，我们使用的除法是地板除法（*floor division*），所以 `10 * 9 / 8` 等于 `11`。这保证结果是一个整数。

实现上面定义的笨函数：给定一个整数 `N`，它返回 `N` 的笨阶乘。

## 示例 1 ##

> 输入：4  
> 输出：7  
> 解释：7 = 4 \* 3 / 2 + 1

## 示例 2 ##

> 输入：10  
> 输出：12  
> 解释：12 = 10 \* 9 / 8 + 7 - 6 \* 5 / 4 + 3 - 2 \* 1

## 提示 ##

1.  **1 <= N <= 10000**
2.  **-231 <= answer <= 231 \- 1 （答案保证符合 32 位整数。）**

# 题解 #

## 暴力算法 ##

循环递减进行计算，使用一个 `k` 来标记当前需要做什么操作，使用一个 `s` 来记录每一段需要优先计算的结果。初始状态下 `k = 0`，此时说明是乘数，直接将当前的值赋值给 `s`,然后使 `k++` 到下一个数值时执行 `*` 操作，继续使 `k++` 到下一个数值执行 `/` 操作。当到 `i = 1` 或者是 `k= 2` 时将结果存储到一个结果数组 `ans` 中，将所有需要加的结果记录到变量 `sum` 中。当 `k = 3` 时使 `k = 0` 进行下一端乘除的操作。

遍历完成之后所有相加的结果存储到了 `sum` 变量中，所有需要相减的数都存储到了结果数组 `ans` 中。最后特判一下结果数组中是否只有一个数值，如果是则直接输出该数值加上 `sum` 即可。否则计算一下 `ans` 中的第一个数值加上 `sum` 依次减去后面的数值。最后返回结果即可。

## 解题代码 ##

class Solution { 
    public:
        int clumsy(int N) { 
            vector<int> ans;
            int k = 0, s = 0, sum = 0;
            for (int i = N; i >= 1; i--) { 
                if (k == 0) { 
                    s = i;
                    if (i == 1) ans.push_back(s);
                    k++;
                } else if (k == 1) { 
                    s *= i;
                    if (i == 1) ans.push_back(s);
                    k++;
                } else if (k == 2) { 
                    s /= i;
                    if (i == 1) ans.push_back(s);
                    else ans.push_back(s);
                    k++;
                } else { 
                    sum += i;
                    k = 0;
                }
            }
            int res = ans[0] + sum;
            if (ans.size() == 1) return res;
            for (int i = 1; i < ans.size(); i++) res -= ans[i];
            return res;
        }
    };

## 数学方法 ##

本方法来自Y总，非常的哇塞！首先将算式展开，计算一下有什么规律。假设要计算 **n** 的笨阶乘，那么算式就是  **n ∗ ( n − 1 ) / ( n − 2 ) + ( n − 3 ) − ( n − 4 ) ∗ ( n − 5 ) / ( n − 6 ) + ( n − 7 ) − ( n − 8 ) . . . . . . n \* (n - 1) / (n - 2) + (n - 3) - (n - 4) \* (n - 5) / (n - 6) + (n - 7) - (n - 8)...... n∗(n−1)/(n−2)\+(n−3)−(n−4)∗(n−5)/(n−6)\+(n−7)−(n−8)......**。将乘除计算一下会得到： **n + 1 + 2 / ( n − 2 ) + ( n − 3 ) − ( n − 3 ) + 2 / ( n − 6 ) + ( n − 7 ) − ( n − 7 ) + 2 / ( n − 10 ) . . . . . . n + 1 + 2 / (n - 2) + (n - 3) - (n - 3) + 2 / (n - 6) + (n - 7) - (n - 7) + 2 / (n - 10)...... n\+1\+2/(n−2)\+(n−3)−(n−3)\+2/(n−6)\+(n−7)−(n−7)\+2/(n−10)......**。

因为题目说明除法是 `地板除` ，所以当 **n** 很大的时候可以只将将中间连着的四项消掉。当 **n** 很大的时候除了第一项 **n + 1** 每相连的 `四项` 都可以被消掉。但是不可能完全被消掉，当 `n % 4 == 0` 时，因为是每除了前三项，中间每四项都会被消掉，所以最后应该剩下 **8** 项（可以直接用当 n = 8时举例），所以该情况下的式子为： **n ∗ ( n − 1 ) / ( n − 2 ) + 5 − 4 ∗ 3 / 2 + 1 = n + 1 n \* (n - 1) / (n - 2) + 5 - 4 \* 3 / 2 + 1 = n + 1 n∗(n−1)/(n−2)\+5−4∗3/2\+1=n\+1**。 当 `n % 4 == 1` 时，最后应该剩下 **9** 项，式子为  **n ∗ ( n − 1 ) / ( n − 2 ) + 6 − 5 ∗ 4 / 3 + 2 − 1 = n + 2 n \* (n - 1) / (n - 2) + 6 - 5 \* 4 / 3 + 2 - 1 = n + 2 n∗(n−1)/(n−2)\+6−5∗4/3\+2−1=n\+2**。同理可以计算出当 `n % 4 == 2` 时的结果为：**n + 2**，当 `n % 4 == 3` 时的结果为：**n - 1**。

这样就可以直接求出结果，而不需要像暴力解法那样一步一步的计算了。只需要特判一下即可。

## 解题代码 ##

代码来源：[AcWing][]

class Solution { 
    public:
        int clumsy(int N) { 
            if (N == 1) return 1;
            if (N == 2) return 2;
            if (N == 3) return 6;
            if (N == 4) return 7;
            if (N % 4 == 0) return N + 1;
            if (N % 4 == 1) return N + 2;
            if (N % 4 == 2) return N + 2;
            return N - 1;
        }
    };

--------------------

> 未完待续，持续更新中……  
> ![20210326120556284.png][]

[LeetCode 61.]: https://ac-fun.blog.csdn.net/article/details/115260509
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode 1006.]: https://leetcode-cn.com/problems/clumsy-factorial/
[AcWing]: https://www.acwing.com/activity/content/code/content/1065430/
[20210326120556284.png]: /images/20221022/d53302594c254ee98818e91deb667772.png