Posts tagged as “easy”

花花酱 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)

花花酱 LeetCode 1539. Kth Missing Positive Number

By zxi on August 9, 2020

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the k^th positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5^th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2^nd missing positive integer is 6.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Solution 1: HashTable

Store all the elements into a hashtable, and check from 1 to max(arr).

Time complexity: O(max(arr)) ~ O(1000)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int findKthPositive(vector<int>& arr, int k) {

unordered_set<int> s(begin(arr), end(arr));

for (int i = 1; i <= arr.back(); ++i) {

if (!s.count(i)) --k;

if (k == 0) return i;

}

return arr.back() + k;

}

};

Solution 2: Binary Search

We can find the smallest index l using binary search, s.t.
arr[l] – l + 1 >= k
which means we missed at least k numbers at index l.
And the answer will be l + k.

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

C++

// Author: Huahua

class Solution {

public:

int findKthPositive(vector<int>& arr, int k) {

int l = 0;

int r = arr.size();

while (l < r) {

int m = l + (r - l) / 2;

if (arr[m] - (m + 1) >= k)

r = m;

else

l = m + 1;

}

return l + k;

}

};

Java

class Solution {

public int findKthPositive(int[] arr, int k) {

int l = 0;

int r = arr.length;

while (l < r) {

int m = l + (r - l) / 2;

if (arr[m] - (m + 1) >= k)

r = m;

else

l = m + 1;

}

return l + k;

}

Python3

class Solution:

def findKthPositive(self, arr: List[int], k: int) -> int:

l, r = 0, len(arr)

while l < r:

m = l + (r - l) // 2

if arr[m] - (m + 1) >= k:

r = m

else:

l = m + 1

return l + k

花花酱 LeetCode 1534. Count Good Triplets

By zxi on August 1, 2020

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c

Where |x| denotes the absolute value of x.

Return the number of good triplets.

Example 1:

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4
Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].

Example 2:

Input: arr = [1,1,2,2,3], a = 0, b = 0, c = 1
Output: 0
Explanation: No triplet satisfies all conditions.

Constraints:

3 <= arr.length <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countGoodTriplets(vector<int>& arr, int a, int b, int c) {

const int n = arr.size();

int ans = 0;

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

for (int j = i + 1; j < n; ++j)

for (int k = j + 1; k < n; ++k)

if (abs(arr[i] - arr[j]) <= a &&

abs(arr[j] - arr[k]) <= b &&

abs(arr[i] - arr[k]) <= c)

++ans;

return ans;

}

};

花花酱 1528. Shuffle String

By zxi on July 25, 2020

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the i^th position moves to indices[i] in the shuffled string.

Return the shuffled string.

Example 1:

Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.

Example 2:

Input: s = "abc", indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.

Example 3:

Input: s = "aiohn", indices = [3,1,4,2,0]
Output: "nihao"

Example 4:

Input: s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
Output: "arigatou"

Example 5:

Input: s = "art", indices = [1,0,2]
Output: "rat"

Constraints:

s.length == indices.length == n
1 <= n <= 100
s contains only lower-case English letters.
0 <= indices[i] < n
All values of indices are unique (i.e. indices is a permutation of the integers from 0 to n - 1).

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string restoreString(string s, vector<int>& indices) {

string ans(s);

for (int i = 0; i < indices.size(); ++i)

ans[indices[i]] = s[i];

return ans;

}

};

Java

// Author: Huahua

class Solution {

public String restoreString(String s, int[] indices) {

char[] ans = new char[s.length()];

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

ans[indices[i]] = s.charAt(i);

return new String(ans);

}

Pyhton3

class Solution:

def restoreString(self, s: str, indices: List[int]) -> str:

ans = [None] * len(s)

for i, idx in enumerate(indices):

ans[idx] = s[i]

return ''.join(ans)