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。

Leave a Reply

Your email address will not be published. Required fields are marked *