Huahua’s Tech Road

花花酱 LeetCode 1401. Circle and Rectangle Overlapping

By zxi on April 4, 2020

Given a circle represented as (radius, x_center, y_center) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.

Return True if the circle and rectangle are overlapped otherwise return False.

In other words, check if there are any point (xi, yi) such that belongs to the circle and the rectangle at the same time.

Example 1:

Input: radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0)

Example 2:

Input: radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true

Example 3:

Input: radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
Output: true

Example 4:

Input: radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
Output: false

Constraints:

1 <= radius <= 2000
-10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
x1 < x2
y1 < y2

Solution: Geometry

Find the shortest distance from the center to the rectangle, return dist <= radius.

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

C++

// Author: Huahua

class Solution {

public:

bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {

int dx = x_center - max(x1, min(x2, x_center));

int dy = y_center - max(y1, min(y2, y_center));

return dx * dx + dy * dy <= radius * radius;

}

};

花花酱 LeetCode 1400. Construct K Palindrome Strings

By zxi on April 4, 2020

Given a string s and an integer k. You should construct k non-empty palindrome strings using all the characters in s.

Return True if you can use all the characters in s to construct k palindrome strings or False otherwise.

Example 1:

Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two palindromes using all characters in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"

Example 2:

Input: s = "leetcode", k = 3
Output: false
Explanation: It is impossible to construct 3 palindromes using all the characters of s.

Example 3:

Input: s = "true", k = 4
Output: true
Explanation: The only possible solution is to put each character in a separate string.

Example 4:

Input: s = "yzyzyzyzyzyzyzy", k = 2
Output: true
Explanation: Simply you can put all z's in one string and all y's in the other string. Both strings will be palindrome.

Example 5:

Input: s = "cr", k = 7
Output: false
Explanation: We don't have enough characters in s to construct 7 palindromes.

Constraints:

1 <= s.length <= 10^5
All characters in s are lower-case English letters.
1 <= k <= 10^5

Solution: HashTable

Compute the frequency of each characters.

Count the # of characters with odd frequency |odd|, each palindrome can consume at most one char with odd frequency. thus k must >= |odd|.
ans = k <= len(s) and k >= odd

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

C++

// Author: Huahua

class Solution {

public:

bool canConstruct(string s, int k) {

if (k > s.length()) return false;

vector<int> f(26);

for (char c : s) f[c - 'a'] ^= 1;

int odd = accumulate(begin(f), end(f), 0);

return k >= odd;

}

};

花花酱 LeetCode 1399. Count Largest Group

By zxi on April 4, 2020

Given an integer n. Each number from 1 to n is grouped according to the sum of its digits.

Return how many groups have the largest size.

Example 1:

Input: n = 13
Output: 4
Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13:
[1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size.

Example 2:

Input: n = 2
Output: 2
Explanation: There are 2 groups [1], [2] of size 1.

Example 3:

Input: n = 15
Output: 6

Example 4:

Input: n = 24
Output: 5

Constraints:

1 <= n <= 10^4

Solution: HashTable

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

C++

// Author: Huahua

class Solution {

public:

int countLargestGroup(int n) {

vector<int> c(37); // max sum is 9+9+9+9 = 36

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

int x = i;

int sum = 0;

while (x) {

sum += x % 10;

x /= 10;

}

++c[sum];

}

return count(begin(c), end(c), *max_element(begin(c), end(c)));

}

};

KMP Algorithm SP19

By zxi on March 31, 2020

KMP Algorithm, KMP 字符串搜索算法

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

Implementation

C++

#include <iostream>

#include <vector>

using namespace std;

// Author: Huahua

namespace KMP {

vector<int> Build(const string& p) {

const int m = p.length();

vector<int> nxt{0, 0};

for (int i = 1, j = 0; i < m; ++i) {

while (j > 0 && p[i] != p[j])

j = nxt[j];

if (p[i] == p[j])

++j;

nxt.push_back(j);

}

return nxt;

}

vector<int> Match(const string& s, const string& p) {

vector<int> nxt(Build(p));

vector<int> ans;

const int n = s.length();

const int m = p.length();

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

while (j > 0 && s[i] != p[j])

j = nxt[j];

if (s[i] == p[j])

++j;

if (j == m) {

ans.push_back(i - m + 1);

j = nxt[j];

}

return ans;

}

}; // namespace KMP

void CheckEQ(const vector<int>& actual, const vector<int>& expected) {

if (actual != expected) {

std::cout << "expected:";

for (int v : expected)

std::cout << " " << v;

std::cout << " actual:";

for (int v : actual)

std::cout << " " << v;

std::cout << std::endl;

} else {

std::cout << "PASS" << std::endl;

}

int main(int argc, char** argv) {

CheckEQ(KMP::Build("ABCDABD"), {0, 0, 0, 0, 0, 1, 2, 0});

CheckEQ(KMP::Build("AB"), {0, 0, 0});

CheckEQ(KMP::Build("A"), {0, 0});

CheckEQ(KMP::Build("AA"), {0, 0, 1});

CheckEQ(KMP::Build("AAA"), {0, 0, 1, 2});

CheckEQ(KMP::Build("AABA"), {0, 0, 1, 0, 1});

CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "ABCDABD"), {15});

CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "AB"), {0, 4, 8, 11, 15, 19});

CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "B"), {1, 5, 9, 12, 16, 20});

CheckEQ(KMP::Match("AAAAA", "A"), {0, 1, 2, 3, 4});

CheckEQ(KMP::Match("AAAAA", "AA"), {0, 1, 2, 3});

CheckEQ(KMP::Match("AAAAA", "AAA"), {0, 1, 2});

CheckEQ(KMP::Match("ABC", "ABC"), {0});

return 0;

}

Python3

#!/usr/bin/env python3

from typing import List

# Author: Huahua

def Build(p: str) -> List[int]:

m = len(p)

nxt = [0, 0]

j = 0

for i in range(1, m):

while j > 0 and p[i] != p[j]:

j = nxt[j]

if p[i] == p[j]:

j += 1

nxt.append(j)

return nxt

def Match(s: str, p: str) -> List[int]:

n, m = len(s), len(p)

nxt = Build(p)

ans = []

j = 0

for i in range(n):

while j > 0 and s[i] != p[j]:

j = nxt[j]

if s[i] == p[j]:

j += 1

if j == m:

ans.append(i - m + 1)

j = nxt[j]

return ans

def CheckEQ(actual, expected):

if actual != expected:

print('actual: %s, expected: %s' % (actual, expected))

else:

print('Pass')

if __name__ == "__main__":

CheckEQ(Build("ABCDABD"), [0, 0, 0, 0, 0, 1, 2, 0])

CheckEQ(Build("AB"), [0, 0, 0])

CheckEQ(Build("A"), [0, 0])

CheckEQ(Build("AA"), [0, 0, 1])

CheckEQ(Build("AAAA"), [0, 0, 1, 2, 3])

CheckEQ(Build("AABA"), [0, 0, 1, 0, 1])

CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "ABCDABD"), [15])

CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "AB"), [0, 4, 8, 11, 15, 19])

CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "B"), [1, 5, 9, 12, 16, 20])

CheckEQ(Match("AAAAA", "A"), [0, 1, 2, 3, 4])

CheckEQ(Match("AAAAA", "AA"), [0, 1, 2, 3])

CheckEQ(Match("AAAAA", "AAAA"), [0, 1])

CheckEQ(Match("AAAAA", "AAAAA"), [0])

CheckEQ(Match("AABAABA", "AABA"), [0, 3])

Applications

LeetCode 28. strStr()

C++

// Author: Huahua

class Solution {

public:

int strStr(string haystack, string needle) {

if (needle.empty()) return 0;

auto matches = KMP::Match(haystack, needle);

return matches.empty() ? -1 : matches[0];

}

};

LeetCode 459. Repeated Substring Pattern

C++

// Author: Huahua

class Solution {

public:

bool repeatedSubstringPattern(string str) {

const int n = str.length();

auto nxt = KMP::Build(str);

return nxt[n] && nxt[n] % (n - nxt[n]) == 0;

}

};

1392. Longest Happy Prefix

C++

// Author: Huahua

class Solution {

public:

string longestPrefix(const string& s) {

return s.substr(0, KMP::Build(s).back());

}

};

花花酱 LeetCode 1395. Count Number of Teams

By zxi on March 28, 2020

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

n == rating.length
1 <= n <= 200
1 <= rating[i] <= 10^5

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int numTeams(vector<int>& rating) {

int n = rating.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 (rating[i] < rating[j] && rating[j] < rating[k]

|| rating[i] > rating[j] && rating[j] > rating[k])

++ans;

return ans;

}

};

Solution 2: Math

For each soldier j, count how many soldiers on his left has smaller ratings as left[j], count how many soldiers his right side has larger ratings as right[j]

ans = sum(left[j] * right[j] + (j – left[j]) * (n – j – 1 * right[j])

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

C++

// Author: Huahua, 4 ms

class Solution {

public:

int numTeams(vector<int>& rating) {

int n = rating.size();

int ans = 0;

for (int j = 0; j < n; ++j) {

int l = 0;

int r = 0;

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

if (rating[i] < rating[j]) ++l;

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

if (rating[j] < rating[k]) ++r;

ans += (l * r) + (j - l) * (n - j - 1 - r);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1401. Circle and Rectangle Overlapping

Solution: Geometry

C++

花花酱 LeetCode 1400. Construct K Palindrome Strings

Solution: HashTable

C++

花花酱 LeetCode 1399. Count Largest Group

Solution: HashTable

C++

KMP Algorithm SP19

Implementation

C++

Python3

Applications

C++

C++

C++

花花酱 LeetCode 1395. Count Number of Teams

Solution 1: Brute Force

C++

Solution 2: Math

C++