Long Luo's Life Notes

每一天都是奇迹

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

By Long Luo

This article is the solution 4 Approaches: Brute Force, HashMap, Binary Search, Two Pointers of Problem 167. Two Sum II - Input Array Is Sorted .

Here shows 4 Approaches to slove this problem: Brute Force, HashMap, Binary Search, Two Pointers.

Brute Force

It’s easy to use Brute Force to find the answer, however, the time complexity is \(O(n^2)\), so the BF solution will Time Limit Exceeded!

1
2
3
4
5
6
7
8
9
10
11
12
public static int[] twoSum_bf(int[] numbers, int target) {
    int len = numbers.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (numbers[i] + numbers[j] == target) {
                return new int[]{i + 1, j + 1};
            }
        }
    }

    return new int[0];
}

Analysis

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

HashMap

We can use a extra \(\texttt{HashMap}\) to record the element we traversalled.

阅读全文 »

发表于 更新于 分类于 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. 😉😃💗

0%