- Leetcode problem solving - Mathematics
Prime decomposition
Each number can be decomposed into the product of prime numbers, for example, 84 = 22 * 31 * 50 * 71 * 110 * 130 * 170 *
to be divisible by
Let x = 2m0 * 3m1 * 5m2 * 7m3 * 11m4 *
Let y = 2n0 * 3n1 * 5n2 * 7n3 * 11n4 *
If x is divided by Y (y mod x == 0), MI < = Ni for all i.
Greatest common divisor least common multiple
The maximum common divisor of X and Y is: gcd(x,y) = 2min(m0,n0) * 3min(m1,n1) * 5min(m2,n2) *
The least common multiple of X and Y is: lcm(x,y) = 2max(m0,n0) * 3max(m1,n1) * 5max(m2,n2) *
1. Generate prime sequence
204. Count Primes (Easy)
Each time a prime number is found, the eratostani sieve method excludes the number that can be divided by the prime number.
public int countPrimes(int n) {
boolean[] notPrimes = new boolean[n + 1];
int count = 0;
for (int i = 2; i < n; i++) {
if (notPrimes[i]) {
continue;
}
count++;
// Start with i * i, because if K < I, k * i has been removed before
for (long j = (long) (i) * i; j < n; j += i) {
notPrimes[(int) j] = true;
}
}
return count;
}
2. Maximum common divisor
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
The least common multiple is the product of two numbers divided by the greatest common divisor.
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
3. Use bit operation and subtraction to solve the maximum common divisor
For the maximum common divisor f(a, b) of a and B, there are:
- If both a and B are even, f(a, b) = 2*f(a/2, b/2);
- If a is even and B is odd, f(a, b) = f(a/2, b);
- If B is even and a is odd, f(a, b) = f(a, b/2);
- If both a and B are odd, f(a, b) = f(b, a-b);
Both multiply by 2 and divide by 2 can be converted to shift operations.
public int gcd(int a, int b) {
if (a < b) {
return gcd(b, a);
}
if (b == 0) {
return a;
}
boolean isAEven = isEven(a), isBEven = isEven(b);
if (isAEven && isBEven) {
return 2 * gcd(a >> 1, b >> 1);
} else if (isAEven && !isBEven) {
return gcd(a >> 1, b);
} else if (!isAEven && isBEven) {
return gcd(a, b >> 1);
} else {
return gcd(b, a - b);
}
}
Binary conversion
1. 7 hex
504. Base 7 (Easy)
public String convertToBase7(int num) {
if (num == 0) {
return "0";
}
StringBuilder sb = new StringBuilder();
boolean isNegative = num < 0;
if (isNegative) {
num = -num;
}
while (num > 0) {
sb.append(num % 7);
num /= 7;
}
String ret = sb.reverse().toString();
return isNegative ? "-" + ret : ret;
}
Static string toString (int num, int radius) in Java can convert an integer into a string represented by radix.
public String convertToBase7(int num) {
return Integer.toString(num, 7);
}
2. Hexadecimal
405. Convert a Number to Hexadecimal (Easy)
Input: 26 Output: "1a" Input: -1 Output: "ffffffff"
Negative numbers should be in its complement form.
public String toHex(int num) {
char[] map = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
if (num == 0) return "0";
StringBuilder sb = new StringBuilder();
while (num != 0) {
sb.append(map[num & 0b1111]);
num >>>= 4; // Because the form of complement is considered, the sign bit cannot have special meaning. It needs to use unsigned right shift and fill in 0 on the left
}
return sb.reverse().toString();
}
3.26 hex
168. Excel Sheet Column Title (Easy)
1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB
Because the calculation starts from 1, not 0, you need to perform the - 1 operation on n.
public String convertToTitle(int n) {
if (n == 0) {
return "";
}
n--;
return convertToTitle(n / 26) + (char) (n % 26 + 'A');
}
Factorial
1. How many zeros are there in the tail of statistical factorial
172. Factorial Trailing Zeroes (Easy)
The tail 0 is derived from 2 * 5. The number of 2 is obviously more than that of 5, so just count how many 5 there are.
For a number n, the number of 5 it contains is: N/5 + N/52 + N/53 +..., where N/5 represents that the multiple of 5 in the number not greater than n contributes a 5, and N/52 represents that the multiple of 52 in the number not greater than n contributes another 5.
public int trailingZeroes(int n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
If the statistics is N! The position of the lowest 1 in the binary representation of, as long as the number of 2 can be counted Beauty of programming: 2.2 . The number of 2 is N/2 + N/22 + N/23 +
String addition and subtraction
1. Binary addition
67. Add Binary (Easy)
a = "11" b = "1" Return "100".
public String addBinary(String a, String b) {
int i = a.length() - 1, j = b.length() - 1, carry = 0;
StringBuilder str = new StringBuilder();
while (carry == 1 || i >= 0 || j >= 0) {
if (i >= 0 && a.charAt(i--) == '1') {
carry++;
}
if (j >= 0 && b.charAt(j--) == '1') {
carry++;
}
str.append(carry % 2);
carry /= 2;
}
return str.reverse().toString();
}
Add string 2
415. Add Strings (Easy)
The value of the string is a nonnegative integer.
public String addStrings(String num1, String num2) {
StringBuilder str = new StringBuilder();
int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
while (carry == 1 || i >= 0 || j >= 0) {
int x = i < 0 ? 0 : num1.charAt(i--) - '0';
int y = j < 0 ? 0 : num2.charAt(j--) - '0';
str.append((x + y + carry) % 10);
carry = (x + y + carry) / 10;
}
return str.reverse().toString();
}
Encounter problem
1. Change the array elements so that all array elements are equal
462. Minimum Moves to Equal Array Elements II (Medium)
Input: [1,2,3] Output: 2 Explanation: Only two moves are needed (remember each move increments or decrements one element): [1,2,3] => [2,2,3] => [2,2,2]
You can add or subtract one to an array element at a time to find the minimum number of changes.
This is a typical encounter problem. The way to minimize the moving distance is to move all elements to the median. The reasons are as follows.
Let m be the median. A and B are two elements on both sides of M, and b > a. To make a and B equal, their total number of moves is b - a, which is equal to (b - m) + (m - a), that is, the number of moves to the median.
If the length of the array is n, the combination of N/2 pairs of a and b can be found to move them to the position of m.
Solution 1
Sort first, time complexity: O(NlogN)
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int move = 0;
int l = 0, h = nums.length - 1;
while (l <= h) {
move += nums[h] - nums[l];
l++;
h--;
}
return move;
}
Solution 2
Use quick selection to find the median, time complexity O(N)
public int minMoves2(int[] nums) {
int move = 0;
int median = findKthSmallest(nums, nums.length / 2);
for (int num : nums) {
move += Math.abs(num - median);
}
return move;
}
private int findKthSmallest(int[] nums, int k) {
int l = 0, h = nums.length - 1;
while (l < h) {
int j = partition(nums, l, h);
if (j == k) {
break;
}
if (j < k) {
l = j + 1;
} else {
h = j - 1;
}
}
return nums[k];
}
private int partition(int[] nums, int l, int h) {
int i = l, j = h + 1;
while (true) {
while (nums[++i] < nums[l] && i < h) ;
while (nums[--j] > nums[l] && j > l) ;
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, l, j);
return j;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
Majority voting question
1. Elements that appear more than n / 2 times in the array
169. Majority Element (Easy)
Sort the array first. The number in the middle must appear more than n / 2.
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
Boyer Moore majority vote algorithm can be used to solve this problem, so that the time complexity is O(N). The algorithm can be understood as follows: use cnt to count the number of occurrences of an element. When the traversed elements are not equal to the statistical elements, make cnt -. If i elements are searched and cnt == 0, it means that the first i elements have no major or have major, but the number of occurrences is less than i / 2, because cnt will not be 0 if it is more than i / 2. At this time, among the remaining N - i elements, the number of major is still more than (n - i) / 2, so continue to find the major.
public int majorityElement(int[] nums) {
int cnt = 0, majority = nums[0];
for (int num : nums) {
majority = (cnt == 0) ? num : majority;
cnt = (majority == num) ? cnt + 1 : cnt - 1;
}
return majority;
}
other
1. Square
367. Valid Perfect Square (Easy)
Input: 16 Returns: True
Square sequence: 1,4,9,16
Interval: 3,5,7
The interval is an equal difference sequence. Using this feature, you can get the square sequence starting from 1.
public boolean isPerfectSquare(int num) {
int subNum = 1;
while (num > 0) {
num -= subNum;
subNum += 2;
}
return num == 0;
}
2. n-th power of 3
326. Power of Three (Easy)
public boolean isPowerOfThree(int n) {
return n > 0 && (1162261467 % n == 0);
}
3. Product array
238. Product of Array Except Self (Medium)
For example, given [1,2,3,4], return [24,12,8,6].
Given an array, create a new array. Each element of the new array is the product of all elements in the original array except the elements at that position.
The time complexity is required to be O(N) and division cannot be used.
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] products = new int[n];
Arrays.fill(products, 1);
int left = 1;
for (int i = 1; i < n; i++) {
left *= nums[i - 1];
products[i] *= left;
}
int right = 1;
for (int i = n - 2; i >= 0; i--) {
right *= nums[i + 1];
products[i] *= right;
}
return products;
}
4. Find the three largest products in the array
628. Maximum Product of Three Numbers (Easy)
Input: [1,2,3,4] Output: 24
public int maximumProduct(int[] nums) {
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE, min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for (int n : nums) {
if (n > max1) {
max3 = max2;
max2 = max1;
max1 = n;
} else if (n > max2) {
max3 = max2;
max2 = n;
} else if (n > max3) {
max3 = n;
}
if (n < min1) {
min2 = min1;
min1 = n;
} else if (n < min2) {
min2 = n;
}
}
return Math.max(max1*max2*max3, max1*min1*min2);
}