Tag Archives: 数论

LeetCode Find the Derangement of An Array

LeetCode Find the Derangement of An Array
In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.
There's originally an array consisting of n integers from 1 to n in ascending order, you need to find the number of derangement it can generate.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:

Input: 3
Output: 2
Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].

Note:
n is in the range of [1, 106].


给定一个长度为n的数组[1,2,3,...,n],如果该数组的一个排列中,每个数字都不在它原来的位置了,我们称这个排列是原数组的一个Derangement(错排)。问长度为n的数组,有多少个Derangement。
维基百科关于错排问题有比较详细的解释
假设dp[n]表示长度为n的数组的错排个数,显然dp[0]=1,dp[1]=0,dp[2]=1。如果已经知道dp[0,...,n-1],怎样求dp[n]。考虑第n个数,因为错排,它肯定不能放在第n位,假设n放在第k位,则有如下两种情况:
数字k放在了第n位,这时,相当于n和k交换了一下位置,还剩下n-2个数需要错排,所以+dp[n-2]
数字k不放在第n位,此时,可以理解为k原本的位置是n,也就是1不能放在第1位、2不能放在第2位、...、k不能放在第n位,也就相当于对n-1个数进行错排,所以+dp[n-1]
因为n可以放在1~n-1这n-1个位置,所以总的情况数等于dp[n]=(n-1)(dp[n-1]+dp[n-2])。
这就类似于求斐波那契数列的第n项了,维护前两个变量,不断滚动赋值就好了,时间复杂度O(n),代码如下:

const int MOD = 1000000007;
class Solution {
public:
	int findDerangement(int n) {
		if (n == 0)return 1;
		if (n == 1)return 0;
		long long p = 0, pp = 1;
		for (int i = 2; i <= n; ++i) {
			long long cur = ((i - 1)*(p + pp)) % MOD;
			pp = p;
			p = cur;
		}
		return p;
	}
};

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

LeetCode Next Greater Element III

LeetCode Next Greater Element III
Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
Example 1:

Input: 12
Output: 21

Example 2:

Input: 21
Output: -1

给定一个数n,要求用和n一样的数字,重组成一个比n大的最小的数。如果不存在这样的数,输出-1。
比如样例1,n=12,则同样用数字1和2,重组出比12大的最小的数就是21。如果n本身等于21,则无法用数字1和2重组出比21更大的数了。
首先很容易想到无解的情况,比如n=76543210,因为n的数字从左到右是非升序的,所以n本身已经是最大的了,无法重组出比n更大的数。所以隐隐约约感觉可以从左往右找第一个上升的位置。
再来,n=76546743,如果从左往右找第一个上升的位置,则是i=3的数字4,4->6是上升的,所以可以考虑从4后面找比4大的最小的数,也就是6,交换4和6,变成76564743,因为原来为4的位置已经变成更大的6了,所以6后面最小即可,对6后面的数排序,变成了76563447。
但是76563447并不是比n大的最小的数,另外还有76547346,也就是不变4,而是变i=4的数字6。所以换一种思路,我们从右往左找第一个下降的位置,比如这里是i=5的数字7,然后从该位置往右找一个比i-1的数6大的最小的数7,交换他们的位置,同时把i-1右边的数从小到大排序。
再比如n=12443322,从右往左找第一个下降的位置是i=2,数字为4,从该位置找一个比i-1的数2大的最小的数是i=4的数3,交换他们n=1344222,再对i-1右边的数从小到大排序,得到n=1322244。
完整代码如下,另外需要注意结果不能超出int范围,所以先转换为long long,再和INT_MAX比较。

class Solution {
public:
	int nextGreaterElement(int n) {
		string s = to_string(n);
		int m = s.size();
		for (int i = m - 1; i > 0; --i) {
			if (s[i] > s[i - 1]) {
				int pos = i;
				for (int j = i; j < m; ++j) {
					if (s[j] > s[i - 1] && s[j] < s[pos]) {
						pos = j;
					}
				}
				swap(s[pos], s[i - 1]);
				sort(s.begin() + i, s.end());
				long long ans = stoll(s);
				if (ans <= INT_MAX)return ans;
				else return -1;
			}
		}
		return -1;
	}
};

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

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。

hihoCoder 1518-最大集合

hihoCoder 1518-最大集合

#1518 : 最大集合

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

描述

给定一个1-N的排列A[1], A[2], ... A[N],定义集合S[K] = {A[K], A[A[K]], A[A[A[K]]] ... }。
显然对于任意的K=1..N,S[K]都是有限集合。
你能求出其中包含整数最多的S[K]的大小吗?

输入

第一行包含一个整数N。(1 <= N <= 100000)
第二行包含N个两两不同的整数,A[1], A[2], ... A[N]。(1 <= A[i] <= N)

输出

最大的S[K]的大小。

样例输入
7
6 5 1 4 2 7 3
样例输出
4

给定一个1~N的排列A,然后定义关于k的集合S[K] = {A[K], A[A[K]], A[A[A[K]]] ... },要求最大的S[K]的大小。
分析一下样例,当k=1时,S[1]={6,7,3,1,6...},循环节是{6,7,3,1},然后又从6开始循环,但是S是集合,所以|S[1]|=4。当k=2时,S[2]={5,2,5...},循环节是{5,2},所以|S[2]|=2。当k=3时,S[3]={1,6,7,3,1...},发现规律了吗,根据集合的无序性,S[3]==S[1]的。
其实这有点像置换群,6开始的循环节中,对于{6,7,3,1}中的任意一个数K,都有S[K]=4。同理对于另一个循环节{2,5}中的任意一个数K,都有S[K]=2。所以其实我们不需要对A中的所有数都求S[K],只需要求出一个循环节之后,其循环内的所有K的S[K]都相等,这样可以节省很多重复计算。
最后从多个不相交的循环中求最大的S[K]即可。
代码如下:

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
using namespace std;
unordered_map<int, int> result;
void solve(vector<int>& A, int start) {
	unordered_set<int> si;
	si.insert(start);
	int last = start;
	while (si.find(A[last]) == si.end()) {
		si.insert(A[last]);
		last = A[last];
	}
	int ans = si.size();
	unordered_set<int>::iterator it = si.begin();
	while (it != si.end()) {
		result[*it] = ans; // 循环内的所有S[K]都相等
		++it;
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	int n;
	scanf("%d", &n);
	vector<int> A(n + 1, 0);
	for (int i = 1; i <= n; ++i)scanf("%d", &A[i]);
	for (int i = 1; i <= n; ++i) {
		if (result.find(A[i]) == result.end())solve(A, A[i]);
	}
	int ans = 0;
	for (unordered_map<int, int>::iterator it = result.begin(); it != result.end(); ++it)ans = max(ans, it->second);
	printf("%d\n", ans);
	return 0;
}

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

hihoCoder 1493-歌德巴赫猜想

hihoCoder 1493-歌德巴赫猜想

#1493 : 歌德巴赫猜想

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

描述

哥德巴赫猜想认为“每一个大于2的偶数,都能表示成两个质数之和”。
给定一个大于2的偶数N,你能找到两个质数P和Q满足P<=Q并且P+Q=N吗?

输入

一个偶数N(4 <= N <= 1000000)

输出

输出P和Q。如果有多组解,输出P最小的一组。

样例输入
10
样例输出
3 7

给定一个大于2的偶数N,找出两个质数P和Q,满足P<=Q且P+Q=N。
我还以为这题有什么数论技巧,没想到直接从小到大暴力枚举P就行了。。。
代码如下:

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
bool isPrim(int x) {
	if (x < 2)return false;
	for (int i = 2; i <= sqrt(x); ++i) {
		if (x%i == 0)return false;
	}
	return true;
}
int main() {
	int N;
	scanf("%d", &N);
	for (int i = 2; i <= N / 2; ++i) {
		if (isPrim(i) && isPrim(N - i)) {
			printf("%d %d\n", i, N - i);
			return 0;
		}
	}
	return 0;
}

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

LeetCode 132 Pattern

LeetCode 132 Pattern
Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.
Example 1:

Input: [1, 2, 3, 4]
Output: False
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: [3, 1, 4, 2]
Output: True
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: [-1, 3, 2, 0]
Output: True
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

给定一个数组,问数组中是否存在132这样的子序列。132是指i<j<k,但a[i]<a[k]<a[j]的形式,132就是这样一个例子,中间最大,右边次之,左边最小。
解法1。朴素解法,直接查找是否存在这样的i,j,k。首先找i,即满足a[i]<a[i+1]这样的i。然后找j,我们希望a[j]越大越好,这样的话,才可能找到a[k]<a[j]的k,所以a[j]<a[j+1]时,j++,因为前面有更大的a[j],照样满足a[i]<a[j],还可能更容易找到小于a[j]的a[k]。当确定i,j之后,a[k]就在j后面不断找在a[i]和a[j]之间的数。
代码如下:

class Solution {
public:
	bool find132pattern(vector<int>& nums) {
		int i = 0, j = 0, k = 0, n = nums.size();
		while (i < n) {
			while (i < n - 1 && nums[i] >= nums[i + 1])++i;
			j = i + 1;
			while (j < n - 1 && nums[j] <= nums[j + 1])++j;
			k = j + 1;
			while (k < n) {
				if (nums[k] > nums[i] && nums[k] < nums[j])return true;
				++k;
			}
			++i;
		}
		return false;
	}
};

本代码提交AC,用时299MS。
解法2。使用栈。从数组末尾往前找,我们希望a[j]越大越好,而a[k]最好是次大的,这样a[i]就更容易小于a[k]了。定义一个变量third表示132模式中的第三个数,就是132中的2。初始时令third=INT_MIN。定义一个堆栈stk保存比third大的所有数,如果nums[i]小于third,表示找到了第一个数1,返回true。如果nums[i]大于stk栈顶,表示找到了更大的数,则把stk中的数给third,表示third保存的是次大的数,然后把nums[i]压入stk。
代码如下:

class Solution {
public:
	bool find132pattern(vector<int>& nums) {
		stack<int> stk;
		int third = INT_MIN;
		for (int i = nums.size() - 1; i >= 0; --i) {
			if (nums[i] < third)return true;
			else {
				while (!stk.empty() && nums[i] > stk.top()) {
					third = stk.top();
					stk.pop();
				}
				stk.push(nums[i]);
			}
		}
		return false;
	}
};

本代码提交AC,用时23MS,快了不少。

LeetCode Water and Jug Problem

LeetCode Water and Jug Problem
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
Operations allowed:

  • Fill any of the jugs completely with water.
  • Empty any of the jugs.
  • Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

很有意思的水罐问题。给定一个3L的水罐和一个5L的水罐和无限的水,问怎样才能得到4L的水。
这个例子很常见了,可以这样做:

  1. 盛满5L水罐;
  2. 将5L水罐中的水导入3L水罐,此时5L水罐中还剩2L水;
  3. 将3L水罐中的水清空;
  4. 将5L水罐中的2L水倒入3L水罐中;
  5. 盛满5L水罐;
  6. 将5L水罐中的水倒入3L水罐中,此时5L水罐中剩余4L水,3L水罐中是满的;
  7. 将3L水罐中的水清空,此时只剩5L水罐中的4L水。

但是遇到一般的x、y、z时,怎样解呢,这里面肯定暗含某种数学规律,看了题解才恍然大悟
将问题转换为这样一个问题:给定xL和yL水罐和无限的水,以及一起无穷大的水罐,怎样利用x和y才能在无穷大的水罐中盛满zL的水。假设我们要往无穷大的水罐中倒m次xL的水和n次yL的水,则有mx+ny=z,如果m为正,则是倒入,为负则是舀出。比如x=3, y=5, z=4时,有(-2)*3+2*5=4,表示往无穷大的水罐中倒入2次5L的水,并且舀出2次3L的水,剩余正好4L。而上面的7步正好也包含2次盛满5L水,2次清空3L水。
所以问题就转换为方程mx+ny=z对于m,n是否有整数解。这需要用到裴蜀定理,又是头一回听说。
假设x和y的最大公约数是d=gcd(x,y),如果z是d的整数倍,则上式有整数解。所以问题就好办了,求一下x,y的最大公约数,然后判断z是否是最大公约数的整数倍就好了。
另外要保证x+y>=z,因为如果x和y加起来的容量都没有z大,怎么可能使得两个罐中水量之和正好等于z呢。
代码如下:

class Solution {
private:
	int gcd(int x, int y) {
		return y == 0 ? x : gcd(y, x%y);
	}
public:
	bool canMeasureWater(int x, int y, int z) {
		return z == 0 || (x + y >= z&&z%gcd(x, y) == 0);
	}
};

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

LeetCode Perfect Number

LeetCode Perfect Number
We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.
Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.
Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

Note: The input number n will not exceed 100,000,000. (1e8)


判断一个数是否是完美数。完美数的定义是:一个正数,它等于它的所有不包括自己正因子数之和。比如28的所有不包括自己的正因子数有1,2,4,7,14,加起来正好等于28,所以28是一个完美数。
判断的方法也简单,因子i从1~sqrt(num),判断i是否是num的因子,如果是,则把i和num/i都加到结果里。最后判断结果是否等于num。
需要说明两点。一是循环只需进行到sqrt(num),因为大于sqrt(num)的因子可以由小于sqrt(num)的因子被num除得到,比如num=a*b,且a<b,则遍历到a时,如果num%a==0,则num/a就是b。二是注意要排除num自己这个因子,所以当a=1时,就不加num/a了。
代码如下:

class Solution {
public:
	bool checkPerfectNumber(int num) {
		if (num <= 1)return false;
		int ans = 0, n = sqrt(num);
		for (int i = 1; i <= n; ++i) {
			if (num%i == 0) {
				ans += i;
				if (i != 1 && num / i != i)ans += num / i;
			}
		}
		return ans == num;
	}
};

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

LeetCode Maximum XOR of Two Numbers in an Array

LeetCode Maximum XOR of Two Numbers in an Array
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:

Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.

给定一个非空数组,从中任意选两个数进行异或操作,问最大的异或结果是多少。
暴力两层循环肯定是不行的,本题需要一些位运算的技巧,解法参考讨论区
题目限制数值范围在[0,231),所以异或操作最多需要考虑32位。我们从最高位开始考察,判断每一位在数组中异或之后能否得到1的结果。
假设我们已经知道前i-1位的异或最大值为ans,现在要求前i位的异或最大值。我们先把数组中所有数的前i位结果取出来,放到unordered_set<int> hash中。理想情况下,我们希望第i位的异或结果是1,即假设前i位的异或最大值为tmpmax=ans|(1<<i)。我们需要判断hash中是否有两个数异或能得到tmpmax的结果,如果能,说明前i位的异或最大值确实可以达到tmpmax。
也就是说我们需要从hash中选两个数a和b,判断a^b==tmpmax是否成立。常规方法是对hash两层循环判断,但是这样太慢了。利用异或的性质,我们有:如果a^b==tmpmax,则a=b^tmpmax和b=a^tmpmax。比如下面的例子,只是把^和=换了个位置,结果照样成立。

  • 0^0=0 | 0=0^0
  • 0^1=1 | 0=1^1
  • 1^0=1 | 1=0^1
  • 1^1=0 | 1=1^0

所以,我们只需要遍历hash中的数a,和tmpmax异或,如果异或结果b还在hash中,则说明b==a^tmpmax也在hash中,即a^b==tmpmax也成立。说明前i位的异或最大值确实可以达到tmpmax。
代码如下:

class Solution {
public:
	int findMaximumXOR(vector<int>& nums) {
		int ans = 0, mask = 0;
		for (int i = 31; i >= 0; --i) {
			mask |= (1 << i);
			unordered_set<int> hash;
			for (const auto& num : nums) {
				hash.insert(num & mask);
			}
			int tmpmax = ans | (1 << i);
			for (const auto& prefix : hash) {
				if (hash.find(prefix ^ tmpmax) != hash.end()) {
					ans = tmpmax;
					break;
				}
			}
		}
		return ans;
	}
};

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

LeetCode Base 7

LeetCode Base 7
Given an integer, return its base 7 string representation.
Example 1:

Input: 100
Output: "202"

Example 2:

Input: -7
Output: "-10"

Note: The input will be in range of [-1e7, 1e7].


本题要把10进制数转换为7进制数。
根据以往10进制转换为2进制的规则,使用短除法,不断的除2取余数,然后把所有余数反排就得到二进制结果了。

将10进制转换为7进制的方法也是一样,不断的除7取余,余数反排就好了。
代码如下:

class Solution {
public:
    string convertToBase7(int num) {
    	if(num == 0) return "0";
    	int num_cp = num < 0 ? -num : num;
    	string ans = "";
    	while(num_cp != 0){
    		ans = to_string(num_cp % 7) + ans;
    		num_cp /= 7;
    	}
    	if(num < 0) return "-" + ans;
    	else return ans;
    }
};

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