# 剑指 Offer 13. 机器人的运动范围

#### 剑指 Offer 13. 机器人的运动范围

1 <= n,m <= 100
0 <= k <= 20

oaxxx
bcxxx
xxxxx

struct Point {
int x_, y_;
Point(int x, int y) : x_(x), y_(y) {};
};

class Solution {
private:
int SumDigits(int num) {
int ans = 0;
while(num != 0) {
ans += (num % 10);
num /= 10;
}
return ans;
}
bool IsValid(int x, int y, int k) {
return SumDigits(x) + SumDigits(y) <= k;
}
public:
int movingCount(int m, int n, int k) {
vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<int>> visited(m, vector<int>(n, 0));
queue<Point> q;
q.push(Point(0, 0));
int ans = 0;
while(!q.empty()) {
Point cur = q.front();
q.pop();

if(visited[cur.x_][cur.y_] == 1) continue; // 注意！

visited[cur.x_][cur.y_] = 1;
++ans;
for(int i = 0; i < dirs.size(); ++i) {
int u = cur.x_ + dirs[i], v = cur.y_ + dirs[i];
if(u >= 0 && u < m && v >= 0 && v < n && visited[u][v] == 0 && IsValid(u, v, k)) {
q.push(Point(u, v));
}
}
}
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]][edges[i]] = succProb[i];
graph[edges[i]][edges[i]] = 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]][edges[i]] = succProb[i];
graph[edges[i]][edges[i]] = 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]][edges[i]] = succProb[i];
graph[edges[i]][edges[i]] = 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]][edges[i]] = succProb[i];
graph[edges[i]][edges[i]] = 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];
}
};

# LCP 09. 最小跳跃次数

LCP 09. 最小跳跃次数

1 <= jump.length <= 10^6
1 <= jump[i] <= 10000

class Solution {
public:
int minJump(vector<int>& jump) {
int n = jump.size();
vector<int> visited(n, 0);
visited = 1;
queue<int> q;
q.push(0);
int steps = 0;
int premax = 0;
while (!q.empty()) {
++steps;
int sz = q.size();
while (sz--) {
int cur = q.front();
q.pop();
int next = cur + jump[cur];
if (next >= n)return steps;
if (visited[next] == 0) {
q.push(next);
}
for (int pre = premax; pre < cur; ++pre) {
if (visited[pre] == 0) {
visited[pre] = 1;
q.push(pre);
}
}
premax = max(premax, cur);
}
}
return 0;
}
};

# LCP 07. 传递信息

LCP 07. 传递信息

1. 有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
2. 每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
3. 每轮信息必须需要传递给另一个人，且信息可重复经过同一个人

• 2 <= n <= 10
• 1 <= k <= 5
• 1 <= relation.length <= 90, 且 relation[i].length == 2
• 0 <= relation[i],relation[i] < n 且 relation[i] != relation[i]

class Solution {
public:
int numWays(int n, vector<vector<int>>& relation, int k) {
vector<vector<int>> graph(n, vector<int>(n, 0));
for (int i = 0; i < relation.size(); ++i) {
graph[relation[i]][relation[i]] = 1;
}
queue<pair<int, int>> q;
q.push(make_pair(0, 0));
int ans = 0;
while (!q.empty()) {
pair<int, int> p = q.front();
q.pop();
if (p.first == n - 1 && p.second == k)++ans;
if (p.second < k) {
for (int i = 0; i < n; ++i) {
if (graph[p.first][i] == 1) {
q.push(make_pair(i, p.second + 1));
}
}
}
}
return ans;
}
};

# LeetCode Check if There is a Valid Path in a Grid

Given a m x ngrid. Each cell of the grid represents a street. The street of grid[i][j] can be:

• 1 which means a street connecting the left cell and the right cell.
• 2 which means a street connecting the upper cell and the lower cell.
• 3 which means a street connecting the left cell and the lower cell.
• 4 which means a street connecting the right cell and the lower cell.
• 5 which means a street connecting the left cell and the upper cell.
• 6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1)The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).


Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)


Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).


Example 4:

Input: grid = [[1,1,1,1,1,1,3]]
Output: true


Example 5:

Input: grid = [,,,,,,]
Output: true


Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• 1 <= grid[i][j] <= 6

class Solution {
public:
bool hasValidPath(vector<vector<int>>& grid) {
int m = grid.size(), n = grid.size();
vector<vector<int>> flag(m, vector<int>(n, 0));
vector<vector<int>> dirs = { {0,-1},{0,1},{-1,0},{1,0} };//左右上下
queue<pair<int, int>> q;
q.push(make_pair(0, 0));
while (!q.empty()) {
pair<int, int> p = q.front();
int u = p.first, v = p.second;
int src = grid[u][v];
if (u == m - 1 && v == n - 1)return true;
q.pop();
flag[u][v] = 1;
for (int i = 0; i < dirs.size(); ++i) {
int x = u + dirs[i], y = v + dirs[i];
if (x >= 0 && x < m&&y >= 0 && y < n && flag[x][y] == 0) {
int dest = grid[x][y];
if (grid[u][v] == 1) {
if ((i == 0 && (dest == 1 || dest == 4 || dest == 6)) ||
(i == 1 && (dest == 1 || dest == 3 || dest == 5))) {
q.push(make_pair(x, y));
}
}
else if (grid[u][v] == 2) {
if ((i == 2 && (dest == 2 || dest == 3 || dest == 4)) ||
(i == 3 && (dest == 2 || dest == 5 || dest == 6))) {
q.push(make_pair(x, y));
}
}
else if (grid[u][v] == 3) {
if ((i == 0 && (dest == 1 || dest == 4 || dest == 6)) ||
(i == 3 && (dest == 2 || dest == 5 || dest == 6))) {
q.push(make_pair(x, y));
}
}
else if (grid[u][v] == 4) {
if ((i == 1 && (dest == 1 || dest == 3 || dest == 5)) ||
(i == 3 && (dest == 2 || dest == 5 || dest == 6))) {
q.push(make_pair(x, y));
}
}
else if (grid[u][v] == 5) {
if ((i == 0 && (dest == 1 || dest == 4 || dest == 6)) ||
(i == 2 && (dest == 2 || dest == 3 || dest == 4))) {
q.push(make_pair(x, y));
}
}
else if (grid[u][v] == 6) {
if ((i == 1 && (dest == 1 || dest == 3 || dest == 5)) ||
(i == 2 && (dest == 2 || dest == 3 || dest == 4))) {
q.push(make_pair(x, y));
}
}
}
}
}
return false;
}
};


# LeetCode Frog Position After T Seconds

1377. Frog Position After T Seconds

Given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts jumping from the vertex 1. In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected. The frog can not jump back to a visited vertex. In case the frog can jump to several vertices it jumps randomly to one of them with the same probability, otherwise, when the frog can not jump to any unvisited vertex it jumps forever on the same vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [fromi, toi] means that exists an edge connecting directly the vertices fromi and toi.

Return the probability that after t seconds the frog is on the vertex target.

Example 1:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
Output: 0.16666666666666666
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1 and then jumping with 1/2 probability to vertex 4 after second 2. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666.


Example 2:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
Output: 0.3333333333333333
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after second 1.


Example 3:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
Output: 0.16666666666666666


Constraints:

• 1 <= n <= 100
• edges.length == n-1
• edges[i].length == 2
• 1 <= edges[i], edges[i] <= n
• 1 <= t <= 50
• 1 <= target <= n
• Answers within 10^-5 of the actual value will be accepted as correct.

struct Point {
int id, time;
double prob;
Point(int i, int t, double p) :id(i), time(t), prob(p) {};
};

class Solution {
public:
double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < edges.size(); ++i) {
graph[edges[i]][edges[i]] = 1;
graph[edges[i]][edges[i]] = 1;
}
vector<int> visited(n + 1, 0);
double prob = 1.0;
int time = 0;

queue<Point> q;
q.push(Point(1, 0, 1.0));
while (true) {
Point cur = q.front();
q.pop();
if (cur.id == target) {
prob = cur.prob;
time = cur.time;
break;
}
visited[cur.id] = 1;
int child = 0;
for (int i = 1; i <= n; ++i) {
if (visited[i] == 0 && graph[cur.id][i] == 1) {
++child;
}
}
for (int i = 1; i <= n; ++i) {
if (visited[i] == 0 && graph[cur.id][i] == 1) {
Point next(i, cur.time + 1, cur.prob / child);
q.push(next);
}
}
}

if (t < time)return 0;
else if (t == time)return prob;
else {
int child = 0;
for (int i = 1; i <= n; ++i) {
if (visited[i] == 0 && graph[target][i] == 1) {
++child;
}
}
if (child == 0)return prob;
else return 0;
}

}
};

# LeetCode Minimum Cost to Make at Least One Valid Path in a Grid

Given a m x ngrid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:

• 1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
• 2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
• 3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
• 4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])

Notice that there could be some invalid signs on the cells of the grid which points outside the grid.

You will initially start at the upper left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path doesn’t have to be the shortest.

You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.

Return the minimum cost to make the grid have at least one valid path.

Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.


Example 2:

Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).


Example 3:

Input: grid = [[1,2],[4,3]]
Output: 1


Example 4:

Input: grid = [[2,2,2],[2,2,2]]
Output: 3


Example 5:

Input: grid = []
Output: 0


Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100

const int MAXCOST = 1000000;
struct Node {
int x, y;
Node() :x(0), y(0) {};
Node(int x_, int y_) :x(x_), y(y_){};
};
class Solution {
public:

int minCost(vector<vector<int>>& grid) {
vector<vector<int>> dirs = { {0, 1}, {0, -1},{1, 0},{-1, 0} };//右左下上
int m = grid.size(), n = grid.size();
vector<vector<int>> cost(m, vector<int>(n, MAXCOST));
cost = 0;
queue<Node> q;
q.push(Node());
while (!q.empty()) {
Node cur = q.front();
q.pop();
for (int i = 0; i < dirs.size(); ++i) {
int x = cur.x + dirs[i], y = cur.y + dirs[i];
if (x < 0 || x >= m || y < 0 || y >= n)continue;
if (i + 1 == grid[cur.x][cur.y] && cost[cur.x][cur.y] < cost[x][y]) {
cost[x][y] = cost[cur.x][cur.y];
q.push(Node(x, y));
}
else if (i + 1 != grid[cur.x][cur.y] && (cost[cur.x][cur.y] + 1 < cost[x][y])) {
cost[x][y] = cost[cur.x][cur.y] + 1;
q.push(Node(x, y));
}
}
}
return cost[m - 1][n - 1];
}
};

struct Node {
int x, y, cost;
Node() :x(0), y(0), cost(0) {};
Node(int x_, int y_, int cost_) :x(x_), y(y_), cost(cost_) {};
};
class Solution {
public:

int minCost(vector<vector<int>>& grid) {
vector<vector<int>> dirs = { {0, 1}, {0, -1},{1, 0},{-1, 0} };//右左下上
int m = grid.size(), n = grid.size();
vector<vector<int>> flag(m, vector<int>(n, 0));
deque<Node> q;
q.push_back(Node());
int ans = 0;
while (!q.empty()) {
Node cur = q.front();
q.pop_front();
flag[cur.x][cur.y] = 1;
if (cur.x == m - 1 && cur.y == n - 1) {
ans = cur.cost;
break;
}
for (int i = 0; i < dirs.size(); ++i) {
int x = cur.x + dirs[i], y = cur.y + dirs[i];
if (x < 0 || x >= m || y < 0 || y >= n)continue;
if (flag[x][y] == 1)continue;
if (i + 1 == grid[cur.x][cur.y]) {
q.push_front(Node(x, y, cur.cost));
}
else {
q.push_back(Node(x, y, cur.cost + 1));
}
}
}
return ans;
}
};

# hihoCoder 1551-合并子目录

hihoCoder 1551-合并子目录

### 输出

3
/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall

8

# LeetCode 2 Keys Keyboard

LeetCode 2 Keys Keyboard Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
2. Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’. Example 1:
Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Note:
1. The n will be in the range [1, 1000].

# LeetCode Average of Levels in Binary Tree

LeetCode Average of Levels in Binary Tree Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array. Example 1:

Input:
3
/ \
9  20
/  \
15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Note:
1. The range of node’s value is in the range of 32-bit signed integer.