Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 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： 阅读次数： 本文字数： 594 阅读时长 ≈ 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(logn)\).
  • 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.

阅读全文 »

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

By Long Luo

This article is the solution Java HashSet Solution of Problem 2215. Find the Difference of Two Arrays.

Intuition

We can use \(\texttt{HashSet}\) to record the distinct integers of the two arrays and judge whether a distinct integer in \(\textit{nums}_1\) which not present in \(\textit{nums}_2\).

We can only use \(2\) \(\texttt{HashSet}\), not \(4\) \(\texttt{HashSet}\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<>();
    Set<Integer> set2 = new HashSet<>();
    for (int num : nums1) {
        set1.add(num);
    }
    for (int num : nums2) {
        set2.add(num);
        set1.remove(num);
    }

    for (int num : nums1) {
        set2.remove(num);
    }

    List<List<Integer>> ans = new ArrayList<>();
    ans.add(new ArrayList<>(set1));
    ans.add(new ArrayList<>(set2));
    return ans;        
}
阅读全文 »

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

By Long Luo

This article is the solution 3 Approaches: Brute Force, Recursion and Two Pointers of Problem 680. Valid Palindrome II.

Here shows 3 Approaches to slove this problem: Brue Force, Recursion and Two Pointers.

Brue Force

Let’s start from the simplest method:

  • if \(len(str) \le 2\), definitely return \(\textit{true}\);
  • if the string is a palindrome, return \(\textit{true}\);
  • if not, enumerate each position as the deleted position, and then check the remaining strings is it a palindrome.

Time complexity of this approach is \(O(n^2)\), time limit will be exceeded.

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
public static boolean validPalindrome_bf(String s) {
    int len = s.length();
    if (len <= 2 || validPalindrome(s, 0, len - 1)) {
        return true;
    }

    for (int i = 0; i < len; i++) {
        String str = s.substring(0, i) + s.substring(i + 1, len);
        if (validPalindrome(str, 0, str.length() - 1)) {
            return true;
        }
    }

    return false;
}

public static boolean validPalindrome(String s, int left, int right) {
    int len = s.length();
    if (left >= len || right < 0 || left > right) {
        return false;
    }

    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }

    return true;
}

Analysis

  • Time Complexity: \(O(n^2)\)
  • Space Complexity: \(O(1)\)
阅读全文 »
0%