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)

Leetcode / Force buckle

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

Beauty of programming: 2.7

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)

Leetcode / Force buckle

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)

Leetcode / Force buckle

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)

Leetcode / Force buckle

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)

Leetcode / Force buckle

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)

Leetcode / Force buckle

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)

Leetcode / Force buckle

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)

Leetcode / Force buckle

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)

Leetcode / Force buckle

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)

Leetcode / Force buckle

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)

Leetcode / Force buckle

public boolean isPowerOfThree(int n) {
    return n > 0 && (1162261467 % n == 0);
}

3. Product array

238. Product of Array Except Self (Medium)

Leetcode / Force buckle

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)

Leetcode / Force buckle

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

Tags: data structure Algorithm leetcode quick sort divide and conquer

Posted by kcorless on Sun, 17 Apr 2022 06:06:55 +0930