# 剑指 Offer 12. 矩阵中的路径

[[“a”,”b”,”c”,”e”],
[“s”,”f”,”c”,”s”],
[“a”,”d”,”e”,”e”]]

1 <= board.length <= 200
1 <= board[i].length <= 200

class Solution {
private:
bool DFS(vector<vector<char>> &board, vector<vector<int>> &visited, int x, int y, const string &word, int idx) {

if(idx == word.size() - 1) return true;

visited[x][y] = 1;
int m = board.size(), n = board[0].size();

vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
for(int i = 0; i < dirs.size(); ++i) {
int u = x + dirs[i][0], v = y + dirs[i][1];
if(u >= 0 && u < m && v >= 0 && v < n && visited[u][v] == 0 && board[u][v] == word[idx + 1]) {
bool ans = DFS(board, visited, u, v, word, idx + 1);
if(ans) return true;
}
}

visited[x][y] = 0;

return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
if(word.size() == 0) return true;
int m = board.size(), n = board[0].size();
vector<vector<int>> visited(m, vector<int>(n, 0));
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(board[i][j] == word[0]) {
if(DFS(board, visited, i, j, word, 0)) return true;
}
}
}
return false;
}
};

# 剑指 Offer 36. 二叉搜索树与双向链表

class Solution {
private:
void DFS(Node *root) {
if(root == NULL) return;

DFS(root->left);
else pre->right = root;

root->left = pre;
pre = root;
DFS(root->right);
}
public:
Node* treeToDoublyList(Node* root) {

if(root == NULL) return NULL;

DFS(root);

}
};

# LeetCode Number of Nodes in the Sub-Tree With the Same Label

5465. Number of Nodes in the Sub-Tree With the Same Label

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).


Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.


Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]


Example 4:

Input: n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa"
Output: [1,2,1,1,2,1]


Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]


Constraints:

• 1 <= n <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• labels.length == n
• labels is consisting of only of lower-case English letters.

class Solution {
private:
void DFS(int parid, int curid, vector<vector<int>> &children_string, unordered_map<int, vector<int>> &graph, const string &labels) {
int mylabel = labels[curid] - 'a';
++children_string[curid][mylabel];

for (int i = 0; i < graph[curid].size(); ++i) {
int childid = graph[curid][i];
if (childid == parid)continue;
DFS(curid, childid, children_string, graph, labels);
for (int j = 0; j < 26; ++j) {
children_string[curid][j] += children_string[childid][j];
}
}
}
public:
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
unordered_map<int, vector<int>> graph;
for (int i = 0; i < edges.size(); ++i) {
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
}
vector<vector<int>> children_string(n, vector<int>(26, 0));

DFS(-1, 0, children_string, graph, labels);

vector<int> ans;
for (int i = 0; i < n; ++i) {
int mylabel = labels[i] - 'a';
ans.push_back(children_string[i][mylabel]);
}
return ans;
}
};


# LeetCode Path with Maximum Probability

1514. Path with Maximum Probability

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to endreturn 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.


Example 2:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000


Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.


Constraints:

• 2 <= n <= 10^4
• 0 <= start, end < n
• start != end
• 0 <= a, b < n
• a != b
• 0 <= succProb.length == edges.length <= 2*10^4
• 0 <= succProb[i] <= 1
• There is at most one edge between every two nodes.

class Solution {
private:
void DFS(const vector<vector<double>> &graph, vector<int> &visited, int start, int end, double curprob, double &maxprob) {

if (start == end) {
maxprob = max(maxprob, curprob);
return;
}

int n = graph.size();
for (int i = 0; i < n; ++i) {
if (visited[i] == 0 && graph[start][i] >= 0) {
visited[i] = 1;
DFS(graph, visited, i, end, curprob*graph[start][i], maxprob);
visited[i] = 0;
}
}

}
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<vector<double>> graph(n, vector<double>(n, -1.0));
for (int i = 0; i < edges.size(); ++i) {
graph[edges[i][0]][edges[i][1]] = succProb[i];
graph[edges[i][1]][edges[i][0]] = succProb[i];
}
vector<int> visited(n, 0);
visited[start] = 1;
double maxprob = 0;
DFS(graph, visited, start, end, 1, maxprob);
return maxprob;
}
};

// 朴素迪杰斯特拉
class Solution {

public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<unordered_map<int, double>> graph(n, unordered_map<int, double>());
for (int i = 0; i < edges.size(); ++i) {
graph[edges[i][0]][edges[i][1]] = succProb[i];
graph[edges[i][1]][edges[i][0]] = succProb[i];
}

vector<int> visited(n, 0);
visited[start] = 1;

vector<double> ans(n, 0);
for (int i = 0; i < n; ++i) {
ans[i] = graph[start][i];
}

while (true) {
int maxid = -1;
double maxprob = 0;
for (int i = 0; i < n; ++i) {
if (visited[i] == 0 && ans[i] > maxprob) {
maxid = i;
maxprob = ans[i];
}
}
if (maxid == -1 || maxid == end)break; // 遇到end提前结束

visited[maxid] = 1;

for (unordered_map<int, double>::iterator it = graph[maxid].begin(); it != graph[maxid].end(); ++it) {
int next = it->first;
double prob = it->second;

if (visited[next] == 0 && (maxprob*prob > ans[next])) {
ans[next] = maxprob * prob;
}

}
}

return ans[end];
}
};


// 优化的迪杰斯特拉
struct P {
int id_;
double prob_;
P(int id, double prob) :id_(id), prob_(prob) {};

// priority_queue默认是最大堆，即小于就是小于
bool operator<(const P& p) const {
return this->prob_ < p.prob_;
}
};

class Solution {

public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<unordered_map<int, double>> graph(n, unordered_map<int, double>());
for (int i = 0; i < edges.size(); ++i) {
graph[edges[i][0]][edges[i][1]] = succProb[i];
graph[edges[i][1]][edges[i][0]] = succProb[i];
}

vector<int> visited(n, 0);

vector<double> ans(n, 0);
ans[start] = 1;

priority_queue<P> pq;
pq.push(P(start, 1));

while (!pq.empty()) {
P cur = pq.top();
pq.pop();

if (cur.id_ == end)break; // 提前结束

if (visited[cur.id_] == 1)continue;
visited[cur.id_] = 1;

for (unordered_map<int, double>::iterator it = graph[cur.id_].begin(); it != graph[cur.id_].end(); ++it) {
int next = it->first;
double prob = it->second;
if (cur.prob_*prob > ans[next]) {
ans[next] = cur.prob_*prob;
pq.push(P(next, ans[next]));
}
}

}
return ans[end];
}
};

SPFA算法。SPFA算法的思想可以参考之前的一道题： http://code.bitjoy.net/2014/12/28/hihocoder-1093/

// SPFA
class Solution {

public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<unordered_map<int, double>> graph(n, unordered_map<int, double>());
for (int i = 0; i < edges.size(); ++i) {
graph[edges[i][0]][edges[i][1]] = succProb[i];
graph[edges[i][1]][edges[i][0]] = succProb[i];
}

vector<int> visited(n, 0);
visited[start] = 1;

vector<double> ans(n, 0);
ans[start] = 1;

queue<int> q;
q.push(start);
while (!q.empty()) {
int cur = q.front();
q.pop();
visited[cur] = 0;

for (unordered_map<int, double>::iterator it = graph[cur].begin(); it != graph[cur].end(); ++it) {
int next = it->first;
double prob = it->second;
if (ans[cur] * prob > ans[next]) {
ans[next] = ans[cur] * prob;
if (visited[next] == 0) {
visited[next] = 1;
q.push(next);
}
}
}
}

return ans[end];
}
};

# hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

### 输出

5 4
1 2
3 1
4 3
5 1

3 1 4 0 1

# LeetCode Find Duplicate Subtrees

LeetCode Find Duplicate Subtrees Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them. Two trees are duplicate if they have the same structure with same node values. Example 1:

        1
/ \
2   3
/   / \
4   2   4
/
4

The following are two duplicate subtrees:
      2
/
4

and
    4

Therefore, you need to return above trees’ root in the form of a list.

  1
/
2

 2
\
1

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

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

# LeetCode Clone Graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

class Node {
public int val;
public List<Node> neighbors;
}


Test case format:

For simplicity sake, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.

Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).


Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.


Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.


Example 4:

Input: adjList = [[2],[1]]
Output: [[2],[1]]


Constraints:

• 1 <= Node.val <= 100
• Node.val is unique for each node.
• Number of Nodes will not exceed 100.
• There is no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.

class Solution {
private:
unordered_map<int, UndirectedGraphNode*> graph;
public:
UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node)
{
if (node == NULL)
return NULL;
if (graph.find(node->label) != graph.end())
return graph[node->label];
UndirectedGraphNode* cur = new UndirectedGraphNode(node->label);
graph[cur->label] = cur;
for (auto& n : node->neighbors) {
cur->neighbors.push_back(cloneGraph(n));
}
return cur;
}
};

class Solution {
public:
Node* clone(Node* node, unordered_map<int, Node*> &hash) {
int val = node->val;
if (hash.find(val) != hash.end())return hash[val];
Node *cp = new Node(node->val);
hash[val] = cp;
for (int i = 0; i < node->neighbors.size(); ++i) {
int child = node->neighbors[i]->val;
if (hash.find(child) != hash.end()) {
cp->neighbors.push_back(hash[child]);
}
else {
cp->neighbors.push_back(clone(node->neighbors[i], hash));
}
}
return cp;
}

Node* cloneGraph(Node* node) {
if (node == NULL)return NULL;
unordered_map<int, Node*> hash;
return clone(node, hash);
}
};

# LeetCode Surrounded Regions

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

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