This is the 14th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

The last number left in the circle

Point to Offer 62. The last number left in the circle

Difficulty: Easy

Topic: leetcode-cn.com/problems/yu…

0,1… , n-1 The n numbers in a circle, starting with the number 0, delete the MTH number from the circle each time (counting from the next number after deletion). Figure out the last number left in the circle.

For example, the five digits 0, 1, 2, 3, and 4 form a circle. If you delete the third digit starting from the digit 0, the first four digits deleted are 2, 0, 4, and 1 in sequence, so the last digit left is 3.

Example 1:

Input: n = 5, m = 3 Output: 3Copy the code

Example 2:

Input: n = 10, m = 17 Output: 2Copy the code

Limitations:

  • 1 <= n <= 10^5
  • 1 <= m <= 10^6

Answer key

Dynamic programming

This is essentially a Joseph ring. N Delete a person every m times with the number 0 to N-1. I’m going to use f(n) for the number of people that are left over from n people.

The number of the first person deleted by n people is (m-1)%n, and the person after that is (m-1+1)%n, which means that m%n is the next Joseph ring person whose number is 0, and the person whose number is I for n-1 people is n people (m+ I)%n.

F (n)=(m+f(n-1))%n, f(1)=0

Therefore, the transfer equation of dynamic programming is:

The code is as follows:

 / * * *@param {number} n
  * @param {number} m
  * @return {number}* /
 ​
 var lastRemaining = function (n, m) {
   let ans = 0;
   for (let i = 2; i <= n; i++) {
     ans = (ans + m) % i;
   }
   return ans;
 };
Copy the code
  • Time complexity: O(N)
  • Space complexity: O(1)

The largest profit on stocks

The maximum profit on the stock

Difficulty: Medium

Topic: leetcode-cn.com/problems/gu…

Suppose the prices of a stock are stored in an array in chronological order. What is the maximum profit that can be made from buying or selling the stock at one time?

Example 1:

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1), sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Notice that the profit cannot be 7 minus 1 = 6, because the selling price has to be greater than the buying price.Copy the code

Example 2:

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

Limit: 0 <= Array length <= 10^5

Answer key

Law i. Violent law

Two for loop, direct violence out of maximum profit.

 / * * *@param {number[]} prices
  * @return {number}* /
 var maxProfit = function (prices) {
   let res = 0;
   for (let i = 0; i < prices.length; i++) {
     for (let j = i + 1; j < prices.length; j++) {
       res = Math.max(res, prices[j] - prices[i])
     }
   }
   return res;
 };
Copy the code
  • Time complexity: O(N^2)
  • Space complexity: O(1)

Method two: dynamic programming

Set dp[I] as the maximum profit of the subarray ending with prices[I].

Transfer equation: the maximum profit dp[I] of the previous day is the maximum profit dp[i-1] of the previous day and the maximum profit sold on day I prices[I]-min(prices[0: I]). The state equation is as follows:

Because this dp[I] is only related to dp[I -1], this dp can actually be replaced by a variable.

 var maxProfit = function (prices) {
   let dp = 0,cost = Infinity;
   for(let i = 0; i < prices.length; i++){
     cost = Math.min(cost,prices[i]);
     dp = Math.max(dp,prices[i] - cost);
   }
   return dp;
 };
Copy the code
  • Time complexity: O(N)
  • Space complexity: O(1)

Practice daily! The front end small adorable new one, hope can point to like ~