This is the 10th day of my participation in the genwen Challenge

Subject to a

Give coins of different denominations and a total amount. Write a function to calculate the number of coin combinations that add up to the total. Suppose there are an infinite number of coins of each denomination.

 

Example 1:

Input: Amount =5, Coins = [1, 2, 5] Output: 4 Explanation: There are four ways to obtain the total amount: 5=5 5=2+2+1 5=2+1+1 5=1+1+1+1 Example 2:

Input: Amount = 3, Coins = [2] Example 3:

Input: Amount = 10, Coins = [10] Output: 1

Note:

You can assume:

  • 0 <= amount <= 5000
  • 1 <= coin value <= 5000
  • There are no more than 500 types of coins
  • The result conforms to a 32 – bit signed integer

Their thinking

To define an array

Dp [I] represents the number of combinations when the amount is I

State transition

Iterating over all amounts, the current amount I may be transferred from the amount i-coin

dp[i]+=dp[i-coin];

Because the outermost loop loops through all the coins, the number of repeated combinations can be eliminated

code

class Solution {
    public int change(int amount, int[] coins) {

        int[] dp = new int[amount + 1];
        dp[0] =1;
        for (int coin : coins) {
        for (inti=coin; i<=amount; i++) { dp[i]+=dp[i-coin]; }}returndp[amount]; }}Copy the code

Topic 2

Given a binary array nums, find the longest continuous subarray with the same number of 0s and 1s, and return the length of that subarray.

Example 1:

Input: nums = [0,1] Output: 2 Description: [0,1] is the longest continuous subarray with the same number of 0s and 1s. Example 2:

Input: nums = [0,1,0] Output: 2 Description: [0,1] (or [1, 0]) is the longest continuous subarray with the same number of 0s and 1s.

Their thinking

Maintains a variable bi that stores the difference between 1 and 0 in the subarray [0, I] (the number of 1s – the number of 0s)

Suppose the subarray [I,j] has the same number of zeros and ones

The number of 1’s in the subarray = the number of 1’s in the subarray [0,j] – the number of 1’s in the subarray [0, I]

The number of zeros in the subarray = the number of zeros in the subarray [0,j] – the number of zeros in the subarray [0, I]

The number of 1’s in the subarray is equal to the number of 0’s in the subarray

Number of 1s in the subarray [0,j] – number of 1s in the subarray [0, I] = number of 0s in the subarray [0,j] – number of 0s in the subarray [0, I]

The difference between 1 and 0 in the subarray [0,j] = the difference between 1 and 0 in the subarray [0, I]

So all we have to do is find the difference between the same ones and zeros, and we can tell that they have the same number of ones and zeros

code

func findMaxLength(nums []int) (maxLength int) {

	max := func(a int, b int) int {
		if a > b {
			return a
		} else {
			return b
		}
	}
	m := map[int]int{}
	b:=0
	for i, num := range nums {
		if num==0{
			b--
		}else{
			b++
		}
     if b==0{
			maxLength=max(maxLength,i+1)
            m[b]=i
			continue
		}
		index,has := m[b]
		if has{
			maxLength=max(maxLength,i-index)
		}else {
			m[b]=i
		}
	}
	return 
}


Copy the code