# Leetcode summary of 20200301-20200308

Posted by chunyang on March 14, 2020

### Summary

It is a little busy this week. So the summary is a little late.

Solved problems list

• 1185. Day of the Week
• 1154. Day of the Year
• 1360. Number of Days Between Two Dates
• 1370. Increasing Decreasing String
• 1356. Sort Integers by The Number of 1 Bits
• 1372. Longest ZigZag Path in a Binary Tree
• 1362. Closest Divisors
• 220. Contains Duplicate III
• 211. Add and Search Word - Data structure design
• 209. Minimum Size Subarray Sum
• 208. Implement Trie (Prefix Tree)
• 207. Course Schedule
• 1365. How Many Numbers Are Smaller Than the Current Number
• 1367. Linked List in Binary Tree
• 1366. Rank Teams by Votes

### Code Section

The sequence of code is the same with the problem list.

// 1185. Day of the Week
// https://leetcode.com/problems/day-of-the-week/
class Solution {
public:
string dayOfTheWeek(int day, int month, int year) {
vector<vector<int>> cols{
{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
function<bool(int)> is_leap_year = [](int y) {
if (y % 100 != 0) return y % 4 == 0;
else return y % 400 == 0;
};
int days = 0;
vector<int> y_d{365, 366};
for (int i = 1971; i < year; ++i) {
days += y_d[is_leap_year(i)];
}
auto& m = cols[is_leap_year(year)];
days += accumulate(begin(m), next(m.begin(), month-1), 0) + day;
days %= 7;
vector<string> weeks = {"Friday", "Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday"};
return weeks[days == 0? 6 : days-1];
}
};

// 1154. Day of the Year
// https://leetcode.com/problems/day-of-the-year/
class Solution {
public:
int dayOfYear(string date) {
vector<int> time(3);
int size = date.size();
vector<vector<int>> cols{
{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
time[0] = stoi(date.substr(0, 4));
time[1] = stoi(date.substr(5, 2));
time[2] = stoi(date.substr(8, 2));
function<bool(int)> is_leap_year = [](int y) {
if (y % 100 != 0) return y % 4 == 0;
else return y % 400 == 0;
};
vector<int>& col = cols[is_leap_year(time[0])];
return accumulate(begin(col), next(begin(col), time[1]-1), 0) + time[2];

}
};

// 1360. Number of Days Between Two Dates
// https://leetcode.com/problems/number-of-days-between-two-dates/
class Solution {
public:
int daysBetweenDates(string date1, string date2) {
vector<vector<int>> month_days = {
{31, 28, 31, 30,31,30,31,31,30,31,30,31},
{31, 29, 31, 30,31,30,31,31,30,31,30,31},
};
int leap_days[2] = {365, 366};
int y1, m1, d1;
int y2, m2, d2;
function<void(int&, int&, int&, string&)> parse = [](int&y ,int& m, int& d, string& s) {
y = stoi(s.substr(0, 4));
m = stoi(s.substr(5, 2));
d = stoi(s.substr(8, 2));
};
function<bool(int)> is_leap = [](int y) {
if (y % 100 == 0) return y % 400 == 0;
return y % 4 == 0;
};
parse(y1, m1, d1, date1);
parse(y2, m2, d2, date2);
int days = 0;
int s1 = y1, s2 = y2;
if (s1 > s2) swap(s1, s2);
for (int i = s1; i < s2; ++i) {
days += leap_days[is_leap(i)];
}
auto& m_d1 = month_days[is_leap(y1)];
int days1 = d1 + accumulate(begin(m_d1), next(m_d1.begin(), m1-1), 0);
auto& m_d2 = month_days[is_leap(y2)];
int days2 = d2 + accumulate(begin(m_d2), next(m_d2.begin(), m2-1), 0);
if (y1 < y2) {
return days + days2 - days1;
} else if (y1 > y2) {
return days + days1 - days2;
} else {
return abs(days1 - days2);
}
}
};

// 1370. Increasing Decreasing String
// https://leetcode.com/problems/increasing-decreasing-string/
class Solution {
public:
string sortString(string s) {
vector<int> x(26, 0);
for_each(begin(s), end(s), [&](char c) { ++x[c-'a'];});
string res;
int size = s.size();
while (res.size() < size) {
for (int i = 0; i < 26; ++i) {
if (x[i] != 0)  {
res += i + 'a';
--x[i];
}
}
for (int i = 25; i >= 0; --i) {
if (x[i] != 0)  {
res += i + 'a';
--x[i];
}
}
}
return res;
}
};

// 1356. Sort Integers by The Number of 1 Bits
// https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/
class Solution {
public:
vector<int> sortByBits(vector<int>& arr) {
unordered_map<int, int> cached;
function<int(int)> n_b = [&](int n) {
if (cached.find(n) != cached.end()) return cached[n];
int key = n;
int cnt = 0;
while (n != 0) { n &= (n-1); ++cnt;}
cached[key] = cnt;
return cnt;
};
function<bool(int, int)> cmp = [&](int l, int r) {
auto ll = n_b(l);
auto rr = n_b(r);
return ll == rr ? l < r : ll < rr;
};
sort(begin(arr), end(arr), cmp);
return arr;
}
};

// 1372. Longest ZigZag Path in a Binary Tree
// https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int longestZigZag(TreeNode* root) {
if (!root || (!root->left && !root->right)) return 0;
int max_length = 0;
function<int(TreeNode*, bool, int)> traverse = [&](TreeNode* node, bool d, int n)
{
// d: true, right
// d: false, left
if (!node) return n;
n = n + 1;
int x, y;
if (d) {
x = node->right ? traverse(node->right, !d, n) : n;
y = node->left ? traverse(node->left, d, 0) : 0;
} else {
x = node->left ? traverse(node->left, !d, n) : n;
y = node->right ? traverse(node->right, d, 0) : 0;
}
return max(x, y);
};
return max(traverse(root->left, true, 0), traverse(root->right, false, 0));
}
};

// 1362. Closest Divisors
// https://leetcode.com/problems/closest-divisors/
class Solution {
public:
vector<int> closestDivisors(int num) {
int s = num + 2;
int k = sqrt(s);
for (; k >= 1; --k) {
auto x = (num+1) % k;
if (x == 0) return {k, (num+1)/k};
if (x == (k-1)) return {k, (num+2)/k};
}
return {0, 0};
}
int a = num + 1;
int b = num + 2;
function<bool(int)> is_prime = [](int x) {
if (x == 1) return false;
if (x < 4) return true;
if (x % 2 == 0 || x % 3 == 0) return false;
int w = 2;
int k = 5;
while (k * k <= x) {
if (x % k == 0) return false;
k += w;
w = 6 - w;
}
return true;
};
function<pair<int,int>(int)> factor = [&](int n) {
if (is_prime(n)) return make_pair(1, n);
int r = (int)sqrt(n);
while (n % r != 0) {
++r;
}
int d = n / r;
if (d > r) swap(d, r);
return make_pair(d, r);
};
auto p1 = factor(a);
auto p2 = factor(b);
if (p1.second - p1.first < p2.second - p2.first) {
return {p1.first, p1.second};
} else {
return {p2.first, p2.second};
}
}
};

// 220. Contains Duplicate III
// https://leetcode.com/problems/contains-duplicate-iii/
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int size = nums.size();
if (k == 0 || size < 2) return false;
multiset<int> s;
s.insert(nums[0]);
// cout << "--------------" << endl;
for (int i = 1; i < size; ++i) {
auto l = s.lower_bound(nums[i]);
decltype(l) r = prev(l);

/*
if (l != s.end()) cout << "*l = " << *l << endl;
else cout << "*l is end()" << endl;
cout <<"*prev(l) = " << *prev(l) << endl;
*/

if (l != s.end() && (abs(*l - (long long)nums[i])) <= t) return true;
if (r != s.end() && (abs(*prev(l) - (long long)nums[i])) <= t) return true;
// cout << "X: " << nums[i]<< " "<< s.size() << endl;
if (s.size() == k) {

auto ite = s.find(nums[i-k]);
// cout << "del: " << *ite << endl;
s.erase(ite);
}
// cout << "Y: " << nums[i]<< " "<< s.size() << endl;
s.insert(nums[i]);
}
return false;
}
};

// 211. Add and Search Word - Data structure design
class WordDictionary {
struct Node {
bool end;
vector<Node*> output;
Node(): output(26, nullptr), end(false) {}
};
public:
/** Initialize your data structure here. */
}

/** Adds a word into the data structure. */
int size = word.size();
for (int i = 0; i < size; ++i) {
char c = word[i];
int index = c - 'a';
if (!(*starts)[index]) {
(*starts)[index] = new Node;
}
if (i == size-1) (*starts)[index]->end = true;
starts = &((*starts)[index]->output);
}
}

/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
bool search(string word) {
function<bool(int, vector<Node*>&)> sea = [&](int index, vector<Node*>& nodes) {
if (word[index] != '.') {
int pos = word[index] - 'a';
if (nodes[pos] == nullptr) return false;
else {
if (index == word.size() - 1) {
return nodes[pos]->end;
}
return sea(index+1, nodes[pos]->output);
}
} else {
for (int i = 0; i < 26; ++i) {
if (nodes[i] != nullptr) {
if (index == word.size() - 1) {
if (nodes[i]->end) return true;
} else {
bool res = sea(index+1, nodes[i]->output);
if (res) return res;
}
}
}
return false;
}
};
}
};

/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary* obj = new WordDictionary();
* bool param_2 = obj->search(word);
*/

// 209. Minimum Size Subarray Sum
// https://leetcode.com/problems/minimum-size-subarray-sum/
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
// use prefix sum
partial_sum(begin(nums), end(nums), begin(nums));
int c = INT_MAX;
int size = nums.size();
int prev = 0;
for (int i = 0; i < size; ++i) {
int target = s + prev;
auto it = lower_bound(begin(nums), end(nums), target);
if (it == nums.end()) break;
int dis = distance(nums.begin(), it) - i + 1;
c = min(c, dis);
prev = nums[i];
}

return c == INT_MAX ? 0 : c;
}
int minSubArrayLenFast(int s, vector<int>& nums) {
int i = 0;
int j = 0;
int size = nums.size();
int sum = 0;
int c = INT_MAX;
while (true) {
while (j < size && sum < s) {
sum += nums[j];
++j;
}
if (sum < s) break;
int dis = j - i;
if (dis < c) c = dis;
sum -= nums[i];
++i;
}
return c == INT_MAX? 0 : c;
}
};

// 208. Implement Trie (Prefix Tree)
// https://leetcode.com/problems/implement-trie-prefix-tree/
class Trie {
struct TrieNode {
bool end;
vector<TrieNode*> out;
TrieNode(): end(false), out(26, nullptr) {}
};
public:
/** Initialize your data structure here. */

}

/** Inserts a word into the trie. */
void insert(string word) {
// cout << "Insert: " << word << endl;
function<void(const string&, int, vector<TrieNode*>&)> insert_helper = [&](
const string& word, int start, vector<TrieNode*>& heads
) {
if (start >= word.size()) return;
int index = word[start] - 'a';
// cout << "char: " << word[start] << ", heads[index]->end: " << heads[index]->end << endl;
};
}

/** Returns if the word is in the trie. */
bool search(string word) {
// cout << "Search: " << word << endl;
function<bool(const string&, int start, const vector<TrieNode*>&)> search_helper = [&](const string& word, int start, const vector<TrieNode*>& heads) {
int size = word.size();
int index = word[start] - 'a';
if (size == start+1) {
} else {
}
};
if (word.empty()) return true;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
function<bool(const string&, int start, const vector<TrieNode*>&)> search_helper = [&](const string& word, int start, const vector<TrieNode*>& heads) {
int size = word.size();
int index = word[start] - 'a';
if (size == start+1) {
} else {
}
};
if (prefix.empty()) return true;
}
};

/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/

// 207. Course Schedule
// https://leetcode.com/problems/course-schedule/
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int, vector<int>> course; // id -> outputs
vector<bool> deps(numCourses, false);
for (vector<int>& dep: prerequisites) {
course[dep[1]].push_back(dep[0]);
deps[dep[0]] = true;
}
vector<bool> taken(numCourses, false);
unordered_set<int> s;
function<bool(int)> dfs = [&](int i) {
if (taken[i]) return false;
s.insert(i);
taken[i] = true;
for (int d : course[i]) {
if(!dfs(d)) return false;
}
taken[i] = false;
return true;
};
for (int i = 0; i < numCourses; ++i) {
if (deps[i]) continue;
if (!dfs(i)) return false;
}
return s.size() == numCourses;
}
};

// 1365. How Many Numbers Are Smaller Than the Current Number
// https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> bkp(nums);
sort(begin(bkp), end(bkp));
vector<int> result;result.reserve(nums.size());
for (int n : nums) {
auto ite = lower_bound(begin(bkp), end(bkp), n);
result.push_back(distance(bkp.begin(), ite));
}
return result;
}
};

// 1367. Linked List in Binary Tree
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSubPath(ListNode* head, TreeNode* root) {

bool k = false, lr = false;
function<bool(ListNode*, TreeNode*, bool)> dfs = [&](
ListNode* head, TreeNode* root, bool cont
) {
if (!root) return false;
if (cont) {
if (head->val != root->val) return false;
}
if (!k)
return k;
};

}
};


// 1366. Rank Teams by Votes
class Solution {
struct Vote {
char c;
Vote(): c('0') {}
bool operator()(const Vote&l, const Vote& r) {
if (l.c == '0') return false;
if (r.c == '0') return true;
for (int i = 0; i < 26; ++i) {
}
return l.c < r.c;
}
};
public:
vector<Vote> v(26);
for (int i = 0; i < team_size; ++i) {
char team = vote[i];
int t_id = team - 'A';
v[t_id].c = team;
}
}
sort(v.begin(), v.end(), Vote());
string s;
for (auto& vv: v) {
if (vv.c == '0') break;
s += vv.c;
}
return s;

}
};