当前位置:网站首页>LeetCode 1566. Repeat the pattern with length m at least k times
LeetCode 1566. Repeat the pattern with length m at least k times
2022-07-06 16:43:00 【Daylight629】
1566. Repeat at least K And the length is M The pattern of
Here's an array of positive integers arr
, Please find a length of m
And repeat at least... In the array k
Second mode .
Pattern Is a subarray of one or more values ( Continuous subsequences ), continuity Repeat many times, but No overlap . The pattern is defined by its length and number of repetitions .
If there are at least duplicates in the array k
And the length is m
The pattern of , Then return to true
, Otherwise return to false
.
Example 1:
Input :arr = [1,2,4,4,4,4], m = 1, k = 3
Output :true
explain : Pattern (4) The length of is 1 , And repeat continuously 4 Time . Be careful , Patterns can be repeated k Times or more , But not less than k Time .
Example 2:
Input :arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output :true
explain : Pattern (1,2) The length is 2 , And repeat continuously 2 Time . Another pattern that fits the meaning of the question is (2,1) , Same repetition 2 Time .
Example 3:
Input :arr = [1,2,1,2,1,3], m = 2, k = 3
Output :false
explain : Pattern (1,2) The length is 2 , But only repeat continuously 2 Time . There is no length of 2 And at least repeat 3 Second mode .
Example 4:
Input :arr = [1,2,3,1,2], m = 2, k = 2
Output :false
explain : Pattern (1,2) appear 2 Times but not continuously , So it can't be counted as continuous repetition 2 Time .
Example 5:
Input :arr = [2,2,2,2], m = 2, k = 3
Output :false
explain : The length is 2 The only mode is (2,2) , But only repeat continuously 2 Time . Be careful , The number of overlapped repetitions cannot be calculated .
Tips :
2 <= arr.length <= 100
1 <= arr[i] <= 100
1 <= m <= 100
2 <= k <= 100
Two 、 Method 1
enumeration
class Solution {
public boolean containsPattern(int[] arr, int m, int k) {
int n = arr.length;
for (int l = 0; l <= n - m * k; ++l) {
int offset;
for (offset = 0; offset < m * k; ++offset) {
if (arr[l + offset] != arr[l + offset % m]) {
break;
}
}
if (offset == m * k) {
return true;
}
}
return false;
}
}
Complexity analysis
- Time complexity :O(n×m×k). Outermost cycle l The number of values is n−m×k, Inner circulation offset The number of values is m×k, Therefore, the asymptotic time complexity is O((n−m×k)×m×k)=O(n×m×k).
- Spatial complexity :O(1).
边栏推荐
- Codeforces Round #802(Div. 2)A~D
- 第三章 MapReduce框架原理
- Anaconda下安装Jupyter notebook
- Bisphenol based CE Resin Industry Research Report - market status analysis and development prospect forecast
- Raspberry pie 4B installation opencv3.4.0
- Research Report on hearing health care equipment industry - market status analysis and development prospect prediction
- Li Kou: the 81st biweekly match
- 软通乐学-js求字符串中字符串当中那个字符出现的次数多 -冯浩的博客
- LeetCode 1560. The sector with the most passes on the circular track
- 图像处理一百题(11-20)
猜你喜欢
One hundred questions of image processing (1-10)
去掉input聚焦时的边框
Local visualization tools are connected to redis of Alibaba cloud CentOS server
QT implementation window gradually disappears qpropertyanimation+ progress bar
Story of [Kun Jintong]: talk about Chinese character coding and common character sets
Tree of life (tree DP)
第6章 DataNode
SQL quick start
解决Intel12代酷睿CPU单线程调度问题(二)
Solve the problem of intel12 generation core CPU [small core full, large core onlookers] (win11)
随机推荐
Chapter 1 overview of MapReduce
Soft music -js find the number of times that character appears in the string - Feng Hao's blog
(lightoj - 1354) IP checking (Analog)
Codeforces Round #771 (Div. 2)
Story of [Kun Jintong]: talk about Chinese character coding and common character sets
Date plus 1 day
Bidirectional linked list - all operations
Classic application of stack -- bracket matching problem
CMake速成
Pull branch failed, fatal: 'origin/xxx' is not a commit and a branch 'xxx' cannot be created from it
Chapter 6 rebalance details
新手必会的静态站点生成器——Gridsome
Installation and configuration of MariaDB
useEffect,函數組件掛載和卸載時觸發
Double specific tyrosine phosphorylation regulated kinase 1A Industry Research Report - market status analysis and development prospect prediction
LeetCode 1447. Simplest fraction
Submit several problem records of spark application (sparklauncher with cluster deploy mode)
QT implementation fillet window
解决Intel12代酷睿CPU单线程只给小核运行的问题
Research Report on market supply and demand and strategy of Chinese table lamp industry