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)\)

By Long Luo

This article is the solution Dynamic Programming Space O(n) Solutions: Top-Down and Bottom-Up Approaches of Problem 120. Triangle .

Intuition

This problem is a classic and typical dynamic programming problem. We can break the large problem into sub-problems.

We can use both the Top-Down and Bottom-Up approach to solve this problem.

Top-Down Approach

1. State definition:

\(dp[i][j]\) represents the minimum path sum of row \(i\) and column \(j\).

2. State Analysis:

\(dp[0][0]=c[0][0]\)

3. The State Transfer Equation:

\[ dp[i][j] = \begin{cases} dp[i-1][0] + c[i][0] & j=0 \\ dp[i-1][i-1] + c[i][i] & j==i \\ min(dp[i-1][j-1], dp[i-1][j]) + c[i][j] & 0 < j < i \\ \end{cases} \]

so we can easily write such code:

By Long Luo

This article is the solution How to Maintain the Enqueued Tasks? | Sorting the array then Priority Queue | minHeap of Problem 1834. Single-Threaded CPU .

Intuition

To simulate the CPU operations, there comes \(3\) questions:

1. Which task should int the enqueued tasks list?

2. How to maintain the enqueued tasks?

3. Which task of the enqueued tasks should the CPU choose?

Let’s answer the \(3\) questions:

1. We assign the tasks to the CPU by \(\textit{enqueueTime}\), so we sort the array first by \(\textit{enqueueTime}\). However, we will lose the \(\textit{index}\) of the task.

We can parse the task by creating a new class \(\texttt{Job}\), whose members are \(\textit{id}\), \(\textit{enqueueTime}\), \(\textit{processTime}\).

2. We put all the tasks assigned to the CPU into a Priority Queue and poll out the task whose \(\textit{processTime}\) is the least each time.

3. We can maintain a \(\textit{curTime}\) variable, which represents the current time with initial value is \(0\).

If the CPU has no tasks to execute, we set the \(\textit{curTime}\) to \(\textit{enqueueTime}\) of the next task in the array that has not yet been assigned to the CPU.

After this, we put all \(\textit{enqueueTime} \le \textit{curTime}\) tasks into the Priority Queue.

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.

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.