“This is my 36th day of participating in the First Challenge 2022. For details: First Challenge 2022.”

Today we will introduce two simple questions, which are the best time to buy and sell stocks in LeetCode 121 and the number that appears only once in LeetCode 136.

The best time to buy and sell stocks

Given an array of prices, the ith element in the array represents the price of the given stock on the ith day. The user can buy a stock one day and sell it at a future date, requiring a calculation of the maximum profit the user can make, and returning zero if there is no profit.

For example, if [6, 4, 3, 1] is entered, there is no profit and 0 is returned. Input [8, 1, 5, 6, 9] gives a profit of 8. Just go back.

Their thinking

Violent solution

The first thing that comes to mind is the violent solution. We only need to traverse ij twice, and the second traverse j is always after the first traverse element I. If the element of J is greater than the element of I, the profit at this time is calculated, and if the profit is greater than the maximum profit, the maximum profit is updated, with the following code:

public int maxProfit(int[] prices) {
        int n=prices.length;
        int maxProfit=0;
        for(int i=0; i<n-1; i++){for(int j=i+1; j<n; j++){if(prices[i]<prices[j]){ maxProfit = Math.max(maxProfit, prices[j] - prices[i]); }}}return maxProfit;
    }
Copy the code

This method will time out, the time complexity is O(n2)O(n^2)O(n2), the space complexity is O(1)O(1)O(1).

Dynamic programming

Another way of thinking is that the profit of the following day depends on the lowest price of the previous day. After obtaining the lowest price of the previous day, it is easy to calculate the profit of the following day, and the lowest price of the current day depends on the lowest price of the current day and the previous day. Therefore, dynamic programming recursion can be obtained:


d p [ i ] = M a t h . m i n ( d p [ i – 1 ] . p r i c e s [ i ] ) dp[i] = Math.min(dp[i-1], prices[i])

Where dp[I] represents the lowest price up to day I. The profit after that is the price of the day minus the lowest price up to that day. The code is as follows:

public int maxProfit(int[] prices) {
        int[] dp = new int[prices.length];
        dp[0] = prices[0];
        int maxProfit=0;
        for(int i=1; i<prices.length; i++){ dp[i] = Math.min(dp[i-1], prices[i]);
            maxProfit = Math.max(maxProfit, prices[i]-dp[i]);
        }
        return maxProfit;
    }
Copy the code

The time complexity and space complexity of the above code are both O(N)O(N)O(N). This code can also be optimized. We can find that we only use the lowest price of the previous day each time, so we can directly save the lowest price of the previous day as a variable.

 public int maxProfit(int[] prices) {
        int maxProfit=0;
        int minPrice=Integer.MAX_VALUE;
        for(int i=0; i<prices.length; i++){ minPrice = Math.min(minPrice, prices[i]); maxProfit = Math.max(maxProfit, prices[i]-minPrice); }return maxProfit;
    }
Copy the code

After optimization, the space complexity is O(1)O(1)O(1).

A number that appears only once

Given a non-empty array in which only one number appears once and all the other numbers appear twice, find the number that appears only once.

Magical xor

To solve this problem, we need to understand a feature of xOR, which is as follows:

  1. 0 ^ N = N
  2. N ^ N = 0

And xOR operation has commutative and distributive laws.

Xor = xor = xor = xor = xor = xor = xor = xor = xor = xor = xor

public int singleNumber(int[] nums) {
        for(int i=0; i<nums.length-1; i++){ nums[i+1] ^= nums[i];
        }
        return nums[nums.length-1];
    }
Copy the code

The time complexity of the above code is O(n)O(n)O(n) O(n), and the space complexity is O(1)O(1)O(1) O(1).