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),代码如下: [cpp] 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; } }; [/cpp] 本代码提交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比较。 [cpp] 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; } }; [/cpp] 本代码提交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呀。代码如下: [cpp] 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; } }; [/cpp] 本代码提交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更好。 完整代码如下: [cpp] 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; } }; [/cpp] 本代码提交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]即可。 代码如下: [cpp] #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; } [/cpp] 本代码提交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就行了。。。 代码如下: [cpp] #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; } [/cpp] 本代码提交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]之间的数。 代码如下: [cpp] 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; } }; [/cpp] 本代码提交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。 代码如下: [cpp] 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; } }; [/cpp] 本代码提交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呢。 代码如下: [cpp] 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); } }; [/cpp] 本代码提交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了。 代码如下: [cpp] 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; } }; [/cpp] 本代码提交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。 代码如下: [cpp] 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; } }; [/cpp] 本代码提交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取余,余数反排就好了。 代码如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时3MS。]]>