72-笨阶乘

自己的做法

算法思想

四次运算为1个轮回，求n的笨阶乘，则需要n - 1次运算。

使用一个栈，乘除直接算，加减先入栈。最后将栈中元素累加即可。

使用i作为循环变量，初始为0，共循环n- 1次，所以条件为i < n - 1。计算 i % 4。

共有四种情况：0 乘， 1 除， 2 加，3 减。

对于乘除：取出栈顶元素，进行相应运算后入栈。

对于加减：加运算将原数入栈，减运算将相反数入栈。

最后将栈中元素累加。

算法实现

class Solution {
public:
    int clumsy(int n) {
        int num = n - 1;
        stack<int> s;
        s.push(n);
        for(int i = 0; i < n - 1; i++) {
            int num1 = s.top();
            switch (i % 4) {
                case 0:
                    s.pop();
                    s.push(num1 * num);
                    break;
                case 1:
                    s.pop();
                    s.push(num1 / num);
                    break;
                case 2:
                    s.push(num);
                    break;
                case 3:
                    s.push(-num);
                    break;
            }
            num--;
        }
        int sum = 0;
        while (!s.empty()) {
            sum += s.top();
            s.pop();
        }
        return sum;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(n)$。

参考做法

​