Tag Archives: DFS

hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

#1542 : 无根数变有根树

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

描述

给定一棵包含 N 个节点的无根树,小Hi想知道如果指定其中某个节点 K 为根,那么每个节点的父节点是谁?

输入

第一行包含一个整数 N 和 K。1 ≤ N ≤ 1000, 1 ≤ K ≤ N
以下N-1行每行包含两个整数 a 和 b,代表ab之间存在一条边。 1 ≤ ab ≤ N
输入保证是一棵树。

输出

输出一行包含 N 个整数,分别代表1~N的父节点的编号。对于 K 的父节点输出0。

样例输入
5 4
1 2
3 1
4 3
5 1
样例输出
3 1 4 0 1

给定一个无根树(其实就是DAG),如果以该树的某个顶点K为根,要求输出每个节点的父节点。
简单题,以K为根,进行DFS,遍历过程中记录每个节点的父节点就好了。完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
const int kMaxN = 1005;
int n, k;
vector<int> parent(kMaxN, 0);
vector<vector<int>> graph(kMaxN, vector<int>(kMaxN, 0));
void DFS(int node, int pre) {
	parent[node] = pre;
	graph[node][pre] = 0;
	graph[pre][node] = 0;
	for (int i = 1; i <= n; ++i) {
		if (graph[node][i] == 1) {
			DFS(i, node);
		}
	}
	graph[node][pre] = 1;
	graph[pre][node] = 1;
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &k);
	int a, b;
	for (int i = 0; i < n - 1; ++i) {
		scanf("%d %d", &a, &b);
		graph[a][b] = 1;
		graph[b][a] = 1;
	}
	DFS(k, 0);
	for (int i = 1; i <= n; ++i)
		printf("%d ", parent[i]);
	return 0;
}

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

LeetCode Find Duplicate Subtrees

LeetCode Find Duplicate Subtrees
Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with same node values.
Example 1: 

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

The following are two duplicate subtrees:

      2
     /
    4

and

    4

Therefore, you need to return above trees' root in the form of a list.


给定一棵二叉树,要求找出其中的重复子树,每组重复子树输出其中一个子树即可。
去重最好的办法就是hash,所以思想是把每个子树hash到一个unordered_map中,如果有多个子树hash到同一个桶,则出现了重复。
所以问题的关键是怎样对一个子树hash。我们可以把一棵子树表示成 (left_hash, root, right_hash),其中left_hash和right_hash分别是左子树和右子树的hash字符串,root表示当前根节点的hash字符串。所以这是一个递归定义。规定空节点的hash值为空串""。
根据子树hash的定义,叶子节点的hash值是("",val,"")。求解子树hash值的过程可以用中序遍历,左根右。为什么子树hash中需要逗号和括号呢,就是为了保证不同严格区分不同的子树,因为单纯的中序遍历是无法区分某些子树的,比如下面的两个子树,中序遍历结果都是2,1,无法区分;但是用本文的hash方法,得到的hash值分别是(2,1,)和(,2,1),这两个字符串是有区别的。

  1
 /
2

 2
  \
   1

在DFS的过程中,把每个子树的hash值记录到一个unordered_map中,然后遍历unordered_map,如果该桶放了多个子树,则取出其中一个即可。
完整代码如下:

class Solution {
private:
	string DFS(TreeNode* root, unordered_map<string, vector<TreeNode*>>& inorders) {
		if (root == NULL)return "";
		string left = DFS(root->left, inorders);
		string right = DFS(root->right, inorders);
		string cur = "(" + left + "," + to_string(root->val) + "," + right + ")";
		inorders[cur].push_back(root);
		return cur;
	}
public:
	vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
		unordered_map<string, vector<TreeNode*>> inorders;
		DFS(root, inorders);
		vector<TreeNode*> ans;
		for (auto &it : inorders) {
			if (it.second.size() > 1)
				ans.push_back(it.second[0]);
		}
		return ans;
	}
};

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

LeetCode Shopping Offers

LeetCode Shopping Offers
In LeetCode Store, there are some kinds of items to sell. Each item has a price.
However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given the each item's price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.
Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.
You could use any of special offers as many times as you want.
Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation:
The price of A is $2, and $3 for B, $4 for C.
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C.
You cannot add more items, though only $9 for 2A ,2B and 1C.

Note:

  1. There are at most 6 kinds of items, 100 special offers.
  2. For each item, you need to buy at most 6 of them.
  3. You are not allowed to buy more items than you want, even if that would lower the overall price.

给定每个商品的单价和需要购买的数量,并且有一些special offer,相当于捆绑销售的优惠套餐。问刚好买到给定数量的商品,所花的最低费用是多少。
注意给定的限制条件中商品最多只有6种,且每件最多只购买6件,所以可以考虑用暴力方法。
把special offer看成一个背包问题里的“商品”,对于每个special offer,我们有两种选择,可以用或者不用。如果需要的needs数组每一项都大于等于某个special offer的每一项,即可以用该special offer,我们比较用和不用该special offer的最终花费,取花费低的。如果用该special offer,则needs数组需要减掉sp捆绑的每件商品的件数,然后继续递归该sp是否可用,相当于完全背包,不计件数的。如果该sp不能用,则递归考虑下一个sp。最后如果递归考虑完所有sp了,则剩余的商品只能按原价购买,算出按原价购买的费用即可。
完整代码如下:

class Solution {
private:
	int dot(vector<int>& price, vector<int>& needs) {
		int ans = 0;
		for (int i = 0; i < needs.size(); ++i) {
			ans += price[i] * needs[i];
		}
		return ans;
	}
	int shopping(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int idx) {
		if (idx == special.size())return dot(price, needs); // 原价购买
		int i = 0, n = special[idx].size();
		vector<int> small_needs = needs;
		for (i = 0; i < n - 1; ++i) {
			if (special[idx][i] > needs[i])break;
			small_needs[i] -= special[idx][i];
		}
		if (i == n - 1)return min(shopping(price, special, small_needs, idx) + special[idx][n - 1], shopping(price, special, needs, idx + 1));
		else return shopping(price, special, needs, idx + 1);
	}
public:
	int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
		return shopping(price, special, needs, 0);
	}
};

本代码提交AC,用时6MS。
参考:https://leetcode.com/articles/shopping-offers/,下次记得看到这种数据量非常小的题,首先尝试暴力方法!

LeetCode Range Sum Query - Mutable

LeetCode Range Sum Query - Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:

Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

给定一个一维数组,要求实现范围求和,即求[i,j]之间的元素的和。sumRange(i,j)求i~j的元素和,update(i,val)更新下标为i的元素值为val。
第一敏感使用线段树,很久之前在hihoCoder上遇到过
建树的方法是类似于树的后序遍历,即左右根。不断把[start,end]二分,构建左右子树,然后构建当前节点,当前节点的sum等于左右子树的sum的和。在递归的时候,递归到start==end时,说明只有一个元素了,此时sum就等于该元素。
查询的方法和建树方法类似,判断区间[i,j]和区间[start,end]的关系,假设start和end的中点是mid,如果j<=mid,递归在左子树查询;如果i>mid,递归在右子树查询;否则在[i,mid]和[mid+1,j]查询然后求和。
更新的方法和查询的方法类似,也是不断判断i和mid的关系,在左子树或者右子树递归更新,当找到该叶子节点时,更新它的sum,返回父节点也更新sum等于新的左右子树的sum的和。
完整代码如下:

class NumArray {
private:
	struct Node {
		int start, end, sum;
		Node *left, *right;
		Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {};
	};
	Node *root;
	Node* constructTree(vector<int> &nums, int start, int end) {
		Node* node = new Node(start, end);
		if (start == end) {
			node->sum = nums[start];
			return node;
		}
		int mid = start + (end - start) / 2;
		node->left = constructTree(nums, start, mid);
		node->right = constructTree(nums, mid + 1, end);
		node->sum = node->left->sum + node->right->sum;
		return node;
	}
	int sumRange(int i, int j, Node *root) {
		if (root == NULL)return 0;
		if (i == root->start&&j == root->end)return root->sum;
		int mid = root->start + (root->end - root->start) / 2;
		if (j <= mid)return sumRange(i, j, root->left);
		else if (i > mid)return sumRange(i, j, root->right);
		else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right);
	}
	void update(int i, int val, Node *root) {
		if (root->start == root->end && root->start == i) {
			root->sum = val;
			return;
		}
		int mid = root->start + (root->end - root->start) / 2;
		if (i <= mid)update(i, val, root->left);
		else update(i, val, root->right);
		root->sum = root->left->sum + root->right->sum;
	}
public:
	NumArray(vector<int> nums) {
		root = NULL;
		if (!nums.empty())root = constructTree(nums, 0, nums.size() - 1);
	}
	void update(int i, int val) {
		if (root == NULL)return;
		update(i, val, root);
	}
	int sumRange(int i, int j) {
		if (root == NULL)return 0;
		return sumRange(i, j, root);
	}
};

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

LeetCode Clone Graph

LeetCode Clone Graph
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.

  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

给定一个无向图,要求克隆一个一样的图,也就是深拷贝。
图的问题,想到应该是DFS或者BFS,但是没太想明白,因为DFS过程中可能遇到之前已经new过的节点,不知道怎么判断比较好,查看讨论区,发现每new一个节点,把这个节点存到一个hash表中就好了,下回先查hash表,不中才new新的。
因为每个节点的label是unique的,所以hash的key可以是label,value是node*。
完整代码如下,注意第9行,new出来的节点要先加入hash,再递归DFS,否则递归DFS在hash表中找不到当前的节点,比如{0,0,0}这个样例就会出错。

class Solution {
private:
	unordered_map<int, UndirectedGraphNode*> graph;
public:
	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
		if (node == NULL)return NULL;
		if (graph.find(node->label) != graph.end())return graph[node->label];
		UndirectedGraphNode *cur = new UndirectedGraphNode(node->label);
		graph[cur->label] = cur;
		for (auto& n : node->neighbors) {
			cur->neighbors.push_back(cloneGraph(n));
		}
		return cur;
	}
};

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

LeetCode Surrounded Regions

LeetCode Surrounded Regions
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

给定一个board,要求把其中被X包围的O也改为X,这里的包围必须四周全都有X
开始的想法是,这个问题类似于找岛屿的问题,可以用BFS/DFS或者并查集,但是感觉不太好弄,比如虽然并查集能找到所有岛屿,但是要区分全包围和半包围还是有点麻烦。
查看讨论区,解法很巧妙。半包围的O肯定出现在边缘,所以我们先从边缘的O开始DFS,把所有半包围的O改为一个其他的字符,比如'1'。这样之后,剩余的所有O肯定是被X全包围的,而那些被标记为'1'的,则是原来被半包围的'O'。所以最后,我们遍历整个board,遇到'O'直接改为'X'就好,遇到'1',则改回原来的'O'。直接O(1)空间复杂度就搞定了,不错。
代码如下:

vector<vector<int>> dirs = { {1,0},{-1,0},{0,1},{0,-1} };
class Solution {
private:
	int m, n;
	bool isOk(int x, int y) {
		return x >= 0 && x < m&&y >= 0 && y < n;
	}
	void dfs(vector<vector<char>>& board, int x, int y) {
		board[x][y] = '1';
		for (int i = 0; i < dirs.size(); ++i) {
			int u = x + dirs[i][0], v = y + dirs[i][1];
			if (isOk(u, v) && board[u][v] == 'O') dfs(board, u, v);
		}
	}
public:
	void solve(vector<vector<char>>& board) {
		if (board.empty() || board[0].empty())return;
		m = board.size(), n = board[0].size();
		for (int i = 0; i < m; ++i) {
			if (board[i][0] == 'O') dfs(board, i, 0);
			if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
		}
		for (int j = 0; j < n; ++j) {
			if (board[0][j] == 'O') dfs(board, 0, j);
			if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
		}
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (board[i][j] == 'O')board[i][j] = 'X';
				else if (board[i][j] == '1')board[i][j] = 'O';
			}
		}
	}
};

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

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 Valid Triangle Number

LeetCode Valid Triangle Number
Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

  1. The length of the given array won't exceed 1000.
  2. The integers in the given array are in the range of [0, 1000].

给定一个数组,问从中能取出所少个三元数组,使得取出的三个数能构成一个三角形。
首先明确三条线段构成三角形的条件是任意两边之和要大于第三遍。
先上暴力,直接dfs枚举出所有的三元组,判断能构成三角形,则方案数加1。代码如下:

class Solution {
private:
	void dfs(int &ans, vector<int>& nums, vector<int>& cand, int idx) {
		if (cand.size() == 3) {
			int &a = cand[0], &b = cand[1], &c = cand[2];
			if (a + b > c&&a + c > b&&b + c > a) {
				++ans;
				//cout << a << "\t" << b << "\t" << c << endl;
			}
			return;
		}
		for (int i = idx; i < nums.size(); ++i) {
			if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return;
			cand.push_back(nums[i]);
			dfs(ans, nums, cand, i + 1);
			cand.pop_back();
		}
	}
public:
	int triangleNumber(vector<int>& nums) {
		int ans = 0;
		vector<int> cand;
		sort(nums.begin(), nums.end());
		dfs(ans, nums, cand, 0);
		return ans;
	}
};

本代码提交TLE:219 / 243。数组最大长度是1000,则所有的组合数有1000*999*998=997002000,确实有点大。。。
后来我发现,报TLE的大数据,虽然有1000个数,但是有很多都是重复的,真正不同的数大概只有100个左右。所以我就想,先对数据去重,在所有互异的数中dfs。然后根据每条边重复的次数来求组合数。
比如样例中,互异的数是[2,3,4],dfs发现[2,3,4]可以构成三角形,则所有由[2,3,4]构成的三角形的个数应该是count[2]*count[3]*count[4]=2*1*1=2。
所以我们先对数组做个hash,统计数值及其出现频率的关系。注意,因为边的长度最大也只为1000,所以用一个1000长的数组来hash比用map或者unordered_map占用的内存更少,否则会MLE。
然后分三类情况进行计算:1. 三条边互不相同;2.有两条边的值相等;3.三条边的值都相等。
其中第一种情况用常规的DFS求解。第二种和第三种情况就是简单的枚举。
还需要注意一点是,边长为0的值需要过滤掉。
完整代码如下:

class Solution {
private:
	void dfs(int& ans, vector<int>& count, vector<int>& nums, vector<int>& cand, int idx) {
		if (cand.size() == 3) {
			int &a = cand[0], &b = cand[1], &c = cand[2];
			if (a + b > c&&a + c > b&&b + c > a) {
				ans += count[a] * count[b] * count; // 三边各异
				//cout << a << "\t" << b << "\t" << c << endl;
			}
			return;
		}
		for (int i = idx; i < nums.size(); ++i) {
			if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return;
			cand.push_back(nums[i]);
			dfs(ans, count, nums, cand, i + 1);
			cand.pop_back();
		}
	}
public:
	int triangleNumber(vector<int>& nums) {
		vector<int> mii(1001, 0);
		for (const auto& i : nums)++mii[i]; // hash
		vector<int> distinct;
		for (int i = 1; i < 1001; ++i) {
			if (mii[i] > 0)distinct.push_back(i);
		}
		int ans = 0;
		vector<int> cand;
		dfs(ans, mii, distinct, cand, 0); // 三边互不相同
		int n = distinct.size();
		for (int i = 0; i < n; ++i) {
			if (mii[distinct[i]] >= 3) { // 三边相同
				int &d = mii[distinct[i]];
				ans += (d*(d - 1)*(d - 2)) / 6;
			}
			for (int j = i + 1; j < n; ++j) {
				if (mii[distinct[i]] >= 2) { // 两条边一样
					int &a = distinct[i], &b = distinct[i], &c = distinct[j];
					if (a + b > c&&a + c > b&&b + c > a) {
						ans += (mii[a] * (mii[a] - 1) / 2)*mii;
					}
				}
				if (mii[distinct[j]] >= 2) { // 两条边一样
					int &a = distinct[i], &b = distinct[j], &c = distinct[j];
					if (a + b > c&&a + c > b&&b + c > a) {
						ans += (mii[b] * (mii[b] - 1) / 2)*mii[a];
					}
				}
			}
		}
		return ans;
	}
};

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

LeetCode Palindrome Partitioning

LeetCode Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

本题要求把字符串s分割成若干个子串,使得每个子串都是回文串。如果有多种分割方法,输出所有的分割方案。
很有意思的一道题。我是这样做的:首先用DP求出任意一个子串s[i,...,j]是否为回文串,这就相当于知道了s中那几个位置可以切割;然后就在s中DFS每个割点,求出所有的分割方案。
DP求s[i,...,j]是否为回文串的过程是这样的,如果s[i]==s[j],且dp[i+1][j-1]也是回文串,则dp[i][j]也是回文串。所以我们需要先求到长度比较短的s[i+1,j-1]是否为回文串,然后再求长度更长的是否为回文串。所以在helper函数的外层循环是子串的长度。
求到了任意一个子串是否为回文串之后,DFS每个割点就好了,这个和枚举排列情况很类似,就不再赘述了。完整代码如下:

class Solution {
private:
	void helper(const string& s, vector<vector<int>>& dp) {
		int n = s.size();
		for (int i = 0; i < n; ++i)dp[i][i] = 1; // 单个字符自身就是回文串
		for (int len = 2; len <= n; ++len) {
			for (int i = 0; i + len - 1 < n; ++i) {
				if (s[i] == s[i + len - 1] && ((i + 1 <= i + len - 2 && dp[i + 1][i + len - 2] == 1) || i + 1 > i + len - 2)) {
					dp[i][i + len - 1] = 1;
				}
			}
		}
	}
	void dfs(const string& s, vector<vector<int>>& dp, vector<vector<string>>& ans, vector<string>& cand,int idx) {
		if (idx == s.size()) {
			ans.push_back(cand);
			return;
		}
		for (int i = idx; i < s.size(); ++i) {
			if (dp[idx][i] == 1) {
				cand.push_back(s.substr(idx, i - idx + 1));
				dfs(s, dp, ans, cand, i + 1);
				cand.pop_back();
			}
		}
	}
public:
	vector<vector<string>> partition(string s) {
		int n = s.size();
		vector<vector<int>> dp(n, vector<int>(n, 0));
		helper(s, dp);
		vector<vector<string>> ans;
		vector<string> cand;
		dfs(s, dp, ans, cand, 0);
		return ans;
	}
};

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

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就非常费劲了。