【LeetCode】笨阶乘 Java 题解

HQ数字卡

关注

发布于: 2021 年 04 月 01 日

题目

通常，正整数 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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/clumsy-factorial

代码

public class DayCode {    public static void main(String[] args) {        int N = 10;        int ans = new DayCode().clumsy(N);        System.out.println("ans is " + ans);    }
    /**     * 时间复杂度 O(N)     * 空间复杂度 O(N)     * @param N     * @return     */    public int clumsy(int N) {        Deque<Integer> stack = new ArrayDeque<>();        stack.push(N);        N--;        int idx = 0;        while (N > 0) {            int flag = idx % 4;            switch (flag) {                case 0:                    stack.push(stack.pop() * N);                    break;                case 1:                    stack.push(stack.pop() / N);                    break;                case 2:                    stack.push(N);                    break;                case 3:                    stack.push(-N);                    break;                default:                    break;            }            N--;            idx++;        }        int ans = 0;        while (!stack.isEmpty()) {            ans += stack.pop();        }        return ans;    }

    /**     * 时间复杂度 O(N)     * 空间复杂度 O(1)     * @param N     * @return     */    public int clumsy2(int N) {        if (N == 1) {            return 1;        } else if (N == 2) {            return 2;        } else if (N == 3) {            return 6;        } else if (N == 4) {            return 7;        }
        if (N % 4 == 0) {            return N + 1;        } else if (N % 4 <= 2) {            return N + 2;        } else {            return N - 1;        }    }

复制代码

总结

今天的每日一题，符合节日的气氛，确实觉得自己有点“笨”。
这题采用了两种解法，第一种解法使用栈，中规中矩，本题只有 +, - , * , / 四则运算，先算 *, / ，后算 + , -。多加练习，才能写出简洁的代码。
第二种解法采用的数学解法，也是本题的最优解法。但是数学解法，写过之后还是容易忘记，得多看多写几次。
昨天看大神聊天，说是看到题解，一看就会，说明基本会了，半天看不懂，说明触及到了知识盲点，需要努力补全学习知识，提升自己，共勉！
坚持每日一题，加油！

发布于: 2021 年 04 月 01 日阅读数: 13

原文链接:【http://xie.infoq.cn/article/b0ceed5567be28eaa32cad230】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】笨阶乘 Java 题解

题目

代码

总结

HQ数字卡

评论