Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

By Long Luo

This article is the solution Any Language Beats 100% with Time O(1) Solution of Problem 1137. N-th Tribonacci Number .

Lookup Table

\(32\) bit signed integers only.

If we don’t need to solve very large values and are time-sensitive, we can find all values in advance.

This function will work strictly in the case that we’re dealing with \(32\) bit signed integers (which could be a constraint in languages like Java, C/C++, etc.)

The tribonacci sequence grows very quickly, which means that only the first 37 tribonacci numbers fit within the range of a \(32\) bit signed integer.

This method requires only a quick list lookup to find the nth tribonacci number, so it runs in constant time. Since the list is of fixed length, this method runs in constant space as well.

阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 508 阅读时长 ≈ 1 分钟

By Long Luo

This article is the solution of Problem 440. K-th Smallest in Lexicographical Order.

Brute Force

1
2
3
4
5
6
7
8
9
10
public int findKthNumber(int n, int k) {
    String[] numStrs = new String[n];
    for (int i = 1; i <= n; i++) {
        numStrs[i - 1] = "" + i;
    }

    Arrays.sort(numStrs);

    return Integer.parseInt(numStrs[k - 1]);
}

Analysis

  • Time Complexity: \(O(n \log n)\).
  • Space Complexity: \(O(n)\).
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 7k 阅读时长 ≈ 6 分钟

By Long Luo

This article is the solution 5 Approaches: BF use Long, BF use Int, Binary Search use Long, Binary Search use Int and Recursion of Problem 29. Divide Two Integers , Chinese version is 3种方法：暴力法，二分搜索，递归 .

Here shows 5 Approaches to slove this problem: Brute Force use \(\texttt{Long}\) , Brute Force use \(\texttt{Int}\) , Binary Search use \(\texttt{Long}\) , Binary Search use \(\texttt{Int}\) and Recursion.

Intuition

To divide two integers without using multiplication, division, and mod operator, so we can subtract the \(\textit{divisor}\) from the \(\textit{dividend}\) util the \(\textit{result} \ge 0\) .

Brute Force use Long

We can make the \(\textit{dividend}\) and \(\textit{divisor}\) positive, and cast to \(\texttt{long}\), then process.

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
29
30
public int divide(int dividend, int divisor) {
    if (dividend == 0) {
        return 0;
    }

    long dividendLong = dividend;
    long divisorLong = divisor;

    boolean sign = false;
    if (dividendLong < 0 && divisorLong < 0) {
        dividendLong = -dividendLong;
        divisorLong = -divisorLong;
    } else if (dividendLong < 0 && divisorLong > 0) {
        sign = true;
        dividendLong = -dividendLong;
    } else if (dividendLong > 0 && divisorLong < 0) {
        sign = true;
        divisorLong = -divisorLong;
    }

    long ans = 0;
    while (dividendLong >= divisorLong) {
        dividendLong -= divisorLong;
        ans++;
    }

    ans = sign ? -ans : ans;

    return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

The solution will Time Limit Exceeded, we have to deal with some corner cases.

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public int divide(int dividend, int divisor) {
    if (divisor == Integer.MIN_VALUE) {
        return dividend == Integer.MIN_VALUE ? 1 : 0;
    }
    
    if (dividend == Integer.MIN_VALUE) {
        if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return Integer.MAX_VALUE;
        }
    } else if (dividend == Integer.MAX_VALUE) {
        if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return -dividend;
        }
    }

    long dividendLong = dividend;
    long divisorLong = divisor;

    boolean sign = false;
    if (dividendLong < 0 && divisorLong < 0) {
        dividendLong = -dividendLong;
        divisorLong = -divisorLong;
    } else if (dividendLong < 0 && divisorLong > 0) {
        sign = true;
        dividendLong = -dividendLong;
    } else if (dividendLong > 0 && divisorLong < 0) {
        sign = true;
        divisorLong = -divisorLong;
    }

    long ans = 0;
    while (dividendLong >= divisorLong) {
        dividendLong -= divisorLong;
        ans++;
    }

    ans = sign ? -ans : ans;

    return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

Analysis

  • Time Complexity: \(O(x / y)\).
  • Space Complexity: \(O(1)\).
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 595 阅读时长 ≈ 1 分钟

By Long Luo

This article is the solution Java Binary Search Solution of Problem 278. First Bad Version.

Intuition

We can use Binary Search method to exclusive a half to reduce the scale Each Round.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int firstBadVersion(int n) {
        int left = 1;
        int right = n;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;  
    }

Analysis

  • Time Complexity: \(O(\log n)\).
  • Space Complexity: \(O(1)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 2 分钟

By Long Luo

This article is the solution 3 Approaches: Sorting, Two Pointers and Reverse Two Pointers of Problem 88. Merge Sorted Array .

Here shows 3 Approaches to slove this problem: Sorting, Two Pointers and Reverse Two Pointers.

Sorting

Let the array \(\textit{nums}_2\) into the rear of array \(\textit{nums}_1\), and then sort the entire array.

1
2
3
4
5
6
7
public static void merge_sort(int[] nums1, int m, int[] nums2, int n) {
    for (int i = 0; i < n; i++) {
        nums1[m + i] = nums2[i];
    }

    Arrays.sort(nums1);
}

Analysis

  • Time Complexity: \(O((m + n)log(m+n))\) .
  • Space Complexity: \(O(log(m+n))\) .

Two Pointers

Since two arrays \(\textit{nums}_1\) and \(\textit{nums}_2\) are both sorted in non-decreasing order, so we can use the Two Pointers method.

We consider the two arrays as two queues, takes the smaller numbers from the two arrays headers each round and put it into our results.

阅读全文 »
0%