2024-07-13:用 go 语言,给定一个从 0 开始的长度为 n 的整数数组 nums 和一个从 0 开始的长度为 m 的整数数组 pattern,其中 pattern 数组仅包含整数 -1、0 和 1。 一个子数组 nums[i.
2024-07-13:用 go 语言,给定一个从 0 开始的长度为 n 的整数数组 nums 和一个从 0 开始的长度为 m 的整数数组 pattern,其中 pattern 数组仅包含整数-1、0 和 1。
一个子数组 nums[i..j]的大小为 m+1,如果满足以下条件,则我们称该子数组与模式数组 pattern 匹配:
1.若 pattern[k]为 1,则 nums[i+k+1] > nums[i+k];
2.若 pattern[k]为 0,则 nums[i+k+1] == nums[i+k];
3.若 pattern[k]为-1,则 nums[i+k+1] < nums[i+k]。
需要计算匹配模式数组 pattern 的 nums 子数组的数量并返回。
输入:nums = [1,2,3,4,5,6], pattern = [1,1]。
输出:4。
解释:模式 [1,1] 说明我们要找的子数组是长度为 3 且严格上升的。在数组 nums 中,子数组 [1,2,3] ,[2,3,4] ,[3,4,5] 和 [4,5,6] 都匹配这个模式。
所以 nums 中总共有 4 个子数组匹配这个模式。
答案 2024-07-13:
题目来自 leetcode3036。
大体步骤如下:
1.在主函数 main 中,定义了一个 nums 数组为[1,2,3,4,5,6]和一个模式数组 pattern 为[1,1]。然后调用 countMatchingSubarrays 函数,并输出结果。
2.countMatchingSubarrays 函数的作用是计算匹配模式数组 pattern 的 nums 子数组的数量。它首先将模式数组 pattern 的长度赋值给 m,然后在模式数组末尾添加一个值为 2 的元素。接着遍历 nums 数组,将每相邻两个数的大小关系转换为-1、0 或 1,并存储在 pattern 数组中。
3.根据 Z 算法,创建一个数组 z 用于存储匹配长度。然后利用两个指针 l 和 r,以及 i 遍历模式数组,并根据当前位置 i 和匹配长度 z[i]更新 l、r 和 z[i]的值,直到找到所有的匹配长度。
4.最后,在 z 数组中,从第 m+1 个值开始遍历,如果匹配长度等于模式数组长度 m,则将计数器 ans 加一。
综上所述,总的时间复杂度为 O(n)(n 为 nums 数组的长度),总的额外空间复杂度为 O(n)。
Go 完整代码如下:
![](https://static001.geekbang.org/infoq/fd/fd7374fe3ddc5c6ac55753fb7fe49f6d.png)
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/ca0b31a2cfb434f345fe7499f】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论