问题1 求子数组的个数
def num_of_subarray(nums): # 子数组的个数
n = len(nums)
curr_num = 0 # 以当前元素结尾的子数组个数
total = 0 # 截止当前所有子数组个数
for i in range(n):
curr_num += 1
total += curr_num
return total
问题2 求出子数组的全部元素都不大于 k的子数组的个数
def num_of_subarray_lower_than_k(nums, k): # 子数组全部元素都不大于k的子数组的个数
n = len(nums)
curr_num = 0
total = 0
for i in range(n):
if nums[i] <= k:
curr_num += 1
else:
curr_num = 0
total += curr_num
return total
问题3,求出子数组最大值刚好是 k 的子数组的个数
直接借用问题2的结果，
return num_of_subarray_lower_than_k(nums, k) - num_of_subarray_lower_than_k(nums, k-1)
问题4 leetcode795 区间子数组个数
给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。
生成的测试用例保证结果符合 32-bit 整数范围。
示例 1：
输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]
示例 2：
输入：nums = [2,9,2,5,6], left = 2, right = 8
输出：7
直接借用问题2的结果，
return num_of_subarray_lower_than_k(nums, right) - num_of_subarray_lower_than_k(nums, left-1)
leetcode 467 环绕字符串中唯一的子字符串
把字符串 s 看作 “abcdefghijklmnopqrstuvwxyz” 26个英文字母的无限环绕字符串，所以 s 看起来是这样的：
“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…” 。
现在给定另一个字符串 p 。返回 s 中不同的p的非空子串的数量 。
示例 1：
输入：p = “a”
输出：1
解释：字符串 s 中只有 p 的一个 “a” 子字符。
示例 2：
输入：p = “cac”
输出：2
解释：字符串 s 中只有 p 的两个子串 (“a”, “c”) 。
示例 3：
输入：p = “zab”
输出：6
解释：在字符串 s 中有 p 的六个子串 (“z”, “a”, “b”, “za”, “ab”, “zab”) 。
class Solution:
def findSubstringInWraproundString(self, p: str) -> int:
n=len(p)
curr_num = 1# 以p[i]为结尾的子字符串的个数，另外循环从1开始，所以这里curr_num=1
res=0
char_count={}
char_count = {p[0]:1}
#每个字符和以这个字符结尾的子字符串最长长度
#以某个字符结尾的子字符串的最长长度 包含了它的所有种类字符串
#这是为了避免已经出现的子字符串重复计数比如cac 只有两个子串('a','c')而不是('c','a','c')
for i in range(1,n):#由于i-1，所以这里只能从1开始
if ord(p[i])-ord(p[i-1])==1 or ord(p[i])-ord(p[i-1])==-25:
curr_num+=1
else:
curr_num=1
char_count[p[i]] = max(char_count.get(p[i],0), curr_num)
res = sum(char_count.values())
return res
|