Tag Archives: 数学

hihoCoder 1552-缺失的拼图

hihoCoder 1552-缺失的拼图

#1552 : 缺失的拼图

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

描述

小Hi在玩一个拼图游戏。如下图所示,整个拼图是由N块小矩形组成的大矩形。现在小Hi发现其中一块小矩形不见了。给定大矩形以及N-1个小矩形的顶点坐标,你能找出缺失的那块小矩形的顶点坐标吗?

输入

第一行包含一个整数,N。
第二行包含四个整数,(X0, Y0), (X'0, Y'0),代表大矩形左下角和右上角的坐标。
以下N-1行每行包含四个整数,(Xi, Yi), (X'i, Y'i),代表其中一个小矩形的左下角和右上角坐标。
对于30%的数据, 1 <= N <= 1000
对于100%的数据,1 <= N <= 100000 所有的坐标(X, Y)满足 0 <= X, Y <= 100000000

输出

输出四个整数(X, Y), (X', Y')代表缺失的那块小矩形的左下角和右上角的坐标。

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

一个矩形由N个小矩形拼接而成,现在丢了一个小矩形,怎样才能找到这个小矩形呢。所有矩形都用左下角坐标和右上角坐标表示。
这一题也很有意思,丢掉的那个小矩形的坐标肯定是其他N-1个矩形的坐标中的某4个。我们可以统计每个坐标点出现的次数,如果出现偶数次,则这个点所在的矩形是出现过的,否则这个点就是缺失矩形的某个顶点。最后,从缺失的4个顶点中找出左下角坐标和右上角坐标。
完整代码如下:

#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;
typedef pair<int, int> Point;
int main() {
	//freopen("input.txt", "r", stdin);
	int n;
	scanf("%d", &n);
	map<Point, int> hash;
	int a, b, c, d;
	while (n--) {
		Point left_bottom, right_top;
		scanf("%d %d %d %d", &left_bottom.first, &left_bottom.second, &right_top.first, &right_top.second);
		Point left_top = Point(left_bottom.first, right_top.second), right_bottom = Point(right_top.first, left_bottom.second);
		++hash[left_bottom];
		++hash[right_top];
		++hash[left_top];
		++hash[right_bottom];
	}
	set<Point> ans;
	for (auto p : hash) {
		if (p.second % 2 == 1) {
			ans.insert(p.first);
		}
	}
	a = c = ans.begin()->first;
	b = d = ans.begin()->second;
	for (auto p : ans) {
		a = min(a, p.first);
		b = min(b, p.second);
		c = max(c, p.first);
		d = max(d, p.second);
	}
	printf("%d %d %d %d\n", a, b, c, d);
	return 0;
}

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

hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

#1543 : SCI表示法

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

描述

每一个正整数 N 都能表示成若干个连续正整数的和,例如10可以表示成1+2+3+4,15可以表示成4+5+6,8可以表示成8本身。我们称这种表示方法为SCI(Sum of Consecutive Integers)表示法。
小Hi发现一个整数可能有很多种SCI表示,例如15可以表示成1+2+3+4+5,4+5+6,7+8以及15本身。小Hi想知道N的所有SCI表示中,最多能包含多少个连续正整数。例如1+2+3+4+5是15包含正整数最多的表示。

输入

第一行一个整数 T,代表测试数据的组数。
以下 T 行每行一个正整数N。
对于30%的数据,1 ≤ N ≤ 1000
对于80%的数据,1 ≤ N ≤ 100000
对于100%的数据,1 ≤ T ≤ 10,1 ≤ N ≤ 1000000000

输出

对于每组数据输出N的SCI表示最多能包含多少个整数。

样例输入
2
15
8
样例输出
5
1

每一个正整数都可以表示成一串连续正整数的和,比如15=1+2+3+4+5,8=8(8也是一串连续正整数的和,只不过该串长度为1罢了:))。给定一个正整数N,问N最长能由多少个连续的正整数的和表示。
要使连续串的长度越长,则这些数越小越好。我们可以用滑动窗口的方法,设[i,j]的累加和为sum,则当sum>n时,++i;当sum<n时,++j;当sum==n时,len=j-i+1,更新最大长度。当j>n时循环终止。
完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld", &n);
		if (n == 1 || n == 2) {
			printf("1\n");
		} else {
			ll i = 1, j = 2;
			ll sum = i + j, ans = 0;
			while (true) {
				while (j <= n && sum < n) {
					++j;
					sum += j;
				}
				if (j > n)break;
				while (i < j && sum > n) {
					sum -= i;
					++i;
				}
				if (sum == n) {
					//printf("%d\n", j - i + 1);
					ans = max(ans, j - i + 1);
					break;
				}
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

无奈,提交后TLE,只过了80%的数据。
实在想不出哪里还可以优化了,网上搜库,发现是记录A109814,但是没有递推公式,OEIS上给出的MAPLE程序也需要现算,试了一下,还是TLE。
后来请教某大神,发现一个巧妙的优化方法。如果从1加到i的累加和是sum,如果sum<n,令left=n-sum,如果left是i的正数倍,则从1~i这i个数,每个数都加上left/i,得到的新序列也是连续的,且和正好是sum+(left/i)*i=n,所以我们得到一个长度为i的连续和是n。
举个例子,当n=14时,遍历i,当i=4时,sum=1+2+3+4=10,剩余差值为left=n-sum=4,4%i=0,此时,给每个数加上left/i=1,就变成了2+3+4+5=14=n。
所以,我们只是从1开始遍历,知道累加和大于n,并没有从2开始重新遍历,这种方法需要的遍历数其实是很少的。
完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld", &n);
		if (n == 1 || n == 2) {
			printf("1\n");
		}
		else {
			ll ans = 1;
			for (ll i = 1; i < n; ++i) {
				ll sum = (1 + i)*i / 2;
				if (sum > n)break;
				ll left = sum - n;
				if (left%i == 0) {
					ans = max(ans, i);
				}
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

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

LeetCode 4 Keys Keyboard

LeetCode 4 Keys Keyboard
Imagine you have a special keyboard with the following keys:
Key 1: (A): Prints one 'A' on screen.
Key 2: (Ctrl-A): Select the whole screen.
Key 3: (Ctrl-C): Copy selection to buffer.
Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.
Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.
Example 1:

Input: N = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2:

Input: N = 7
Output: 9
Explanation:
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Note:

  1. 1 <= N <= 50
  2. Answers will be in the range of 32-bit signed integer.

给定四个按键,有四种操作:

  • A: 打印一个字符A
  • Ctrl-A: 全选
  • Ctrl-C: 复制
  • Ctrl-V: 粘贴

问通过n次按键操作,最多可以打印出多少个字符。
稍微分析一下,增加字符比较快的方法是用Ctrl-V,连带着需要Ctrl-C和Ctrl-A的配合,所以要想快速增加字符,必须要以Ctrl-A, Ctrl-C, Ctrl-V结尾,这就需要3个操作。当n比较小时,这3个操作相对来说比较耗时,通过分析可知,当N<=6时,直接用N次Print(A)操作能得到最多的字符。
假设dp[i]表示使用i次操作能得到的最多字符,显然dp[i]=i,当i<=6时。
当i>6时,我们可以考虑用Ctrl-A, Ctrl-C, Ctrl-V,所以结尾我们至少要空出3个操作来使用技能,也就是我们最多只能在i-3的地方开始释放Ctrl-A, Ctrl-C, Ctrl-V技能,假设释放技能的位置是b,则b<=i-3;下界是我们可以在一开始只有一个字符时使用技能,即b>=1。所以我们遍历[1,i-3]的地方释放技能,则我们可以有i-b-2个Ctrl-V结尾,再加上释放技能的位置已经有一个dp[b]了,所以总字符数是dp[b]*(i-b-1)。使用贪心策略求最大值。
完整代码如下:

class Solution {
public:
	int maxA(int N) {
		if (N <= 6)return N;
		vector<int> dp(N + 1, 0);
		for (int i = 1; i <= 6; ++i)dp[i] = i;
		for (int i = 7; i <= N; ++i) {
			for (int b = i - 3; b >= 1; --b) {
				dp[i] = max(dp[i], dp[b] + dp[b] * (i - b - 2));
			}
		}
		return dp[N];
	}
};

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

LeetCode Set Mismatch

LeetCode Set Mismatch
The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.
Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.
Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Note:

  1. The given array size will in the range [2, 10000].
  2. The given array's numbers won't have any order.

一个大小为n的数组,本来包含1~n这n个数,但是某个数x“突变”成y了,这就导致数组中丢了x,而y重复出现了两次,现在要找出丢掉的x和重复的y。
简单题,首先用hash可以找到重复的y,然后根据数学关系可以找到x,本来1~n的和是S=n*(n+1)/2,设现在的和是T,则有x=y-T+S。
代码如下:

class Solution {
public:
	vector<int> findErrorNums(vector<int>& nums) {
		vector<int> ans(2, 0);
		unordered_set<int> hash;
		int sum = 0, n = nums.size();
		for (const auto& num : nums) {
			if (hash.find(num) != hash.end())ans[0] = num;
			hash.insert(num);
			sum += num;
		}
		ans[1] = ans[0] - sum + n*(n + 1) / 2;
		return ans;
	}
};

本代码提交AC,用时59MS。
还有一种空间复杂度O(1)的方法,不过需要改变原有数组。
因为数组元素是1~n的,所以遍历数组,把数值-1当作下标访问数组,使该处的元素变为原来的相反数,如果遇到某个数y-1访问的那个数是负数,说明y重复了,之前有一个y把y-1处的数变成了负数。
遍历完一遍之后,丢失的那个数x指向的x-1处的数应该是正数,因为x丢掉了,没有经过上面的过程,所以再遍历一遍可以找到x。
整个过程不需要借助额外的空间,代码如下:

class Solution {
public:
	vector<int> findErrorNums(vector<int>& nums) {
		vector<int> ans(2, 0);
		for (int i = 0; i < nums.size(); ++i) {
			int idx = nums[i] < 0 ? -nums[i] : nums[i];
			if (nums[idx - 1] < 0) {
				ans[0] = idx;
			} else {
				nums[idx - 1] = -nums[idx - 1];
			}
		}
		for (int i = 0; i < nums.size(); ++i) {
			if (nums[i] > 0) {
				ans[1] = i + 1;
				break;
			}
		}
		return ans;
	}
};

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

LeetCode Solve the Equation

LeetCode Solve the Equation
Solve a given equation and return the value of x in the form of string "x=#value". The equation contains only '+', '-' operation, the variable xand its coefficient.
If there is no solution for the equation, return "No solution".
If there are infinite solutions for the equation, return "Infinite solutions".
If there is exactly one solution for the equation, we ensure that the value of x is an integer.
Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"

解一个一元一次方程。简单题,首先把方程分解成等号两边两个子表达式,然后解析这两个子表达式,使成为la+lb*x=ra+rb*x,再转换为(lb-rb)x=ra-la,令lb-rb=b, ra-la=a,则最终的表达式等价于bx=a。
如果b等于0,且a也等于0,则有无穷多解。如果b等于0,但a不等于0,则无解。否则x=a/b。
所以问题的难点是怎样把一个表达式转换为a+bx的形式。也就是代码中的convert函数。遍历字符串,取出每个带符号的操作数,如果该操作数包含'x',则取出系数,加到b上;否则是常数项,加到a上。
有一个需要注意的点是包含'x'的操作数可能是'-x'或者'+x',提取系数时需要特殊判断。
代码如下:

class Solution {
private:
	void convert(string& s, int& a, int& b) {
		int aa = 0, bb = 0;
		s += "+";
		int start = 0, end = 0;
		for (end = 0; end < s.size(); ++end) {
			if (end != 0 && (s[end] == '+' || s[end] == '-')) { // -x=-1
				string tmp = s.substr(start, end - start);
				if (tmp.find('x') != string::npos) {
					if (tmp == "x" || tmp == "+x")bb += 1;
					else if (tmp == "-x")bb -= 1;
					else bb += stoi(tmp.substr(0, tmp.size() - 1));
				}
				else {
					aa += stoi(tmp);
				}
				start = end;
			}
		}
		a = aa;
		b = bb;
	}
public:
	string solveEquation(string equation) {
		size_t pos = equation.find('=');
		string left = equation.substr(0, pos), right = equation.substr(pos + 1);
		int la = 0, lb = 0, ra = 0, rb = 0;
		convert(left, la, lb);
		convert(right, ra, rb);
		int b = lb - rb, a = ra - la;
		if (b == 0) {
			if (a == 0)return "Infinite solutions";
			else return "No solution";
		}
		else {
			return "x=" + to_string(a / b);
		}
	}
};

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

LeetCode Continuous Subarray Sum

LeetCode Continuous Subarray Sum
Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.
Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

  1. The length of the array won't exceed 10,000.
  2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

给定一个非负整数数组和k,问数组中是否存在长度至少为2的连续子数组,子数组的和是k的n倍,n也是一个整数。
这个题之前好像在哪遇到过。遇到连续子数组的问题,首先要想到前缀和。因为这里要求和是k的n倍,有点麻烦。
首先我们需要知道一个数学知识,如果到i的前缀和accusum1和到j的前缀和accusum2除以k的余数相等,那么(i,j]的连续子数组的和就是k的整数倍。比如第一个样例中,连续子数组的和以及连续子数组的和除以k的余数:

  • [23,25,29,35,42]
  • [5,1,5,5,0]

如果下标从0开始,则下标为0和2的accusum%k都等于5,说明(0,2]的连续子数组的和是k的整数倍。accusum(0,2]=2+4=6,确实是6的整数倍。
这个道理其实很好理解,accusum0%k=5,到了accusum2%k还等于5,说明中间只加了整数倍的k,才导致余数没变,因为整数倍的k 模k是等于0的。
知道了这个道理就好办了,我们用map保存accusum%k的值和计算到现在的accusum的下标,如果后来遇到一个accusum模k的余数在map中,说明找到了一个可能,我们再判断一下他们之间的距离是否至少为2即可。
还有一个特殊的地方需要注意的是,如果k等于0,则不能取模运算。
最后还要注意的一点是,第12行,把当前余数和下标插入map是在else分支的,只有当map中不存在这个余数才插入,否则不插入。比如上面的例子,我们遇到多个accusum模k的余数是5,但是我们map中保存的应该是第0个下标,后续的余数等于5的下标不能更新0这个下标,因为这样才能使得后续的余数相等的下标和map中的下标的差越大,即更好的满足距离至少为2的约束。
完整代码如下:

class Solution {
public:
	bool checkSubarraySum(vector<int>& nums, int k) {
		unordered_map<int, int> reminders;
		reminders[0] = -1;
		int accusum = 0;
		for (int i = 0; i < nums.size(); ++i) {
			accusum += nums[i];
			if (k != 0)accusum %= k; // 注意k为0时,不能取模
			if (reminders.find(accusum) != reminders.end()) {
				if (i - reminders[accusum] >= 2)return true;
			} else reminders[accusum] = i; // 注意必须是在else分支
		}
		return false;
	}
};

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

LeetCode Sum of Square Numbers

LeetCode Sum of Square Numbers
Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.
Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

给定一个非负整数c,问是否存在两个整数a和b,使得a2 + b2 = c。
简单题,首尾指针法,首尾指针分别指向[0,c],根据a2 + b2 和 c的大小,首指针++或者尾指针--。
但是这样性能太差,过不了大数据,其实尾指针只需要到sqrt(c)即可,因为如果b大于sqrt(c)的话,a2 + b2 肯定大于 c的。所以新的首尾指针范围就是[0,sqrt(c)],性能大幅提升。
代码如下:

class Solution {
public:
	bool judgeSquareSum(int c) {
		long long i = 0, j = sqrt(c) + 1;
		while (i <= j) {
			long long cur = i*i + j*j;
			if (cur == c)return true;
			else if (cur < c)++i;
			else --j;
		}
		return false;
	}
};

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

LeetCode Minimum Factorization

LeetCode Minimum Factorization
Given a positive integer a, find the smallest positive integer b whose multiplication of each digit equals to a.
If there is no answer or the answer is not fit in 32-bit signed integer, then return 0.
Example 1
Input:

48

Output:

68

Example 2
Input:

15

Output:

35

给定一个数a,要求找一个最小的数b,使得b的各位数字相乘的结果等于a。
很有意思的一个题,考察数学,当时没做出来,参考了这个题
首先,如果a小于10的话,那么最小的b就是a了,否则b就要变成十位数或者百位数。比如a=8,则最小的b就是8,当然b也可以是十位数比如24或者42,但是都大于个位数8自己。
当a大于等于10时,我们需要找a的因子,为了是b最小,则我们希望b的位数越少越好。所以我们要找b的因子应该越大越好。所以我们从最大的因子9开始找起,从9一直找到2,把a的所有因子都找出来。比如48从大到小的因子是8和6,则最终结果就是把因子从小到大组成一个数,即68。
这里有一个问题,48的因子还可以是4和2呀,为什么没有了呢。因为我们从9→2开始找因子的过程中,是用a除以因子得到的商来不断的找。上面48找到8和6的因子之后,商就等于1了,不需要再找因子了,所以结束。
如果在找因子的过程中,发现商变成了一个质数,因为大于10的质数不可能被分解,所以无解,返回0。
代码如下:

class Solution {
public:
	int smallestFactorization(int a) {
		if (a < 10)return a;
		vector<int> factors;
		for (int i = 9; i >= 2; --i) {
			while (a%i == 0) {
				factors.push_back(i);
				a /= i;
			}
		}
		if (a != 1)return 0; // caution
		long long ans = 0;
		for (int i = factors.size() - 1; i >= 0; --i) {
			ans = ans * 10 + factors[i];
		}
		return ans > INT_MAX ? 0 : ans;
	}
};

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

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 Rotate Function

LeetCode Rotate Function
Given an array of integers A and let n to be its length.
Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow:
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
Calculate the maximum value of F(0), F(1), ..., F(n-1).
Note:
n is guaranteed to be less than 105.
Example:

A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

给定一个数组A,和函数F(k),其中F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1],数组B为数组A顺时针旋转k次后的新数组。要求所有F(k)的最大值。
仔细观察样例,会发现F(k)=\sum_{i=0}^{n-1}((k+i)\%n)*a_i。于是可以算出所有的F(k),然后求最大值。代码如下:

class Solution {
public:
	int maxRotateFunction(vector<int>& A) {
		if (A.empty())return 0;
		int ans = INT_MIN, n = A.size();
		for (int k = 0; k < n; ++k) {
			int cur = 0;
			for (int i = 0; i < n; ++i) {
				cur += ((k + i) % n)*A[i];
			}
			ans = max(ans, cur);
		}
		return ans;
	}
};

本代码提交TLE,复杂度是O(kn),遇到大数据时超时了。
如果再仔细研究一下样例,会发现一个更优的递推公式:F(k)=F(k-1)+sum-n*A[n-k]。这样直接根据前一项F(k-1),可以在O(1)时间算出下一项F(k)。总的时间复杂度只有O(n)。代码如下:

class Solution {
public:
	int maxRotateFunction(vector<int>& A) {
		if (A.empty())return 0;
		int n = A.size(), sum = 0, f0 = 0;
		for (int i = 0; i < n; ++i) {
			sum += A[i];
			f0 += i*A[i];
		}
		int ans = f0, pre = f0;
		for (int i = 1; i < n; ++i) {
			int cur = pre + sum - n * A[n - i];
			ans = max(ans, cur);
			pre = cur;
		}
		return ans;
	}
};

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