LeetCode Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

1
/ \
2   3

Output: 6


Example 2:

Input: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

Output: 42

• 仅包含节点本身（当左、右、父亲节点的路径和都是负数时）
• 穿过该节点，且还会往该节点的父亲上面走，说明最优路径的跟在该节点上面，该节点的左子树或右子树路径构成了最优路径的一部分
• 没有穿过该节点，即该节点为最优路径的跟，则路径的两端可能是该节点的左右孩子

class Solution {
public:
int maxSum(TreeNode *root, int &ans) {
if (root == NULL)return 0;
int left_sum = maxSum(root->left, ans), right_sum = maxSum(root->right, ans);

// 经过root节点的子树，还得往root的父亲上面走
int left_or_right_root = max(root->val, root->val + max(left_sum, right_sum));

// 最后一项是以root为根，左右子树都走，即不往root的父亲上面走
ans = max(ans, max(left_or_right_root, root->val + left_sum + right_sum));

return left_or_right_root;
}
int maxPathSum(TreeNode* root) {
int ans = INT_MIN;
maxSum(root, ans);
return ans;
}
};

LeetCode First Unique Number

LeetCode First Unique Number

You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

• FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
• int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
• void add(int value) insert value to the queue.

Example 1:

Input:
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:


[null,2,null,2,null,3,null,-1]

Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2);            // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 firstUnique.add(3);            // the queue is now [2,3,5,5,2,3] firstUnique.showFirstUnique(); // return -1

Example 2:

Input:
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output:


[null,-1,null,null,null,null,null,17]

Explanation: FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]); firstUnique.showFirstUnique(); // return -1 firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7] firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3] firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3] firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7] firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17] firstUnique.showFirstUnique(); // return 17

Example 3:

Input:
[[[809]],[],[809],[]]
Output:


[null,809,null,-1]

Explanation: FirstUnique firstUnique = new FirstUnique([809]); firstUnique.showFirstUnique(); // return 809 firstUnique.add(809); // the queue is now [809,809] firstUnique.showFirstUnique(); // return -1

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^8
• 1 <= value <= 10^8
• At most 50000 calls will be made to showFirstUnique and add.

class FirstUnique {
private:
list<int> uniques_;
unordered_map<int, list<int>::iterator> hash;
public:
FirstUnique(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
}
}

int showFirstUnique() {
if (uniques_.empty())return -1;
else return uniques_.front();
}

if (hash.find(value) == hash.end()) {
uniques_.push_back(value);
hash[value] = --uniques_.end();
}
else {
if (hash[value] != uniques_.end()) {
uniques_.erase(hash[value]);
hash[value] = uniques_.end();
}
}
}
};

LeetCode Diagonal Traverse II

1424. Diagonal Traverse II

Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]


Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]


Example 3:

Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]]
Output: [1,4,2,5,3,8,6,9,7,10,11]


Example 4:

Input: nums = [[1,2,3,4,5,6]]
Output: [1,2,3,4,5,6]


Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i].length <= 10^5
• 1 <= nums[i][j] <= 10^9
• There at most 10^5 elements in nums.

bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) {
int sum1 = p1.first + p1.second, sum2 = p2.first + p2.second;
if (sum1 == sum2) {
return p1.first > p2.first;
}
else {
return sum1 < sum2;
}
}
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
vector<pair<int, int>> idxs;
for (int i = 0; i < nums.size(); ++i) {
for (int j = 0; j < nums[i].size(); ++j) {
idxs.push_back(make_pair(i, j));
}
}
sort(idxs.begin(), idxs.end(), cmp);
vector<int> ans;
for (int i = 0; i < idxs.size(); ++i) {
ans.push_back(nums[idxs[i].first][idxs[i].second]);
}
return ans;
}
};

LeetCode Maximum Points You Can Obtain from Cards

1423. Maximum Points You Can Obtain from Cards

There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.


Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.


Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.


Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1.


Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202


Constraints:

• 1 <= cardPoints.length <= 10^5
• 1 <= cardPoints[i] <= 10^4
• 1 <= k <= cardPoints.length

class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
int sum = 0, n = cardPoints.size();
for (int i = 0; i < n; ++i)sum += cardPoints[i];
if (k == n)return sum;

int min_window_sum = 0, i = 0, j = n - k - 1;
for (int k = i; k <= j; ++k)min_window_sum += cardPoints[k];
int cur_window_sum = min_window_sum;
while (j < n) {
if (j == n - 1)break;
cur_window_sum = cur_window_sum + cardPoints[++j] - cardPoints[i++];
min_window_sum = min(min_window_sum, cur_window_sum);
}
return sum - min_window_sum;
}
};

LeetCode Longest Common Subsequence

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.


Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.


Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.


Constraints:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• The input strings consist of lowercase English characters only.

class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
int a = dp[i - 1][j], b = dp[i][j - 1], c = dp[i - 1][j - 1];
if (text1[i - 1] == text2[j - 1])++c;
dp[i][j] = max(max(a, b), c);
}
}
return dp[m][n];
}
};


LeetCode Maximum Score After Splitting a String

1422. Maximum Score After Splitting a String

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

Input: s = "011101"
Output: 5
Explanation:
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5
left = "01" and right = "1101", score = 1 + 3 = 4
left = "011" and right = "101", score = 1 + 2 = 3
left = "0111" and right = "01", score = 1 + 1 = 2
left = "01110" and right = "1", score = 2 + 1 = 3


Example 2:

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5


Example 3:

Input: s = "1111"
Output: 3


Constraints:

• 2 <= s.length <= 500
• The string s consists of characters ‘0’ and ‘1’ only.

class Solution {
public:
int maxScore(string s) {
int n = s.size();
vector<int> zeros(n, 0), ones(n, 0);
for (int i = 0; i < n - 1; ++i) {
if (i == 0)zeros[i] = (s[i] == '0' ? 1 : 0);
else zeros[i] = zeros[i - 1] + (s[i] == '0' ? 1 : 0);

int j = n - i - 1;
if (j == n - 1)ones[j] = (s[j] == '1' ? 1 : 0);
else ones[j] = ones[j + 1] + (s[j] == '1' ? 1 : 0);
}
int ans = 0;
for (int i = 0; i < n - 1; ++i) {
ans = max(ans, zeros[i] + ones[i + 1]);
}
return ans;
}
};

LeetCode Leftmost Column with at Least a One

LeetCode Leftmost Column with at Least a One

(This problem is an interactive problem.)

A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn’t exist, return -1.

You can’t access the Binary Matrix directly.  You may only access the matrix using a BinaryMatrix interface:

• BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed).
• BinaryMatrix.dimensions() returns a list of 2 elements [m, n], which means the matrix is m * n.

Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer.  Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes you’re given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Example 1:

Input: mat = [[0,0],[1,1]]
Output: 0


Example 2:

Input: mat = [[0,0],[0,1]]
Output: 1


Example 3:

Input: mat = [[0,0],[0,0]]
Output: -1

Example 4:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1


Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• mat[i][j] is either 0 or 1.
• mat[i] is sorted in a non-decreasing way.

class Solution {
public:
int LeftMost(BinaryMatrix &binaryMatrix, int row, int m, int n) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
int midv = binaryMatrix.get(row, mid);
if (midv == 0)l = mid + 1;
else r = mid - 1;
}
return r + 1;
}
int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
vector<int> dim = binaryMatrix.dimensions();
int m = dim[0], n = dim[1];
int ans = n;
for (int i = 0; i < m; ++i) {
ans = min(ans, LeftMost(binaryMatrix, i, m, n));
}
if (ans == n)return -1;
else return ans;
}
};

hint还提示了另一种解法，从矩阵的右上角开始，遇到0则往下走，遇到1则往左走。因为如果是1的话，至少当前所在列是包含1的，也许还可以再往左试探一下，而如果是0的话，只能往下走了。这种方法极端情况下可能从矩阵的右上角走到左下角，时间复杂度为O(m+n)。完整代码如下：

class Solution {
public:

int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
vector<int> dim = binaryMatrix.dimensions();
int m = dim[0], n = dim[1];
int x = 0, y = n - 1;
int ans = n;
while (x < m&&y >= 0) {
int val = binaryMatrix.get(x, y);
if (val == 0)++x;
else if (val == 1) {
ans = y;
if (y - 1 >= 0 && binaryMatrix.get(x, y - 1) == 1) {
--y;
ans = y;
}
else ++x;
}
}
if (ans == n)return -1;
else return ans;
}
};


LeetCode Construct Binary Search Tree from Preorder Traversal

1008. Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val.  Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]



Note:

1. 1 <= preorder.length <= 100
2. The values of preorder are distinct.

class Solution {
public:
TreeNode* Work(vector<int> &preorder, int l, int r) {
if (l > r)return NULL;
if (l == r)return new TreeNode(preorder[l]);
TreeNode *root = new TreeNode(preorder[l]);
int mid = -1;
for (int i = l; i <= r; ++i) {
if (preorder[i] > root->val) {
mid = i;
break;
}
}
if (mid == -1)root->left = Work(preorder, l + 1, r);
else {
root->left = Work(preorder, l + 1, mid - 1);
root->right = Work(preorder, mid, r);
}
return root;
}
TreeNode* bstFromPreorder(vector<int>& preorder) {
return Work(preorder, 0, preorder.size() - 1);
}
};

LeetCode Minimum Number of Frogs Croaking

Given the string croakOfFrogs, which represents a combination of the string “croak” from different frogs, that is, multiple frogs can croak at the same time, so multiple “croak” are mixed. Return the minimum number of different frogs to finish all the croak in the given string.

A valid “croak” means a frog is printing 5 letters ‘c’, ’r’, ’o’, ’a’, ’k’ sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of valid “croak” return -1.

Example 1:

Input: croakOfFrogs = "croakcroak"
Output: 1
Explanation: One frog yelling "croak" twice.


Example 2:

Input: croakOfFrogs = "crcoakroak"
Output: 2
Explanation: The minimum number of frogs is two.
The first frog could yell "crcoakroak".
The second frog could yell later "crcoakroak".


Example 3:

Input: croakOfFrogs = "croakcrook"
Output: -1
Explanation: The given string is an invalid combination of "croak" from different frogs.


Example 4:

Input: croakOfFrogs = "croakcroa"
Output: -1


Constraints:

• 1 <= croakOfFrogs.length <= 10^5
• All characters in the string are: 'c''r''o''a' or 'k'.

class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
map<char, char> pre = { {'r','c'},{'o','r'},{'a','o'},{'k','a'} };
vector<vector<char>> ans;
map<char, int> count;
for (int i = 0; i < croakOfFrogs.size(); ++i) {
int letter = croakOfFrogs[i];
++count[letter];
if (!(count['c'] >= count['r'] && count['r'] >= count['o'] && count['o'] >= count['a'] && count['a'] >= count['k']))return -1;
if (letter == 'c') {
if (ans.empty()) {
ans.push_back({ 'c' });
}
else {
bool found = false;
for (int j = 0; j < ans.size(); ++j) {
if (ans[j].empty()) {
ans[j].push_back('c');
found = true;
break;
}
}
if (!found) {
ans.push_back({ 'c' });
}
}
}
else {
if (ans.empty())return -1;
else {
bool found = false;
for (int j = 0; j < ans.size(); ++j) {
if (!ans[j].empty() && ans[j].back() == pre[letter]) {
ans[j].push_back(letter);
found = true;
if (letter == 'k')ans[j].clear();
break;
}
}
if (!found)return -1;
}
}
}

for (int j = 0; j < ans.size(); ++j) {
if (!ans[j].empty())return -1;
}

return ans.size();
}
};

class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
int n = croakOfFrogs.size();
map<char, int> count;
int free = 0, ans = 0;
for (int i = 0; i < croakOfFrogs.size(); ++i) {
char letter = croakOfFrogs[i];
++count[letter];
if (!(count['c'] >= count['r'] && count['r'] >= count['o'] && count['o'] >= count['a'] && count['a'] >= count['k']))return -1;
if (letter == 'c'&&free == 0) {
++ans;
}
else if (letter == 'c'&&free > 0) {
--free;
}
else if (letter == 'k') {
++free;
}
}
if (count['c'] != count['k'])return -1;
return ans;
}
};


LeetCode Display Table of Food Orders in a Restaurant

Given the array orders, which represents the orders that customers have done in a restaurant. More specifically orders[i]=[customerNamei,tableNumberi,foodItemi] where customerNamei is the name of the customer, tableNumberi is the table customer sit at, and foodItemi is the item customer orders.

Return the restaurant’s “display table. The “display table” is a table whose row entries denote how many of each food item each table ordered. The first column is the table number and the remaining columns correspond to each food item in alphabetical order. The first row should be a header whose first column is “Table”, followed by the names of the food items. Note that the customer names are not part of the table. Additionally, the rows should be sorted in numerically increasing order.

Example 1:

Input: orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]
Output: [["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]]
Explanation:
The displaying table looks like:
Table,Beef Burrito,Ceviche,Fried Chicken,Water
3    ,0           ,2      ,1            ,0
5    ,0           ,1      ,0            ,1
10   ,1           ,0      ,0            ,0
For the table 3: David orders "Ceviche" and "Fried Chicken", and Rous orders "Ceviche".
For the table 5: Carla orders "Water" and "Ceviche".
For the table 10: Corina orders "Beef Burrito".


Example 2:

Input: orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]]
Explanation:
For the table 12: James, Ratesh and Amadeus order "Fried Chicken".


Example 3:

Input: orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]
Output: [["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]


Constraints:

• 1 <= orders.length <= 5 * 10^4
• orders[i].length == 3
• 1 <= customerNamei.length, foodItemi.length <= 20
• customerNamei and foodItemi consist of lowercase and uppercase English letters and the space character.
• tableNumberi is a valid integer between 1 and 500.

class Solution {
public:
vector<vector<string>> displayTable(vector<vector<string>>& orders) {
vector<map<string, int>> tables(501, map<string, int>());
set<string> allfoods;
for (int i = 0; i < orders.size(); ++i) {
string name = orders[i][0], tb = orders[i][1], food = orders[i][2];
int ntb = stoi(tb.c_str());
++tables[ntb][food];
allfoods.insert(food);
}
vector<vector<string>> ans;
for (set<string>::iterator it = allfoods.begin(); it != allfoods.end(); ++it)header.push_back(*it);
for (int i = 1; i <= 500; ++i) {
vector<string> cur;
if (tables[i].size() > 0) {
cur.push_back(to_string(i));
for (set<string>::iterator it = allfoods.begin(); it != allfoods.end(); ++it) {
cur.push_back(to_string(tables[i][*it]));
}
ans.push_back(cur);
}
}
return ans;
}
};