Tag Archives: BFS

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

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

地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

示例 1:

输入:m = 2, n = 3, k = 1
输出:3
示例 2:

输入:m = 3, n = 1, k = 0
输出:1
提示:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一个m*n的矩阵,要求从(0,0)开始移动,不能移动到坐标数字的位数之和超过k的位置,问最多有多少个可以走的格子。

简单的BFS的题,需要注意的是,BFS出队列的时候,检查一下这个点之前有没有被访问过。比如下图,最开始访问o点,然后会把a和b都进队列,接着a会把c进队列,但b也会把c进队列,导致c被进了两次,所以需要判断一下之前是否被访问。

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

本代码提交AC,用时8MS。

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.

给定一个无向图,边表示概率,问从start到end的最大概率是多少。

借此题复习一下若干最短路径算法吧。

首先朴素的DFS,代码如下:

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

本代码提交TLE。

其次, 朴素的迪杰斯特拉算法。迪杰斯特拉算法思路很简单,维护两个集合,一个集合S是已经找到最短路径的,另一个集合U是还未找到最短路径的。每次,从U选一个距离最小的节点u,这个节点已经是最短路径了,加入到S中。然后更新与u相连的其他节点的最短路径。如此循环往复。代码如下:

// 朴素迪杰斯特拉
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];
	}
};

很遗憾,上述代码在最后一个样例上TLE了。

优化版本的迪杰斯特拉算法。朴素迪杰斯特拉算法最耗时的是while循环内的两个for循环,第二个for循环是对找到的u节点的边进行循环,这个无法再优化,主要优化第一个for循环,即在U集合中找距离最短的u节点的过程。这里可以用优先队列来存储U中的所有节点。但是需要注意的是去重,比如题目中的第一个图,对于节点2,节点0弹出pq时,会访问节点2并把节点2加入到pq中;当节点1弹出pq时,又会访问节点2并把节点2加入到pq中,此时pq中出现了两个节点2,只不过prob不一样。所以pq弹出时可能会出现相同的节点,不过由于pq的性质,同样是2,先弹出来的肯定是概率最大的路径(最短路径),所以每次pq弹出时,更新visited数组,后续如果弹出的节点已经visited了,则不需要做第二个for循环了,直接continue。比如题目中的第一个图,0访问2时,压pq的是(id=2,prob=0.2);1访问2时,压pq的是(id=2,prob=0.25)。所以(id=2,prob=0.25)先于(id=2,prob=0.2)弹出,并设置visited[2]=1。当(id=2,prob=0.2)弹出时,visited[2]已经==1了,此时continue。


// 优化的迪杰斯特拉
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];
	}
};

本代码提交AC,用时428MS。

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

简单来说,SPFA就是带剪枝的BFS。它和迪杰斯特拉算法非常像,迪杰斯特拉算法是每次找U中距离最小的一个节点u,此时u的最短距离已经确定了,后续不会再更新了。因为迪杰斯特拉算法每次加入S的节点都是最优的,所以必须要线性(朴素迪杰斯特拉算法)或者用优先队列的方法从U中找到最小距离节点u。而SPFA算法就更简单一点,该算法不要求每次找到最优的节点u,因为SPFA是渐进逼近最优解的过程,它不需要线性查找,也不需要优先队列,它只需要一个简单的队列即可,每次把可以更新的节点u加入到队列中,然后BFS更新与u相连的其他节点。之前更新过的节点,后续还有可能更新。代码如下:

// 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];
	}
};

本代码提交AC,用时392MS。

LCP 09. 最小跳跃次数

LCP 09. 最小跳跃次数

为了给刷题的同学一些奖励,力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排,编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处,通过按动弹簧,可以选择把小球向右弹射 jump[i] 的距离,或者向左弹射到任意左侧弹簧的位置。也就是说,在编号为 i 弹簧处按动弹簧,小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧(若 i+jump[i]>=N ,则表示小球弹出了机器)。小球位于编号 0 处的弹簧时不能再向左弹。

为了获得奖励,你需要将小球弹出机器。请求出最少需要按动多少次弹簧,可以将小球从编号 0 弹簧弹出整个机器,即向右越过编号 N-1 的弹簧。

示例 1:

输入:jump = [2, 5, 1, 1, 1, 1]

输出:3

解释:小 Z 最少需要按动 3 次弹簧,小球依次到达的顺序为 0 -> 2 -> 1 -> 6,最终小球弹出了机器。

限制:

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


给定一个数组,每个数表示能从该位置往右跳的的步数。每个位置,要么往右一次性跳这么多步,要么可以跳回左边任意位置。问要跳出最右边,需要最少跳是多少。

每跳到一个i,可以往右跳到i+jump[i],或者跳回[0,i-1]任意位置。采用BFS思路,i+jump[i]和[0,i-1]任意位置作为BFS的一层。但是,简单的BFS会TLE。每轮BFS时,记录[0,i-1]测试过的最大位置,下次只要从这个位置开始测试即可。

完整代码如下:

class Solution {
public:
	int minJump(vector<int>& jump) {
		int n = jump.size();
		vector<int> visited(n, 0);
		visited[0] = 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;
	}
};

本代码提交AC,用时544MS。

LCP 07. 传递信息

LCP 07. 传递信息

小朋友 A 在和 ta 的小伙伴们玩传信息游戏,游戏规则如下:

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

给定总玩家数 n,以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数;若不能到达,返回 0。

示例 1:

输入:n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3

输出:3

解释:信息从小 A 编号 0 处开始,经 3 轮传递,到达编号 4。共有 3 种方案,分别是 0->2->0->4, 0->2->1->4, 0->2->3->4。

示例 2:

输入:n = 3, relation = [[0,2],[2,1]], k = 2

输出:0

解释:信息不能从小 A 处经过 2 轮传递到编号 2

限制:

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

给定n名玩家,以及玩家的传递关系。问从0号玩家经过k轮传递到n-1号玩家的方案数。

首先把玩家传递关系建一个图,然后从0号节点开始BFS,并统计传递的步数。当步数为k且到达n-1号玩家时,方案数加一。完整代码如下:

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][0]][relation[i][1]] = 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;
	}
};

本代码提交AC,用时8MS。

LeetCode Check if There is a Valid Path in a Grid

1391. 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 = [[2],[2],[2],[2],[2],[2],[6]]
Output: true

Constraints:

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

给定一个网格,每个格子中标明了路的走向,问能否从网格的左上角走到右下角。

简单题,bfs或dfs都可以,我用的是bfs。就是在搜索的时候,各种条件比较多,写起来很费劲。

完整代码如下:

class Solution {
public:
	bool hasValidPath(vector<vector<int>>& grid) {
		int m = grid.size(), n = grid[0].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][0], y = v + dirs[i][1];
				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;
	}
};

本代码提交AC,用时200MS。

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][0], edges[i][1] <= n
  • 1 <= t <= 50
  • 1 <= target <= n
  • Answers within 10^-5 of the actual value will be accepted as correct.

这题其实不是很hard。

给定一个无向树,节点编号是1~n。有一个青蛙开始在1号节点,每秒钟它会随机跳到与其相邻的未被访问的过的节点中,注意不能走回头路,访问过的节点不能再访问了。如果它周围的节点都被访问了,则它就在原地打转。问经过t秒,它跳到指定节点的概率是多少。

解法。从1号节点开始BFS,每到一个节点时,记录当前走过的时间以及走到当前节点的概率。计算概率也很简单,维护一个visited数组,看看有多少个未被访问的邻居child,则路径概率要乘上(1/child)。

还需要注意的是,如果走到目标节点的时间大于给定时间,则走不到目标节点;如果走的时间小于给定时间,则要看看目标节点还有没有未被访问的节点,如果没有的话,青蛙在目标节点原地打转,否则青蛙就跳走了不会再回来了。

完整代码如下:

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][0]][edges[i][1]] = 1;
			graph[edges[i][1]][edges[i][0]] = 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;
		}

	}
};

本代码提交AC,用时40MS。

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

1368. 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 = [[4]]
Output: 0

Constraints:

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

这个题目路有点难,我想了一下午,不过想明白之后也就不难了。

给定一个网格地图,每个网格标明了从该位置可以到达的下一个位置。现在要从地图的左上角走到右下角,有可能根据图标不能到达,问最少改变几个图标可以到达。每个图标仅可改变一次,可将其改为上下左右任意一个方向。

解法1。事实上,对于网格中的每个点,它都可以走到其上下左右的4个点,只不过按图标走费用为0,不按图标走费用为1。所以可以构造一个长和宽都是m*n的图,总元素即为(m*n)*(m*n),新的图中的值就是老图中相邻两个点之间的费用。然后在新的图中执行Dijkstra算法,寻找最短路径,即为原图的最小消费。

解法1太复杂了,忘记怎么写Dijkstra了,放弃。

解法2。不转换为新的图,直接在原图中执行算法。设置一个和原图同样大小的cost二维数组,cost[i][j]表示从左上角走到该位置的最小费用。对原图从左上角开始执行BFS,如果从当前点走到下一个节点的累加费用小于下一个节点的当前费用,则更新下一个节点的费用,并且BFS走到下一个节点。最终右下角的费用就是最小费用。

完整代码如下:

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[0].size();
		vector<vector<int>> cost(m, vector<int>(n, MAXCOST));
		cost[0][0] = 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][0], y = cur.y + dirs[i][1];
				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];
	}
};

本代码提交AC,用时76MS。

该解法没有设置visited数组标记走过的节点,因为没必要。一方面,以题目中的Example 2的图为例(下标从1开始),其(2,1)位置有可能从(1,1)直接下来,也有可能(1,1)先走右边下来再走左边到达(2,1),而第二条路径的费用低于第一条路径,如果设置visited数组的话,第二条路径就没法走了。另一方面,也不用担心不设置visited数组会导致程序来回来反复跑而无法终止,因为只有当走到该点的费用小于该点的当前费用时,才会将其加入队列,如果来回跑的话,费用肯定大于改点当前费用,也就不会加入队列了。所以无需设置visited数组,程序也能正常结束并得到正确结果。

解法3。参考讨论区题解,和解法2类似,但比解法2效率更高。BFS的时候,使用双端队列存储需要访问的节点,而且每次插入队列时,先插入满足原图方向标识的节点,而且是插入到队列开头,因为满足方向标识的路径费用为0,插入到队列开头之后,下次BFS时也先从队列开头取节点。对于不满足方向标识的节点,插入到队列尾部。这个策略相当于优先走费用为0的路径,只有当这些路径无法到达时,才会走费用为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[0].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][0], y = cur.y + dirs[i][1];
				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;
	}
};

本代码提交AC,用时36MS,比解法2效率更高。

hihoCoder 1551-合并子目录

hihoCoder 1551-合并子目录

#1551 : 合并子目录

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi的电脑的文件系统中一共有N个文件,例如: /hihocoder/offer22/solutions/p1 /hihocoder/challenge30/p1/test /game/moba/dota2/uninstall 小Hi想统计其中一共有多少个不同的子目录。上例中一共有8个不同的子目录: /hihocoder /hihocoder/offer22 /hihocoder/offer22/solutions /hihocoder/challenge30 /hihocoder/challenge30/p1 /game /game/moba /game/moba/dota2/

输入

第一行包含一个整数N (1 ≤ N ≤ 10000) 以下N行每行包含一个字符串,代表一个文件的绝对路径。保证路径从根目录”/”开始,并且文件名和目录名只包含小写字母和数字。 对于80%的数据,N个文件的绝对路径长度之和不超过10000 对于100%的数据,N个文件的绝对路径长度之和不超过500000

输出

一个整数代表不同子目录的数目。
样例输入
3
/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall
样例输出
8

给定很多个文件的绝对路径,问从这些文件的绝对路径中,我们可以知道其一共有多少个不同文件夹出现过。 常规思路很简单,直接解析每个文件所在的每一级文件夹路径,存到一个set里面,最后返回unordered_set的大小。但是这种方法TLE,看了一下,内存基本也用完了。因为对于100%的数据,路径长度太长了,hash的时间和空间都随之增长。 后来马上想到,路径问题是一层一层的,有可能很多文件的路径前缀都是相同的,那么我们可以构建一个Trie树,每个节点仅是当前文件夹的名称。最后我们统计一下构建好的Trie树的节点个数,就是文件夹的个数。 完整代码如下: [cpp] #include<algorithm> #include<vector> #include<iostream> #include<unordered_map> #include<unordered_set> #include<string> #include<set> #include<map> #include<queue> using namespace std; typedef long long ll; struct Node { string key_; map<string, Node*> children_; Node(string key) :key_(key) {}; }; int main() { //freopen("input.txt", "r", stdin); int n; scanf("%d\n", &n); string line; Node* root = new Node(""); while (n–) { getline(cin, line); int pre = 0; int pos = line.find(‘//’); Node* cur = root; while (pos != string::npos) { if (pos != 0) { string tmp = line.substr(pre + 1, pos – pre – 1); if (cur->children_[tmp] == NULL) { cur->children_[tmp] = new Node(tmp); } cur = cur->children_[tmp]; } pre = pos; pos = line.find(‘//’, pos + 1); } } ll ans = 0; queue<Node*> q; q.push(root); while (!q.empty()) { Node* cur = q.front(); q.pop(); ++ans; for (auto it : cur->children_) { q.push(it.second); } } printf("%lld\n", ans – 1); return 0; } [/cpp] 本代码提交AC,用时126MS。]]>

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

一个记事本中原本只有一个字符A,每次可以做两种操作中的一种,分别是全选和粘贴。问要得到n个字符A,至少需要经过多少次操作。 这一题我一开始想到用BFS来做,两种操作相当于两条搜索路径,所以很容易能写出BFS的代码: [cpp] class Solution { private: struct Node { int presented_cnt_; // 现在有多少个字符 int copied_cnt_; // 剪切板中有多少个字符 int step_; // 走过多少步了 Node(int p, int c, int s) :presented_cnt_(p), copied_cnt_(c), step_(s) {}; }; public: int minSteps(int n) { queue<Node> q; Node node(1, 0, 0); q.push(node); while (!q.empty()) { Node cur = q.front(); q.pop(); if (cur.presented_cnt_ == n) return cur.step_; if (cur.presented_cnt_ > n)continue; Node copy_node(cur.presented_cnt_, cur.presented_cnt_, cur.step_ + 1); // 全选 q.push(copy_node); if (cur.copied_cnt_ != 0) { // 粘贴 Node paste_node(cur.presented_cnt_ + cur.copied_cnt_, cur.copied_cnt_, cur.step_ + 1); q.push(paste_node); } } } }; [/cpp] 预料到了,本代码提交TLE。 搜索会超时的,用DP一般都不会超时。设dp[i]表示要得到i个字符A,至少需要的操作数。显然,dp[1]=0。 假设已经求到了dp[1,…,i-1],现在要求dp[i]。要得到i个字符,最多的操作数是i,即先复制一个A,然后粘贴i-1次,总共需要i次操作。比较快的方法是,如果i是偶数,则可以从i/2个字符开始,全选粘贴就能得到i个字符。 所以我们遍历i前面的所有j,如果i能整除j,则可以全选j,然后粘贴i/j-1次得到i个字符,即操作数是1+(i/j-1)=i/j,当然还需要加上到达i的操作数,所以dp[j]=dp[i]+i/j。 完整代码如下: [cpp] class Solution { public: int minSteps(int n) { vector<int> dp(n + 1, INT_MAX); dp[1] = 0; for (int i = 2; i <= n; ++i) { dp[i] = i; for (int j = i – 1; j >= 1; –j) { if (i%j == 0) { dp[i] = min(dp[i], dp[j] + i / j); } } } return dp[n]; } }; [/cpp] 本代码提交AC,用时79MS。 还有一种解法类似于素数筛法,我们首先知道dp[1]=0,如果我们对1个字符先全选,然后不停粘贴,则能得到2,3,4,…个字符,且操作数是2,3,4,…;下一次,我们知道dp[2]=2,如果我们对2个字符全选,然后不停粘贴,则能得到4,6,8,…个字符,且操作数是4,5,6,…。每一轮我们都只保留最小操作数。最终筛完之后,就是全局最优结果了。 完整代码如下: [cpp] class Solution { public: int minSteps(int n) { vector<int> dp(n + 1, INT_MAX); dp[1] = 0; for (int i = 1; i <= n; ++i) { for (int j = 2 * i, k = 2; j <= n; j += i, ++k) { dp[j] = min(dp[j], dp[i] + k); } } return dp[n]; } }; [/cpp] 本代码提交AC,用时3MS,速度飞快,因为越到后面,循环倍数越少。]]>

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.

求二叉树每一层的平均数。简单题,BFS层次遍历。代码如下: [cpp] class Solution { public: vector<double> averageOfLevels(TreeNode* root) { if (root == NULL)return{}; vector<double> ans; queue<TreeNode*> q; q.push(root); while (!q.empty()) { double sum = 0; size_t n = q.size(); for (size_t i = 0; i < n; ++i) { TreeNode* f = q.front(); q.pop(); sum += f->val; if (f->left != NULL)q.push(f->left); if (f->right != NULL)q.push(f->right); } ans.push_back(sum / n); } return ans; } }; [/cpp] 本代码提交AC,用时15MS。]]>