Posts tagged as “easy”

花花酱 LeetCode 1566. Detect Pattern of Length M Repeated K or More Times

By zxi on August 29, 2020

Given an array of positive integers arr, find a pattern of length m that is repeated k or more times.

A pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.

Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.

Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.

Example 4:

Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.

Example 5:

Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.

Constraints:

2 <= arr.length <= 100
1 <= arr[i] <= 100
1 <= m <= 100
2 <= k <= 100

Solution 1: Brute Force

Time complexity: O(nmk)
Space complexity: O(1)

C++

class Solution {

public:

bool containsPattern(vector<int>& arr, int m, int k) {

const int n = arr.size();

for (int i = 0; i + m * k <= n; ++i) {

bool valid = true;

for (int j = 1; j < k && valid; ++j)

for (int p = 0; p < m && valid; ++p)

if (arr[i + j * m + p] != arr[i + p])

valid = false;

if (valid) return true;

}

return false;

}

};

Solution 2: Shift and count

Since we need k consecutive subarrays, we can compare arr[i] with arr[i + m], if they are the same, increase the counter, otherwise reset the counter. If the counter reaches (k – 1) * m, it means we found k consecutive subarrays of length m.

ex1: arr = [1,2,4,4,4,4], m = 1, k = 3
i arr[i], arr[i + m] counter
0 1. 2. 0
0 2. 4. 0
0 4. 4. 1
0 4. 4. 2. <– found

ex2: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
i arr[i], arr[i + m] counter
0 1. 1. 1
0 2. 2. 2 <– found

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

bool containsPattern(vector<int>& arr, int m, int k) {

const int n = arr.size();

int count = 0;

for (int i = 0; i + m < n; ++i) {

if (arr[i] == arr[i + m]) {

if (++count == (k - 1) * m) return true;

} else {

count = 0;

}

return false;

}

};

花花酱 LeetCode 1560. Most Visited Sector in a Circular Track

By zxi on August 23, 2020

Given an integer n and an integer array rounds. We have a circular track which consists of n sectors labeled from 1 to n. A marathon will be held on this track, the marathon consists of m rounds. The i^th round starts at sector rounds[i - 1] and ends at sector rounds[i]. For example, round 1 starts at sector rounds[0] and ends at sector rounds[1]

Return an array of the most visited sectors sorted in ascending order.

Notice that you circulate the track in ascending order of sector numbers in the counter-clockwise direction (See the first example).

Example 1:

Input: n = 4, rounds = [1,3,1,2]
Output: [1,2]
Explanation: The marathon starts at sector 1. The order of the visited sectors is as follows:
1 --> 2 --> 3 (end of round 1) --> 4 --> 1 (end of round 2) --> 2 (end of round 3 and the marathon)
We can see that both sectors 1 and 2 are visited twice and they are the most visited sectors. Sectors 3 and 4 are visited only once.

Example 2:

Input: n = 2, rounds = [2,1,2,1,2,1,2,1,2]
Output: [2]

Example 3:

Input: n = 7, rounds = [1,3,5,7]
Output: [1,2,3,4,5,6,7]

Constraints:

2 <= n <= 100
1 <= m <= 100
rounds.length == m + 1
1 <= rounds[i] <= n
rounds[i] != rounds[i + 1] for 0 <= i < m

Solution: Simulation

Time complexity: O(m*n)
Space complexity: O(n)

C++

class Solution {

public:

vector<int> mostVisited(int n, vector<int>& rounds) {

vector<int> counts(n);

counts[rounds[0] - 1] = 1;

for (int i = 1; i < rounds.size(); ++i)

for (int s = rounds[i - 1]; ; ++s) {

++counts[s %= n];

if (s == rounds[i] - 1) break;

}

const int max_count = *max_element(begin(counts), end(counts));

vector<int> ans;

for (int i = 0; i < n; ++i)

if (counts[i] == max_count) ans.push_back(i + 1);

return ans;

}

};

花花酱 LeetCode 1556. Thousand Separator

By zxi on August 22, 2020

Given an integer n, add a dot (“.”) as the thousands separator and return it in string format.

Example 1:

Input: n = 987
Output: "987"

Example 2:

Input: n = 1234
Output: "1.234"

Example 3:

Input: n = 123456789
Output: "123.456.789"

Example 4:

Input: n = 0
Output: "0"

Constraints:

0 <= n < 2^31

Solution: Digit by digit

Time complexity: O(log^2(n)) -> O(logn)
Space complexity: O(log(n))

C++

class Solution {

public:

string thousandSeparator(int n) {

string ans;

int count = 0;

do {

if (count++ % 3 == 0 && ans.size())

ans = "." + ans;

ans = to_string(n % 10) + ans;

n /= 10;

} while (n);

return ans;

}

};

花花酱 LeetCode 1550. Three Consecutive Odds

By zxi on August 15, 2020

Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.

Example 1:

Input: arr = [2,6,4,1]
Output: false
Explanation: There are no three consecutive odds.

Example 2:

Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] are three consecutive odds.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000

Solution: Counting

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

bool threeConsecutiveOdds(vector<int>& arr) {

int count = 0;

for (int x : arr) {

if (x & 1) {

if (++count == 3) return true;

} else {

count = 0;

}

return false;

}

};

花花酱 LeetCode 1544. Make The String Great

By zxi on August 10, 2020

Given a string s of lower and upper case English letters.

A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:

0 <= i <= s.length - 2
s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

Example 1:

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".

Example 2:

Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

Example 3:

Input: s = "s"
Output: "s"

Constraints:

1 <= s.length <= 100
s contains only lower and upper case English letters.

Solution: Stack

Iterator over the string, compare current char with top of the stack, if they are a bad pair, pop the stack (remove both of them). Otherwise, push the current char onto the stack.

input: “abBAcC”
“a”
“ab”
“abB” -> “a”
“aA” -> “”
“c”
“cC” -> “”
ans = “”

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

string makeGood(string s) {

string ans;

for (char c : s) {

if (ans.length() &&

abs(ans.back() - c) == abs('a' - 'A'))

ans.pop_back();

else

ans.push_back(c);

}

return ans;

}

};

Java

class Solution {

public String makeGood(String s) {

var sb = new StringBuilder();

for (int i = 0; i < s.length(); ++i) {

int l = sb.length();

if (l > 0 && Math.abs(sb.charAt(l - 1) - s.charAt(i)) == 32) {

sb.setLength(l - 1); // remove last char

} else {

sb.append(s.charAt(i));

}

return sb.toString();

}

Python3

class Solution:

def makeGood(self, s: str) -> str:

ans = []

for c in s:

if ans and abs(ord(ans[-1]) - ord(c)) == 32:

ans.pop()

else:

ans.append(c)

return "".join(ans)