【Leetcode Daily】3152特殊数组II

发表于2025-07-04|更新于2025-07-04|力扣日常 | LeetcodeDaily

|总字数:326|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个整型数组，和一个二维整型数组，将二维数组的每个元素视为区间，要求每个区间内的数组，是否每一对相邻元素都是奇偶性不同的数字。

思路分享

基本前缀和的思路，可以参考【Leetcode Daily】303区域和检索-数组不可变
虽然明知是前缀和，但如何把题目抽象为前缀和能解答的形式还是需要多多学习的。
比如本题，可以将相邻数字奇偶性是否相同直接化为布尔值存储，如果相同则记 1，不同则记 0，然后求前缀和。这样子，如果区间两侧的值相同，说明区间中的奇偶性都是不同的。
值得说道的是，在 Python 中（3.10以上），可以通过 pairwise 函数来遍历数组内的每个数对。

https://leetcode.cn/problems/special-array-ii/solutions/2782830/qian-zhui-he-wei-yun-suan-pythonjavacgo-3pvya/

代码解答（强烈建议自行解答后再看）

参考题解

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        s = list(accumulate((x%2==y%2 for x, y in pairwise(nums)), initial=0))
        return [s[q[0]]==s[q[1]] for q in queries]

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/9b3f7b4e.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

Algorithm 前缀和

相关推荐

【Leetcode Daily】1534统计好三元组

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组，要求统计其中所有满足要求三元组的数量。该要求是，两两之差，满足题目的三个数字。思路分享首先就是暴力解法，O(n^3)，不过陆爻齐在普通的暴力上做了一点点剪枝，但终究还是暴力。想要比较好的完成本题，就需要学习前缀和，总体的思路是固定三元组中的两个，通过要求来求得剩下一个值的范围，将该范围在前缀和中搜寻，符合则找到合适的三元组。 https://leetcode.cn/problems/count-good-triplets/?envType=daily-question&envId=2025-04-14 代码解答（强烈建议自行解答后再看）陆爻齐小改良的暴力解法 12345678910111213141516171819class Solution {public: int countGoodTriplets(vector<int>& arr, int a, int b, int c) { int size =...

【Leetcode Daily】2389和有限的最长子序列

题目浅析想查看原题可以点击题目链接。简单地说，就是求一个数组的每个值，与另一个数组子序列和的关系，在子序列和不超过这个值的前提下，求最长子序列的长度。思路分享前缀和+二分 https://leetcode.cn/problems/longest-subsequence-with-limited-sum/solutions/1781111/fei-bao-li-zuo-fa-qian-zhui-he-er-fen-by-ny4m/ 为了使得子序列长度越长，要尽可能选取数值较小的元素。所以先排序，然后用前缀和得到各个子序列的和。具体实现中，前缀和用 numeric 库的 partial_sum 实现，而二分就直接用 ranges 库的 upper_bound 函数，之所以不用 lower_bound 是因为本题要求“不超过”，而非小于。当然，用加一值的lower_cound也行。代码解答（强烈建议自行解答后再看）参考题解 123456789101112class Solution {public: ...

【Leetcode Daily】303区域和检索-数组不可变

题目浅析想查看原题可以点击题目链接。简单地说，就是要求实现一个类，这个类能够返回数组中任意一个闭区间的数值和。思路分享这是前缀和的模板题，所谓前缀和的计算，正如其名，就是把数组从左往右一个个数值累加并记录。 https://leetcode.cn/problems/range-sum-query-immutable/solutions/2693498/qian-zhui-he-ji-qi-kuo-zhan-fu-ti-dan-py-vaar/ 实现方式很简单，但是有一点需要特别注意，就是留出第一位的 0.如果采用第一位就放第一位的数值，那么就需要特别处理闭区间左部为 0 的情况，但是如果第一位置零，第二位放第一个数值，第三位放前两个数值，这样子下去，取区间和就只要调整一下下标加一即可。代码解答（强烈建议自行解答后再看）参考题解 12345678910111213141516class NumArray: def __init__(self, nums: List[int]): s = [0] * (len(nums)+1) ...

【Leetcode Daily】3427变长子数组求和

题目浅析想查看原题可以点击题目链接。简单地说，就是给了一个整型数组，对其中的每一个元素，都要根据一个要求创建一个子数组，而题目要求则要返回这些所有子数组的数值和。思路分享前缀和的思路，可以参考【Leetcode Daily】303区域和检索-数组不可变由于题目子数组和求得的方式，可以通过前缀和方便完成，所以采用这种方法。重要的是，终于搞清楚了 Python 中 accumulate 函数到底是怎么形成的。对于 [1, 2, 3] 这样的列表，accumulate([1, 2, 3]) 会产生 [1, 3, 6]，也就是前缀和，但是通过增加参数 initial 的值可以改变初始前缀和值（该参数默认为 None），比如 accumulate([1, 2, 3], initial=0)，会在初始的地方增加一个 0，变成 [0, 1, 3, 6]；accumulate([1, 2, 3], initial=1)，就是 [1, 2, 4, 7]。代码解答（强烈建议自行解答后再看）参考题解 123456789class...

【Leetcode Daily】2559统计范围内的元音字符串数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个字符串和一个二维整数数组，二维数组内每个元素有两个数值，代表一个区间，要求返回每个区间内开头和结尾都是元音字母的数量。思路分享基本前缀和的思路，可以参考【Leetcode Daily】303区域和检索-数组不可变除了题目，几乎与昨日的题目一模一样（【Leetcode Daily】3427变长子数组求和），故不做赘述。只补充一点感受，还真是有点不习惯这个 accumulate 函数，还是得慢慢适应这种有各种方便函数调用的 Python ~（蛇堕*n） https://leetcode.cn/problems/count-vowel-strings-in-ranges/solutions/2093978/suan-fa-xiao-ke-tang-qian-zhui-he-by-end-n0mx/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415161718class Solution: def vowelStrings(self, words:...

【Leetcode Daily】1052爱生气的书店老板

题目浅析想查看原题可以点击题目链接。简单地说，就是给两个整型数组，以及一个整数 minutes，按某个要求（具体看原题，难以简化），求一个数组在另一个数组和 minutes 约束下的求的最大值。思路分享陆爻齐的思路是计算窗口内（也就是冷静的分钟）不满意生气离开的最大值，加上不生气的心情值，再减去所有生气离开的数值得出答案，但由于思想复杂了点，所以略微修改模板结构，也就是下面陆爻齐的答案。参照灵茶山艾府，其实只要区分开两部分相加即可，然后直接参照模板。这两部分，一个是不生气的值，一个是生气下的值，取生气下最大值即可。这样就不用像上面一样多一次运算。 https://leetcode.cn/problems/grumpy-bookstore-owner/solutions/2751888/ding-chang-hua-dong-chuang-kou-fu-ti-dan-rch7/ 代码解答（强烈建议自行解答后再看）陆爻齐的解法 12345678910111213141516171819202122232425class Solution...

数据加载中