# LeetCode Shopping Offers

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:

1. There are at most 6 kinds of items, 100 special offers.
2. For each item, you need to buy at most 6 of them.
3. You are not allowed to buy more items than you want, even if that would lower the overall price.

```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);
}
};
```

# LeetCode Range Sum Query - Mutable

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 nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
```

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

```class NumArray {
private:
struct Node {
int start, end, sum;
Node *left, *right;
Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {};
};
Node *root;
Node* constructTree(vector<int> &nums, int start, int end) {
Node* node = new Node(start, end);
if (start == end) {
node->sum = nums[start];
return node;
}
int mid = start + (end - start) / 2;
node->left = constructTree(nums, start, mid);
node->right = constructTree(nums, mid + 1, end);
node->sum = node->left->sum + node->right->sum;
return node;
}
int sumRange(int i, int j, Node *root) {
if (root == NULL)return 0;
if (i == root->start&&j == root->end)return root->sum;
int mid = root->start + (root->end - root->start) / 2;
if (j <= mid)return sumRange(i, j, root->left);
else if (i > mid)return sumRange(i, j, root->right);
else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right);
}
void update(int i, int val, Node *root) {
if (root->start == root->end && root->start == i) {
root->sum = val;
return;
}
int mid = root->start + (root->end - root->start) / 2;
if (i <= mid)update(i, val, root->left);
else update(i, val, root->right);
root->sum = root->left->sum + root->right->sum;
}
public:
NumArray(vector<int> nums) {
root = NULL;
if (!nums.empty())root = constructTree(nums, 0, nums.size() - 1);
}
void update(int i, int val) {
if (root == NULL)return;
update(i, val, root);
}
int sumRange(int i, int j) {
if (root == NULL)return 0;
return sumRange(i, j, root);
}
};
```

# LeetCode Surrounded Regions

LeetCode Surrounded Regions
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.
For 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```

```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], v = y + dirs[i];
if (isOk(u, v) && board[u][v] == 'O') dfs(board, u, v);
}
}
public:
void solve(vector<vector<char>>& board) {
if (board.empty() || board.empty())return;
m = board.size(), n = board.size();
for (int i = 0; i < m; ++i) {
if (board[i] == '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[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

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:

1. You could assume that there won't be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
2. The test cases are using double-quotes to represent a character.
3. 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.

• Get(int row, char column)，获取坐标为(row,column)的cell的值
• Set(int row, char column, int val)，把坐标为(row,column)的值设置为val
• Sum(int row, char column, List of Strings : numbers)，numbers表示一系列求和公式，把公式计算结果填入坐标(row,column)中，并且当公式中的格子更新时，该公式计算出来的值也要更新。

Excel包含两个成员，二维矩阵matrix表示一个excel表格，hashmap formula的key为某个格子，value为该格子对应的求和公式。如果某个格子的值是实实在在的值，不是用公式计算出来的，则不在这个hashmap中。

• 对于get，如果坐标不在formula中，说明该格子是实实在在的值，直接返回matrix中的值。否则需要从formula中取出求和公式进行计算。
• 对于set，直接把matrix对应坐标设置为value就好，注意的是，因为set之后就变成了实实在在的值，所以要清空formula中该格子的公式（如果有的话）。
• 对于sum，计算字符串公式的值，把结果填入对应的格子，然后在formula中设置该格子的公式。

```class Excel {
private:
vector<vector<int>> matrix;
unordered_map<int, vector<string>> formula;
// 把坐标hash成一个int
int id(int r, char c) {
return r * 27 + c - 'A' + 1;
}
void parse(string& s, int& r, char& c) {
c = s;
r = stoi(s.substr(1));
}
int get_cell(string& s) {
int r;
char c;
parse(s, r, c);
return get(r, c);
}
int get_range(string& s) {
size_t pos = s.find(':');
string s1 = s.substr(0, pos), s2 = s.substr(pos + 1);
int r1, r2;
char c1, c2;
parse(s1, r1, c1);
parse(s2, r2, c2);
int ans = 0;
for (int i = r1; i <= r2; ++i) {
for (char c = c1; c <= c2; ++c) {
ans += get(i, c);
}
}
return ans;
}
int get_cells(vector<string>& strs) {
int ans = 0;
for (auto& s : strs) {
if (s.find(':') == string::npos)
ans += get_cell(s);
else
ans += get_range(s);
}
return ans;
}
public:
Excel(int H, char W) {
matrix.clear();
formula.clear();
for (int i = 0; i <= H; ++i) {
matrix.push_back(vector<int>(W - 'A' + 1, 0));
}
}
void set(int r, char c, int v) {
matrix[r] = v;
formula.erase(id(r, c)); // caution
}
int get(int r, char c) {
if (formula.find(id(r, c)) == formula.end())return matrix[r];
return get_cells(formula[id(r, c)]);
}
int sum(int r, char c, vector<string> strs) {
int ans = get_cells(strs);
matrix[r] = ans;
formula[id(r, c)] = strs;
return ans;
}
};
```

# LeetCode Mini Parser

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,]]",
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.```

```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();
}
};
```

```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);
}
};
```

# LeetCode Lowest Common Ancestor of a Binary Tree

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).”

```        _______3______
/              \
___5__          ___1__
/      \        /      \
6      _2       0       8
/  \
7   4
```

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.

```struct MyNode {
TreeNode* node;
int par;
MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
};
```

```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;
}
};
```

```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;
}
};
```

# LeetCode Merge Two Binary Trees

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:

```Input:
Tree 1                     Tree 2
1                         2
/ \                       / \
3   2                     1   3
/                           \   \
5                             4   7
Output:
Merged tree:
3
/ \
4   5
/ \   \
5   4   7
```

Note: The merging process must start from the root nodes of both trees.

```class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == NULL&&t2 == NULL)return NULL;
if (t1 == NULL&&t2 != NULL)return t2;
if (t1 != NULL&&t2 == NULL)return t1;
TreeNode* left = mergeTrees(t1->left, t2->left);
TreeNode* right = mergeTrees(t1->right, t2->right);
TreeNode* root = new TreeNode(t1->val + t2->val);
root->left = left;
root->right = right;
return root;
}
};
```

# LeetCode Longest Palindromic Subsequence

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".

```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[n - 1];
}
};
```

```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);
}
};
```

# LeetCode Array Nesting

LeetCode Array Nesting
A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1].
Sets S[K] for 0 <= K < N are defined as follows:
S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }.
Sets S[K] are finite for each K and should NOT contain duplicates.
Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.
Example 1:

```Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A = 5, A = 4, A = 0, A = 3, A = 1, A = 6, A = 2.
One of the longest S[K]:
S = {A, A, A, A} = {5, 6, 2, 0}
```

Note:

1. N is an integer within the range [1, 20,000].
2. The elements of A are all distinct.
3. Each element of array A is an integer within the range [0, N-1].

```class Solution {
private:
int nest(vector<int> &nums, vector<int> &visited, int k) {
int ans = 0;
while (visited[k] == 0) {
visited[k] = 1;
++ans;
k = nums[k];
}
return ans;
}
public:
int arrayNesting(vector<int>& nums) {
int n = nums.size();
vector<int> visited(n, 0);
int ans = 0;
for (int i = 0; i < nums.size(); ++i) {
if (visited[i] == 0) {
int cur = nest(nums, visited, i);
ans = max(ans, cur);
}
}
return ans;
}
};
```

# LeetCode Construct String from Binary Tree

LeetCode Construct String from Binary Tree
You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.
The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:

```Input: Binary tree: [1,2,3,4]
1
/   \
2     3
/
4
Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())",
but you need to omit all the unnecessary empty parenthesis pairs.
And it will be "1(2(4))(3)".
```

Example 2:

```Input: Binary tree: [1,2,3,null,4]
1
/   \
2     3
\
4
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example,
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.```

```class Solution {
public:
string tree2str(TreeNode* t) {
if (!t)return "";
if (!t->left && !t->right)return to_string(t->val);
if (!t->left)return to_string(t->val) + "()(" + tree2str(t->right) + ")";
if (!t->right)return to_string(t->val) + "(" + tree2str(t->left) + ")";
return to_string(t->val) + "(" + tree2str(t->left) + ")(" + tree2str(t->right) + ")";
}
};
```