# 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].

```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;
}
};
```

# 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```

```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;
}
};
```

# 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```

1. 如果n是偶数，把n变成n/2
2. 如果n是奇数，把n变成n+1或者n-1

```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;
}
};
```

```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;
}
};
```

# hihoCoder 1518-最大集合

hihoCoder 1518-最大集合

### 输出

```7
6 5 1 4 2 7 3```

`4`

```#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;
}
```

# hihoCoder 1493-歌德巴赫猜想

hihoCoder 1493-歌德巴赫猜想

### 输出

`10`

`3 7`

```#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;
}
```

# 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].```

```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;
}
};
```

```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;
}
};
```

# 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```

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水。

```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);
}
};
```

# 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)

```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;
}
};
```

# 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^0=0 | 0=0^0
• 0^1=1 | 0=1^1
• 1^0=1 | 1=0^1
• 1^1=0 | 1=1^0

```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;
}
};
```

# 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].

```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;
}
};
```