Tag Archives: BFS

LeetCode Kill Process

LeetCode Kill Process
Given n processes, each process has a unique PID (process id) and its PPID (parent process id).
Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.
We use two list of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.
Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.
Example 1:

Input:
pid =  [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation:
           3
         /   \
        1     5
             /
            10
Kill 5 will also kill 10.

Note:

  1. The given kill id is guaranteed to be one of the given PIDs.
  2. n >= 1.

给定一个父子进程的对应关系,现在要kill掉某个进程id,那么id的子进程,孙进程也会被kill掉,问最终被kill掉的进程有哪些。
简单题。先使用map把父子进程的对应关系存起来,因为是一个父亲可能有多个孩子进程,所以要用multimap。然后用bfs类似于树的层次遍历,把所有孩子进程遍历一遍并存到结果数组中。
代码如下,刚好看了C++ primer的unordered_multimap的范围查找,用equal_range很方便。

class Solution {
public:
	vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
		unordered_multimap<int, int> umm;
		for (int i = 0; i < pid.size(); ++i) {
			umm.insert(pair<int, int>(ppid[i], pid[i]));
		}
		vector<int> ans;
		queue<int> q;
		q.push(kill);
		while (!q.empty()) {
			int id = q.front();
			q.pop();
			ans.push_back(id);
			auto r = umm.equal_range(id);
			for (auto i = r.first; i != r.second; ++i)q.push(i->second);
		}
		return ans;
	}
};

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

LeetCode Friend Circles

LeetCode Friend Circles
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are directfriends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Example 1:

Input:
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.

Example 2:

Input:
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Note:

  1. N is in range [1,200].
  2. M[i][i] = 1 for all students.
  3. If M[i][j] = 1, then M[j][i] = 1.

给定一个矩阵,M[i][j]=1表示i和j有直接关系,如果i和j有直接关系,j和k有直接关系,则i和k有间接关系。问这个矩阵共有多少个关系网。
简单题,有两种解法。第一种解法是DFS或者BFS,每次把能搜索到的点标记为一个新的关系网,直到所有点都属于一个关系网。但是无论DFS还是BFS,复杂度都比较高。
这种题应该条件反射想到并查集,只要M[i][j]=1,则把i和j union起来,最后看一下有多少个代表就好了。这种解法非常简单,代码如下:

class Solution {
private:
	int n;
	vector<int> parent;
	void init() {
		parent.resize(n);
		for (int i = 0; i < n; ++i) {
			parent[i] = i;
		}
	}
	int find_set(int x) {
		if (parent[x] != x)
			parent[x] = find_set(parent[x]);
		return parent[x];
	}
	void union_set(int u, int v) {
		parent[find_set(u)] = find_set(v);
	}
public:
	int findCircleNum(vector<vector<int>>& M) {
		n = M.size();
		init();
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (M[i][j] == 1) {
					union_set(i, j);
				}
			}
		}
		set<int> circles;
		for (int i = 0; i < n; ++i)circles.insert(find_set(i)); // 注意最后还要find一下找到代表
		return circles.size();
	}
};

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

hihoCoder 1519-逃离迷宫II

hihoCoder 1519-逃离迷宫II

#1519 : 逃离迷宫II

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

描述

小Hi被坏女巫抓进里一间有N x M个格子组成的矩阵迷宫。
有些格子是小Hi可以经过的,我们用'.'表示;有些格子上有障碍物小Hi不能经过,我们用'#'表示。小Hi的起始位置用'S'表示,他需要到达用'T'表示的格子才能逃离迷宫。
麻烦的是小Hi被坏女巫施了魔法,他只能选择上下左右某一个方向,沿着这个方向一直走,直到遇到障碍物或者迷宫边界才能改变方向。新的方向可以是上下左右四个方向之一。之后他还是只能沿着新的方向一直走直到再次遇到障碍物或者迷宫边界……
小Hi想知道他最少改变几次方向才能逃离这个迷宫。

输入

第一行包含两个整数N和M。  (1 <= N, M <= 500)
以下N行每行M个字符,代表迷宫。

输出

一个整数代表答案。如果小Hi没法逃离迷宫,输出-1。

样例输入
5 5
S.#.T
.....
.....
.....
.....
样例输出
2

给定一个迷宫,S表示起点,T表示终点,#表示障碍物。行走的时候,只能沿着直线走,直到遇到障碍物或者碰壁,问从S到T,最少需要改变多少次方向。
我一开始是用DFS做的,每次朝一个方向DFS下去,但是因为每次DFS时走了一长条直线,所以回溯的时候需要把之前走过的直线复位。代码如下:

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
using namespace std;
const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;
int ans = INT_MAX;
vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<char>> visited(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ {-1,0},{1,0},{0,-1},{0,1} }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向
bool ok(int x, int y) {
	if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
	return false;
}
void dfs(int sx,int sy, int step) {
	for (int i = 0; i < 4; ++i) {
		int newx = sx + dirs[i][0], newy = sy + dirs[i][1];
		if (ok(newx, newy) && visited[newx][newy] == '0') {
			visited[newx][newy] = '1';
			bool done = false;
			while (ok(newx, newy)) {
				visited[newx][newy] = '1';
				if (newx == endx&&newy == endy) {
					done = true;
					break;
				}
				newx = newx + dirs[i][0], newy = newy + dirs[i][1];
			}
			if (done) {
				ans = min(ans, step);
			}
			else {
				dfs(newx + opdirs[i][0], newy + opdirs[i][1], step + 1);  // 往回走一步再递归
			}
			while (!(newx == sx&&newy == sy)) {
				if (ok(newx, newy))visited[newx][newy] = '0'; // 复位
				newx = newx + opdirs[i][0], newy = newy + opdirs[i][1];
			}
		}
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	char c;
	for (int i = 0; i < n; ++i) {
		scanf("%c", &c);
		for (int j = 0; j < m; ++j) {
			scanf("%c", &maze[i][j]);
			if (maze[i][j] == 'S') {
				startx = i;
				starty = j;
			}
			else if (maze[i][j] == 'T') {
				endx = i;
				endy = j;
			}
		}
	}
	visited[startx][starty] = '1';
	dfs(startx, starty, 0);
	if (ans == INT_MAX)printf("-1\n");
	else printf("%d\n", ans);
	return 0;
}

本代码提交TLE,很明显会TLE,因为DFS必须把所有方案都走一遍才能得到最小值。
比赛的时候脑子短路,这种搜索问题要求最短XX的肯定用BFS比DFS快呀,因为第一次BFS到的方案肯定就是最优方案呀。只不过这题判断距离用的是转弯次数,以前都是算走过的步数。
对于这题,用BFS也是一样的,BFS的下一个点肯定就是走直线走到无法再走的那个拐角点(cornor)。不过为了防止死循环,要把以前走过的拐角都记录下来,只走那些以前没走过的拐点。
代码如下:

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;
typedef struct P {
	int x, y, step;
	P(int x_, int y_, int step_) :x(x_), y(y_), step(step_) {};
};
vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向
set<int> points;
bool ok(int x, int y) {
	if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
	return false;
}
int id(int x, int y) {
	return x*n + y;
}
int bfs() {
	queue<P> q;
	P p(startx, starty, 0);
	q.push(p);
	while (!q.empty()) {
		p = q.front();
		q.pop();
		points.insert(id(p.x, p.y));
		for (int i = 0; i < dirs.size(); ++i) {
			int newx = p.x + dirs[i][0], newy = p.y + dirs[i][1];
			while (ok(newx, newy)) {
				if (newx == endx&&newy == endy) {
					return p.step;
				}
				newx = newx + dirs[i][0], newy = newy + dirs[i][1];
			}
			int cornorx = newx + opdirs[i][0], cornory = newy + opdirs[i][1]; // 往回走一步
			if (points.find(id(cornorx, cornory)) == points.end()) {
				P tmp(cornorx, cornory, p.step + 1);
				q.push(tmp);
			}
		}
	}
	return -1;
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	char c;
	for (int i = 0; i < n; ++i) {
		scanf("%c", &c);
		for (int j = 0; j < m; ++j) {
			scanf("%c", &maze[i][j]);
			if (maze[i][j] == 'S') {
				startx = i;
				starty = j;
			}
			else if (maze[i][j] == 'T') {
				endx = i;
				endy = j;
			}
		}
	}
	printf("%d\n", bfs());
	return 0;
}

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

LeetCode Minimum Height Trees

LeetCode Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

return [1]
Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5

return [3, 4]
Show Hint

    Note:
    (1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
    (2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.


    给定一个无向无环图,问以哪个顶点为根形成的有根树的树高是最小的,如果有多个这样的最小高度的有根树,则输出所有这样的根节点。
    很有意思的一题,需要把无向无环图转换为有根树。提示问这样的最小高度的有根树最多有多少个,我想了想,应该最多只有两个吧。可以用反证法,假设有3个,则这3个根肯定会形成环,具体原因大家可以在纸上画个图举个例子就知道了。
    然后我由题目的样例想到的是,把图转换为有根的最小高度的树,根节点应该是从度数最高的前两个节点中选一个。所以我首先统计了所有节点的度数,然后选两个度数最高的节点,对这两个点DFS求以他们为根时的树高,如果树高相同,说明这两个点都是答案,否则取树高更高的节点作为根节点。
    但是很可惜,代码提交之后WA,错误样例是这样的[[0,1],[0,2],[0,3],[2,4],[0,5],[5,6],[6,7],[2,8],[7,9]]。

    8     3
      \    \
        2----0----5----6----7----9
      /    /
    4    1

    在上图中,度数最多的前两个点是0和2,但是转换为有根树的最小高度的树根节点是5。所以我的解法是错误的。
    参考网上的题解,好巧妙呀。这种解法类似于剥洋葱,一层一层把叶子节点剥离掉,最后剩下的2个或者1个节点就是最小树高的根节点。这种解法显然是正确的,没剥掉一层,相当于树高减一,一直减,到最后还剩下的节点肯定就是根节点了。比如上图中,第一层剥掉8,3,9,4,1,变成下图

    2----0----5----6----8

    第二层剥掉之后变成下图

    0----5----6

    第三层剥掉之后就只剩下5号节点了,所以以5号节点为根,树的高度最低,只有3,而我的解法算出来的根节点0的树高是4,不是最小的。

    5

    剥洋葱的解法用BFS来实现就非常方便了,BFS天然就是一层循环就是剥掉一层。
    代码中,初始时,我们把图转换为类似邻接表的结果,但是每个vector里存的是unordered_set,而不是list,因为剥洋葱的时候,比如第一层时剥掉8号节点时,我们同时需要把2号节点的邻接表中的8号节点删掉,所以用unordered_set.erase就非常方便。后面循环时,没剥一层,我们就检查一下,把当前的叶子节点加入到队列中。当剩余的节点数不超过2个时,剩余的节点就是有根树的根节点。如果剩余两个节点,说明这两个节点的高度是一样的,都是正确答案。
    代码如下:

    class Solution {
    public:
    	vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
    		if (n == 1)return{ 0 };
    		int m = edges.size();
    		vector<unordered_set<int>> graph(n, unordered_set<int>());
    		for (int i = 0; i < m; ++i) {
    			graph[edges[i].first].insert(edges[i].second);
    			graph[edges[i].second].insert(edges[i].first);
    		}
    		queue<int> q;
    		for (int i = 0; i < n; ++i) {
    			if (graph[i].size() == 1) q.push(i);
    		}
    		while (n > 2) {
    			int t = q.size();
    			n -= t;
    			while (t--) {
    				int leaf = q.front();
    				q.pop();
    				for (auto par : graph[leaf]) { // only one par
    					graph[par].erase(leaf);
    					if (graph[par].size() == 1)q.push(par);
    				}
    			}
    		}
    		vector<int> ans;
    		while (!q.empty()) {
    			ans.push_back(q.front());
    			q.pop();
    		}
    		return ans;
    	}
    };
    

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

    LeetCode Evaluate Division

    LeetCode Evaluate Division
    Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
    Example:
    Given a / b = 2.0, b / c = 3.0.
    queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
    return [6.0, 0.5, -1.0, 1.0, -1.0 ].
    The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.
    According to the example above:

    equations = [ ["a", "b"], ["b", "c"] ],
    values = [2.0, 3.0],
    queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

    The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.


    给定一系列的除法表达式,要计算另一些除法表达式的结果。比如知道a/b=2.0,b/c=3.0,问a/c=?。
    本题的解法是把一系列表达式转换为图,比如a/b=2.0转换为a指向b的边,边的值为2.0,同时b指向a的边的值为1/2.0。如果要求a/c,则在图中找一条a到c的边,并且把走过的边的值乘起来。
    构建图的过程先把表达式中的string编码成int,然后把已知的直连边加入到图中。对于要查询的边start/target,首先判断一下两个端点是否在图中,如果至少有一个端点不在图中,则无法求值,返回-1。否则,在图中DFS或BFS找到target,走过的路径乘积就是结果。
    题目说明所有values都是正数,所以不存在除0问题。
    DFS代码如下:

    class Solution {
    private:
    	bool dfs(vector<vector<double>>& graph, int start, int x, int y, int target) {
    		graph[start][y] = graph[start][x] * graph[x][y];
    		graph[y][start] = 1.0 / graph[start][y];
    		if(y == target)return true;
    		int n = graph.size();
    		for(int i = 0; i < n; ++i){
    			if(graph[start][i] == 0 && graph[y][i] != 0){
    				if(dfs(graph, start, y, i, target))return true;
    			}
    		}
    		return false;
    	}
    	double helper(vector<vector<double>>& graph, int start, int target) {
    		if (start == target)return 1.0;
    		else if (graph[start][target] != 0.0)return graph[start][target];
    		int n = graph.size();
    		for (int y = 0; y < n; ++y) {
    			if (y == start)continue;
    			if (graph[start][y] != 0.0) {
    				if (dfs(graph, start, start, y, target))return graph[start][target];
    			}
    		}
    		return -1.0;
    	}
    public:
    	vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
    		int cnt = 0, n = equations.size();
    		unordered_map<string, int> hash;
    		for (int i = 0; i < n; ++i) {
    			if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++;
    			if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++;
    		}
    		vector<vector<double>> graph(cnt, vector<double>(cnt, 0));
    		for (int i = 0; i < n; ++i) {
    			int x = hash[equations[i].first], y = hash[equations[i].second];
    			graph[x][x] = 1;
    			graph[y][y] = 1;
    			graph[x][y] = values[i];
    			graph[y][x] = 1.0 / values[i];
    		}
    		vector<double> ans;
    		for (int i = 0; i < queries.size(); ++i) {
    			if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0);
    			else {
    				int x = hash[queries[i].first], y = hash[queries[i].second];
    				ans.push_back(helper(graph, x, y));
    			}
    		}
    		return ans;
    	}
    };
    

    本代码提交AC,用时3MS。
    BFS代码如下:

    class Solution {
    private:
    	double bfs(vector<vector<double>>& graph, int start, int target) {
    		if (start == target)return 1.0;
    		else if (graph[start][target] != 0.0)return graph[start][target];
    		int n = graph.size();
    		queue<int> q;
    		for(int x = 0; x < n; ++x){
    			if(x != start && graph[start][x] != 0)q.push(x);
    		}
    		while(!q.empty()){
    			int x = q.front();
    			if(x == target) return graph[start][target];
    			q.pop();
    			for(int y = 0; y < n; ++y){
    				if(graph[start][y] == 0 && graph[x][y] != 0){
    					graph[start][y] = graph[start][x] * graph[x][y];
    					graph[y][start] = 1.0 / graph[start][y];
    					q.push(y);
    				}
    			}
    		}
    		return -1.0;
    	}
    public:
    	vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
    		int cnt = 0, n = equations.size();
    		unordered_map<string, int> hash;
    		for (int i = 0; i < n; ++i) {
    			if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++;
    			if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++;
    		}
    		vector<vector<double>> graph(cnt, vector<double>(cnt, 0));
    		for (int i = 0; i < n; ++i) {
    			int x = hash[equations[i].first], y = hash[equations[i].second];
    			graph[x][x] = 1;
    			graph[y][y] = 1;
    			graph[x][y] = values[i];
    			graph[y][x] = 1.0 / values[i];
    		}
    		vector<double> ans;
    		for (int i = 0; i < queries.size(); ++i) {
    			if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0);
    			else {
    				int x = hash[queries[i].first], y = hash[queries[i].second];
    				ans.push_back(bfs(graph, x, y));
    			}
    		}
    		return ans;
    	}
    };
    

    本代码提交AC,用时0MS,类似的题BFS显然要比DFS快,而且这题用BFS思路更清晰。

    LeetCode 01 Matrix

    LeetCode 01 Matrix
    Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
    The distance between two adjacent cells is 1.
    Example 1:
    Input:

    0 0 0
    0 1 0
    0 0 0
    

    Output:

    0 0 0
    0 1 0
    0 0 0
    

    Example 2:
    Input:

    0 0 0
    0 1 0
    1 1 1
    

    Output:

    0 0 0
    0 1 0
    1 2 1
    

    Note:

    1. The number of elements of the given matrix will not exceed 10,000.
    2. There are at least one 0 in the given matrix.
    3. The cells are adjacent in only four directions: up, down, left and right.

    给定一个0/1矩阵,要求每个点到其最近的0的距离。显然,如果自身是0的话,到最近的0的距离就是0,所以这里只需要求当cell不为0时,它到最近的0的距离。
    显然是个BFS的题,从点(i,j)往外广度搜索,第一个遇到0时,走过的步数就是和0的最短距离;没遇到0时,不断的把点加入到队列中。
    自定义一个MyPoint结构体,保存点的坐标,以及从出发点到该点的步数。注意本题不需要visited数组,visited数组的目的是保证在BFS时不走之前走过的点,但是BFS走过的路径肯定有那种没走之前走过的点的路径,这样的路径到达0的距离肯定会比走重复点的路径到达0的距离要短。所以不用visited也能找到最短距离。
    代码如下:

    typedef struct MyPoint {
    	int x, y;
    	int step;
    	MyPoint(int x_, int y_, int step_) :x(x_), y(y_), step(step_) {};
    };
    class Solution {
    private:
    	int bfs(int i, int j, vector<vector<int>>& matrix) {
    		int m = matrix.size(), n = matrix[0].size();
    		MyPoint p(i, j, 0);
    		queue<MyPoint> qp;
    		qp.push(p);
    		while (!qp.empty()) {
    			p = qp.front();
    			if (matrix[p.x][p.y] == 0)return p.step;
    			qp.pop();
    			if (p.x - 1 >= 0) {
    				MyPoint tmp(p.x - 1, p.y, p.step + 1);
    				qp.push(tmp);
    			}
    			if (p.x + 1 < m) {
    				MyPoint tmp(p.x + 1, p.y, p.step + 1);
    				qp.push(tmp);
    			}
    			if (p.y - 1 >= 0) {
    				MyPoint tmp(p.x, p.y - 1, p.step + 1);
    				qp.push(tmp);
    			}
    			if (p.y + 1 < n) {
    				MyPoint tmp(p.x, p.y + 1, p.step + 1);
    				qp.push(tmp);
    			}
    		}
    	}
    public:
    	vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
    		int m = matrix.size(), n = 0;
    		if (m > 0)n = matrix[0].size();
    		if (m == 0 || n == 0)return vector<vector<int>>();
    		vector<vector<int>> ans(m, vector<int>(n, 0));
    		for (int i = 0; i < m; ++i) {
    			for (int j = 0; j < n; ++j) {
    				if (matrix[i][j] != 0) {
    					ans[i][j] = bfs(i, j, matrix);
    				}
    			}
    		}
    		return ans;
    	}
    };
    

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

    LeetCode Find Largest Value in Each Tree Row

    LeetCode Find Largest Value in Each Tree Row
    You need to find the largest value in each row of a binary tree.
    Example:

    Input:
              1
             / \
            3   2
           / \   \
          5   3   9
    Output: [1, 3, 9]

    给定一棵二叉树,找出每层的最大值。
    简单题,直接BFS,在每一层找最大值。代码如下:

    class Solution {
    public:
    	vector<int> largestValues(TreeNode* root) {
    		vector<int> ans;
    		if (!root)return ans;
    		queue<TreeNode*> q;
    		q.push(root);
    		while (!q.empty()) {
    			int largest = INT_MIN, n = q.size();
    			while (n--) {
    				TreeNode* front = q.front();
    				q.pop();
    				largest = max(largest, front->val);
    				if (front->left)q.push(front->left);
    				if (front->right)q.push(front->right);
    			}
    			ans.push_back(largest);
    		}
    		return ans;
    	}
    };
    

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

    LeetCode Find Bottom Left Tree Value

    LeetCode Find Bottom Left Tree Value
    Given a binary tree, find the leftmost value in the last row of the tree.
    Example 1:

    Input:
        2
       / \
      1   3
    Output:
    1
    

    Example 2:

    Input:
            1
           / \
          2   3
         /   / \
        4   5   6
           /
          7
    Output:
    7
    

    Note: You may assume the tree (i.e., the given root node) is not NULL.


    找出一棵二叉树最后一行的最左边元素。
    简单题,直接BFS,每层保存队列第一个元素,BFS结束之后,就能得到最后一行的第一个元素。
    代码如下:

    class Solution {
    public:
    	int findBottomLeftValue(TreeNode* root) {
    		queue<TreeNode*> q;
    		q.push(root);
    		int ans = 0;
    		while (!q.empty()) {
    			int n = q.size();
    			ans = q.front()->val;
    			while (n--) {
    				TreeNode* front = q.front();
    				q.pop();
    				if (front->left)q.push(front->left);
    				if (front->right)q.push(front->right);
    			}
    		}
    		return ans;
    	}
    };
    

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

    LeetCode Binary Tree Zigzag Level Order Traversal

    LeetCode Binary Tree Zigzag Level Order Traversal
    Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
    For example:
    Given binary tree [3,9,20,null,null,15,7],

        3
       / \
      9  20
        /  \
       15   7
    

    return its zigzag level order traversal as:

    [
      [3],
      [20,9],
      [15,7]
    ]

    本题还是树的层次遍历,但是稍微有点不一样,要求奇数层从左往右输出,偶数层从右往左输出。常规的层次遍历使用BFS实现,即队列,这里要求颠倒顺序,马上想到用堆栈。
    维护一个left2right布尔变量,当tru时,把孩子从左往右压栈,这样下一层的输出顺序就是从右往左了;当为false时相反。这里我们还需要用到两个堆栈,分别保存当前层和下一层的结果。
    talk is cheap, show you the code!

    class Solution {
    public:
    	vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    		vector<vector<int>> ans;
    		if (!root)return ans;
    		bool left2right = true;
    		stack<TreeNode*> stk;
    		stk.push(root);
    		while(!stk.empty()) {
    			stack<TreeNode*> stk2;
    			vector<int> cand;
    			size_t n = stk.size();
    			for (size_t i = 0; i < n; ++i) {
    				TreeNode* top = stk.top();
    				stk.pop();
    				if (!top)continue;
    				cand.push_back(top->val);
    				if (left2right) {
    					stk2.push(top->left);
    					stk2.push(top->right);
    				}
    				else {
    					stk2.push(top->right);
    					stk2.push(top->left);
    				}
    			}
    			left2right = !left2right;
    			if (!cand.empty()) ans.push_back(cand);
    			stk = stk2;
    		}
    		return ans;
    	}
    };
    

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

    LeetCode Word Ladder

    LeetCode Word Ladder
    Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

    1. Only one letter can be changed at a time.
    2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

    For example,
    Given:
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot","dot","dog","lot","log","cog"]
    As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
    return its length 5.
    Note:

    • Return 0 if there is no such transformation sequence.
    • All words have the same length.
    • All words contain only lowercase alphabetic characters.
    • You may assume no duplicates in the word list.
    • You may assume beginWord and endWord are non-empty and are not the same.

    UPDATE (2017/1/20):
    The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.


    很有意思的一个题。给定两个单词beginWord和endWord,以及一个字典数组,问从beginWord到endWord,最少需要多少次变换,每次只能变换一个字母,而且变换的单词都必须存在于字典数组中。
    很明显是一个BFS题,从beginWord开始广搜,直到第一次搜到endWord时停止,此时走过的变换数就是最小变换数。因为广搜会搜索所有的空间,那么第一次到达endWord也就是最早到达的。
    当然BFS的题也都能用DFS来做,但是DFS显然会慢,想想便知,DFS必须搜索完一条完整的路径才能知道结果,才能进入下一条路径开始搜索;而BFS是每条路径同步进行,只要有一条路径到达,就结束搜索。
    常规的BFS代码如下:

    typedef struct Item {
    	string cur;
    	string used;
    	int step;
    	Item(string c, string u, int s) :cur(c), used(u), step(s) {};
    };
    class Solution {
    public:
    	bool differOne(const string &s1, const string &s2) {
    		int cnt = 0;
    		for (size_t i = 0; i < s1.size(); ++i) {
    			if (s1[i] != s2[i]) {
    				++cnt;
    				if (cnt > 1)return false;
    			}
    		}
    		return cnt == 1;
    	}
    	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    		size_t n = wordList.size();
    		queue<Item> q;
    		Item it(beginWord, string(n, '0'), 1);
    		q.push(it);
    		while (!q.empty()) {
    			Item t = q.front();
    			q.pop();
    			if (t.cur == endWord)return t.step;
    			for (size_t i = 0; i < n; ++i) {
    				if (t.used[i] == '0'&&differOne(t.cur, wordList[i])) {
    					string newUsed = t.used;
    					newUsed[i] = '1';
    					Item tmp(wordList[i], newUsed, t.step + 1);
    					q.push(tmp);
    				}
    			}
    		}
    		return 0;
    	}
    };
    

    本代码很好理解,定义一个结构体Item,cur为当前到达的单词,用一个和wordList大小相同的字符串used表示走到cur时走过的单词,step表示当前走过的步数。很可惜,这个版本的代码提交MLE,超空间了。肯定是因为Item这个结构体太大了,两个string,一个int。
    后来想到一个优化的方法,当某条路径path1走到单词cur时,其他路径就没必要再经过cur了,因为一旦经过cur,必定后续步骤和path1后续要走的路径就相同了,造成了重复搜索。所以我们走过每个单词时,可以直接将该单词置空,这样后续就不会再走该路了,同时这样也不需要Item结构体了。新版代码如下:

    class Solution {
    public:
    	bool differOne(const string &s1, const string &s2) {
    		int cnt = 0;
    		for (size_t i = 0; i < s1.size(); ++i) {
    			if (s1[i] != s2[i]) {
    				++cnt;
    				if (cnt > 1)return false;
    			}
    		}
    		return cnt == 1;
    	}
    	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    		size_t n = wordList.size();
    		queue<string> q;
    		q.push(beginWord);
    		int step = 1;
    		while (!q.empty()) {
    			size_t len = q.size();
    			for (size_t i = 0; i < len; ++i) {
    				string t = q.front();
    				q.pop();
    				if (t == endWord)return step;
    				for (size_t j = 0; j < wordList.size(); ++j) {
    					if (wordList[j] != ""&&differOne(t, wordList[j])) {
    						q.push(wordList[j]);
    						wordList[j] = "";
    					}
    				}
    			}
    			++step;
    		}
    		return 0;
    	}
    };
    

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