Given a binary tree root and a linked list with head as the first node.
Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.
In this context downward path means a path that starts at some node and goes downwards.
Example 1:
Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.
Example 2:
Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Example 3:
Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.
Constraints:
1 <= node.val <= 100 for each node in the linked list and binary tree.
The given linked list will contain between 1 and 100 nodes.
The given binary tree will contain between 1 and 2500 nodes.
LeetCode Shopping Offers
In LeetCode Store, there are some kinds of items to sell. Each item has a price.
However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.
Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.
You could use any of special offers as many times as you want.
Example 1:
Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.
Example 2:
Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation:
The price of A is $2, and $3 for B, $4 for C.
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C.
You cannot add more items, though only $9 for 2A ,2B and 1C.
Note:
There are at most 6 kinds of items, 100 special offers.
For each item, you need to buy at most 6 of them.
You are not allowed to buy more items than you want, even if that would lower the overall price.
给定每个商品的单价和需要购买的数量，并且有一些special offer，相当于捆绑销售的优惠套餐。问刚好买到给定数量的商品，所花的最低费用是多少。
注意给定的限制条件中商品最多只有6种，且每件最多只购买6件，所以可以考虑用暴力方法。
把special offer看成一个背包问题里的“商品”，对于每个special offer，我们有两种选择，可以用或者不用。如果需要的needs数组每一项都大于等于某个special offer的每一项，即可以用该special offer，我们比较用和不用该special offer的最终花费，取花费低的。如果用该special offer，则needs数组需要减掉sp捆绑的每件商品的件数，然后继续递归该sp是否可用，相当于完全背包，不计件数的。如果该sp不能用，则递归考虑下一个sp。最后如果递归考虑完所有sp了，则剩余的商品只能按原价购买，算出按原价购买的费用即可。
完整代码如下：
[cpp]
class Solution {
private:
int dot(vector<int>& price, vector<int>& needs) {
int ans = 0;
for (int i = 0; i < needs.size(); ++i) {
ans += price[i] * needs[i];
}
return ans;
}
int shopping(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int idx) {
if (idx == special.size())return dot(price, needs); // 原价购买
int i = 0, n = special[idx].size();
vector<int> small_needs = needs;
for (i = 0; i < n – 1; ++i) {
if (special[idx][i] > needs[i])break;
small_needs[i] -= special[idx][i];
}
if (i == n – 1)return min(shopping(price, special, small_needs, idx) + special[idx][n – 1], shopping(price, special, needs, idx + 1));
else return shopping(price, special, needs, idx + 1);
}
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
return shopping(price, special, needs, 0);
}
};
[/cpp]
本代码提交AC，用时6MS。
参考：https://leetcode.com/articles/shopping-offers/，下次记得看到这种数据量非常小的题，首先尝试暴力方法！]]>
LeetCode Range Sum Query – Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Example:
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Explanation:
Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
vector<vector<int> > dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
class Solution {
private:
int m, n;
bool isOk(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; }
void dfs(vector<vector<char> >& board, int x, int y)
{
board[x][y] = ‘1’;
for (int i = 0; i < dirs.size(); ++i) {
int u = x + dirs[i][0], v = y + dirs[i][1];
if (isOk(u, v) && board[u][v] == ‘O’)
dfs(board, u, v);
}
}
public:
void solve(vector<vector<char> >& board)
{
if (board.empty() || board[0].empty())
return;
m = board.size(), n = board[0].size();
for (int i = 0; i < m; ++i) {
if (board[i][0] == ‘O’)
dfs(board, i, 0);
if (board[i][n – 1] == ‘O’)
dfs(board, i, n – 1);
}
for (int j = 0; j < n; ++j) {
if (board[0][j] == ‘O’)
dfs(board, 0, j);
if (board[m – 1][j] == ‘O’)
dfs(board, m – 1, j);
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == ‘O’)
board[i][j] = ‘X’;
else if (board[i][j] == ‘1’)
board[i][j] = ‘O’;
}
}
}
};
LeetCode Design Excel Sum Formula
Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions:
Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from ‘A’ to ‘Z’. It represents that the width is the number of characters from ‘A’ to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from ‘A’.
void Set(int row, char column, int val): Change the value at C(row, column) to be val.
int Get(int row, char column): Return the value at C(row, column).
int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula.
numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, “F7” represents the cell at (7, F).
If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.
Example 1:
Excel(3,"C");
// construct a 3*3 2D array with all zero.
// A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0
Set(1, "A", 2);
// set C(1,"A") to be 2.
// A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0
Sum(3, "C", ["A1", "A1:B2"]);
// set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4.
// A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4
Set(2, "B", 2);
// set C(2,"B") to be 2. Note C(3, "C") should also be changed.
// A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6
Note:
You could assume that there won’t be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
The test cases are using double-quotes to represent a character.
Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.
LeetCode Mini Parser
Given a nested list of integers represented as a string, implement a parser to deserialize it.
Each element is either an integer, or a list — whose elements may also be integers or other lists.
Note: You may assume that the string is well-formed:
String is non-empty.
String does not contain white spaces.
String contains only digits 0-9, [, -,, ].
Example 1:
Given s = "324",
You should return a NestedInteger object which contains a single integer 324.
Example 2:
Given s = "[123,[456,[789]]]",
Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
i. An integer containing value 456.
ii. A nested list with one element:
a. An integer containing value 789.
给定一个嵌套的字符串，要求把它解析成一个NestedInteger。
解法1，使用栈。遇到左括号时，增加一个空的NestedInteger实例，压栈。遇到逗号时，把前面的数add到栈顶的NestedInteger中。遇到右括号时，把栈顶的NestedInteger弹栈，并add到新的栈顶（相当于前一个）NestedInteger中。最后栈顶只有一个元素，返回该元素即可。
代码如下：
[cpp]
class Solution {
public:
NestedInteger deserialize(string s) {
auto isnumber = [](char c) {return c == ‘-‘ || isdigit(c); };
stack<NestedInteger> stk;
stk.push(NestedInteger());
for (auto it = s.begin(); it != s.end();) {
if (isnumber(*it)) {
auto it2 = find_if_not(it, s.end(), isnumber);
int v = stoi(string(it, it2));
stk.top().add(NestedInteger(v));
it = it2;
}
else {
if (*it == ‘[‘) {
stk.push(NestedInteger());
}
else if (*it == ‘]’) {
NestedInteger tmp = stk.top();
stk.pop();
stk.top().add(tmp);
}
++it;
}
}
return stk.top().getList().front();
}
};
[/cpp]
本代码提交AC，用时19MS。
解法2，递归法。如果当前的字符串是一个裸的整数的话，类似于样例1，则直接返回以该数为参数的NestedInteger；否则剥掉左括号[，递归反序列化，把递归的结果add到当前的NestedInteger中。
代码如下：
[cpp]
class Solution {
private:
NestedInteger deserialize(istringstream &in) {
int number;
if (in >> number)
return NestedInteger(number);
in.clear();
in.get();
NestedInteger list;
while (in.peek() != ‘]’) {
list.add(deserialize(in));
if (in.peek() == ‘,’)in.get();
}
in.get();
return list;
}
public:
NestedInteger deserialize(string s) {
istringstream in(s);
return deserialize(in);
}
};
[/cpp]
本代码提交AC，用时19MS。
参考1，栈：https://discuss.leetcode.com/topic/54904/c-non-recursive-one-pass-solution-using-stack-a-possible-implementation-of-nestedinteger
参考2，递归：https://discuss.leetcode.com/topic/54258/python-c-solutions/10]]>
LeetCode Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
给定一棵二叉树和两个节点p,q，问p和q的最近公共祖先节点是哪个。LCA问题。
思路：要找p和q的最近公共祖先，很直观的方法是找到从根节点分别到p和q的路径，然后把其中一条路径（比如根到p）上的点hash成path1，从另一条路径（比如根到q）的底端（q）往根节点走，把走过的每个点去path1中找，如果找到，则就是他们的LCA，因为这是距离q最近、且在path1中的点。
但是怎样找到根到p和q的路径呢。这里换一种思路，定义如下新的数据结构，par表示该节点的父节点，根节点的父节点为-1。
[cpp]
struct MyNode {
TreeNode* node;
int par;
MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
};
[/cpp]
先整体把树层次遍历一遍，成为一个保存MyNode的数组，记录每个点的父节点在数组中的下标。在遍历的同时，记录下p和q节点的下标。这样通过下标往前递归就可以找到p和q到根节点的路径了。
找到路径之后，对其中一条路径hash，另一条路径在该hash中找。代码如下：
[cpp]
class Solution {
private:
struct MyNode {
TreeNode* node;
int par;
MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
};
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<MyNode> nodes;
int i = 0, j = 0;
queue<MyNode> tree;
tree.push({ root,-1 });
while (!tree.empty()) {
MyNode cur = tree.front();
tree.pop();
if (cur.node == NULL) continue;
if (cur.node == p)i = nodes.size();
if (cur.node == q)j = nodes.size();
tree.push({ cur.node->left,nodes.size() });
tree.push({ cur.node->right,nodes.size() });
nodes.push_back(cur);
}
if (i == j)return nodes[i].node;
unordered_set<int> path1;
while (i != -1) {
path1.insert(i);
i = nodes[i].par;
}
while (j != -1) {
if (path1.find(j) != path1.end()) {
return nodes[j].node;
}
j = nodes[j].par;
}
return NULL;
}
};
[/cpp]
本代码提交AC，用时19MS。
讨论区还有一种递归的解法，很有意思。我们在以root为根的树中找p和q的LCA，如果root等于p或q其中之一，说明p或q就是他们的LCA。否则分别在左子树和右子树中递归的找LCA，如果发现在左右子树中找到的LCA都不为null，说明他们p和q分别位于root的两个子树，类似样例中的5和1，则root就是他们的LCA。如果某个子树返回的LCA为空，说明p和q都不在这个子树中，则先遇到谁，谁就是LCA，比如样例中的5和4，都不在3的右子树，在递归3的左子树的时候，先遇到了5，所以5是LCA。
完整代码如下：
[cpp]
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || root == p || root == q)return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL&&right != NULL)return root;
return left != NULL ? left : right;
}
};
[/cpp]
本代码提交AC，用时23MS。]]>
LeetCode Merge Two Binary Trees
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Example 1:
LeetCode Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
"bbbab"
Output:
4
One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input:
"cbbd"
Output:
2
One possible longest palindromic subsequence is “bb”.
求一个字符串的最长回文子序列。
使用DP求解，假设dp[i][j]表示原字符串范围[i,j]中的最长回文子序列的长度。则如果s[i]==s[j]，则dp[i][j]=dp[i+1][j-1]+2，即是临近内层的最长回文子序列长度加2。如果s[i]!=s[j]，则dp[i][j]=max(dp[i][j-1],dp[i+1][j])，即是左端或者右端最长回文子序列长度的最大值。
初始时dp[i][i]=1，即单个字符自成回文，长度为1。
代码如下：
[cpp]
class Solution2 {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = n – 1; i >= 0; –i) {
dp[i][i] = 1;
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j])dp[i][j] = dp[i + 1][j – 1] + 2;
else dp[i][j] = max(dp[i][j – 1], dp[i + 1][j]);
}
}
return dp[0][n – 1];
}
};
[/cpp]
本代码提交AC，用时68MS。
上述计算有些区间会重复计算dp[i][j]，可以用递归方法求解，并且把计算过的值记录下来，下次遇到查询时直接返回。代码如下：
[cpp]
class Solution {
private:
int helper(int l, int r, const string &s, vector<vector<int>> &dp) {
if (l > r)return 0;
if (l == r)return 1;
if (dp[l][r] != 0)return dp[l][r];
if (s[l] == s[r])dp[l][r] = helper(l + 1, r – 1, s, dp) + 2;
else dp[l][r] = max(helper(l, r – 1, s, dp), helper(l + 1, r, s, dp));
return dp[l][r];
}
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
return helper(0, n – 1, s, dp);
}
};
[/cpp]
本代码提交AC，用时49MS。
参考：https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution/2]]>
