[Leetcode] Math

Posted on | In , |

Maximum Common Divisor (最大公约数)

Source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Function to return gcd of a and b
static int gcd(int a, int b) {
  if(a == 0 || b == 0) return a+b; // base case
  return gcd(b, a%b);
}

// Function to find gcd of array of
  // numbers
static int findGCD(int arr[], int n) {
  int result = arr[0];
  for (int i = 1; i < n; i++)
      result = gcd(arr[i], result);

  return result;
}

149. Max Points on a Line

Calculate GCD:

1
2
3
4
5
def gcd(a, b):
    if a == 0 or b == 0:
        return a + b
    else:
        return gcd(b, a % b)

Calculation Problems

43. Multiply Strings

Solution

  • Use an length = m + n array to record all the sums
  • The product of num1[i] * num2[j] will locate at [i + j, i + j + 1]
  • char to int: str1.charAt(2) - '0'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public String multiply(String num1, String num2) {
        // i, j, product will locate at [i + j, i + j + 1]
        int m = num1.length();
        int n = num2.length();
        int[] pos = new int[m + n]; // result array

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j;
                int p2 = i + j + 1;

                int sum = product + pos[p2];
                pos[p1] += sum / 10;
                pos[p2] = sum % 10;
            }
        }
        StringBuilder sb = new StringBuilder("");
        for (int num : pos) {
            if (!(num == 0 && sb.length() == 0)) { // Avoid 0 in head
                sb.append(String.valueOf(num));
            }
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

Palindrome Problems

9.Palindrome Number

[Solution] Compare half of the number with another half

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isPalindrome(int x) {
        // Edge Case
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }

        int reverse = 0; // Use a reverse number to track the reverse version of half of the number
        while (reverse < x) {
            reverse = reverse * 10 + x % 10;
            x = x / 10;
        }
        return (reverse == x || x == reverse / 10); // reverse == x if the number of digits is even, reverse / 10 == x if the the number of digits is odd
    }
}

829. Consecutive Numbers Sum

Leetcode: https://leetcode.com/problems/consecutive-numbers-sum/description/

Solution: From length = 1, find all the combinations that satisfies the condition.

(Time Limit Exceeds)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def consecutiveNumbersSum(self, N: int) -> int:
    l = 1
    cnt = 0
    while True:
        sum = (1 + l) * l // 2
        if sum > N:
            break
        while sum <= N:
            if sum == N:
                cnt += 1
                break
            sum += l
        l += 1
    return cnt

(Optimized but also TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def consecutiveNumbersSum(self, N: int) -> int:
        if N == 1:
            return 1
        l = 1
        cnt = 0
        while l <= N / 2 + 1:
            cur = N // l
            if cur < l / 2:
                l += 1
                continue
            if l % 2 == 0 and (cur * 2 + 1) / 2 * l == N:
                cnt += 1
            elif l % 2 == 1 and cur * l == N:
                cnt += 1
            l += 1
        return cnt

https://zhanghuimeng.github.io/post/leetcode-295-find-median-from-data-stream/

1
2
3
4
5
6
7
8
9
10
11
def consecutiveNumbersSum(self, N: int) -> int:
    cnt = 0
    l = 1
    while True:
        cur = N - l * (l - 1) / 2
        if cur <= 0:
            break
        if cur % l == 0:
            cnt += 1
        l += 1
    return cnt

273. Integer to English Words

Leetcode: https://leetcode.com/problems/integer-to-english-words/

[Solution]

  • Use 1000 as a base
  • Use the helper function to calculate results within [1, 999]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def __init__(self):
        self.lessThan20 = ["","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"]
        self.tens = ["","Ten","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"]
        self.thousands = ["","Thousand","Million","Billion"]

    def numberToWords(self, num):
        if num == 0:
            return "Zero"
        res = ""
        for i in range(len(self.thousands)):
            if num % 1000 != 0:
                res = self.helper(num%1000) + self.thousands[i] + " " + res
            num /= 1000
        return res.strip()

    def helper(self, num):
        if num == 0:
            return ""
        elif num < 20:
            return self.lessThan20[num] + " "
        elif num < 100:
            return self.tens[num/10] + " " + self.helper(num%10)
        else:
            return self.lessThan20[num/100] + " Hundred " + self.helper(num%100)

Probablity

528. Random Pick with Weight

Leetcode: https://leetcode.com/problems/random-pick-with-weight/

Pick random numbers from array with probability.

等比数列

1
2
3
4
5
SUM = (a1 * q^n - a1) / (q - 1)
a1: 首项
q: 比

1 + 2 + 4 + 8 + 16 + ... 2 ^ n = 2 ^ n - 1

Calculator problems

224. Basic Calculator

Leetcode: https://leetcode.com/problems/basic-calculator/

[Solution]

  • The character could only be (, ), 0-9, +, -
  • num represents current number
  • Use 1 and -1 to represent +- operations

Note: The stack is used to store number, and operators before (. We start traversing the input string, we use num to store the current number, if we meet with + or -, we add the current number to the previous result in the stack, and update the oper for the next calculation. When we meet (, we want to remember what operator is before the (, thus, we push current operator into stack, at the same time, in order to avoid directly add operator numbers, we push another 0 into the stack, as the initial value of the current calculation. In the end, when we meet ), we want to pop the previous result from the stack, add num to it, and update num. Also, we pop again from the stack, this time, the popped value would be the operator before the (.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def calculate(self, s: str) -> int:
    stack = [0]
    oper = 1
    num = ""
    for i in range(len(s)):
        ch = s[i]
        if ch.isdigit():
            num += ch
        if ch == "+" or (i == len(s) - 1 and ch != ")"):
            stack[-1] += oper * int(num)
            oper = 1
            num = ""
        elif ch == "-":
            stack[-1] += oper * int(num)
            oper = -1
            num = ""
        elif ch == "(":
            stack.append(oper)
            stack.append(0)
            oper = 1
            num = ""
        elif ch == ")":
            prev = stack.pop()
            num = str(prev + oper * int(num))
            oper = stack.pop()
    if num:
        stack.append(oper * int(num))
    return sum(stack)

227. Basic Calculator II

Leetcode: https://leetcode.com/problems/basic-calculator-ii/

Note:

  1. Do the calculation before inserting into the stack
  2. Use stack[-1] as previous number
  3. Only store numbers in stack
  4. Note that when operator is /, we need to deal with different situations (when result < 0) since the “integer division should truncate toward zero”
  5. oper means how we need to deal with the current number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def calculate(self, s: str) -> int:
    stack = []
    num = ""
    oper = "+"
    for i in range(len(s)):
        ch = s[i]
        if ch.isdigit():
            num += ch
        if ch in "+-*/" or i == len(s) - 1:
            if oper == "+":
                stack.append(int(num))
            elif oper == "-":
                stack.append(-int(num))
            elif oper == "*":
                stack[-1] *= int(num)
            elif oper == "/":
                prev = stack.pop()
                if prev // int(num) >= 0 or prev % int(num) == 0:
                    stack.append(prev // int(num))
                else:
                    stack.append(prev // int(num) + 1)
            num = ""
            oper = ch
    return sum(stack)

394. Decode String

Leetcode: https://leetcode.com/problems/decode-string/

Note: to check if a character is character:

1
2
if ch.isalpha():
    print("is character")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def decodeString(self, s: str) -> str:
    if not s:
        return ""
    stack = [[1, ""]]
    i = 0
    while i < len(s):
        num = ""
        while s[i].isdigit():
            num += s[i]
            i += 1
        if s[i] == "[":
            cur = [int(num), ""]
            stack.append(cur)
        elif s[i].isalpha():
            stack[-1][1] += s[i]
        elif s[i] == "]":
            last = stack.pop()
            if stack:
                stack[-1][1] += last[0] * last[1]
            else:
                return last[0] * last[1]
        i += 1
    return stack[0][0] * stack[0][1]

772. Basic Calculator III

Leetcode: https://leetcode.com/problems/basic-calculator-iii/

679. 24 Game(hard)

Leetcode: https://leetcode.com/problems/24-game/

Note:

  • For each two combinations in nums, calculate their ALL possible results (including a - b and b - a), append their result to the next round, and keep iterating
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def judgePoint24(self, nums: List[int]) -> bool:
    # [3,5,9,9]
    if len(nums) == 1:
        return abs(nums[0] - 24) < 0.001
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            combs = [nums[i] + nums[j], nums[i] - nums[j], nums[j] - nums[i], nums[i] * nums[j], nums[j] and nums[i] / nums[j], nums[i] and nums[j] / nums[i]] # ! ALL COMBINATIONS
            for c in combs:
                nextRound = [c] # !! each next round array should be reinitiated
                for k in range(len(nums)):
                    if k != i and k != j:
                        nextRound.append(nums[k])
                if self.judgePoint24(nextRound):
                    return True
    return False