3 个简单题~

1588. Sum of All Odd Length Subarrays

Analysis

题意是求含有奇数个项的所有子序列的和，100 的数量级，应该可以直接做出来。

Code

method 1

用 step 来控制每次选择连续奇数个数组成子序列，然后求和。

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int size = arr.size(), sum = 0;
        for(int step = 1; step <= size; step += 2) {
            for(int i = 0; i < size; i++) {
                if(i + step <= size) {
                    for(int j = i; j < i + step; j++) {
                        sum += arr[j];
                    }
                } else break;
            }
        }
        return sum;
    }
};

这样做的时间复杂度是 $O(n^3)$。

method 2

但是直接做显然不够优雅，观察上面的计算过程，以 $1, 2, 3$ 的序列为例，计算过程是 $1 + 2 + 3 + 1 + 2 + 3 = 9$，实际上是求了两次数组的元素之和，如果能想个办法只求一次和就好了。按照这样的思考思路，可以使用前缀和思想来做。

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int size = arr.size(), sum = 0;
        vector<int> prefixnum(size + 1);
        for(int i = 0; i < size; i++) {
            prefixnum[i + 1] = prefixnum[i] + arr[i];
        }
        for(int i = 0; i < size; i++) {
            for(int step = 1; step + i <= size; step += 2) {
                int tmp = i + step - 1;
                sum += prefixnum[tmp + 1] - prefixnum[i];
            }
        }
        return sum;
    }
};

使用前缀和需要借助 $O(n)$ 的空间，但可以将时间复杂度降到 $O(n^2)$。

method 3

尽管利用前缀和思想解决了重复求和的问题，但是整个过程还是不断的将和重复的相加。按照给的样例 $1, 4, 2, 5, 3$ 的计算过程可以发现，这 5 个元素总是不断的重复出现，最终的结果可以写成：$1 \times 3 + 4 \times 4 + 2 \times 5 + 5 \times 4 + 3 \times 3 = 58$，整个数字序列的系数对应它们的出现次数，分别是：$3, 4, 5, 4, 3$。
如果能很容易得到这些系数，那么整个计算过程不就简单了吗？
实际上，这些系数的含义正好就是当前这个数字能组成的连续奇数个项的子序列的个数（说的有点绕）。那么仔细思考一下，对于一个数字，如果其出现在奇数个连续数字的子序列中，那么其左右两边数的个数要么同是奇数要么同是偶数，只有这样最终得到的序列的项数才是奇数。那么，假设当前数字为 $arr[i]$，其左边的数字个数为 $leftcount$，右边的数字为 $rightcount$，分类讨论一下：

同是奇数，那么 $arr[i]$ 左边的奇数个数就是 $leftodd = \lfloor \frac {leftcount + 1}{2} \rfloor$，右边奇数的个数就是 $rightodd = \lfloor \frac {rightcount + 1}{2} \rfloor$，这样由 $arr[i]$ 组成的子序列个数就是 $leftodd \times rightodd$。
同是偶数，那么 $arr[i]$ 左边的偶数个数就是 $lefteven = \lfloor \frac {leftcount}{2} \rfloor + 1$，右边偶数的个数就是 $righteven = \lfloor \frac {rightcount}{2} \rfloor + 1$，这样由 $arr[i]$ 组成的子序列个数就是 $lefteven \times righteven$。

最终由 $arr[i]$ 组成的符合条件的子序列个数就是 $leftodd \times rightodd \sum lefteven \times righteven$，这也就是它的系数。

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int size = arr.size(), sum = 0;
        for(int i = 0; i < size; i++) {
            int leftcount = i, rightcount = size - i - 1;
            int leftodd = (leftcount + 1) / 2, rightodd = (rightcount + 1) / 2;
            int lefteven = leftcount / 2 + 1, righteven = rightcount / 2 + 1;
            sum += arr[i] * (leftodd * rightodd + lefteven * righteven);
        }
        return sum;
    }
};

283. Move Zeroes

这个题是做过的题，参考：Leetcode_14 天算法入门_day3。
再做一次吧~

1672. Richest Customer Wealth

Analysis

这好像是道单纯的二维数组遍历的题目~

Code

class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int max = -1, sum;
        for(int i = 0; i < accounts.size(); i++) {
            sum = 0;
            for(int j = 0; j < accounts[i].size(); j++) {
                sum += accounts[i][j];
            }
            if(max < sum) max = sum;
        }
        return max;
    }
};

嗯，回忆一下库函数的使用吧。

class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int maxwealth = -1, sum;
        for(int i = 0; i < accounts.size(); i++) {
            maxwealth = max(maxwealth, accumulate(accounts[i].begin(), accounts[i].end(), 0));
        }
        return maxwealth;
    }
};

Summary

嗯，我发觉这里面的简单题总是有不那么简单的做法啊，就拿第一个题来说，不管是前缀和的思路还是数学的思路，都是很不错的锻炼思维的方法，得多思考下。