LeetCode – 518. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note: You can assume that

  • 0 <= amount <= 5000
  • 1 <= coin <= 5000
  • the number of coins is less than 500
  • the answer is guaranteed to fit into signed 32-bit integer

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

 

Idea: this problem is very similar like Coin Change, the difference is to store the total number of combinations to make up the amount, larger amount (dp[i]) is dependent on the smaller one (dp[i – c]) and coins.

 

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int

        beats 93.06%
        """
        coins.sort()
        dp = [1] + [0] * amount
        for c in coins:
            for i in range(c, amount+1):
                if dp[i-c]:
                    dp[i] += dp[i-c]
        return dp[-1]

    def change0(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int

        https://leetcode.com/problems/coin-change-2/discuss/99210/python-O(n)-space-dp-solution

        beats 55.21%
        """
        dp = [0] * (amount + 1)
        dp[0] = 1
        for i in coins:
            for j in range(1, amount + 1):
                if j >= i:
                    dp[j] += dp[j - i]
        return dp[amount]

    def change1(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int

        https://leetcode.com/problems/coin-change-2/discuss/99235/Classic-problem-python-clean-DP-O(MN)

        beats 34.72%
        """
        dp = [1] + [0] * amount
        for c in coins:
            for i in range(1, amount + 1):
                if i >= c:
                    dp[i] += dp[i - c]
        return dp[-1]

    def change2(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int

        TLE for test case: 500, [3,5,7,8,9,10,11]
        """
        if amount < 0:
            return 0
        if amount == 0:
            return 1
        if coins is None:
            return 0
        if len(coins) == 0:
            if amount == 0:
                return 1
            else:
                return 0

        coins.sort(reverse=True)
        if amount < coins[-1]:
            return 0
        res = [0]
        self.help_func(coins, amount, 0, res)
        return res[0]

    def help_func(self, coins, amount, depth, res):
        """
        :param coins:
        :param amount:
        :param depth:
        :param res_list:
        :return:

        use current largest coin as much as possible
        back tracking to use less largest coin if cannot make the target amount
        repeat above procedure for each coin from large to small
        """
        coins_len = len(coins)
        if amount == 0:
            res[0] += 1
            return
        elif amount < 0:
            return
        else:
            if depth == coins_len:
                return
            else:
                i = depth
                coin_nums = amount // coins[i]
                for cur_coin_num in range(coin_nums, -1, -1):
                    cur_amount = amount - coins[i] * cur_coin_num
                    self.help_func(coins, cur_amount, depth + 1, res)

 

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Resources:

Core Java Volume I–Fundamentals (10th Edition) (Core Series)

Core Java, Volume II–Advanced Features (10th Edition) (Core Series)

Test-Driven Java Development

Java Concurrency in Practice

Java: An Introduction to Problem Solving and Programming (7th Edition)

Java 9 for Programmers (Deitel Developer Series)

Java SE8 for the Really Impatient: A Short Course on the Basics (Java Series)

Core Java for the Impatient

Java: The Beginners Guide for every non-programmer which will attend you trough your learning process

Java Deep Learning Essentials

Machine Learning in Java

Learning Reactive Programming With Java 8

Java 9 Programming By Example

Thinking in Java (4th Edition)

The Java EE Architect’s Handbook, Second Edition: How to be a successful application architect for Java EE applications

Java Artificial Intelligence: Made Easy, w/ Java Programming

Advertisements
Posted in Algorithm&DataStructure, Uncategorized | Tagged , | Leave a comment

LeetCode – 322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

 

Idea: this problem is very classic one for demonstrating Dynamic Programming (DP), but DP is always from brute force method and memorized cache mechanism. Brute force way is to process from highest value denomination coin and use it as much as possible, repeat for other lower value denomination coins, back tracking (use less number of the coin) if  cannot make the amount with certain number of the coin.

There are two optimized solution (cache minimum number to achieve amounts which are less than the target amount):

1. start from coins, use them as a base (current queue) to add each coin to calculate current level sum, if there is sum equaling to target amount and return, otherwise keep calculating until consume all the elements.

2. calculate minimum number to achieve each number from zero to the target amount, if current number (dp[i]) is larger or equal to coin denomination, it can definitely be represented by the coin and difference value (dp[i – coin]).

class Solution(object):
    """
    This solution is inspired by the BFS solution for problem Perfect Square.
    Since it is to find the least coin solution (like a shortest path from 0 to amount),
    using BFS gives results much faster than DP.
    https://discuss.leetcode.com/topic/26262/short-python-solution-using-bfs

    beats 97.75%
    """
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if amount == 0:
            return 0
        cur_queue = [0]  # current queue
        next_queue = []  # next queue
        num_counter = 0
        visited = [False] * (amount + 1)
        visited[0] = True
        while cur_queue:
            num_counter += 1
            for v in cur_queue:
                for coin in coins:
                    new_val = v + coin
                    if new_val == amount:
                        return num_counter
                    elif new_val > amount:
                        continue
                    elif not visited[new_val]:
                        visited[new_val] = True
                        next_queue.append(new_val)
            cur_queue, next_queue = next_queue, []
        return -1

    def coinChange1(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int

        Assume dp[i] is the fewest number of coins making up amount i, then for every coin in coins,
        dp[i] = min(dp[i - coin] + 1).
        dp[i] works as a cache, max_val is default value, otherwise is cached

        The time complexity is O(amount * coins.length) and the space complexity is O(amount)

        [dp[amount], -1][dp[amount] == max_val] => [dp[amount], -1][0/1]
        if dp[amount] == max_val: [dp[amount], -1][1] => -1
        else: [dp[amount], -1][0] => dp[amount]

        https://leetcode.com/problems/coin-change/discuss/77372/Clean-dp-python-code

        beats 77.61%
        """
        max_val = float('inf')
        dp = [0] + [int(max_val)] * amount

        for i in range(1, amount + 1):
            dp[i] = min([dp[i - c] if i - c >= 0 else max_val for c in coins]) + 1

        # return [dp[amount], -1][dp[amount] == max_val]

        if dp[amount] == max_val:
            return -1
        else:
            return dp[amount]

    def coinChange2(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int

        brute force

        Time Limit Exceeded (TLE)
        """
        if coins is None or amount < 0:
            return -1
        if amount == 0:
            return 0
        coins.sort(reverse=True)
        if amount < coins[-1]:
            return -1
        return self.help_func(coins, amount, 0, [])

    def help_func(self, coins, amount, depth, res_list):
        """
        :param coins:
        :param amount:
        :param depth:
        :param res_list:
        :return:

        use current largest coin as much as possible
        back tracking to use less largest coin if cannot make the target amount
        repeat above procedure for each coin from large to small
        """
        coins_len = len(coins)
        if depth == coins_len:
            return -1
        if amount == 0:
            return len(res_list)
        elif amount < 0:
            return -1
        else:
            i = depth
            coin_nums = amount // coins[i]
            for cur_coin_num in range(coin_nums, -1, -1):
                cur_amount = amount - coins[i] * cur_coin_num
                tmp_res = self.help_func(coins, cur_amount, depth + 1, res_list + [coins[i]] * cur_coin_num)
                if tmp_res == -1:
                    continue
                else:
                    return tmp_res
            return -1

 

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Resources:

Core Java Volume I–Fundamentals (10th Edition) (Core Series)

Core Java, Volume II–Advanced Features (10th Edition) (Core Series)

Test-Driven Java Development

Java Concurrency in Practice

Java: An Introduction to Problem Solving and Programming (7th Edition)

Java 9 for Programmers (Deitel Developer Series)

Java SE8 for the Really Impatient: A Short Course on the Basics (Java Series)

Core Java for the Impatient

Java: The Beginners Guide for every non-programmer which will attend you trough your learning process

Java Deep Learning Essentials

Machine Learning in Java

Learning Reactive Programming With Java 8

Java 9 Programming By Example

Thinking in Java (4th Edition)

The Java EE Architect’s Handbook, Second Edition: How to be a successful application architect for Java EE applications

Java Artificial Intelligence: Made Easy, w/ Java Programming

Posted in Algorithm&DataStructure, Uncategorized | Tagged , | Leave a comment

LeetCode – 697. Degree of an Array

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Input: [1, 2, 2, 3, 1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

Example 2:

Input: [1,2,2,3,1,4,2]
Output: 6

Note:

 

  • nums.length will be between 1 and 50,000.
  • nums[i] will be an integer between 0 and 49,999.

 

Idea: use a hash map to store number elements as key and indices as value, then the length of the value is frequency of a specific number element, and difference between first and last indices in the value is the potential minimum length of the sub-array which has the degree as the input array.

 

Code:

def findShortestSubArray1(self, nums):
    """
    :type nums: List[int]
    :rtype: int

    https://leetcode.com/problems/degree-of-an-array/discuss/108647/Python-O(n)-concise-with-explanation-(two-approaches)

    Firstly, group each num and collect the index it appears into a list. The list with the longest length will be
    the degree of the array.

    Next loop through each of the lists, only those lists with the same length as the degree will qualify.
    We simply take difference between the first and last value of each qualifying lists to find the length of such
    a possible subarray.

    For example if we have [1, 1, 2, 2, 2, 3, 1], after grouping by value:

    [1, 1, 2, 2, 2, 3, 1] => { 1: [0, 1, 6], 2: [2, 3, 4], 3: [4] }, degree: 3

    Only have to consider values where the length == degree:

    1: [0, 1, 6] => subarray length: (6 - 0) + 1 = 7
    2: [2, 3, 4] => subarray length: (4 - 2) + 1 = 3 (Winner!)

    beats 27.26%
    """
    nums_map, deg, min_len = collections.defaultdict(list), 0, float('inf')
    for index, num in enumerate(nums):
        nums_map[num].append(index)
        deg = max(deg, len(nums_map[num]))
    for num, indices in nums_map.items():
        if len(indices) == deg:
            min_len = min(min_len, indices[-1] - indices[0] + 1)
    return min_len

def findShortestSubArray2(self, nums):
    """
    :type nums: List[int]
    :rtype: int

    nums_map: k as num, v as indices of num in the array
    deg: degree of array (maximum frequency of any one of its elements)
    min_len: minimum length to hold the continuous sub-array which has the degree

    difference between first and last indices of an element is the degree and potential min length for the num

    beats 52.72%
    """
    nums_map, deg, min_len = collections.defaultdict(list), 0, float('inf')
    for index, num in enumerate(nums):
        nums_map[num].append(index)
        if len(nums_map[num]) == deg:
            min_len = min(min_len, nums_map[num][-1] - nums_map[num][0] + 1)
        elif len(nums_map[num]) > deg:
            deg = len(nums_map[num])
            min_len = nums_map[num][-1] - nums_map[num][0] + 1
    return min_len

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Resources:

Core Java Volume I–Fundamentals (10th Edition) (Core Series)

Core Java, Volume II–Advanced Features (10th Edition) (Core Series)

Test-Driven Java Development

Java Concurrency in Practice

Java: An Introduction to Problem Solving and Programming (7th Edition)

Java 9 for Programmers (Deitel Developer Series)

Java SE8 for the Really Impatient: A Short Course on the Basics (Java Series)

Core Java for the Impatient

Java: The Beginners Guide for every non-programmer which will attend you trough your learning process

Java Deep Learning Essentials

Machine Learning in Java

Learning Reactive Programming With Java 8

Java 9 Programming By Example

Thinking in Java (4th Edition)

The Java EE Architect’s Handbook, Second Edition: How to be a successful application architect for Java EE applications

Java Artificial Intelligence: Made Easy, w/ Java Programming

 

Posted in Algorithm&DataStructure, Uncategorized | Tagged , , , | Leave a comment

LeetCode – 308. Range Sum Query 2D – Mutable


Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10

Note:

  1. The matrix is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRegion function is distributed evenly.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

 

Idea: it should come out some way to store the computed results of sums and get region sum based on the pre-computed results. “Range Sum” is a good idea in this case, because every element in the matrix stores the sum of all previous elements in this row and it can get the range sum by difference of end element and previous element of start point.

 

Similar problems:

LC 303. Range Sum Query – Immutable

 

Code:

class NumMatrix(object):
    """
    Your NumMatrix object will be instantiated and called as such:
    obj = NumMatrix(matrix)
    obj.update(row,col,val)
    param_2 = obj.sumRegion(row1,col1,row2,col2)

    https://leetcode.com/problems/range-sum-query-2d-mutable/discuss/75872/Python-94.5-Simple-sum-array-on-one-dimension-O(n)-for-both-update-and-sum

    beats 83.86%
    """

    def __init__(self, matrix):
        """
        :type matrix: List[List[int]]

        element m[i][j] in self.matrix means sum of previous elements in this row,
        namely sum(m[i][0] + m[i][1] + ... + m[i][j])
        """
        for row in matrix:
            for col in range(1, len(row)):
                row[col] += row[col - 1]
        self.matrix = matrix

    def update(self, row, col, val):
        """
        :type row: int
        :type col: int
        :type val: int
        :rtype: void

        original means the single element value in original matrix
        """
        original = self.matrix[row][col]
        if col != 0:
            original -= self.matrix[row][col - 1]

        diff = original - val

        for y in range(col, len(self.matrix[0])):  # update elements in the row
            self.matrix[row][y] -= diff

    def sumRegion(self, row1, col1, row2, col2):
        """
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int

        region sum is the sum of range sum in every row from row1 to row2
        as the above definition of self.matrix
        each range sum could be calculated as (m[row][col2] - m[row][col1 - 1])
        """
        region_sum = 0
        for x in range(row1, row2 + 1):
            region_sum += self.matrix[x][col2]
            if col1 != 0:
                region_sum -= self.matrix[x][col1 - 1]
        return region_sum
Posted in Algorithm&DataStructure, Uncategorized | Tagged | Leave a comment

Dynamic Programming Notes

wpid-Programming-Wallpaper-3

Dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler sub-problems, solving each of those sub-problems just once, and storing their solutions. The next time the same sub-problem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space.

 

Solution:

Figure out a way to break the problem into sub-problems:

The original problem can be solved relatively easily once solutions to the sub-problems are available and these sub-problem solutions are cached.

 

4 key factors:

1. function definition and meaning (f[n] in Fibonacci Numbers)

2. transition function (f[n] = f[n-1] + f[n-2])

3. base case and initial condition (f[0] = 0, f[1] = 1)

4. result (f[n])

Refer:

Divide and Conquer Summary

Dynamic Programming – From Novice to Advanced

 

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Resources:

Core Java Volume I–Fundamentals (10th Edition) (Core Series)

Core Java, Volume II–Advanced Features (10th Edition) (Core Series)

Test-Driven Java Development

Java Concurrency in Practice

Java: An Introduction to Problem Solving and Programming (7th Edition)

Java 9 for Programmers (Deitel Developer Series)

Java SE8 for the Really Impatient: A Short Course on the Basics (Java Series)

Core Java for the Impatient

Java: The Beginners Guide for every non-programmer which will attend you trough your learning process

Java Deep Learning Essentials

Machine Learning in Java

Learning Reactive Programming With Java 8

Java 9 Programming By Example

Thinking in Java (4th Edition)

The Java EE Architect’s Handbook, Second Edition: How to be a successful application architect for Java EE applications

Java Artificial Intelligence: Made Easy, w/ Java Programming

Posted in Algorithm&DataStructure, Uncategorized | Tagged , | Leave a comment

Startup Blogs

Flat designt business startup launch concept.

How to start a startup

Startup

Founders at Work

The Best Simple Business Models

Why I’m leaving silicon valley

未来世界的幸存者

Software and technology stack used by top companies

Do things that don’t scale

 

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Posted in IT, startup, Uncategorized | Tagged , , | Leave a comment

Python Blogs

567828_67d0

Google’s Python Class

Dive into Python

A Python Reading List

Map, Filter, Reduce

Python Tutorial: Shallow and Deep Copy

Python Numpy Tutorial

PEP 8 — Style Guide for Python Code

Python Zen – FooFish Python之禅

 

 

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.

Follow me @Yaoli0615 at Twitter to get latest tech updates.

Posted in CS Research&Application, Uncategorized | Tagged | Leave a comment