2022.10 Daily LeetCode Coding Problems Tutorial
If you get any problem of my code or you find something wrong, just leave a comment or contact with me, I’ll response you as fast as I can if I see it.
If this tutorial helps you well, you can subscribe my website, every time I update any Tutorial, I’ll send an email to all subscribers.
10-31 766. Toeplitz Matrix
Difficulty: Easy
Accepted Code
class Solution {
public:
bool isToeplitzMatrix(vector<vector<int>>& matrix) {
vector<int> n[int(matrix.size() + matrix[0].size() - 1)];
int beginIdx = 0;
for(int i = matrix.size() - 1; i >= 0; --i){
int j = beginIdx;
for(int k : matrix[i]) n[j++].push_back(k);
beginIdx++;
}
for(auto i : n) {
int j = i[0];
for(int k : i) if(k != j) return false;
}
return true;
}
};
10-30 1293. Shortest Path in a Grid with Obstacles Elimination
Difficulty: Hard
Tutorial
BFS
Accepted Code( T/ M : 68.41%/82.45%)
class Solution {
public:
int shortestPath(vector<vector<int>>& grid, int k) {
int n = grid.size(), m = grid[0].size(); //define n, m as problem describe
if(n == 1 && m == 1) return 0;
queue<pair<pair<int, int>, pair<int, int>>> q; //( (x, y), (k, step) ) //current position(x, y), can elemate k obstacle, have moved step times;
q.push({{0,0}, {k, 0}}); //start point
int dx[] = {-1, 0, 1, 0}; //direction
int dy[] = {0, -1, 0, 1}; //direction
map<pair<int, int>, int> visit;
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) visit[{i,j}] = -1;
while(!q.empty()){
auto t = q.front();
q.pop();
for(int i = 0; i < 4; ++i){ //traverse four directions
int nx = t.first.first + dx[i]; //next x
int ny = t.first.second + dy[i]; //next y
int nk = t.second.first; //next k;
//check is (nx, ny) end point;
if(nx == n - 1 && ny == m - 1) return t.second.second + 1; // reach end point
//check next position whether is valid or not
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; //out of grid;
if(grid[nx][ny] == 1 && t.second.first == 0) continue; //next step is obstacle, but cannot elemate any obstacle now;
if(grid[nx][ny]) nk--;
if(visit[{nx, ny}] != -1 && visit[{nx, ny}] >= nk) continue;
visit[{nx, ny}] = nk;
//move;
q.push({{nx, ny}, {nk, t.second.second + 1}});
}
}
return -1;
}
};
10-29 2136. Earliest Possible Day of Full Bloom
Difficulty: Hard
Tutorial
Obviously we need sum of plantTime to plant all the flowers. And After plant, we just need to wait all flowers grown-up.
Look at the example 1, after we plant all flower, we need to wait third flower to grow. So plant the min grow time flower last could be better. So we sort all the flower by grow time in decreasing order.
But there are some special cases.
If we change example 1 to: plantTime = [4, 3], growTime = [6, 1]. the answer will be 4 + 6. First we use 4 days to plant 1st flower, and then we take 3 days to plant 2nd flower, and 2nd flower takes 1 days to grow. But 1st flower need 6 days to grow, while 1st flower is growing, we can plant 2nd flower and wait it grwon-up. So the answer only depends on the 1st flower.
Accepted Code
class Solution {
public:
int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
int all = 0, ans = 0;
int n = plantTime.size();
vector<pair<int, int>> pg;
for(int i = 0; i < n; ++i) pg.push_back({plantTime[i], growTime[i]});
sort(pg.begin(), pg.end(), [](pair<int, int> a, pair<int, int> b){
return a.second > b.second;
});
for(pair<int, int> it : pg){
all += it.first;
ans = max(ans, all + it.second);
// in case the special case, record the longest time to grow current flower.
}
return ans;
}
};
10-28 49. Group Anagrams
Difficulty: Medium
Tutorial
If two strings are in the same group, after sorting two strings, they will be the same string. It is easy to understand, because two strings have the same letter, and times of each letters’ appera are the same also.
So just traverse all the string, use unordered_map or map to record the same string after sorting.
Accepted Code:(T / M : 86.78% / 56.57%)
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> pos;
int cnt = 0;
for(string s: strs){
sort(s.begin(), s.end());
pos[s].push_back(strs[cnt++]);
}
vector<vector<string>>ans;
for(auto it : pos) ans.push_back(it.second);
return ans;
}
};
10-27 835. Image Overlap
Difficulty: Medium
Tutorial
For the answer, we move ans step for every 1 in image1.
For every 1 in image1, we make enumerate the last position in image2, make two 1 overlap, check the step, most step will be the ans. Because if we move ans steps, most 1 will overlap.
Accepted Code:
class Solution {
public:
int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
int n = img1.size();
vector<pair<int, int> > vp1, vp2;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(img1[i][j]) vp1.push_back({i,j});
if(img2[i][j]) vp2.push_back({i,j});
}
}
int ans = 0;
map<pair<int, int>, int> mp;
for(auto it1 : vp1){
for(auto it2 : vp2){
int a = it1.first - it2.first;
int b = it1.second - it2.second;
mp[{a, b}]++;
ans = max(ans, mp[{a, b}]);
}
}
return ans;
}
};
10-26 523. Continuous Subarray Sum
Difficulty: Medium
Tutorial
If sum[1 ~ l] % k == 0 && sum[1 ~ r] % k == 0, sum[l ~ r] % k == 0, this judgement is valid when r - l > 1.
Accepted Code
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
int sum = 0;
for(int i = 0; i < nums.size(); ++i){
sum += nums[i];
sum %= k;
if(mp.count(sum) != 0 && i - mp[sum] > 1 || sum == 0 && i > 0) return true;
else if(mp.count(sum) == 0) mp[sum] = i;
}
return false;
}
};
10-24 1239. Maximum Length of a Concatenated String with Unique Characters
Difficulty: Medium
Tutorial
Use Dfs to enumerate all concatenated string, check whether is valid.
Accepted Code: (T/M : 78.69% / 79.31%)
class Solution {
public:
int maxLength(vector<string>& arr) {
return dfs(0, arr, "");
}
int dfs(int idx, vector<string> &arr, string cur){
if(idx == arr.size()){
return cur.size();
}
int ans = 0;
for(int i = idx; i < arr.size(); ++i){
string nxt = cur + arr[i];
if(check(nxt)){
ans = max(ans, int(nxt.size()));
ans = max(ans, dfs(i + 1, arr, nxt));
}
}
return ans;
}
bool check(string s){
if(s.size() > 26) return false;
bool vis[26] = {false};
for(char i : s){
if(vis[i - 'a']) return false;
vis[i - 'a'] = true;
}
return true;
}
};
10-23 645. Set Mismatch
Difficulty: Easy
Tutorial
No Tutorial.
Accepted Code
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
bool vis[10005];
memset(vis, false, sizeof(vis));
vector<int> res;
for(int i : nums){
if(vis[i]) res.push_back(i);
vis[i] = true;
}
for(int i = 1; i <= n; ++i){
if(vis[i] == false){
res.push_back(i);
return res;
}
}
}
};
more beautiful code from HERE
vector<int> findErrorNums(vector<int>& nums) {
for(int i = 0; i<nums.size(); i++){
while(nums[i] != nums[nums[i] - 1])swap(nums[i], nums[nums[i] - 1]);
}
for(int i = 0; i<nums.size() ; i++){
if(nums[i] != i + 1)return {nums[i], i + 1};
}
}
10-22 76. Minimum Window Substring
Difficulty: Hard
Tutorial
Use two pointer。
I’m playing mahjong, I’ll write later
First, use two pointer to index a window, which include all the letters in t.
Second, try to make the window shorter by moving its left side. When shorting the window, make window always be valid.
After second step, compare valid window length with current answer. If shorter, update answer.
Third, continue to move window’s right side, util window include all letters in t, then repeat from second step.
Accepted Code（T/M：80.58%， 94.27%）
class Solution {
public:
string minWindow(string s, string t) {
if(s.size() < t.size()) return "";
int cnt[130] = {0};
bool exist[130] = {false};
for(char c: t) cnt[c]++, exist[c] = true;
int minl = -1, minr = 1000000;
int l = 0, r = 0, tn = t.size();
while(r < s.size()){
if(exist[s[r]]){
if(--cnt[s[r]] >= 0) tn--;
if(tn == 0){ // current [l, r] include all letters in t.
while(tn == 0){ //step 2nd.
while(l <= r && !exist[s[l]]) ++l; //move left side of the window.
if(++cnt[s[l]] > 0) ++tn; //if after move, window invalid, break current loop.
++l;
}
if(minr - minl > r - l) minr = r, minl = l - 1; // compare with answer
}
}
++r; // step 3rd.
}
if(minl == -1) return "";
s = s.substr(minl, minr - minl + 1);
return s;
}
};
10-21 219. Contains Duplicate II
Difficulty：Easy
Tutorial
Traverse nums, record all number last index in traversal, compare distance of current number index and last index with k, if valid, return true, else update last index to current index.
Accepted Code
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> lastPos;
for(int i = 0; i < nums.size(); ++i){
if(lastPos[nums[i]] == 0) lastPos[nums[i]] = i + 1;
else{
if(i + 1 - lastPos[nums[i]] <= k) return true;
lastPos[nums[i]] = i + 1;
}
}
return false;
}
};
10-19 692. Top K Frequent Words
Difficulty：Medium
Tutorial
Count the number of occurrences of every word. Make word and its count be an struct, sort the struct list, and select top k frequent words.
Accepted Code (T/M : 27.39%/39.56%)
class Solution {
public:
unordered_map<string, int> count;
struct Word{
string w;
int count;
friend bool operator < (Word a, Word b){
if(a.count != b.count) return a.count > b.count;
return a.w < b.w;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
for(string s : words) count[s]++;
vector<Word> s;
for(auto it: count){
s.push_back((Word){it.first, it.second});
}
sort(s.begin(), s.end());
vector<string> res;
for(int i = 0; i < k; ++i) res.push_back(s[i].w);
return res;
}
};
10-18 38. Count and Say
Difficulty：Medium
Tutorial
For countAndSay(n), calculate countAndSay(n - 1) til n == 1 by DFS.
Accepted Code(T/M : 66%/89.76%)
class Solution {
public:
string countAndSay(int n) {
if(n == 1) return "1";
string pre = countAndSay(n - 1);
int cnt = 1;
string cur = "";
for(int i = 0; i < pre.size() - 1; ++i){
if(pre[i] == pre[i + 1]){
cnt++;
} else{
cur += getNum(cnt);
cur += pre[i];
cnt = 1;
}
}
cur += getNum(cnt);
cur += pre[pre.size() - 1];
return cur;
}
string getNum(int n){
string res = "";
while(n){
res += char(n % 10 + '0');
n /= 10;
}
reverse(res.begin(), res.end());
return res;
}
};
10-17 1832. Check if the Sentence Is Pangram
Difficulty：Easy
Tutorial
Accepted Code（T/M ：80.43%/100%）
class Solution {
public:
bool checkIfPangram(string sentence) {
int cnt = 0;
for(char c : sentence) cnt |= (1 << (c - 'a'));
return cnt == 67108863;
}
};
10-16 1335. Minimum Difficulty of a Job Schedule
Tutorial
It a very classic dp problem: split an array to dsubarrarys, minimize the sum of all subarray’s maximum number.
Usually, we use two-dimensional array dp to solve this kind of problem. dp[idx][d], idx represents current index, d represents we need to split the remaining arrary [idx, n] to d subarrarys. Enumerate the endpoints of first subarrary from idx to n, calculate best dp[endPoint + 1][d - 1]. With dfs, the last state we need to calculate is: get one subarray, make the max number minimum(dp[x][1]). When dfs returns, we could get dp[x - 1][2]. At last, we get dp[0][d], which is our answer.
To be clear: dp[idx][d] = min(dp[idx + 1][d - 1], dp[idx + 2][d - 1], dp[idx +3][d - 1], …… , dp[n][d - 1]). So we set invalid dp state to infinite to avoid affecting dp[idx][d].
Accepted Code(T/M : 88.85%/99.15%)
class Solution {
public:
int dp[305][15];
int dfs(int idx, int d, const vector<int> &job){
if(dp[idx][d] != -1) return dp[idx][d];
// have been calculated.
if(idx == job.size() && d == 0) return 0;
// dp[n][0] = 0
if(idx == job.size() || d == 0) return 0x3f3f3f3f;
//invalid, d is not 0, but job is splited over or remain d days to split, but no job.
if(job.size() - idx < d) return 0x3f3f3f3f;
//invalid, cannot split job[idx :] to d subarrays.
int m = job[idx], ans = 0x3f3f3f3f;
for(int i = idx; i < job.size(); ++i){
m = max(m, job[i]);
ans = min(ans, m + dfs(i + 1, d - 1, job));
// dp[idx][d] = maxJobDiff(idx, i) + dp[i + 1][d - 1];
}
dp[idx][d] = ans;
return ans;
}
int minDifficulty(vector<int>& job, int d) {
memset(dp, -1, sizeof(dp));
if(job.size() < d) return -1;
return dfs(0, d, job);
}
};
10-15 1531. String Compression II
Tutorial
Accepted Code
class Solution {
public:
int dp[101][101];
int N;
int getCodingLen(int l){
if(l == 1) return 1;
if(l <= 9) return 2;
if(l <= 99) return 3;
return 4;
}
int dfs(const string &s, int idx, int k){
if(k < 0) return N; //cannot delete any letter, return max len;
if(dp[idx][k] != -1) return dp[idx][k]; //have been calculated;
if(idx >= N or N - idx <= k) return 0; //delete all remain letters;
dp[idx][k] = N; //initiate dp
int maxCnt = 0; //declear maxCnt
int cnt[26] = {0}; //declear cnt to record each letters count in s[idx] -> s[i];
for(int i = idx; i < N; ++i){
maxCnt = max(maxCnt, ++cnt[s[i] - 'a']); //calculate maxCnt
dp[idx][k] = min(dp[idx][k], getCodingLen(maxCnt) + dfs(s, i + 1, k - (i - idx + 1 - maxCnt))); //after delete all letters(most commonly apperaed in s[idx]->s[i])
}
return dp[idx][k];
}
int getLengthOfOptimalCompression(string s, int k) {
N = s.size();
memset(dp, -1, sizeof(dp));
return dfs(s, 0, k);
}
};
10-14 2095. Delete the Middle Node of a Linked List
Difficulty：Medium
Tutorial
This type of problem’s most commonly solution is use two pointer, one is move faster than the other.
As for this problem, we need to move faster pointer 2 node per time, slower pointer move one by one. Only if the faster pointer could not move anymore, we stop the movement. At that time, the slower pointer is pointing to the previous node of middle node. And then change the next node of current node to be the next next node, the problem solved.
Accepted Code (T/M : 99.38%/64.88%)
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
ListNode *h = head;
if(head -> next == nullptr) return nullptr;
ListNode *fast = head -> next;
while(fast != nullptr && fast -> next != nullptr && fast -> next -> next != nullptr) {
head = head -> next;
fast = fast -> next -> next;
}
head -> next = head -> next -> next;
return h;
}
};
10-13 237. Delete Node in a Linked List
Difficulty：Medium
Tutorial
If We know the head node, we could traverse the linked list, if node->next->val == targetValue, then node->next = node->next->next.
But now we only know the targetNode we need to remove, so we could’n change the next pointer to remove given node. Cause answer check only check the value in the link list. We can move all the value after give node forward one node, and then, delete the last node.
process:
4 -> 5 -> 1 -> 9
4 -> 1 -> 1 -> 9
4 -> 1 -> 9 -> 9
4 -> 1 -> 9
Accepted Code(T/M: 44%/92%)
class Solution {
public:
void deleteNode(ListNode* node) {
while(node -> next -> next != nullptr) {
node -> val = node -> next -> val;
node = node -> next;
}
node -> val = node -> next -> val;
node -> next = nullptr;
}
};
10-12 976. Largest Perimeter Triangle
Difficulty：Easy
Tutorial
For a triangle, any two vertices’ sum should bigger than remain one.
So we sort all the numbers, and from big to small, check the smaller two numbers’ sum whether bigger than the biggest one. If so, this three number can form a triangle.
Accepted Code
class Solution {
public:
int largestPerimeter(vector<int>& nums) {
sort(nums.begin(), nums.end());
for(int i = nums.size() - 1; i - 2 >= 0; --i){
if(nums[i - 2] + nums[i - 1] <= nums[i]) continue;
return nums[i - 2] + nums[i - 1] + nums[i];
}
return 0;
}
};
10-11 334. Increasing Triplet Subsequence
Difficulty：Medium
Tutorial
Consider a very easy problem: Give you an array, find two element a and b, required a < b, if exist valid a and b, return true. else return false. To solve this question, we only need one variable a, if current element i smaller than a, assign i to a, else if i bigger than a, return true, after traverse the array, return false.
Back to this problem, before we return true(find valid a and b), we need another element c, c is smaller than a. if we could find valid c, the problem will be solved.
Now, If we find a valid c before find a and b, remain problem is exactly the same as the easy problem above. The different is, before we update a to be an smaller number, we need to be sure that new a is bigger than c.
Accepted Code
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if(nums.size() < 3) return false;
int c = INT_MAX, a = INT_MAX;
for(int i = 0; i < nums.size(); ++i){
if(nums[i] <= c) c = nums[i]; //update c first
else if(nums[i] <= a) a = nums[i]; //if nums[i] is bigger than c, but smaller than a, we could update a to nums[i], every time we update a to be a smaller number, the range of valid b is bigger.
else return true;
}
return false;
}
};
10-10 1328. Break a Palindrome
Difficulty：Medium
Tutorial
First of all, if palindrome’s length is 1, we could not make it not palindromic.
Secondly, If palindrome’s length is odd, we could not make it not palindromic by change the letter in the middle.
Otherwise, If we change any letter, the palindrome will not palindromic anymore.
For purpose, we need to break the palindrome and at the same time make it lexicographically smallest, we only need to change a valid letter(can change the palindromic) to be ‘a’, if we could’n find a valid letter, change the last letter to be ‘b’. Because at that time, all the valid letter is ‘a’, so the last letter must be ‘a’ also.
Accepted Code(100%, 45%)
class Solution {
public:
string breakPalindrome(string palindrome) {
if(palindrome.size() == 1) return "";
bool isEven = !(palindrome.size() % 2);
for(int i = 0; i < palindrome.size(); ++i){
if(palindrome[i] != 'a'){
if(!isEven && palindrome.size() / 2 == i) continue;
palindrome[i] = 'a';
return palindrome;
}
}
palindrome[palindrome.size() - 1] = 'b';
return palindrome;
}
};
10-09 653. Two Sum IV - Input is a BST
Difficulty：Easy
Tutorial
DFS this BST, and while searching, check whether exist value equal to target - currentRoot->val.
Accepted Code(92.29% / 98.68%)
class Solution {
public:
bool exist[30001];
bool findTarget(TreeNode* root, int k) {
if(root == nullptr) return false;
if(exist[k - root->val + 10000] == true) return true;
exist[root->val + 10000] = true;
return findTarget(root -> left, k) || findTarget(root->right, k);
}
};
10-08 16. 3Sum Closest
Difficulty：Medium
Tutorial
As we could see, if we use brute force to solve the problem, it need O(n3) time complexity, which is unacceptable. So at least, we need to improve time complexity to O(n2).
We consider another easier problem first: give a sorted array, find two numbers in array, which’s sum is closest to target. Because this array is sorted, if we use two pointers, l and r, l = 1, r = array.size(). For every time we move pointer, we could easily know: if move l to l + 1, will make current sum bigger, if move r to r - 1, will make current sum smaller. So if current sum is smaller than target, we should move l to l + 1 to make it bigger, vice versa. And after every time moving, we could check whether current sum is the closet sum to target. This approach’s time complexity is O(n).
Back to the origin problem. We only need to enumerate first number, and then the problem we need to solve is just exactly the same with the problem above. All time complexity is O(nlogn + n2).
Accepted Code
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ans = nums[0] + nums[1] + nums[2];
int n = nums.size();
for(int i = 0; i < n - 2; ++i){
int l = i + 1, r = n - 1;
int tans = nums[i] + nums[l] + nums[r];
while(l < r) {
if(check(tans, ans, target, &ans)) ;
if(check(tans - nums[r] + nums[r - 1], tans - nums[l] + nums[l + 1], target, &tans)) r--;
else l++;
}
}
return ans;
}
bool check(int n1, int n2, int target, int *ans) { //return true if n1 is closer than n2 to target.
if(abs(n1 - target) < abs(n2 - target)) {
*ans = n1;
return true;
}
*ans = n2;
return false;
}
};
10-07 732. My Calendar III
Tutorial
For every event, the range where it contribute to the answer, is [event, end - 1]. So we only need to record all event point, and then traverse all point, calculate current k event.
Accepted Code(6%/100%)
class MyCalendarThree {
public:
MyCalendarThree() {
}
int book(int start, int end) {
add(start, end);
return check();
}
private:
vector<int> ev;
inline void add(int s, int e){ //be invoked n times;
ev.push_back(s);
ev.push_back(-e);
sort(ev.begin(), ev.end(), [](int a, int b){ //O(nlogn);
if(abs(a) == abs(b)) return a < b; // to prevent after sorted, will turn up like: 50, -50
return abs(a) < abs(b);
});
return;
}
inline int check(){
int res = 0, cur = 0;
for(int i = 0; i < ev.size(); ++i){
cur += ev[i] < 0 ? -1 : 1;
res = max(res, cur);
}
return res;
}
};
10-06 981. Time Based Key-Value Store
Difficulty：Medium
Tutorial
Read the code
Accepted Code
class TimeMap {
public:
TimeMap() {
}
void set(string key, string value, int timestamp) {
mapKey2Time[key].insert(timestamp);
kv[key][timestamp] = value;
}
string get(string key, int timestamp) {
auto it = mapKey2Time[key].upper_bound(timestamp);
if(it == mapKey2Time[key].begin()) return "";
it--;
return kv[key][*it];
}
private:
unordered_map<string, ::set<int> > mapKey2Time;
unordered_map<string, unordered_map<int, string>> kv;
};
10-05 623. Add One Row to Tree
Difficulty：Medium
Tutorial
Observed this two examles, we could find that, add row in depth is to add two new TreeNode to all node which’s depth is depth - 1. And then, the right new node inherit father’s left subtree, right new node inherit father’s right subtree.
So We could Use DFS or BFS to find the target node, which’s depth is depth - 1.
Accepted Code With DFS(9.9%/98.26%)
class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int val, int depth) {
if(depth == 1) {
TreeNode *nRoot = new(TreeNode);
nRoot->val = val;
nRoot->left = root;
return nRoot;
}
addRow(root, 1, val, depth);
return root;
}
private:
void addRow(TreeNode* root, int currentDepth, int val, int depth){
if(root == nullptr) return;
if(currentDepth + 1 == depth) {
TreeNode *left = new(TreeNode);
left->left = root->left;
left->val = val;
TreeNode *right = new(TreeNode);
right->right = root->right;
right->val = val;
root->left = left, root->right = right;
return;
}
addRow(root->left, currentDepth+1, val, depth);
addRow(root->right, currentDepth+1, val, depth);
return;
}
};
Accepted Code With BFS(85.7%/16.59%)
class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int val, int depth) {
if(depth == 1) {
TreeNode *nRoot = new(TreeNode);
nRoot->val = val;
nRoot->left = root;
return nRoot;
}
NewNode *nroot = new(NewNode);
nroot->node = root;
nroot->dep = 1;
vector<TreeNode*> targetNode; //all the target depth TreeNode
queue<NewNode> q;
q.push(*nroot);
while(!q.empty()){
NewNode f = q.front(); q.pop();
if(f.dep + 1 == depth) {
targetNode.push_back(f.node);
}
else{
if(f.node->left != nullptr){
q.push((NewNode){f.node->left, f.dep+1});
}
if(f.node->right != nullptr){
q.push((NewNode){f.node->right, f.dep+1});
}
}
}
for(int i = 0; i < targetNode.size(); ++i){
TreeNode *r = targetNode[i];
TreeNode *left = new(TreeNode), *right = new(TreeNode);
left->val = right->val = val;
left->left = r->left;
right->right = r->right;
r->right = right;
r->left = left;
}
return root;
}
private:
struct NewNode{
TreeNode *node;
int dep;
};
};
10-04 112. Path Sum
Difficulty：Easy
Tutorial
Nothing to say, read the code.
Accepted Code (13ms, 21.6MB)
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
return solve(root, targetSum, 0);
}
bool solve(TreeNode *root, int t, int c) {
if(root == nullptr) return false;
if(root->left == nullptr && root->right == nullptr) return t == (c + root->val);
return solve(root->left, t, c + root->val) || solve(root->right, t, c + root->val);
}
};
10-03 1578. Minimum Time to Make Rope Colorful
Difficulty：Medium
Tutorial
Obviously, when some balloons have the same color and they are adjcent to each other, we need to remove all the ballon except the neededTime is minimum.
So for easily, we can use prioriy_queue to restore all the neededTime of adjcent ballons, and remove the minimum neededTime, then sum the remain neededTime.
Accepted Code 1(638 ms(5%), 106.6 MB(5%))
class Solution {
public:
int minCost(string colors, vector<int>& neededTime) {
int n = colors.size();
int sum = 0;
for(int i = 0; i < n - 1; ++i){
if(colors[i] == colors[i + 1]){
priority_queue<int> q;
while(i < n - 1 && colors[i] == colors[i + 1]) q.push(neededTime[i++]);
q.push(neededTime[i]);
q.pop();
while(!q.empty()) {
sum += q.top();
q.pop();
}
}
}
return sum;
}
};
First step improvement
In fact, we only need to know two variables, the adjcent ballons summation of neededTime and the maximum neededTime. So we don’t really need to use priority_queeu to do that. just calculate this two variables by ourself.
First Step Improvement Accepted Code(159 ms(95%), 95.4MB(84%))
class Solution {
public:
int minCost(string colors, vector<int>& neededTime) {
int ans = 0;
int l = 0, r = 1;
int sum = 0, maxT = 0;
int n = colors.size();
if(n == 1) return 0;
while(r < n){
maxT = neededTime[l];
sum = maxT;
while(colors[l] == colors[r]){
maxT = max(maxT, neededTime[r]);
sum += neededTime[r];
r++;
}
if(r - l == 1){ //eg: abc, l = 0, r = 1, don't need to remove any ballon.
++l;
++r; //move to next ballon;
}
else { //eg: aabaa, [-1,2,3,4,1]; l = 0, r = 2, sum = 1 + 2 = 3, maxT = 2, need to remove 1 ballon.
ans += sum - maxT;
l = r++;
}
}
return ans;
}
};
Second step improvement
This step is not to improve the efficiency of the code. Just improve the code beauty.
We can learn from the idea of bubble-sorting, make the maximum neededTime to the last position, and in process, we sum the other neededTime.
Second step Accepted Code(156 ms(96%), 95.5 MB(50%))
class Solution {
public:
int minCost(string colors, vector<int>& neededTime) {
int ans = 0;
int n = colors.size();
for (int i = 0; i + 1 < colors.size(); i++) {
if (colors[i] == colors[i + 1]) {
if (neededTime[i] > neededTime[i + 1]) {
ans += neededTime[i + 1]; //add smaller time
neededTime[i + 1] = neededTime[i]; //bubble;
}
else ans += neededTime[i];
}
}
return ans;
}
};
10-02 1155. Number of Dice Rolls With Target Sum
Difficulty：Medium
Tutorial
Obviously we need to us dp to solve this problem.
Define a two-dimensional array dp, dp[i][j] means, the count of ways that if we use i dice to get sum j. So the transfer equation of dp[i][j] is: the sum of the dp[i - 1][j - k], k means ith dice’s number. The equation’s meaning is if we use i dice, and we have know all count of ways that if we use i-1 dice to get targets, current dice face-up number is k, so the dp[i][j] must be dp[i - 1][j - k]’s sum.
C++ Accepted Code(43ms, 6MB)
class Solution {
public:
int dp[31][1001]; // dp[i][j] = x, used i dices, get sum j, have x ways;
int mod;
int numRollsToTarget(int n, int k, int target) {
mod = 1e9 + 7;
dp[0][0] = 1;
for(int i = 1; i <= n; ++i){
for(int x = 1; x <= target; ++x){
for(int j = 1; j <= k; ++j){
if(j > x) break; //invalid;
dp[i][x] += dp[i - 1][x - j];
dp[i][x] %= mod;
}
}
}
return dp[n][target];
}
};
Improve1:
As we can see, In above code, we only use dp[i] and dp[i - 1], this 2 array, so we can optimize other space, only use dp[2][target]. Detail to see code below.
C++ Accepted Code(51ms, 5.9MB(99%))
class Solution {
public:
int dp[2][1001];
int mod;
int numRollsToTarget(int n, int k, int target) {
mod = 1e9 + 7;
dp[0][0] = 1;
for(int i = 1; i <= n; ++i){
for(int x = 1; x <= target; ++x){
for(int j = 1; j <= k; ++j){
if(j > x) break; //invalid;
dp[i & 1][x] += dp[!(i & 1)][x - j];
dp[i & 1][x] %= mod;
}
}
memset(dp[!(i & 1)], 0, sizeof(dp[!(i & 1)]));
}
return dp[n & 1][target];
}
};
Improve2:
In the third loop, we calculate dp[i & 1][x] asdp[i & 1][x] += dp[!(i&1)][x - j], is very similar to another thing: the prefix sum. If we record the dp[i][x - 1] + dp[i][x - 2] + ...... + dp[i][x - k] as sum[i][x - 1], we could calculate dp[i + 1][x] which is the sum of dp[i][x- 1], dp[i][x - 2], ......, dp[x - k] very fast.
So the improve way is to calculate sum[i][x]. The same as dp, we only need to use two array to record sum, sum[i][x] means dp[i][x] + dp[i][x - 1] + ..... + dp[i][x - k + 1]. When x is biger than k, sum[i][x] = sum[i][x - 1] - dp[i][x - 1 - k] + dp[i][x], otherwise sum[i][x] = sum[i][x - 1] + dp[i][x];
Just remember the defination of dp and sum, and you can easily understand the code below.
Previously: dp[i][j] = x, means we can use x ways to get the sum of all dice’s face-up number to j with i dice. sum[i][j] = x, means the sum of dp[i][j], dp[i][j - 1], ......, dp[i][j - k + 1].
C++ Accepted Code(7ms(98%), 6MB(97%))
class Solution {
public:
int dp[2][1001];
int mod;
int sum[2][1001];
int numRollsToTarget(int n, int k, int target) {
mod = 1e9 + 7;
dp[0][0] = 1;
for(int i = 0; i < k; ++i) sum[0][i] = 1;
for(int i = 1; i <= n; ++i){
for(int x = 1; x <= target; ++x){
dp[(i & 1)][x] = sum[!(i & 1)][x - 1];
if(x >= k) sum[i & 1][x] = (sum[i & 1][x - 1] - dp[i & 1][x - k] + mod) % mod + dp[i & 1][x];
else sum[i & 1][x] = sum[i & 1][x - 1] + dp[i & 1][x];
sum[i & 1][x] %= mod;
dp[i & 1][x] %= mod;
}
memset(dp[!(i & 1)], 0, sizeof(dp[!(i & 1)]));
memset(sum[!(i & 1)], 0, sizeof(sum[!(i & 1)]));
}
return dp[n & 1][target];
}
};
10-01 91. Decode Ways
Difficulty：Medium
Tutorial
If We could only format single digit to letter (except digit 0), the answer will be 1. So the only way to increse the answer is we combine two digits for decoding a letter.
We traverse the string, define dp[i] means end with s[i - 1], we will get dp[i] ways to decode the string, for easy, we transfer dp[i] to dp[i + 1]. Like said above, if we just use one digit to decode, we won’t get new answer. So if s[i] is not ‘0’, dp[i + 1] is equal to dp[i]. If s[i] is ‘0’, dp[i + 1] is 0, because we cannot decode ‘0’ to any letter. Meanwhile, for every i (i > 0), we could check whether s[i - 1, i] is an valid digit string to decode to a single letter, if so, we could let dp[i + 1] add dp[i - 1].
By this logic, evertime s[i - 1] and s[i +1] can be combined to decode a letter, the answer increase.
C++ Accepted Code1:(4ms, 6.2MB)
class Solution {
public:
int dp[105];
int numDecodings(string s) {
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(int i = 0; i < s.size(); ++i){
if(s[i] != '0') dp[i + 1] = dp[i];
if(i > 0 && (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6')) dp[i + 1] += dp[i - 1];
printf("dp[%d] = %d\n", i, dp[i]);
}
return dp[s.size()];
}
};
If you carefully look this code, you will find that, although we use dp to cal the answer, we only need to use dp[i], dp[i - 1], and dp[i + 1], which means we only need three avariables. So we can Smplify this code to the below one:
C++ Accepted Code2:(0ms, 6MB)
class Solution {
public:
int numDecodings(string s) {
int fi = 0, se = 1;
int cur = 0;
for(int i = 0; i < s.size(); ++i){
cur = 0;
if(s[i] != '0') cur = se;
if(i > 0 && (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6')) cur += fi;
fi = se, se = cur;
}
return cur;
}
};