Huahua’s Tech Road

花花酱 LeetCode 1002. Find Common Characters

By zxi on March 2, 2019

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

Example 1:

Input: ["bella","label","roller"]
Output: ["e","l","l"]

Example 2:

Input: ["cool","lock","cook"]
Output: ["c","o"]

Note:

1 <= A.length <= 100
1 <= A[i].length <= 100
A[i][j] is a lowercase letter

Solution: Min count for each character

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

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

vector<string> commonChars(vector<string>& A) {

vector<int> min_count(26, INT_MAX);

for (const string& a : A) {

vector<int> count(26, 0);

for (const char ch : a)

++count[ch - 'a'];

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

min_count[i] = min(min_count[i], count[i]);

}

vector<string> ans;

for (int i = 0; i < 26; ++i) {

if (min_count[i] == INT_MAX) continue;

for (int j = 0; j < min_count[i]; ++j)

ans.push_back(string(1, 'a' + i));

}

return ans;

}

};

花花酱 LeetCode 1004. Max Consecutive Ones III

By zxi on March 2, 2019

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Note:

1 <= A.length <= 20000
0 <= K <= A.length
A[i] is 0 or 1

Solution : Sliding Window

Maintain a window that has at most K zeros

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

C++

class Solution {

public:

int longestOnes(vector<int>& A, int K) {

int l = 0;

int zeros = 0;

int ans = 0;

for (int r = 0; r < A.size(); ++r) {

if (A[r] == 0) ++zeros;

while (zeros > K)

if (A[l++] == 0) --zeros;

ans = max(ans, r - l + 1);

}

return ans;

}

};

花花酱 LeetCode 30. Substring with Concatenation of All Words

By zxi on March 2, 2019

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in sthat is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

Solution1: HashTable + Brute Force

Time complexity: O((|S| – |W|*l) * |W|*l))
Space complexity: O(|W|*l)

C++

// Author: Huahua

// std::string_view running time: 128 ms, 16 MB

// std::string running time: 156 ms, 22.4 MB

class Solution {

public:

vector<int> findSubstring(string s, vector<string>& words) {

if (words.empty() || s.empty()) return {};

const int n = words.size();

const int l = words[0].length();

if (n * l > s.length()) return {};

std::string_view ss(s);

std::unordered_map<std::string_view, int> expected;

for (const string& word : words)

++expected[string_view(word)];

vector<int> ans;

for (int i = 0; i <= ss.length() - n * l; ++i) {

std::unordered_map<std::string_view, int> seen;

int count = 0;

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

std::string_view w = ss.substr(i + j * l, l);

auto it = expected.find(w);

if (it == expected.end()) break;

if (++seen[w] > it->second) break;

++count;

}

if (count == n)

ans.push_back(i);

}

return ans;

}

};

花花酱 LeetCode Weekly 125

By zxi on February 24, 2019

Problems

花花酱 LeetCode 1001. Grid Illumination

By zxi on February 24, 2019

On a N x N grid of cells, each cell (x, y) with 0 <= x < N and 0 <= y < N has a lamp.

Initially, some number of lamps are on. lamps[i] tells us the location of the i-th lamp that is on. Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).

For the i-th query queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.

After each query (x, y) [in the order given by queries], we turn off any lamps that are at cell (x, y) or are adjacent 8-directionally (ie., share a corner or edge with cell (x, y).)

Return an array of answers. Each value answer[i] should be equal to the answer of the i-th query queries[i].

Example 1:

Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation: 
Before performing the first query we have both lamps [0,0] and [4,4] on.
The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,4] is the bottom right corner:
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 1 1
1 1 1 1 1
Then the query at [1, 1] returns 1 because the cell is lit.  After this query, the lamp at [0, 0] turns off, and the grid now looks like this:
1 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
1 1 1 1 1
Before performing the second query we have only the lamp [4,4] on.  Now the query at [1,0] returns 0, because the cell is no longer lit.

Note:

1 <= N <= 10^9
0 <= lamps.length <= 20000
0 <= queries.length <= 20000
lamps[i].length == queries[i].length == 2

Solution: HashTable

use lx, ly, lp, lq to track the # of lamps that covers each row, col, diagonal, antidiagonal

Time complexity: O(|L| + |Q|)
Space complexity: O(|L|)

C++

// Author: Huahua, running time: 460 ms, 82.2 MB

class Solution {

public:

vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {

unordered_set<long> s;

unordered_map<int, int> lx, ly, lp, lq;

for (const auto& lamp : lamps) {

const int x = lamp[0];

const int y = lamp[1];

s.insert(static_cast<long>(x) << 32 | y);

++lx[x];

++ly[y];

++lp[x + y];

++lq[x - y];

}

vector<int> ans;

for (const auto& query : queries) {

const int x = query[0];

const int y = query[1];

if (lx.count(x) || ly.count(y) || lp.count(x + y) || lq.count(x - y)) {

ans.push_back(1);

for (int tx = x - 1; tx <= x + 1; ++tx)

for (int ty = y - 1; ty <= y + 1; ++ty) {

if (tx < 0 || tx >= N || ty < 0 || ty >= N) continue;

const long key = static_cast<long>(tx) << 32 | ty;

if (!s.count(key)) continue;

s.erase(key);

if (--lx[tx] == 0) lx.erase(tx);

if (--ly[ty] == 0) ly.erase(ty);

if (--lp[tx + ty] == 0) lp.erase(tx + ty);

if (--lq[tx - ty] == 0) lq.erase(tx - ty);

}

} else {

ans.push_back(0);

}

return ans;

}

};

C++ v2

// Author: Huahua, running time: 444 ms, 82.2 MB

class Solution {

public:

vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {

unordered_set<long> s;

unordered_map<int, int> lx, ly, lp, lq;

for (const auto& lamp : lamps) {

const int x = lamp[0];

const int y = lamp[1];

s.insert(static_cast<long>(x) << 32 | y);

++lx[x];

++ly[y];

++lp[x + y];

++lq[x - y];

}

vector<int> ans;

auto dec = [](unordered_map<int, int>& m, int key) {

auto it = m.find(key);

if (it->second == 1)

m.erase(it);

else

--it->second;

};

for (const auto& query : queries) {

const int x = query[0];

const int y = query[1];

if (lx.count(x) || ly.count(y) || lp.count(x + y) || lq.count(x - y)) {

ans.push_back(1);

for (int tx = x - 1; tx <= x + 1; ++tx)

for (int ty = y - 1; ty <= y + 1; ++ty) {

if (tx < 0 || tx >= N || ty < 0 || ty >= N) continue;

const long key = static_cast<long>(tx) << 32 | ty;

auto it = s.find(key);

if (it == s.end()) continue;

s.erase(it);

dec(lx, tx);

dec(ly, ty);

dec(lp, tx + ty);

dec(lq, tx - ty);

}

} else {

ans.push_back(0);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1002. Find Common Characters

Solution: Min count for each character

C++

花花酱 LeetCode 1004. Max Consecutive Ones III

Solution : Sliding Window

C++

花花酱 LeetCode 30. Substring with Concatenation of All Words

Solution1: HashTable + Brute Force

C++

花花酱 LeetCode Weekly 125

Problems

花花酱 LeetCode 1001. Grid Illumination

Solution: HashTable

C++

C++ v2