smj2302_79682652头像
解决leetcode第4109题统计有效后缀排序的数量II封面图

解决leetcode第4109题统计有效后缀排序的数量II

4109.统计有效后缀排序的数量II

难度:困难

问题描述:

给你两个整数数组nums和target,长度分别为n和m,其中n<=m。

对于每个下标i,考虑将原数组的后缀nums[i..n-1]按非递增顺序排序。

返回一个长度为m-n+1的整数数组ans,其中ans[k]表示使排序后的数组等于target[k..k+n-1]的下标i的数量。

子数组是数组中一个连续的非空元素序列。

数组的后缀是从任意下标开始并延伸至数组末尾的子数组。

示例1:

输入:nums=[2,2,3],target=[2,2,3,2,1,3,2,2]

输出:[1,1,0,0,0,1]

解释:

分别对从下标0、1和2开始的后缀排序,会依次得到[3,2,2]、[2,3,2]和[2,2,3]。

k=0:选择i=2可以得到[2,2,3]。

k=1:选择i=1可以得到[2,3,2]。

k=2,3,4:均无法得到对应的子数组。

k=5:选择i=0可以得到[3,2,2]。

因此,答案为[1,1,0,0,0,1]。

示例2:

输入:nums=[5,6,5],target=[5,6,5,5,6,5]

输出:[2,1,0,2]

解释:

对从下标0开始的后缀排序,会得到[6,5,5];对从下标1或2开始的后缀排序,都会得到[5,6,5]。

k=0:选择i=1或i=2可以得到[5,6,5]。

k=1:选择i=0可以得到[6,5,5]。

k=2:无法得到[5,5,6]。

k=3:选择i=1或i=2可以得到[5,6,5]。

因此,答案为[2,1,0,2]。

提示:

n==nums.length

m==target.length

1<=n<=m<=10**5

1<=nums[i],target[i]<=10**5

问题分析:

解决分为下列步骤,一是对nums的每一个索引i将其后缀按非递增排序之后得到的序列求出并返回,这通过子函数 get_non_increasing_order_postfix_from_every_index(nums)实现,二是对target中的每一个k截取子数组,统计这个子数组在按后缀排序得到的序列中出现的个数,存入列表并返回,这通过子函数def get_number_of_valid_suffix_sorts(t,target)实现,最后在主程序中输出这个列表即是问题的解。

程序如下:

#对nums的每一个i将后缀按非递增排序之后得到的序列求出并返回
def get_non_increasing_order_postfix_from_every_index(nums):
    n=len(nums)
    t=[]
    for i in range(n):
        a=nums[:i]
        b=nums[i:]
        b.sort(reverse=True)
        t.append(a+b)
    return t

#统计有效后缀排序的数量列表并返回
def get_number_of_valid_suffix_sorts(t,target):
    n=len(t[0])
    ans=[]
    m=len(target)
    for k in range(m-n+1):
        a=target[k:k+n]
        c=t.count(a)
        ans.append(c)
    return ans

#主程序
nums=eval(input('pls input nums='))
target=eval(input('pls input target='))
t=get_non_increasing_order_postfix_from_every_index(nums)
a=get_number_of_valid_suffix_sorts(t,target)
print(a)

运行实例一

pls input nums=[2,3,2,4]

pls input target=[2,3,2,4,3,2,4,1]

[1, 0, 1, 0, 0]

运行实例二

pls input nums=[2,3,4]

pls input target=[4,3,2,3,4,2,4,3]

[1, 0, 1, 0, 0, 1]

转载自 CSDN-专业IT技术社区

原文链接:https://blog.csdn.net/2302_79682652/article/details/170435847

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数:0
关注数:0
粉丝:0
文章:0
关注标签:0
加入于:--