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

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

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

hihoCoder 1518-最大集合

hihoCoder 1518-最大集合

输出

7
6 5 1 4 2 7 3

4

hihoCoder 1493-歌德巴赫猜想

hihoCoder 1493-歌德巴赫猜想

输出

10

3 7

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

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

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)

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

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