2021 05 27

This week’s five leetcodes are:

• Play 1217 chip
• 55 Jumping Game
• 62 Different Paths
• The best time to buy and sell stocks
• 279 perfect squares

Play 1217 chip

Topic describes

Some chips are placed on the number line, and the position of each chip is stored in the array CHIPS.

You can perform one of the following two operations on any chip (unlimited number of operations, or 0) :

• If you move the ith counter 2 to the left or right, the cost is 0.
• Move the ith counter 1 to the left or right at a cost of 1.

At the beginning, there may be two or more chips in the same position.

Returns the minimum cost required to move all chips to the same (arbitrary) position.

• Example 1:

Input: chips = [1,2,3] Output: 1 Explanation: the cost of moving the second chip to position 3 is 1, the cost of moving the first chip to position 3 is 0, and the total cost is 1.Copy the code

• Example 2:

Input: chips = [2,2,2,3,3] Output: 2Copy the code

Source: LeetCode link: leetcode-cn.com/problems/mi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution: greedy thinking

The basic idea of greed is to choose the local optimal solution as far as possible, that is, to move the chip as far as possible according to the cost of 0 every time, if there is no cost of 0 move, then consider the cost of 1.

We can know that chips store the positions of chips.

• Odd position to odd positionorEven position to even positionPrice for0
• Odd to even positionsorEven to odd positionsPrice for1

So you move all the odd-numbered chips to one of these positions, and then you move all the even-numbered chips to one of these positions, and the cost is zero.

Since the last two positions must be odd and even, the cost of the move is 1, and the cost of the move is x 1.

The above process of moving odd and even bits can also be expressed as counting odd (even) numbers.

// Greedy thinking
class Solution {
    public int minCostToMoveChips(int[] position) {
        int even = 0;   // The number of even positions
        int odd = 0;    // The number of odd positions
        for(int i = 0; i < position.length; ++i){
            if(position[i] % 2= =0){
                even++;
            }else{ odd++; }}returnMath.min(even,odd); }}Copy the code

55 Jumping Game

Topic describes

Given an array of non-negative integers, nums, you start at the first index of the array.

Each element in the array represents the maximum length you can jump at that location.

Determine if you can reach the last index.

– Example 1:

Input: nums = [2,3,1,1,4] output: trueCopy the code

• Example 2:

Input: nums = [3,2,1,0,4] Output: false But this subscript has a maximum jump length of 0, so you can never reach the last subscript.Copy the code

Source: LeetCode link: leetcode-cn.com/problems/ju… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1 dynamic programming

Nums [I] + I <= nums.length if the current position is I, the condition that the last subscript can be reached is that the distance from I to the last subscript is less than or equal to nums[I], that is, nums[I] + I <= nums.length, which can be used to determine whether to return true.

Dp [I] is used to represent the furthest position that the next hop can reach after reaching position I, then

Continuously evaluates the DP array and uses judgment criteria to determine whether it can return true.

Note also that if the current position I is unreachable — dp[i-1] < I — then return false.

If the array has only one element, the last index is the initial position and can always be reached.

public boolean canJump(int[] nums) {
    if(nums.length == 1) {return true;
    }
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    for(int i = 1; i < dp.length; i++){
        if(dp[i-1] < i){
            return false;
        }
        dp[i] = Math.max(dp[i-1],nums[i] + i);
        if(dp[i] >= nums.length - 1) {return true; }}return false;
}
Copy the code

Solution 2 greed

Greedy method is very similar to the idea of dynamic programming. Greedy method always considers the maximum position that the current position I can reach, and constantly updates the maximum position. The method of determining conditions and updates is the same as dynamic programming.

public boolean canJump(int[] nums) {
    int maxDistance = 0;
    for(int i = 0; i < nums.length; ++i){ 
        if(i > maxDistance){
            return false;
        }
        maxDistance = Math.max(maxDistance,nums[i] + i);
        if(maxDistance >= nums.length-1) {return true; }}return false;
}
Copy the code

62 Different Paths

Topic describes

A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).

The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).

How many different paths are there?

• Example 1:

`

Input: m = 3, n = 7 Output: 28Copy the code

• Example 2:

Input: m = 3, n = 2 Output: 3 Description: There are three paths to the lower right corner starting from the upper left corner.1.Right -> down -> down2.Down -> down -> to the right3.Down -> right -> downCopy the code

Source: LeetCode link: leetcode-cn.com/problems/un… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1 dynamic programming

For any position (I,j) in the grid, it is only possible to reach that position from the upper and left grids to the next step and one step to the right of that position.

Use dp[I][j] to represent the number of different paths to (I,j) (where I and j start from 0), then:

Initial conditions as follows: when I = = 0 | | j = = 0 is arrived at the location of the column with the Start position in the peer, there was only a different path.

// Dynamic programming
public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(i == 0 || j == 0){
                dp[i][j] = 1;
            }else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]; }}}return dp[m-1][n-1];
}   
Copy the code

Solution two recursion + memo

The above process can also use recursive functions to complete, assuming uniquePaths (I, j) said at position (I, j) on the number of different paths, is in the recursive function call, at the same time recursive termination conditions for I = = 1 | | j = = 1.

int uniquePaths(int i, int j) {
    if(i == 1 || j == 1) {return 1;
    }
    return uniquePaths(i-1,j) + unqiuePaths(i,j-1);
}
Copy the code

For example, when m == 3 and n == 2, the recursion tree is as follows, in which the green node (2,2) has been repeatedly calculated twice. With the expansion of the problem scale, the positions of repeated calculation will be more and more.

To ensure that each location is computed only once, we can store the computed result in the memo int[][] result. (I,j) is computed from the memo, and if the result of the memo is 0, the function is recursively called, and the result is stored in the memo.

// method two recursion + memo
public int uniquePaths(int m, int n) {
    // Initialize memos. Default is 0, indicating that none of them have been evaluated
    int[][] results = new int[m][n];
    return uniquePaths(results, m, n);
} 

// a recursive function
public int uniquePaths(int[][] results, int m, int n){
    // Termination conditions
    if(m == 1 || n == 1){
        results[m-1][n-1] = 1;
        return 1;
    }
    // Get results from the memo first
    int upResult = results[m-2][n-1];
    int leftResult = results[m-1][n-2];
    // If not, the result is computed recursively and stored in a memo
    if(upResult == 0){
        upResult = uniquePaths(results,m-1,n);
        results[m-2][n-1] = upResult;
    }
    if(leftResult == 0){
        leftResult = uniquePaths(results,m,n-1);
        results[m-1][n-2] = leftResult;
    }
    // Return the result
    return upResult + leftResult;
}
Copy the code

The best time to buy and sell stocks

Topic describes

Given an array prices, its ith element prices[I] represents the price of a given stock on day I.

You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

• Example 1:

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), maximum profit = 6-1 = 5.Note that the profit cannot be 7-1 = 6, because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them.Copy the code

• Example 2:

Input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

Source: LeetCode link: leetcode-cn.com/problems/be… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1 dynamic programming

Dp [I] is used to represent the maximum profit from selling the stock on day I, so the maximum profit from selling the stock on day 1 is 0.

Assuming that dp[I] is currently being calculated, the various cases are analyzed in detail below:

• (1) The maximum profit if sold the day beforedp[i-1] = 0Before,i-1The price of the day isThe ascending order of.
  • ifprices[i] > prices[i-1]So the maximum profit you can make from selling that day isprices[i] - prices[i-1]
  • Otherwise, the maximum profit is0
• (2) The maximum profit if sold the day beforedp[i-1] > 0Before,i-1The price of the lowest day isprices[i-1] - dp[i-1]When will
  • ifprices[i] > prices[i-1], then the profit is higher than the profit sold the day before,dp[i] = dp[i-1] + prices[i] - prices[i-1]
  • Otherwise, then the price of the day andprices[i-1] - dp[i-1]To compare
    • Such asprices[i] < prices[i-1] - dp[i-1]Before,i-1Every day the price is higher than that day and the profit is0
    • Otherwise, it means that there is a profit in selling on the day,dp[i] = prices[i] - (prices[i-1] - dp[i-1])

If diff = prices[I] -prices [i-1],temp = diff + dp[i-1]

if(dp[i-1] = =0){
    dp[i] = diff > 0 ? diff : 0;
}else{
    dp[i] = diff > 0 ? temp : (temp < 0 ? 0 : temp);
}
Copy the code

The code implementation is as follows:

// Dynamic programming
public int maxProfit(int[] prices) {
    int[] dp = new int[prices.length];
    int max = dp[0];
    for(int i = 1; i < prices.length; i++){
        int diff = prices[i] - prices[i-1];
        int temp = diff + dp[i-1];
        if(dp[i-1] = =0){
            dp[i] = diff > 0 ? diff : 0;
        }else{
            dp[i] = diff > 0 ? temp : (temp < 0 ? 0 : temp);
        }
        max = Math.max(dp[i],max);
    }
    return max;
}
Copy the code

Solution two: buy at the lowest price

A simple way to think about it is to buy a stock on the day it is cheapest, then just look at the maximum profit you can make at that day’s price and update that maximum profit.

Iterate through the price array, recording the current lowest price and updating the maximum profit each subsequent day.

Note that if the price on a given day is lower than the lowest price, the lowest price is updated and the profit is not calculated.

// Method 2: Buy at the lowest price
public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;
    for(int i = 0; i < prices.length; i++){
        if(prices[i] < minPrice){
            minPrice = prices[i];
        }else if(maxProfit < prices[i] - minPrice){ maxProfit = prices[i] - minPrice; }}return maxProfit;
}
Copy the code

279 perfect squares

Topic describes

Given a positive integer n, find several perfect squares (e.g. 1, 4, 9, 16…). So that their sum is equal to n. You want to minimize the number of perfect squares that make up the sum.

Given an integer n, return the minimum number of perfect squares that sum to n.

A perfect square is an integer whose value equals the square of another integer; In other words, its value is equal to the product of an integer. For example, 1, 4, 9, and 16 are perfect squares, but 3 and 11 are not.

• Example 1:

Input: n = 12 Output: 3 Description: 12 = 4 + 4 + 4Copy the code

• Example 2:

Input: n = 13 Output: 2 Description: 13 = 4 + 9Copy the code

Source: LeetCode link: leetcode-cn.com/problems/pe… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1 dynamic programming

Use dp[I] to represent the minimum number of perfect squares whose integers sum is I.

If I is itself a perfect square, then dp[I] = 1.

If I is not a perfect square, we can regard I as the sum of j and i-j, where j is a perfect square smaller than I, then:

In dynamic programming, to record the number of perfect squares smaller than the current integer, we use a list list to store all the perfect squares that have occurred so far.

If a number is a perfect square, set dp to 1 and add the number to the list. If a number is not a perfect square, the list is iterated (j represents an element in the list) and dp[I] is calculated using the formula above.

Finally, return dp[n].

// Dynamic programming
public int numSquares(int n) {
    int[] dp = new int[n+1];
    // list records the number of perfect squares currently traversed
    List<Integer> list = new ArrayList<>();
    dp[1] = 1;
    list.add(1);
    for(int i = 1; i <= n; ++i){
        // If it is a perfect square and the result is 1, add to list
        if(isSquare(i)){
            dp[i] = 1;
            list.add(i);
            continue;
        }
        // If not a perfect square
        // To compare minimum values, dp[I] is initially set to a larger value, which can also be set at new
        dp[i] = n+1;
        for(intj : list){ dp[i] = Math.min(dp[j] + dp[i-j],dp[i]); }}return dp[n];
}

// check whether num is a perfect square
public boolean isSquare(int num){
    int i = (int)Math.sqrt(num);
    return i*i == num;
}
Copy the code