Tag Archives: DFS

LeetCode Reconstruct Itinerary

LeetCode Reconstruct Itinerary Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK. Note:

  1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
  2. All airports are represented by three capital letters (IATA code).
  3. You may assume all tickets form at least one valid itinerary.
Example 1: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Return ["JFK", "MUC", "LHR", "SFO", "SJC"]. Example 2: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Return ["JFK","ATL","JFK","SFO","ATL","SFO"]. Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
给定一系列机票,每张机票标明了A→B的一段旅程,现在要求把所有的机票旅程连成一条完整的长距离航线,要求起点是JFK。如果有多条合法的航线,则输出字典序最小的那条。 显然要转换为图的问题,每个机场转换为一个点,每张机票转换为一条边,然后从JFK开始DFS,保留每条合法的航线,然后sort取字典序最小的航线。 把问题转换为图不难,使用hash给每个机场编号,然后新建一个图。在图中以JFK开始DFS也不难,每深入DFS一层,机票数目减1,当机票数目为0时,DFS结束,找到一条合法航线。 我一开始是这么做的,但是TLE了,因为这样可能会进行很多次DFS, 找到多条航线,还需要sort取字典序最小的航线。 有没有办法一次找到字典序最小的航线呢,只需要在DFS的时候,每次都从字典序最小的机场开始下一层DFS,这样第一次DFS成功的航线肯定是字典序最小的航线。 所以我们给机场编号的时候,先使用map记录,map会自动按key的字典序从小到大排好。然后遍历map重新编号,并且用hash2记录编号和机场的对应关系。这样,在DFS的时候,从0→n的遍历,就自动是按字典序从小到大遍历。 代码如下: [cpp] class Solution { private: bool dfs(string& ans, vector<string>& hash2, vector<vector<int>>& graph, int start, int lines) { if (lines == 0) return true; int n = hash2.size(); for (int i = 0; i < n; ++i) { // 字典序从小到大深搜 if (graph[start][i] > 0) { –graph[start][i]; ans += hash2[i]; if (dfs(ans, hash2, graph, i, lines – 1))return true; ++graph[start][i]; ans = ans.substr(0, ans.size() – 3); } } return false; } public: vector<string> findItinerary(vector<pair<string, string>> tickets) { map<string, int> hash1; vector<string> hash2; int cnt = 0, n = tickets.size(); for (int i = 0; i < tickets.size(); ++i) { // 记录 hash1[tickets[i].first] = 0; hash1[tickets[i].second] = 0; } for (auto it = hash1.begin(); it != hash1.end(); ++it) { it->second = cnt++; // 字典序从小到大编号 hash2.push_back(it->first); } vector<vector<int>> graph(cnt, vector<int>(cnt, 0)); // 构图 for (int i = 0; i < tickets.size(); ++i)++graph[hash1[tickets[i].first]][hash1[tickets[i].second]]; int start = hash1["JFK"]; string ans = "JFK"; dfs(ans, hash2, graph, start, n); // 深搜 vector<string> Itinerary; for (int i = 0; i <= ans.size() – 3; i += 3)Itinerary.push_back(ans.substr(i, 3)); return Itinerary; } }; [/cpp] 本代码提交AC,用时22MS。]]>

LeetCode Additive Number

LeetCode Additive Number Additive number is a string whose digits can form additive sequence. A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two. For example: "112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid. Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number. Follow up: How would you handle overflow for very large input integers?
给定一个数字字符串,问这个字符串是否是可加的数。一个可加的数是指它可以分割成若干个字符串,每个字符串代表一个数,且这个数列满足斐波那契数列的规律,即后一个数等于前两个数之和。 明显的DFS题。从起点枚举所有可能的长度,转换成数字,然后判断是否等于前两个数字之和。 需要注意的是数组至少要有3个数,且每个数不能有前导0。另外字符串可能很长,导致转换成的数超过int范围,所以用long long和atoll函数。 代码如下: [cpp] typedef long long LL; class Solution { private: bool dfs(const string& num, int start, LL last1, LL last2, int cnt) { int n = num.size(); if (start == n&&cnt >= 3)return true; //if (start < n&&num[start] == ‘0’)return false; // "101" is true int m = num.size() – start; // left length bool ans = false; for (int i = 1; i <= m; ++i) { if (i != 1 && num[start] == ‘0’)continue; // leading zero LL sum = atoll(num.substr(start, i).c_str()); if (cnt >= 2) { if (last1 + last2 > sum)continue; else if (last1 + last2 < sum)return false; else ans = dfs(num, start + i, last2, sum, cnt + 1); } else if (cnt == 0)ans = dfs(num, start + i, sum, last2, cnt + 1); else if(cnt==1)ans= dfs(num, start + i, last1, sum, cnt + 1); if (ans)return true; } return false; } public: bool isAdditiveNumber(string num) { return dfs(num, 0, 0, 0, 0); } }; [/cpp] 本代码提交AC,用时0MS。]]>

LeetCode Target Sum

LeetCode Target Sum You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
  1. The length of the given array is positive and will not exceed 20.
  2. The sum of elements in the given array will not exceed 1000.
  3. Your output answer is guaranteed to be fitted in a 32-bit integer.

给定一个数组nums,和目标结果S,要求给数组中的每个数加上符号+或-,使得和为S。问共有多少种加符号的方案。 第一反应是DFS,遍历每个数,对其加上+或者-,更新S,然后递归。当遍历完所有数,且和等于0时,找到一种方案。 代码如下: [cpp] class Solution { private: void dfs(vector<int>& nums, int step, int S, int& ans) { if (step == nums.size() && S == 0) { ++ans; return; } if (step == nums.size())return; dfs(nums, step + 1, S – nums[step], ans); dfs(nums, step + 1, S + nums[step], ans); } public: int findTargetSumWays(vector<int>& nums, int S) { int ans = 0; dfs(nums, 0, S, ans); return ans; } }; [/cpp] 本代码提交AC,用时1072MS。居然需要这么长时间,果断优化。 思来想去,这本质是一个背包问题,常规0/1背包是对每个商品要还是不要,这题的背包是,对每个数字,是加正号还是负号。 假设dp[i][j]表示前i个数字之和为j的不同加符号方案数,则有如下递归公式 dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]] 右边第一项是指对第i个数字,要赋加号,那么就要保证前i-1个数字之和是j-nums[i],这样(j-nums[i])+nums[i]才会等于j。类似的,如果要对第i个数字赋减号,就要保证前i-1个数字之和是j+nums[i]。所以总的就是这两种情况加和。 需要注意的是,因为可以赋负号,所以加和的结果可能是负数(范围是[-sum,sum]),为了dp[i][j]中的j能用下标访问,统一把所有和加上总和sum,做一个偏移(范围是[0,2*sum]),最终结果就是dp[n][S+sum]。 DP的代码如下: [cpp] class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { int n = nums.size(), sum = 0; for (int i = 0; i < n; ++i)sum += nums[i]; if (S<-sum || S>sum)return 0; //if (S == -sum || S == sum)return 1; // nums={1,0},S=1; 1=1+0=1-0 vector<vector<int>> dp(n + 1, vector<int>(2 * sum + 1, 0)); dp[0][sum] = 1; for (int i = 1; i <= n; ++i) { for (int j = 0; j < 2 * sum + 1; ++j) { //考虑第i个数字是+还是- //i从1开始,所以第i个数字的下标是i-1 if (j >= nums[i – 1])dp[i][j] += dp[i – 1][j – nums[i – 1]]; if (j + nums[i – 1] < 2 * sum + 1)dp[i][j] += dp[i – 1][j + nums[i – 1]]; } } return dp[n][S + sum]; } }; [/cpp] 本代码提交AC,用时19MS,加速将近100倍! DP的问题一般都可以优化空间,比如上述代码可以用两个数组互相滚动赋值来代替n+1个数组。 上面的DP公式理解起来还是有点费劲,下面介绍另一种DP思路,非常简单。 假设我们已经求到前i-1个数字赋不同的符号可以得到的不同和的方案数了,也就是dp[pre]数组,现在要求对第i个数字赋不同符号可能得到的不同和的方案数。那么我们可以遍历dp[pre]数组,只要某个和j对应的方案数不为0(dp[pre][j]!=0),则说明前i-1个数能够组合出和j,且和为j的方案数正好是dp[pre][j],那么我们只需要在和j的基础上考虑加nums[i]或者减nums[i],如果对应的j+nums[i]或j-nums[i]没有超出范围,则这一轮和为j+nums[i]的方案数要加上上一轮和为j的方案数,这一轮和为j-nums[i]的方案数要加上上一轮和为j的方案数。 最后返回dp[cur][S+sum]。非常好理解的一个思路。用这种思路还可以求出从给定数组中取任意多个数相加,可以得到的不同和的方案数,其实和这个题类似,只不过把每个数字的状态改为了取和不取。 代码如下: [cpp] class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { int n = nums.size(), sum = 0; for (int i = 0; i < n; ++i)sum += nums[i]; if (S<-sum || S>sum)return 0; vector<vector<int>> dp(2, vector<int>(2 * sum + 1, 0)); int i = 0, pre = (i & 1) ? 1 : 0, cur = (i & 1) ? 0 : 1; dp[pre][sum] = 1; // 取0个数字,加和为0的方案有1种。把和0偏移到sum位置 while (i < n) { pre = (i & 1) ? 1 : 0; cur = (i & 1) ? 0 : 1; for (int j = 0; j < 2 * sum + 1; ++j) { if (dp[pre][j] != 0) { if (j + nums[i] < 2 * sum + 1)dp[cur][j + nums[i]] += dp[pre][j]; // 在j的基础上加nums[i] if (j – nums[i] >= 0)dp[cur][j – nums[i]] += dp[pre][j]; // 在j的基础上减nums[i] } } fill(dp[pre].begin(), dp[pre].end(), 0); // 清空pre数组,因为下一轮pre要用作cur数组 ++i; } return dp[cur][S + sum]; } }; [/cpp] 本代码提交AC,用时13MS。用了两个滚动数组,空间效率高一点。 ]]>

LeetCode Increasing Subsequences

LeetCode Increasing Subsequences Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 . Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
Note:
  1. The length of the given array will not exceed 15.
  2. The range of integer in the given array is [-100,100].
  3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

给定一个数组,求出改数组的所有递增子序列。注意两点,一是递增,二是子序列。 因为是求子序列,所以没必要对数组排序! 使用DFS,尝试将每个数加入cand,然后从下一个数开始,如果比cand的最后一个数大,则递归DFS。比较简单的思路。 需要注意的点是,结果不能有重复数组,所以需要满足第19、6行的条件,并且用set去重。 第19行条件:比如样例[4,4,6,7,7,8,9,10],第一个4为起点的DFS的结果已经包含第二个4为起点的DFS结果,所以需要第19行。 第6行条件:比如样例[4,4,6,7,7,8,9,10],从6开始DFS时,遇到第一个7和遇到第二个7后续DFS的结果都是一样的,所以需要第6行。 set去重:还会遇到这样的样例比如样例[4,6,7,4,8,9,10],第一个4DFS的结果包含了第二个4DFS的结果,但是这两个4不相邻,所以不能被第19行的条件防止重复,只能用set去重了。 代码如下: [cpp] class Solution { private: void dfs(set<vector<int>>& ans, vector<int>& nums, vector<int>& cand, int start){ if(cand.size() >= 2)ans.insert(cand); for(int i = start + 1; i < nums.size(); ++i){ if(i == start + 1 || nums[i] != nums[i – 1]){ if(nums[i] >= cand[cand.size() – 1]){ cand.push_back(nums[i]); dfs(ans, nums, cand, i); cand.pop_back(); } } } } public: vector<vector<int>> findSubsequences(vector<int>& nums) { set<vector<int>> ans; for(int i = 0; i < nums.size(); ++i){ if(i == 0 || nums[i] != nums[i-1]){ vector<int> cand = {nums[i]}; dfs(ans, nums, cand, i); } } return vector<vector<int>>(ans.begin(), ans.end()); } }; [/cpp] 本代码提交AC,用时269MS。]]>

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代码如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时3MS。 BFS代码如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时0MS,类似的题BFS显然要比DFS快,而且这题用BFS思路更清晰。]]>

hihoCoder 1487-岛屿3

hihoCoder 1487-岛屿3

#1487 : 岛屿3

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

描述

H国正在进行一项持续N周的填海造岛工程。整片工程海域可以被看作是1000×1000的网格。 每周都有一块1×1的单位方格海域被填成陆地。如果我们将连成一片的陆地(一块单位方格与它上下左右4个单位方格是相连的)视为岛屿,H国想监测每周末整片海域中一共存在有多少个岛屿,以及这些岛屿的总面积和总周长各是多少。 假设工程持续三周,第一周被填的海域坐标是(0, 0),那么第一周结束后有1座岛屿、总面积是1、总周长是4:
#..
...
...
第二周被填的海域坐标是(1, 1),那么第二周结束后有2座岛屿、总面积是2、总周长是8:
#..
.#.
...
第三周被填的海域坐标是(1, 0),那么第三周结束后有1座岛屿、总面积是3、总周长是8:
#..
##.
...
你能完成这项任务么?

输入

第一行包含一个整数N,表示工程持续的周数。(1 <= N <= 100000) 以下N行每行包含两个整数x和y,表示当周被填的海域坐标。(0 <= x, y < 1000)

输出

输出N行,每行包含3个整数,依次是当周末岛屿的数量、总面积和总周长。
样例输入
3
0 0
1 1
1 0
样例输出
1 1 4
2 2 8
1 3 8

有一个1000*1000的海域,每周往其中填入1*1的陆地,要求输出每周该海域中会形成多少个岛屿,以及岛屿的总面积和总周长。 其实这题不算难,只是太久没用并查集,用了DFS导致超时了。现在分别介绍两种方法。 首先我们来解决总面积和总周长这两个问题。 总面积好说,每周填入一个单元的陆地,则面积加一。 总周长要稍微注意,如果新加入的方块和其他所有方块都不邻接,则贡献+4周长;如果和一个已有方块邻接,则贡献+4-2周长;如果和两个已有方块邻接,则贡献+4-2*2周长;如果和3个已有方块邻接,则贡献+4-2*3周长。。。所以每加入一个方块,就看看该方块四周,如果和intercnt个方块邻接,则贡献周长+4-2*intercnt。 最麻烦的是求岛屿个数。当然可以像往常一样,对所有点DFS,求连通分量,但是TLE。 我稍微优化了一下,在board中,把每个连通分量都标记为一个不同的islandID,每次新加入一个方块时,令board[x][y]=++islandID,并从这个方块开始DFS,把所有和(x,y)连通的方块的ID都标记为新的(x,y)的islandID,同时记录一下被(x,y) DFS的方块旧的islandID。通过这个过程,能知道新方块(x,y)和多少个不同的旧岛屿相连,同时把所有和(x,y)相连的旧岛屿都标记为新的islandID了。 假设原来有n个岛屿,和新方块相连的旧岛屿有m个,则加入新方块之后,岛屿数更新为n-m+1,即m个旧岛屿都缩成1个新岛屿了。 DFS思路的代码如下: [cpp] #include<iostream> #include<vector> #include<algorithm> #include<utility> #include<cstdio> #include<unordered_set> using namespace std; vector<vector<int>> board(1000, vector<int>(1000, 0)); vector<pair<int,int>> dirs = { {1,0},{-1,0},{0,1},{0,-1} }; void dfs(int x,int y, int islandID, unordered_set<int>& neighbor) { neighbor.insert(board[x][y]); board[x][y] = islandID; for (int i = 0; i < dirs.size(); ++i) { int newx = x + dirs[i].first, newy = y + dirs[i].second; if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] != 0 && board[newx][newy] != islandID)dfs(newx, newy, islandID, neighbor); } } int main() { //freopen("input.txt", "r", stdin); int N, x, y; int island = 0, area = 0, perimeter = 0; int islandID = 1; bool first = true; scanf("%d", &N); while (N–) { scanf("%d %d", &x, &y); board[x][y] = islandID; ++area; if (first) { perimeter = 4; island = 1; first = false; } else { int intercnt = 0; // 邻接方块数 for (int i = 0; i < dirs.size(); ++i) { int newx = x + dirs[i].first, newy = y + dirs[i].second; if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] != 0)++intercnt; } perimeter = perimeter + 4 – 2 * intercnt; if (intercnt == 0)++island; else { unordered_set<int> neighbor; // 邻接岛屿旧编号+新方块编号 dfs(x, y, islandID, neighbor); island = island – neighbor.size() + 2; // 因为neighbor中包含新方块编号,所以这里要多加1 } } ++islandID; printf("%d %d %d\n", island, area, perimeter); } return 0; } [/cpp] 本代码提交TLE,用时2792MS。 比赛结束之后,看了看AC的代码,用的全是并查集,没一个用DFS的。。。 好吧,那就改成并查集。求总面积和总周长的方法都一样,不同的是求岛屿个数。 我们用数组来实现并查集,把坐标(x,y)编码成x*1000+y便于存入一维数组。对于每个新加入的点u,在并查集中先用自己代表自己,represent[u]=u。然后环顾四周,把四周陆地所在岛屿的代表放到neighbor中并去重,这样就能得到新方块邻接的旧岛屿数,根据n-m+1算到新岛屿数。最后把邻接的旧岛屿和新方块u union起来。 代码如下: [cpp] #include<iostream> #include<vector> #include<algorithm> #include<utility> #include<cstdio> #include<unordered_set> using namespace std; vector<vector<int>> board(1000, vector<int>(1000, 0)); vector<pair<int, int>> dirs = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; vector<int> represent(1000 * 1000, -1); int find_rep(int u) { if (u == represent[u])return u; else { represent[u] = find_rep(represent[u]); return represent[u]; } } void union_rep(int u, int v) { represent[find_rep(u)] = find_rep(v); } int main() { //freopen("input.txt", "r", stdin); int N, x, y, u; int island = 0, area = 0, perimeter = 0; bool first = true; scanf("%d", &N); while (N–) { scanf("%d %d", &x, &y); board[x][y] = 1; ++area; u = x * 1000 + y; represent[u] = u; if (first) { perimeter = 4; island = 1; first = false; } else { int intercnt = 0; // 邻接方块数 unordered_set<int> neighbor; // 邻接岛屿 for (int i = 0; i < dirs.size(); ++i) { int newx = x + dirs[i].first, newy = y + dirs[i].second; if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] == 1) { ++intercnt; neighbor.insert(find_rep(newx * 1000 + newy)); } } for (auto it = neighbor.begin(); it != neighbor.end(); ++it)union_rep(u, *it); perimeter = perimeter + 4 – 2 * intercnt; island = island – neighbor.size() + 1; } printf("%d %d %d\n", island, area, perimeter); } return 0; } [/cpp] 本代码提交AC,用时436MS,果然快了不少。]]>

LeetCode Minesweeper

LeetCode Minesweeper Let’s play the minesweeper game (Wikipedia, online game)! You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine. Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

  1. If a mine (‘M’) is revealed, then the game is over – change it to ‘X’.
  2. If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.
  3. If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.
  4. Return the board when no more squares will be revealed.
Example 1:
Input:
[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]
Click : [3,0]
Output:
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
Explanation:

Example 2:
Input:
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
Output:
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
Explanation:

Note:
  1. The range of the input matrix’s height and width is [1,50].
  2. The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.
  3. The input board won’t be a stage when game is over (some mines have been revealed).
  4. For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

扫雷。给定一个棋盘和点击的坐标,要求给出点击之后新的棋盘布局。 为了做这个题,玩了一上午的扫雷。。。 更新规则很简单:
  1. 如果周围(上下左右和四个对角)没有雷,则该位置写’B’,并且递归的在周围模拟点击
  2. 如果周围有雷,则在该位置写上周围有雷的数目
  3. 如果点中了雷,则写上’X’,游戏结束
简单题,使用DFS,遇到以上第1条规则时,递归DFS。 代码如下: [cpp] class Solution { private: void dfs(vector<vector<char>>& board, int i, int j) { if (board[i][j] == ‘E’) { int m = board.size(), n = board[0].size(); vector<vector<int>> dirs = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 },{ -1,-1 },{ -1,1 },{ 1,-1 },{ 1,1 } }; int mines = 0; for (int k = 0; k < dirs.size(); ++k) { int x = i + dirs[k][0], y = j + dirs[k][1]; if (x >= 0 && x < m&&y >= 0 && y < n&&board[x][y] == ‘M’)++mines; } if (mines == 0) { board[i][j] = ‘B’; for (int k = 0; k < dirs.size(); ++k) { int x = i + dirs[k][0], y = j + dirs[k][1]; if (x >= 0 && x < m&&y >= 0 && y < n)dfs(board, x, y); } } else board[i][j] = ‘0’ + mines; } } public: vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) { if (board[click[0]][click[1]] == ‘M’) { board[click[0]][click[1]] = ‘X’; return board; } dfs(board, click[0], click[1]); return board; } }; [/cpp] 本代码提交AC,用时12MS。]]>

LeetCode Beautiful Arrangement

LeetCode Beautiful Arrangement Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:

  1. The number at the ith position is divisible by i.
  2. i is divisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct? Example 1:
Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
Note:
  1. N is a positive integer and will not exceed 15.

本题要求1~N共有多少个漂亮的排列。一个漂亮的排列A[]需要满足以下两个条件中的一个:
  1. A[i]能整除i
  2. i能整除A[i]
上面的规则中下标从1开始。 本题使用DFS解决,想象数组长度为N,每个位置上都可能填入1~N这N个数。咱们从第一个位置,尝试填入1~N,然后把visited置位;第二个位置,尝试填入除第一个已经填入的其他所有数字。每个位置尝试填入时,都需要至少满足以上两个条件中的一个。当所有位置都填满时,找到一个可行解。回退时,需要把visited相关位复位。 完整代码如下: [cpp] class Solution { void dfs(int step, const int& N, vector<int>& visited, int& ans) { if (step > N) { ++ans; return; } for (int i = 1; i <= N; ++i) { if (visited[i] == 0 && (i%step == 0 || step%i == 0)) { visited[i] = 1; dfs(step + 1, N, visited, ans); visited[i] = 0; } } } public: int countArrangement(int N) { vector<int> visited(N + 1, 0); int ans = 0; dfs(1, N, visited, ans); return ans; } }; [/cpp] 本代码提交AC,用时149MS。]]>

LeetCode Number of Islands

200. Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

给定一个二维数组,标’1’表示陆地,标’0’表示水。问这个网格中共有多少个岛屿。一个岛屿就是若干个联通的’1’。 简单题,对所有标’1’的网格进行DFS或BFS,把所有联通的’1’都标记一下。下次遇到一个没标记的’1’就代表一个新的岛屿的出现。 完整代码如下:

class Solution {
private:
    void dfs(vector<vector<char> >& grid, vector<vector<int> >& mark, int i, int j, const int& m, const int& n)
    {
        mark[i][j] = 1;
        if (i – 1 >= 0 && grid[i – 1][j] == ‘1’ && mark[i – 1][j] == 0)
            dfs(grid, mark, i – 1, j, m, n);
        if (i + 1 < m && grid[i + 1][j] == ‘1’ && mark[i + 1][j] == 0)
            dfs(grid, mark, i + 1, j, m, n);
        if (j – 1 >= 0 && grid[i][j – 1] == ‘1’ && mark[i][j – 1] == 0)
            dfs(grid, mark, i, j – 1, m, n);
        if (j + 1 < n && grid[i][j + 1] == ‘1’ && mark[i][j + 1] == 0)
            dfs(grid, mark, i, j + 1, m, n);
    }
public:
    int numIslands(vector<vector<char> >& grid)
    {
        int m = grid.size(), n = 0;
        if (m != 0)
            n = grid[0].size();
        if (m == 0 || n == 0)
            return 0;
        vector<vector<int> > mark(m, vector<int>(n, 0));
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == ‘1’ && mark[i][j] == 0) {
                    ++ans;
                    dfs(grid, mark, i, j, m, n);
                }
            }
        }
        return ans;
    }
};

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

LeetCode Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

本题要根据树的中序和后序遍历结果,重构出树的结构。 有了之前LeetCode Construct Binary Tree from Preorder and Inorder Traversal根据前序和中序重构树的算法,这一题就是照猫画虎了。因为后序遍历是最后一个数为根节点,和前序遍历其实没本质差别。找准inorder和postorder下标的起止位置就可以开始写代码了:

class Solution {
private:
    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int inL, int inR, int postL, int postR, unordered_map<int, int>& hash)
    {
        if (inL > inR || postL > postR)
            return NULL;
        TreeNode* root = new TreeNode(postorder[postR]);
        int idx = hash[root->val];
        root->right = dfs(inorder, postorder, inL + 1, inR, postR – (inR – idx), postR – 1, hash);
        root->left = dfs(inorder, postorder, inL, idx – 1, postL, postR – (inR – idx) – 1, hash);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    {
        if (inorder.size() == 0)
            return NULL;
        unordered_map<int, int> hash;
        for (int i = 0; i < inorder.size(); ++i) {
            hash[inorder[i]] = i;
        }
        return dfs(inorder, postorder, 0, inorder.size() – 1, 0, postorder.size() – 1, hash);
    }
};

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