Tag Archives: BFS

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树的节点个数,就是文件夹的个数。
完整代码如下:

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

本代码提交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的代码:

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

预料到了,本代码提交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。
完整代码如下:

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

本代码提交AC,用时79MS。
还有一种解法类似于素数筛法,我们首先知道dp[1]=0,如果我们对1个字符先全选,然后不停粘贴,则能得到2,3,4,...个字符,且操作数是2,3,4,...;下一次,我们知道dp[2]=2,如果我们对2个字符全选,然后不停粘贴,则能得到4,6,8,...个字符,且操作数是4,5,6,...。每一轮我们都只保留最小操作数。最终筛完之后,就是全局最优结果了。
完整代码如下:

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

本代码提交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层次遍历。代码如下:

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

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

LeetCode Course Schedule II

LeetCode Course Schedule II
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

click to show more hints.

Hints:

  1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.

LeetCode Course Schedule的基础上,要求输出一种拓扑排序结果。
因为已经知道拓扑排序的Kahn解法,即BFS解法,那么输出一种拓扑排序的结果是很简单的事。在BFS的过程中,存储在队列中的点肯定都是入度为0的点,也就是这些课程可以在这一阶段完成,所以我们只需要在每轮BFS的时候,保存一下这一轮的节点就好了。
完整代码如下:

class Solution {
public:
	vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
		vector<unordered_set<int>> pre(numCourses), next(numCourses);
		for (const auto& p : prerequisites) {
			pre[p.first].insert(p.second);
			next[p.second].insert(p.first);
		}
		vector<int> ans;
		queue<int> q;
		for (int i = 0; i < numCourses; ++i) {
			if (pre[i].empty())q.push(i);
		}
		int edges = prerequisites.size();
		while (!q.empty()) {
			int n = q.size();
			for (int i = 0; i < n; ++i) {
				int cur = q.front();
				ans.push_back(cur);
				q.pop();
				for (const auto& nxt : next[cur]) {
					pre[nxt].erase(cur);
					--edges;
					if (pre[nxt].empty())q.push(nxt);
				}
			}
		}
		if (edges > 0)return{};
		else return ans;
	}
};

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

LeetCode Task Scheduler

LeetCode Task Scheduler
Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.
Example 1:

Input: tasks = ['A','A','A','B','B','B'], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

  1. The number of tasks is in the range [1, 10000].

CPU需要处理一系列任务,限制条件是两个相同的任务被处理的时间至少需要间隔n时刻,问CPU最少需要多长时间能处理完所有任务。
比赛没做出来,参考讨论区
根据题意,两个任务被处理至少需要间隔n时刻,所以我们可以认为CPU处理一批任务的循环周期是n+1,比如0时刻处理了任务'A',则至少要到n+1时刻才能再次处理任务'A',中间间隔了n时刻。
假设数量最多的任务的数量是k,则我们至少需要k个周期才能把这个任务处理完。为了让CPU处理的空闲时间更少,我们在一个周期内尽量让CPU处理的任务更丰富。所以想象一下,我们有k个桶,相当于k个周期,每个周期,我们把频率最高的任务拿出来,分发到这最多k个桶中。如果所有不同任务都分发完了还没有填满一个桶,则说明该桶内(周期内)CPU需要空闲等待。
比如样例中,最高频的任务是A和B,都是3,所以我们至少需要3个桶。每个桶的容量是n+1=3,相当于相同任务的距离是3。每次我们把A和B扔到不同的桶中,前两个桶各有一个空闲等待,第三个桶因为结束了,所以不需等待。
因为每次都需要取出最高频的任务去分发,所以用一个优先队列来实时更新频率排名。
完整代码如下:

class Solution {
public:
	int leastInterval(vector<char>& tasks, int n) {
		map<char, int> count;
		for (const auto& c : tasks)++count;
		priority_queue<pair<int, char>> pq;
		for (const auto& p : count)pq.push({ p.second,p.first });
		int cycle = n + 1, time = 0;
		while (!pq.empty()) {
			vector<pair<int, char>> tmp;
			int tsk = 0;
			for (int i = 0; i < cycle; ++i) {
				if (!pq.empty()) {
					tmp.push_back(pq.top());
					pq.pop();
					++tsk;
				}
			}
			for (auto& t : tmp) {
				if (--t.first) {
					pq.push(t);
				}
			}
			time += pq.empty() ? tsk : cycle;
		}
		return time;
	}
};

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

LeetCode Add One Row to Tree

LeetCode Add One Row to Tree
Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.
The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree.
Example 1:

Input:
A binary tree as following:
       4
     /   \
    2     6
   / \   /
  3   1 5
v = 1
d = 2
Output:
       4
      / \
     1   1
    /     \
   2       6
  / \     /
 3   1   5

Example 2:

Input:
A binary tree as following:
      4
     /
    2
   / \
  3   1
v = 1
d = 3
Output:
      4
     /
    2
   / \
  1   1
 /     \
3       1

Note:

  1. The given d is in range [1, maximum depth of the given tree + 1].
  2. The given binary tree has at least one tree node.

在二叉树深度为d的那一层增加一行值全为v的节点,如果d=1的话,新增一个值为v的根节点,原来的树作为新根节点的左子树。
简单题,层次遍历到深度为d-1时,对d-1层的所有节点,都增加值为v的左右孩子,如果d-1层的节点原来有左右孩子,则原来的左右孩子接到新加入的v的节点上,作为左右孩子。
完整代码如下:

class Solution {
public:
	TreeNode* addOneRow(TreeNode* root, int v, int d) {
		if (d == 1) {
			TreeNode* newRoot = new TreeNode(v);
			newRoot->left = root;
			return newRoot;
		}
		queue<TreeNode*> tree;
		tree.push(root);
		int depth = 0;
		while (!tree.empty()) {
			++depth;
			int n = tree.size();
			if (depth == d - 1) {
				for (int i = 0; i < n; ++i) {
					TreeNode* p = tree.front();
					tree.pop();
					if (p == NULL)continue;
					TreeNode* l = new TreeNode(v);
					l->left = p->left;
					p->left = l;
					TreeNode* r = new TreeNode(v);
					r->right = p->right;
					p->right = r;
				}
				break;
			}
			else {
				for (int i = 0; i < n; ++i) {
					TreeNode* p = tree.front();
					tree.pop();
					if (p == NULL)continue;
					tree.push(p->left);
					tree.push(p->right);
				}
			}
		}
		return root;
	}
};

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

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.


给定一棵二叉树和两个节点p,q,问p和q的最近公共祖先节点是哪个。LCA问题
思路:要找p和q的最近公共祖先,很直观的方法是找到从根节点分别到p和q的路径,然后把其中一条路径(比如根到p)上的点hash成path1,从另一条路径(比如根到q)的底端(q)往根节点走,把走过的每个点去path1中找,如果找到,则就是他们的LCA,因为这是距离q最近、且在path1中的点。
但是怎样找到根到p和q的路径呢。这里换一种思路,定义如下新的数据结构,par表示该节点的父节点,根节点的父节点为-1。

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

先整体把树层次遍历一遍,成为一个保存MyNode的数组,记录每个点的父节点在数组中的下标。在遍历的同时,记录下p和q节点的下标。这样通过下标往前递归就可以找到p和q到根节点的路径了。
找到路径之后,对其中一条路径hash,另一条路径在该hash中找。代码如下:

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

本代码提交AC,用时19MS。
讨论区还有一种递归的解法,很有意思。我们在以root为根的树中找p和q的LCA,如果root等于p或q其中之一,说明p或q就是他们的LCA。否则分别在左子树和右子树中递归的找LCA,如果发现在左右子树中找到的LCA都不为null,说明他们p和q分别位于root的两个子树,类似样例中的5和1,则root就是他们的LCA。如果某个子树返回的LCA为空,说明p和q都不在这个子树中,则先遇到谁,谁就是LCA,比如样例中的5和4,都不在3的右子树,在递归3的左子树的时候,先遇到了5,所以5是LCA。
完整代码如下:

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

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

LeetCode Integer Replacement

LeetCode Integer Replacement
Given a positive integer n and you can do operations as follow:

  1. If n is even, replace n with n/2.
  2. If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?
Example 1:

Input:
8
Output:
3
Explanation:
8 -> 4 -> 2 -> 1

Example 2:

Input:
7
Output:
4
Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

给定一个数n,不断对n进行如下两种操作中的一种

  1. 如果n是偶数,把n变成n/2
  2. 如果n是奇数,把n变成n+1或者n-1

问要把n变为1,需要的最少的变换次数是多少。
为啥我首先想到的是BFS。。。这不就相当于每个点根据情况可以走不同的方向,问走到终点1需要的最少步数吗?很像BFS呀。代码如下:

class Solution {
private:
	struct P {
		long long val;
		int step;
		P(long long v_, int s_) :val(v_), step(s_) {};
	};
public:
	int integerReplacement(int n) {
		P p(n, 0);
		queue<P> qp;
		qp.push(p);
		while (!qp.empty()) {
			P f = qp.front();
			qp.pop();
			if (f.val == 1)return f.step;
			else if (f.val & 1) {
				qp.push(P(f.val + 1, f.step + 1));
				qp.push(P(f.val - 1, f.step + 1));
			}
			else {
				qp.push(P(f.val / 2, f.step + 1));
			}
		}
		return 0;
	}
};

本代码提交AC,用时6MS,只击败5%的人。。。
看讨论区,用位运算求解。要想快速的到达1,则n的二进制中0越多越好,因为0越多,后续越有可能用n/2快速的去掉一位。所以如果n是奇数时,我们判断一下n+1和n-1哪个包含的0越多,就走哪步。
但是每次都需要求n+1和n-1中1的个数,复杂度有点高。
其实,我们只需要关注n的最后两个二进制位即可。任何一个数的二进制尾数最后两位可能有四种情况,00、01、10、11,如果n是偶数,即以00或10结尾,则显然n/2能快速的减少一位。但是如果是01或者11呢。如果是01,则减1会变成00,如果加1,会变成10。显然,减1之后多出一个0,而加1之后0的个数没变,所以如果是以01结尾,则减1更优。
如果末尾是11,则减1变成10,加1变成100,显然加1更优。
有一个例外是,如果n就等于3,即二进制为11,则11→10→1比11→100→10→1更优,即当n==3时,减1更好。
完整代码如下:

class Solution {
public:
	int integerReplacement(int n) {
		if (n == INT_MAX)return 32;
		int ans = 0;
		while (n > 1) {
			if ((n & 1) == 0) n >>= 1;
			else if (n == 3 || ((n >> 1) & 1) == 0)--n;
			else ++n;
			++ans;
		}
		return ans;
	}
};

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

LeetCode Course Schedule

LeetCode Course Schedule
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

click to show more hints.

Hints:

  1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.

排课表问题,一看就是拓扑排序的题。
之前介绍过,拓扑排序有两种解法,一种是类似BFS的Kahn算法,另一种是DFS算法,具体可以参考维基百科的伪代码
解法1:Kahn算法。基本思想,首先把所有入度为0的点放到集合S中(表示这些课没有先修课程,可以首先完成),然后不断从S中取点x,把x指向的所有的点y的边(x,y)删掉,如果删掉之后,y的入度也变为0了,把y也加入到S中。当S为空时,如果图中还有边没删掉,说明形成环了,否则是一个DAG。
想象一下图中的一个环,如同时有边(x,y)和(y,x),则x和y因为都有入度,说明都不可能加入到集合S中,所以这两条边永远都删不掉。
Kahn的算法很好理解,代码类似于BFS,如下:

class Solution {
public:
	bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
		int numEdges = prerequisites.size();
		vector<set<int>> pre(numCourses, set<int>()), next(numCourses, set<int>());
		for (const auto& p : prerequisites) {
			pre[p.first].insert(p.second);
			next[p.second].insert(p.first);
		}
		queue<int> Q;
		for (int i = 0; i < numCourses; ++i) {
			if (pre[i].size() == 0)Q.push(i);
		}
		while (!Q.empty()) {
			int node = Q.front();
			Q.pop();
			for (const auto& n : next[node]) {
				pre[n].erase(node);
				--numEdges;
				if (pre[n].size() == 0)Q.push(n);
			}
		}
		return numEdges == 0;
	}
};

本代码提交AC,用时15MS。
解法2:DFS算法。还可以用DFS求解,基本思想是,维护两个访问标记数组,visited[i]表示全局是否被访问数组,相当于维基百科中的permanently标记,onpath[i]表示当前DFS路径是否被访问数组,相当于维基百科中的temporarily标记。
对于所有visited[i]没访问的点i,我们DFS它。把从i开始DFS到的点标记为onpath[j],如果在DFS的过程中访问到了onpath[k]被标记过的点,说明这条路形成了环,返回false,不是DAG。否则,如果visited[node]==1,说明node是DFS之前的点时被访问过,而之前的DFS返回了true,说明从node DFS的结果是不会形成环的,可以直接返回true。否则如果visited[node]==0,我们从node继续DFS,具体步骤是,首先标记onpath[node]=1,然后把node指向的所有点都DFS一遍,如果都没发现换,则永久标记visited[node]=1,说明从node这个点DFS是没问题的,不会形成环的;同时复位onpath[node]=0,以便下次DFS使用。
完整代码如下,实现方法完全参考维基百科中的DFS版本。

class Solution {
private:
	bool dfs(vector<int>& visited, vector<int>& onpath, vector<vector<int>>& graph, int node) {
		if (onpath[node] == 1)return false;
		if (visited[node] == 0) {
			onpath[node] = 1;
			for (int i = 0; i < graph.size(); ++i) {
				if (graph[node][i] == 1) {
					if (!dfs(visited, onpath, graph, i))return false;
				}
			}
			visited[node] = 1;
			onpath[node] = 0;
			return true;
		}
		return true;
	}
public:
	bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
		vector<vector<int>> graph(numCourses, vector<int>(numCourses, 0));
		for (const auto& p : prerequisites) graph[p.second][p.first] = 1;
		vector<int> visited(numCourses, 0), onpath(numCourses, 0); // visited==permanently; onpath=temporarily
		for (int i = 0; i < numCourses; ++i) {
			if (visited[i] == 0) {
				if (!dfs(visited, onpath, graph, i))return false;
			}
		}
		return true;
	}
};

本代码提交AC,用时62MS,比Kahn慢好多。

LeetCode Pacific Atlantic Water Flow

LeetCode Pacific Atlantic Water Flow
Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:

  1. The order of returned grid coordinates does not matter.
  2. Both m and n are less than 150.

Example:

Given the following 5x5 matrix:
  Pacific ~   ~   ~   ~   ~
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

给定一个矩阵,每个元素表示一个方格中水柱的高度,左上角是太平洋,右下角是大西洋,问哪些坐标的水柱既能流向太平洋,又能流向大西洋。注意每个水柱能流向和它同样高或者比它第的地方。
一看就是DFS或者BFS的题。
拍脑袋解法。对于每个坐标,我们DFS看能否分别到达太平洋或者大西洋。代码如下:

vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down
class Solution4 {
private:
	int m, n;
	bool isOk(int x, int y) {
		return x >= 0 && x < m&&y >= 0 && y < n;
	}
	// type=0:Pacific; 1:Atlantic
	bool dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int x, int y, const int& type) {
		for (int i = 0; i < dirs.size(); ++i) {
			int xx = x + dirs[i][0], yy = y + dirs[i][1];
			if (isOk(xx, yy) && visited[xx][yy] == 0 && matrix[x][y] >= matrix[xx][yy]) {
				visited[xx][yy] = 1;
				if (dfs(matrix, visited, xx, yy, type)) {
					visited[xx][yy] = 0;
					return true;
				}
				visited[xx][yy] = 0;
			}
			else if ((type == 0 && (xx < 0 || yy < 0)) || (type == 1 && (xx >= m || yy >= n))) {
				return true;
			}
		}
		return false;
	}
public:
	vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
		if (matrix.empty() || matrix[0].empty())return{};
		m = matrix.size(), n = matrix[0].size();
		vector<vector<int>> visited(m, vector<int>(n, 0));
		vector<pair<int, int>> ans;
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				visited[i][j] = 1;
				if (dfs(matrix,visited,i,j,0)&&dfs(matrix,visited,i,j,1))
					ans.push_back(pair<int, int>(i, j));
				visited[i][j] = 0;
			}
		}
		return ans;
	}
};

本代码提交AC,用时702MS。
这种DFS的解法重复计算非常多,比如(a,b)这个点DFS时会经过(a-1,b-1),而(a-1,b-1)之前其实已经DFS过了。可以在DFS的过程中记录下经过的点的DFS状态,比如在DFS(a,b)时,走到(a-1,b-1),先查状态,发现(a-1,b-1)到不了大西洋,那现在这条路就没必要继续DFS下去了;相反,如果查状态发现(a-1,b-1)能到大西洋,则后续不需要再DFS其他路径了。
保存状态的DFS版本如下:

vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down
// memory version
class Solution3 {
private:
	int m, n;
	bool isOk(int x, int y) {
		return x >= 0 && x < m&&y >= 0 && y < n;
	}
	bool dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int x, int y, const int& type, vector<vector<vector<int>>>& mem) {
		for (int i = 0; i < dirs.size(); ++i) {
			int xx = x + dirs[i][0], yy = y + dirs[i][1];
			if (isOk(xx, yy) && visited[xx][yy] == 0 && matrix[x][y] >= matrix[xx][yy]) {
				if (mem[xx][yy][type] == 1) {
					mem[x][y][type] = 1;
					return true;
				}
				else if (mem[xx][yy][type] == 0)continue;
				visited[xx][yy] = 1;
				if (dfs(matrix, visited, xx, yy, type, mem)) {
					mem[x][y][type] = 1;
					visited[xx][yy] = 0;
					return true;
				}
				visited[xx][yy] = 0;
			}
			else if ((type == 0 && (xx < 0 || yy < 0)) || (type == 1 && (xx >= m || yy >= n))) {
				mem[x][y][type] = 1;
				return true;
			}
		}
		mem[x][y][type] = 0;
		return false;
	}
public:
	vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
		if (matrix.empty() || matrix[0].empty())return{};
		m = matrix.size(), n = matrix[0].size();
		vector<vector<int>> visited(m, vector<int>(n, 0));
		vector<vector<vector<int>>> mem(m, vector<vector<int>>(n, vector<int>(2, -1)));
		vector<pair<int, int>> ans;
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				visited[i][j] = 1;
				if (mem[i][j][0] == -1)
					dfs(matrix, visited, i, j, 0, mem);
				if (mem[i][j][1] == -1)
					dfs(matrix, visited, i, j, 1, mem);
				visited[i][j] = 0;
				if (mem[i][j][0] == 1 && mem[i][j][1] == 1)
					ans.push_back(pair<int, int>(i, j));
			}
		}
		return ans;
	}
};

无奈,在第112/113这个数据上WA了,但是这个数据太大了,面对的是汪洋大海,调试太费劲,暂时没fix bug。
看了下讨论区,发现主流解法是从海洋开始BFS,分别从大西洋和太平洋BFS,记录下两个海洋分别能访问到的点,最后如果某个点同时被两个海洋访问到了,则说明该点既能到达大西洋,也能到达太平洋。
代码如下:

vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down
class Solution {
private:
	int m, n;
	bool isOk(int x, int y) {
		return x >= 0 && x < m&&y >= 0 && y < n;
	}
	void bfs(vector<vector<int>>& matrix, queue<pair<int, int>>& Q, vector<vector<int>>& visited) {
		while (!Q.empty()) {
			auto f = Q.front();
			Q.pop();
			visited[f.first][f.second] = 1;
			for (int i = 0; i < dirs.size(); ++i) {
				int x = f.first + dirs[i][0], y = f.second + dirs[i][1];
				if (isOk(x, y) && visited[x][y] == 0 && matrix[f.first][f.second] <= matrix[x][y]) {
					Q.push(pair<int, int>(x, y));
				}
			}
		}
	}
public:
	vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
		if (matrix.empty() || matrix[0].empty())return{};
		m = matrix.size(), n = matrix[0].size();
		vector<vector<int>> pacific(m, vector<int>(n, 0)), atlantic(m, vector<int>(n, 0));
		queue<pair<int, int>> pQ, aQ;
		for (int i = 0; i < m; ++i) { // vertical
			pQ.push(pair<int, int>(i, 0));
			aQ.push(pair<int, int>(i, n - 1));
		}
		for (int i = 0; i < n; ++i) { // horizontal
			pQ.push(pair<int, int>(0, i));
			aQ.push(pair<int, int>(m - 1, i));
		}
		bfs(matrix, pQ, pacific);
		bfs(matrix, aQ, atlantic);
		vector<pair<int, int>> ans;
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (pacific[i][j] == 1 && atlantic[i][j] == 1)
					ans.push_back(pair<int, int>(i, j));
			}
		}
		return ans;
	}
};

本代码提交AC,用时减少到45MS。
对于类似的搜索题目,如果是求单个点能否达到目的地,则从起始点或者目的点开始BFS/DFS的效果都是一样的。但是如果要求所有能到达目的点的点,则从目的点开始BFS就能一次性找到这些点,而从每个起始点开始BFS/DFS就非常费劲了。