Huahua's Tech Road

花花酱 LeetCode 1185. Day of the Week

By zxi on September 7, 2019

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the day, month and year respectively.

Return the answer as one of the following values {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.

Example 1:

Input: day = 31, month = 8, year = 2019
Output: "Saturday"

Example 2:

Input: day = 18, month = 7, year = 1999
Output: "Sunday"

Example 3:

Input: day = 15, month = 8, year = 1993
Output: "Sunday"

Constraints:

The given dates are valid dates between the years 1971 and 2100.

Solution: LeapYear

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

C++

// Author: Huahua

inline bool leapYear(int y) {

return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);

}

class Solution {

public:

string dayOfTheWeek(int day, int month, int year) {

vector<string> names = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

vector<int> days = {31, 28 + leapYear(year), 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int sum = 0;

for (int i = 1970; i < year; ++i)

sum += 365 + leapYear(i);

for (int i = 1; i < month; ++i)

sum += days[i - 1];

sum += day;

return names[(sum + 3) % 7];

}

};

花花酱 LeetCode 1184. Distance Between Bus Stops

By zxi on September 7, 2019

A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given start and destination stops.

Example 1:

Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

Example 2:

Input: distance = [1,2,3,4], start = 0, destination = 2
Output: 3
Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.

Example 3:

Input: distance = [1,2,3,4], start = 0, destination = 3
Output: 4
Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.

Constraints:

1 <= n <= 10^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4

Solution: Summation

compute the total sum
compute the sum from s to d, c
ans = min(c, sum – c)

Time complexity: O(d-s)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int distanceBetweenBusStops(vector<int>& ds, int s, int d) {

if (s > d) swap(s, d);

int sum = accumulate(begin(ds), end(ds), 0);

int d1 = accumulate(begin(ds) + s, begin(ds) + d, 0);

return min(d1, sum - d1);

}

};

花花酱 LeetCode 1178. Number of Valid Words for Each Puzzle

By zxi on September 1, 2019

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

word contains the first letter of puzzle.
For each letter in word, that letter is in puzzle.
For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”; while invalid words are “beefed” (doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

Example :

Input: 
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

Constraints:

1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] are English lowercase letters.
Each puzzles[i] doesn’t contain repeated characters.

Solution: Subsets

Preprocessing:
Compress each word to a bit map, and compute the frequency of each bit map.
Since there are at most |words| bitmaps while its value ranging from 0 to 2^26, thus it’s better to use a hashtable instead of an array.

Query:
Use the same way to compress a puzzle into a bit map.
Try all subsets (at most 128) of the puzzle (the bit of the first character is be must), and check how many words match each subset.

words = [“aaaa”,”asas”,”able”,”ability”,”actt”,”actor”,”access”],
puzzle = “abslute”
bitmap(“aaaa”) = {0}
bitmap(“asas”) = {0, 18}
bitmap(“able”) = {0,1,4,11}
bitmap(“actt”) = {0, 2, 19}
bitmap(“actor”) = {0, 2, 14, 17, 19}
bitmap(“access”) = {0, 2, 4, 18}

bitmap(“abslute”) = {0, 1, 4, 11, 18, 19, 20}

Time complexity: O(sum(len(w_i)) + |puzzles|)
Space complexity: O(|words|)

C++

// Author: Huahua, 136 ms, 29.7 MB

class Solution {

public:

vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {

vector<int> ans;

unordered_map<int, int> freq;

for (const string& word : words) {

int mask = 0;

for (char c : word)

mask |= 1 << (c - 'a');

++freq[mask];

}

for (const string& p : puzzles) {

int mask = 0;

for (char c : p)

mask |= 1 << (c - 'a');

int first = p[0] - 'a';

int curr = mask;

int total = 0;

while (curr) {

if ((curr >> first) & 1) {

auto it = freq.find(curr);

if (it != freq.end()) total += it->second;

}

curr = (curr - 1) & mask;

}

ans.push_back(total);

}

return ans;

}

};

花花酱 LeetCode 1177. Can Make Palindrome from Substring

By zxi on September 1, 2019

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], ..., s[right], and then choose up to k of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return an array answer[], where answer[i] is the result of the i-th query queries[i].

Note that: Each letter is counted individually for replacement so if for example s[left..right] = "aaa", and k = 2, we can only replace two of the letters. (Also, note that the initial string s is never modified by any query.)

Example :

Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0] : substring = "d", is palidrome.
queries[1] : substring = "bc", is not palidrome.
queries[2] : substring = "abcd", is not palidrome after replacing only 1 character.
queries[3] : substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4] : substring = "abcda", could be changed to "abcba" which is palidrome.

Constraints:

1 <= s.length, queries.length <= 10^5
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s only contains lowercase English letters.

Solution: Prefix frequency

Compute the prefix frequency of each characters, then we can efficiently compute the frequency of each characters in the substring in O(1) time. Count the number odd frequency characters o, we can convert it to a palindrome if o / 2 <= k.

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

C++

// Author: Huahua

class Solution {

public:

vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {

vector<bool> ans;

int n = s.length();

vector<vector<int>> f(n + 1, vector<int>(26));

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

++f[i][s[i] - 'a'];

f[i + 1] = f[i];

}

for (const auto& q : queries) {

int l = q[0];

int r = q[1];

int k = q[2];

int o = 0;

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

int c = f[r][i] - (l == 0 ? 0 : f[l - 1][i]);

o += c % 2;

}

ans.push_back(o / 2 <= k);

}

return ans;

}

};

花花酱 LeetCode 1176. Diet Plan Performance

By zxi on August 31, 2019

A dieter consumes calories[i] calories on the i-th day. For every consecutive sequence of k days, they look at T, the total calories consumed during that sequence of k days:

If T < lower, they performed poorly on their diet and lose 1 point;
If T > upper, they performed well on their diet and gain 1 point;
Otherwise, they performed normally and there is no change in points.

Return the total number of points the dieter has after all calories.length days.

Note that: The total points could be negative.

Example 1:

Input: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0
Explaination: calories[0], calories[1] < lower and calories[3], calories[4] > upper, total points = 0.

Example 2:

Input: calories = [3,2], k = 2, lower = 0, upper = 1
Output: 1
Explaination: calories[0] + calories[1] > upper, total points = 1.

Example 3:

Input: calories = [6,5,0,0], k = 2, lower = 1, upper = 5
Output: 0
Explaination: calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, total points = 0.

Constraints:

1 <= k <= calories.length <= 10^5
0 <= calories[i] <= 20000
0 <= lower <= upper

Solution: Sliding Window

Maintain the sum of a sliding window length of k.

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

C++

// Author: Huahua

class Solution {

public:

int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {

int ans = 0;

int t = accumulate(begin(calories), begin(calories) + k - 1, 0);

for (int i = k - 1; i < calories.size(); ++i) {

if (i >= k) t -= calories[i - k];

t += calories[i];

if (t > upper) ++ans;

if (t < lower) --ans;

}

return ans;

}

};