Daily question brushing record (V)

The first question is : The longest continuous sequence

LeetCode: The finger of the sword Offer II 119. The longest continuous sequence
describe :
Given an array of unsorted integers nums , Find the longest sequence of consecutive numbers （ Sequence elements are not required to be contiguous in the original array ） The length of .

Their thinking :

1. First, put the array elements into HashSet in
2. Find current element , To determine if anyone is younger than him 1 The elements of
3. without . Then judge whether anyone is older than him 1 The elements of , loop , Record how many elements are satisfied .
4. If there is , Go directly to the next cycle .
5. Returns the maximum number of times in the record

Code implementation :

class Solution {
    
    public int longestConsecutive(int[] nums) {
    
        Set<Integer> set = new HashSet<>();
        //  The first iteration stores the array in the hash 
        for(int val : nums) {
    
            set.add(val);
        }
        int ans = 0;
        for(int val : nums) {
    
        	//  Determine whether there is any element smaller than the current one 1 Of 
            if(!set.contains(val-1)){
    
            //  There is nothing smaller than the current element 1 Of 
                int ret = val + 1;
                int count = 1;
                //  there count by 1,  Because I have to count myself 
                while (set.contains(ret)) {
    
                    count++;
                    ret++;
                }
                ans = Math.max(ans,count);
            }
        }
        return ans;
    }
}

The second question is : The minimum number of coins

LeetCode: The finger of the sword Offer II 103. The minimum number of coins
describe :
Give coins of different denominations coins And a total amount amount. Write a function to calculate the minimum number of coins needed to make up the total amount . If no combination of coins can make up the total amount , return -1.

You can think of the number of coins of each kind as infinite .

Their thinking :

Dynamic planning ideas :

• state F(i) : Indicates that the current i Minimum number of coins per coin
• State transition equation : F[i] = Math.min(F[i],F[i-coins[j]]+1)
• The initial state : F(0) = 0;
• Return results : F(amount)

Code implementation :

class Solution {
    
    public int coinChange(int[] coins, int amount) {
    
        int[] dp = new int[amount+1];
        // amount+1 Can avoid overflow 
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for(int i = 1; i < amount+1; i++) {
    
            for(int j = 0; j < coins.length; j++) {
    
            	//  The denomination of coins should be less than the total amount 
                if(coins[j] <= i) {
    
                    dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        //  If  amount The value of the subscript does not change ,  Can't come up with 
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Third question : The least cost of climbing stairs

LeetCode: The finger of the sword Offer II 088. The least cost of climbing stairs
describe :
Each subscript of the array acts as a ladder , The first i A ladder corresponds to a non negative amount of physical expenditure cost[i]（ Subscript from 0 Start ）.

Each time you climb a ladder, you have to spend the corresponding physical strength , Once you've paid for your strength , You can choose to climb up one step or two steps .

Please find out the lowest cost to reach the top of the floor . At the beginning , You can choose from the subscript to 0 or 1 As the initial step .

Their thinking :

Dynamic planning ideas :

• state F(i) : It means to climb to the first i The minimum cost of a staircase
• State transition equation : F[i] = Math.min(F[i-2],F[i-1])+cost[i];
• The initial state : F(0) = cost[0];F(1) = cost[1]
• Return results : Math.min( F(len-1) , F(len-2) )

Because you can jump here 1 Step or 2 Step , Therefore, it is necessary to judge the first two minimum costs , Then add the current cost
The return result depends on Who is the smaller of the last step or the penultimate step

Code implementation :

class Solution {
    
    public int minCostClimbingStairs(int[] cost) {
    
        int[] dp = new int[cost.length];
        //  initialization 
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2; i < cost.length; i++) {
    
            dp[i] = Math.min(dp[i-2],dp[i-1])+cost[i];
        }
        return Math.min(dp[cost.length-1],dp[cost.length-2]);
    }
}

Fourth question : Flip the character

LeetCode: The finger of the sword Offer II 092. Flip the character
describe :
If one consists of ‘0’ and ‘1’ Composed string , With some ‘0’（ There may be no ‘0’） Followed by some ‘1’（ Or maybe not ‘1’） In the form of , Then the string is Monotone increasing Of .

We give a character ‘0’ and ‘1’ Composed string s, We can take any ‘0’ Flip to ‘1’ Or will ‘1’ Flip to ‘0’.

Return to make s Monotone increasing Minimum number of flips .

Their thinking :

• Traversal string s
• Determine whether the current character is 0
  If 0, Just record zero = Math.min(one, zero+1) Because when the initial state , No, 1 When , Start recording 0 Will waste , To record when 1 sometimes . Use here min The way to judge .
  If 1, Just record one++
  End of traversal , Compare zero and one Size , Return to the smaller

Code implementation :

Fifth question : Paint the house

LeetCode: The finger of the sword Offer II 091. Paint the house
describe :
If there is a row of houses , common n individual , Every house can be painted red 、 One of the three colors blue or green , You need to paint all the houses and make the two adjacent houses not the same color .

Of course , Because the prices of different colors of paint on the market are different , So the cost of painting the house in different colors is different . The cost of painting each house in a different color is one n x 3 Positive integer matrix of costs To represent the .

for example ,costs[0][0] It means the first one 0 The cost of painting the house red ;costs[1][2] It means the first one 1 The cost of painting the house green , And so on .

Please calculate the minimum cost of painting all the houses .

Their thinking :

There are requirements in the title : Paint all the houses and make them adjacent Two houses cannot be the same color
cost[i][0] = cost[i-1][1]+cost[i-1][2], In this way , Calculate the minimum value of each layer using the current color .
Return to the last layer , The youngest one

Code implementation :

class Solution {
    
    public int minCost(int[][] costs) {
    
        for(int i = 1; i < costs.length; i++){
    
            costs[i][0] += Math.min(costs[i-1][1],costs[i-1][2]);
            costs[i][1] += Math.min(costs[i-1][0],costs[i-1][2]);
            costs[i][2] += Math.min(costs[i-1][1],costs[i-1][0]);
        }
        return Math.min(costs[costs.length-1][0],Math.min(costs[costs.length-1][1],costs[costs.length-1][2]));
    }
}

Sixth question : House theft

LeetCode: The finger of the sword Offer II 089. House theft
describe :
A professional thief , Plan to steal houses along the street . There is a certain amount of cash in every room , The only constraint on thieves' theft is that adjacent houses are equipped with interconnected anti-theft systems , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .

Given an array of non negative integers representing the storage amount of each house nums , Please calculate Without triggering the alarm , The maximum amount that can be stolen overnight .

Their thinking :

Dynamic planning ideas :

• state F(i) : It means stealing i Maximum amount when subscribing
• State transition equation : F[i] = Math.max( F[i-2] + nums[i], F[i-1]) ;
• The initial state : F(0) = nums[0], F(1) = Math.max(nums[0],nums[1])
• Return results : F(len-1)

Code implementation :

class Solution {
    
    public int rob(int[] nums) {
    
        if(nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2; i < nums.length; i++) {
    
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
}