LeetCode笔记：Biweekly Contest 31 比赛记录

1. 题目一

首先，给出题目一的试题链接如下：

• Count Odd Numbers in an Interval Range

1. 解题思路

这题作为一道easy题目，本身不会有太大的难度，无非就是统计一下闭区间中的奇数个数而已，因此，我们只需要按照如下规则实现算法即可：

1. 如果闭区间包含2N个数字，则奇数的数目为N；
2. 如果闭区间包含2N+1个数字，则分情况讨论：
   1. 如果第一个数字为奇数，则奇数数字数目为N+1；
   2. 反之，若第一个数字为偶数，则奇数数字数目为N；

2. 代码实现

给出代码实现如下：

int countOdds(int low, int high){
    if((high - low + 1) % 2 == 0){
        return (high - low + 1) / 2;
    }
    else if(low % 2 == 1){
        return (high - low + 1) / 2 + 1;
    }
    else{
        return (high - low + 1) / 2;
    }
}

上述代码实现提交之后测评得到：耗时0ms，占用内存5.1MB。

2. 题目二

题目二的试题链接如下：

• Number of Sub-arrays With Odd Sum

1. 解题思路

坦率地说，这题一看就是基于奇偶性的动态规划题目，解法一定是先求解每个元素的前面所有元素的累计值，然后通过分析这些累计值的奇偶性得到最终的答案。

可惜在第一时间做这题的时候一下子没能想清楚后面这个对应关系，想着反正就是一道medium的题目，暴力求解估计也能搞定，反正也就O(N^2)的时间复杂度，应该也不至于超时。

然后，然后就没有然后了。。。

脸好疼。。。

下面，我们给出正确的解法思路如下：

1. 给出list中每一个元素前面所有的元素总和，得到一个cumsum列表；
2. 对上述cumsum列表，分析其中每一个元素的前方所有元素的奇数个数与偶数个数；
3. 对于每一个元素，我们分情况讨论：
   1. 如果到该元素的累计总和为奇数，则以该元素为终点的合法子串数目为cumsum列表中其前方的偶数元素个数；
   2. 如果到该元素的累计总和为偶数，则以该元素为终点的合法子串数目为cumsum列表中其前方的奇数元素个数；

这一解法的时间复杂度为O(N)。

当然，上述算法依然可以在细节上进行更进一步的优化，比如：

1. 在第一步的求和中，事实上我们只需要知道其奇偶性就行了，没有必要真的求和；
2. 这三个步骤可以在同一个for循环中一起实现，因为他们之间没有前后的交错依赖关系；

但是，为了使得代码尽可能地可读，这里，我们不再进行后续的优化。

2. 代码实现

给出上述思路下的代码实现如下：

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = 1000000007
        
        cumsum = [0]
        for n in arr:
            cumsum.append(cumsum[-1] + n)
        
        n = len(arr)
        odd = [0] * (n+1)
        even = [0] * (n+1)
        for i in range(n):
            if cumsum[i] % 2 == 0:
                even[i+1] = even[i] + 1
                odd[i+1] = odd[i]
            else:
                even[i+1] = even[i]
                odd[i+1] = odd[i] + 1

        ans = 0
        for i in range(1, n+1):
            if cumsum[i] % 2 == 0:
                ans += odd[i]
            else:
                ans += even[i]
        return ans % MOD

提交上述代码之后得到评测结果：耗时1572ms，占用内存24MB。

而当前提交的最优实现的耗时为1204ms，大致看了一下它的代码，思路和我们差不多，但是比我们做了更多细节上的优化。

3. 题目三

题目三的试题链接如下：

• Number of Good Ways to Split a String

1. 解题思路

这道题就没有什么技巧可言，按照题目的意思求出以每个元素为切分点时前方和后方的字符集合数量即可。

2. 代码实现

给出代码实现如下：

class Solution:
    def numSplits(self, s: str) -> int:
        n = len(s)

        preset = set()
        prenum = [0] * n
        for i in range(n):
            preset.add(s[i])
            prenum[i] = len(preset)

        postset = set()
        postnum = [0] * n
        for i in range(n-1, -1, -1):
            postset.add(s[i])
            postnum[i] = len(postset)

        ans = 0
        for i in range(n-1):
            if prenum[i] == postnum[i+1]:
                ans += 1
        return ans

提交代码之后得到评测结果如下：耗时176ms，占用内存15.8MB。

而当前的最优代码耗时164ms，并没有太过显著的差异。

4. 题目四

给出题目四的试题链接如下：

• Minimum Number of Increments on Subarrays to Form a Target Array

1. 解题思路

这道题是比赛的时候把我坑的最惨的一题，第一眼看过去感觉只要按照题目的思路做就完事了，做完之后发现超时，然后想着有没有优化的空间，然后一看代码，诶，还真有，然后就优化，还优化了两次，结果两次优化之后依然超时，直到整个比赛结束还在努力地优化代码的细节，完全没觉得哪里有问题。

然后，到优化到实在优化不动了之后，去看了一下为啥头几名的大佬做这题的时间居然只有几分钟，然后发现，他们的代码居然他喵的只有不到10行，而且看了之后就是秒懂的程度，顿时整个人都是崩溃的！！！

总而言之，言而总之，这道题，千万千万千万不要按照题目的讲解方式去暴力的一层一层去处理，那样的时间复杂度是在O(N×H)这个量级（N为列的数目，H为最高的列高度），虽然我们可以通过通过一些操作来大量的进行剪枝操作，但是感觉应该是不可能达到O(N)的时间复杂度的。

下面，废话不多说，直接给出大佬们的解法思路如下：

1. 考察第一列，假设这一列高度为n，则无论如何我们都得通过n次操作来达到这一高度；
2. 考察其后方的每一列的高度：
   1. 如果这一列高度低于前一列的高度，那么说明当前一列已经被消除时，这一列的高度一定是可以通过停在某一次中间过程中达到的；
   2. 如果这一列的高度高于前一列的高度，那么假设两者的高度差为m，则我们在通过一系列操作达到了上一列的高度之后，还需要m次额外的操作来达到这一列的高度，即总的操作次数需要加上m。

通过这种解题思路，我们可以直接将时间复杂度降低至O(N)，而且其代码实现也异常的简单，真的是被大佬们打击的体无完肤。

2. 代码实现

下面，我们给出上述解法的代码实现，嗯，只有区区几行代码而已。。。

int max(int x, int y){
    return x > y ? x : y;
}

int minNumberOperations(int* target, int targetSize){
    int ans = target[0];
    for(int i=0; i<targetSize-1; ++i){
        ans += max(target[i+1] - target[i], 0);
    }
    return ans;
}

提交后得到评测数据如下：耗时160ms，占用内存12.8MB。