美文网首页
【教3妹学编程-算法题】匹配模式数组的子数组数目 I

【教3妹学编程-算法题】匹配模式数组的子数组数目 I

作者: 程序员小2 | 来源:发表于2024-02-21 20:27 被阅读0次
    瑟瑟发抖

    3妹:2哥2哥,你有没有看到上海女老师出轨男学生的瓜啊。
    2哥 : 看到 了,真的是太毁三观了!
    3妹:是啊, 老师本是教书育人的职业,明确规定不能和学生谈恋爱啊,更何况是出轨。
    2哥 : 是啊,更何况男生才16,年龄也不匹配啊。
    3妹:抛开这个事件不说,你觉得多大的年龄差才是匹配的?2哥找到你匹配的另一半了吗?
    2哥:切,又拿我单身狗开玩笑了。
    3妹:说到匹配,我今天看到一个关于“匹配”的题目,让我们一起来做下吧~

    吃瓜

    题目:

    给你一个下标从 0 开始长度为 n 的整数数组 nums ,和一个下标从 0 开始长度为 m 的整数数组 pattern ,pattern 数组只包含整数 -1 ,0 和 1 。

    大小为 m + 1 的
    子数组
    nums[i..j] 如果对于每个元素 pattern[k] 都满足以下条件,那么我们说这个子数组匹配模式数组 pattern :

    如果 pattern[k] == 1 ,那么 nums[i + k + 1] > nums[i + k]
    如果 pattern[k] == 0 ,那么 nums[i + k + 1] == nums[i + k]
    如果 pattern[k] == -1 ,那么 nums[i + k + 1] < nums[i + k]
    请你返回匹配 pattern 的 nums 子数组的 数目 。

    示例 1:

    输入: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 个子数组匹配这个模式。
    示例 2:

    输入:nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
    输出:2
    解释:这里,模式数组 [1,0,-1] 说明我们需要找的子数组中,第一个元素小于第二个元素,第二个元素等于第三个元素,第三个元素大于第四个元素。在 nums 中,子数组 [1,4,4,1] 和 [3,5,5,3] 都匹配这个模式。
    所以 nums 中总共有 2 个子数组匹配这个模式。

    提示:

    2 <= n == nums.length <= 100
    1 <= nums[i] <= 109
    1 <= m == pattern.length < n
    -1 <= pattern[i] <= 1

    思路:

    思考

    KMP,
    把 nums的相邻元素,根据题目规定的大小关系,转换成 1,0,−1,得到一个长为 n−1的数组 bbb。

    问题相当于问 b 中有多少个连续子数组等于 pattern。

    这是一个标准的字符串匹配问题(本题匹配的是数字不是字符),可以用 KMP解决。

    java代码:

    class Solution {
        public int countMatchingSubarrays(int[] nums, int[] pattern) {
            int m = pattern.length;
            int[] pi = new int[m];
            int cnt = 0;
            for (int i = 1; i < m; i++) {
                int v = pattern[i];
                while (cnt > 0 && pattern[cnt] != v) {
                    cnt = pi[cnt - 1];
                }
                if (pattern[cnt] == v) {
                    cnt++;
                }
                pi[i] = cnt;
            }
    
            int ans = 0;
            cnt = 0;
            for (int i = 1; i < nums.length; i++) {
                int v = Integer.compare(nums[i], nums[i - 1]);
                while (cnt > 0 && pattern[cnt] != v) {
                    cnt = pi[cnt - 1];
                }
                if (pattern[cnt] == v) {
                    cnt++;
                }
                if (cnt == m) {
                    ans++;
                    cnt = pi[cnt - 1];
                }
            }
            return ans;
        }
    }
    
    
    

    相关文章

      网友评论

          本文标题:【教3妹学编程-算法题】匹配模式数组的子数组数目 I

          本文链接:https://www.haomeiwen.com/subject/dskwadtx.html