leetcode/algorithms/contains_pattern.cpp at master · hanfezh/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
 * =====================================================================================
 *
 *       Filename:  contains_pattern.cpp
 *
 *    Description:  1566. Detect Pattern of Length M Repeated K or More Times
 *
 *        Version:  1.0
 *        Created:  03/01/2025 16:02:29
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  xianfeng.zhu@gmail.com
 *   Organization:
 *
 * =====================================================================================
 */

#include <algorithm>
#include <tuple>
#include <vector>

#include "gtest/gtest.h"

class Solution {
 public:
  bool containsPattern(std::vector<int>& arr, int m, int k) {
    int cnt = 1;
    auto pre = arr.begin();
    auto cur = pre + m;
    while (cur + m <= arr.end()) {
      if (std::equal(pre, pre + m, cur)) {
        cnt++;
        if (cnt >= k) {
          return true;
        }
        cur += m;
      } else {
        pre++;
        cur = pre + m;
        cnt = 1;
      }
    }
    return false;
  }
};

TEST(Solution, containsPattern) {
  std::vector<std::tuple<std::vector<int>, int, int, bool>> cases = {
      std::make_tuple(std::vector<int>{1, 2, 4, 4, 4, 4}, 1, 3, true),
      std::make_tuple(std::vector<int>{1, 2, 1, 2, 1, 1, 1, 3}, 2, 2, true),
      std::make_tuple(std::vector<int>{1, 2, 1, 2, 1, 3}, 2, 3, false),
      std::make_tuple(std::vector<int>{2, 2}, 1, 2, true),
      std::make_tuple(std::vector<int>{3, 6, 6, 6, 5, 1, 5, 2, 2, 3, 1, 5, 2,
                                       6, 1, 5, 1, 2, 6, 3, 3, 5, 3, 6, 3, 4},
                      6, 2, false),
      std::make_tuple(std::vector<int>{3, 2, 2, 1, 2, 2, 1, 1, 1, 2, 3, 2, 2}, 3, 2, true),
      std::make_tuple(std::vector<int>{2, 2, 2, 2}, 2, 3, false),
      std::make_tuple(std::vector<int>{2, 2}, 1, 2, true),
      std::make_tuple(std::vector<int>{2, 1, 1, 2, 2, 1, 2, 2, 1, 2}, 1, 3, false),
  };
  for (auto& [arr, m, k, exst] : cases) {
    EXPECT_EQ(Solution().containsPattern(arr, m, k), exst);
  }
}