Long Luo's Life Notes

每一天都是奇迹

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

By Long Luo

This article is the solution 6 Approaches: Cycle, API, Divide and Conquer, Low Bit, Bit Set, Recursion of Problem 191. Number of 1 Bits.

Here shows 6 Approaches to slove this problem: Cycle, Divide and Conquer, LowBit, Bit Set, Recursion.

Brute Force: Cycle

Juse use a Loop to check if each bit of the binary bits of the given integer \(n\) is \(1\).

1
2
3
4
5
6
7
8
9
10
11
12
public int hammingWeight(int n) {
    int cnt = 0;
    for (int i = 0; i < 32 && n != 0; i++) {
        if ((n & 0x01) == 1) {
            cnt++;
        }

        n = n >>> 1;
    }

    return cnt;
}

Analysis

  • Time Complexity: \(O(k)\).
  • Space Complexity: \(O(1)\).

API

Use API: \(\texttt{Integer.bitCount}\).

1
2
3
public static int hammingWeight(int n) {
    return Integer.bitCount(n);
}

Analysis

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

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

By Long Luo

This article is the solution 3 Approaches: Sorting, Priority Queue and Divide and Conquer of Problem 215. Kth Largest Element in an Array.

Here shows 3 Approaches to slove this problem: Sorting, Priority Queue, Divide and Conquer.

Sorting

Sort the array first, then the \(k-th\) element of the array.

1
2
3
4
5
6
7
8
9
public int findKthLargest(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int len = nums.length;
    Arrays.sort(nums);
    return nums[len - k];
}

Analysis

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

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

By Long Luo

This article is the solution Priority Queue + Greedy: Consider Ladder as a One-time Unlimited Bricks of Problem 1642. Furthest Building You Can Reach.

Intuition

While we are moving, we will need to use bricks or ladders several times. Suppose we have to move to the next building, which means we must use one ladder or \(\Delta h\) bricks, so there is a question, whether to use ladders or bricks?

If the gap of buildings is large, we may use the ladder, otherwise we use the bricks.

We can consider ladder as a one-time unlimited number of bricks, That is, if we have l ladders, we will use the ladder on the \(l\) times where \(\Delta h\) is the largest, and use the bricks in the rest.

Therefore, we got the answer. We maintain no more than \(l\) largest \(\Delta h\) using priority queues, and these are where the ladders are used. For the remaining \(\Delta h\), we need to use bricks, so we need to accumulate them, if the \(sum\) exceeds the number of bricks \(b\), then we have move to the furthest building.

The code is as follows:

阅读全文 »

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

By Long Luo

This article is the solution 2 Approaches: DFS and BFS with Detailed Explanation of Problem 199. Binary Tree Right Side View.

Here shows 2 Approaches to slove this problem: DFS and BFS.

DFS

We traverse the tree in the order of \(\textit{root node} \to \textit{right subtree} \to \textit{left subtree}\) to ensure that each level traverse the rightmost node first.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<Integer> rightSideView_dfs(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }

    dfs(root, 1, ans);
    return ans;
}

public void dfs(TreeNode root, int depth, List<Integer> numList) {
    if (root == null) {
        return;
    }

    if (numList.size() < depth) {
        numList.add(root.val);
    }

    dfs(root.right, depth + 1, numList);
    dfs(root.left, depth + 1, numList);
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)

BFS

We can use BFS to traverse the levels of the tree and record the last element of each level.

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
public List<Integer> rightSideView_bfs(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = size - 1; i >= 0; i--) {
            TreeNode node = queue.poll();
            if (i == size - 1) {
                ans.add(node.val);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }

            if (node.left != null) {
                queue.offer(node.left);
            }
        }
    }

    return ans;
}

Analysis

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

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： 阅读次数： 本文字数： 4.5k 阅读时长 ≈ 4 分钟

By Long Luo

This article is the solution 3 Approaches: DFS, BFS, DP of Problem 322. Coin Change.

Here shows 3 Approaches to slove this problem: DFS, BFS and Dynamic Programming.

DFS

TLE!

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
class Solution {
    int minCount = Integer.MAX_VALUE;

    public int coinChange(int[] coins, int amount) {
        if (amount <= 0) {
            return 0;
        }

        minCount = Integer.MAX_VALUE;
        dfs(coins, amount, 0);
        return minCount == Integer.MAX_VALUE ? -1 : minCount;
    }

    private int dfs(int[] coins, int remain, int count) {
        if (remain < 0) {
            return -1;
        }

        if (remain == 0) {
            minCount = Math.min(minCount, count);
            return count;
        }
        
        for (int x : coins) {
            dfs(coins, remain - x, count + 1);
        }

        return -1;
    }
}

Sorting the array first, then use DFS:

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 {
    int minAns = Integer.MAX_VALUE;
    
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        minAns = Integer.MAX_VALUE;
        coinChange(coins, amount, coins.length - 1, 0);
        return minAns == Integer.MAX_VALUE ? -1 : minAns;
    }

    private void coinChange(int[] coins, int amount, int index, int cnt) {
        if (amount == 0) {
            minAns = Math.min(minAns, cnt);
            return;
        }

        if (index < 0) {
            return;
        }

        for (int k = amount / coins[index]; k >= 0 && k + cnt < minAns; k--) {
            coinChange(coins, amount - k * coins[index], index - 1, cnt + k);
        }
    }
}

Memory DFS:

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
public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount <= 0) {
            return 0;
        }

        return coinChange(coins, amount, new int[amount]);
    }

    private int coinChange(int[] coins, int rem, int[] count) {
        if (rem < 0) {
            return -1;
        }

        if (rem == 0) {
            return 0;
        }

        if (count[rem - 1] != 0) {
            return count[rem - 1];
        }

        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = coinChange(coins, rem - coin, count);
            if (res >= 0 && res < min) {
                min = 1 + res;
            }
        }
        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];
    }
}

Analysis

  • Time Complexity: \(O(amount \times n)\)
  • Space Complexity: \(O(amount)\)
阅读全文 »
0%