& & other algorithms

1, Algorithm

1. Given an array of prices, its ith element price [i] represents the price of a given stock on day I.
   You can only choose to buy this stock 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 this transaction. If you can't make any profit, return 0

Analysis: simple questions (lc121)

Idea 1: dynamic programming: according to the meaning of the topic, there are the following two constraints:
Condition 1: you cannot sell stocks before buying stocks;
Condition 2: only one transaction is allowed to be completed at most.
Whether to hold shares on the same day is a very important factor, and whether to hold shares today is related to whether to hold shares yesterday. Therefore, we need to design whether to hold shares into the status array

Train of thought 2: record the lowest point in history:
1. Record historical lowest price minprice with variable
2. Then the profit from selling stocks on day I is price [i] - minprice
3. Therefore, we only need to traverse the price array once to record the lowest point in history

class Solution_dp:
    def maxProfit(self , prices ):
        maxprofit = 0
        dp = 0                            #dp is recorded as the maximum gain from selling on day i
        for i in range(1,len(prices)):
            dp = max(dp, 0) + prices[i]-prices[i-1] #Then dp[i+1]=max(prices[i+1]-prices[i]+dp[i],prices[i+1]-prices[i])
            if dp > maxprofit:
                maxprofit = dp
        return maxprofit
        # write code here
        
class Solution_histMin:
    def maxProfit(self , prices ):
        # write code here
        # Initialize maximum
        inf = int(1e9)
        minprice = inf
        maxprofit = 0
        for price in prices:
            maxprofit = max(price - minprice, maxprofit)
            # Find the lowest stock price
            minprice = min(price, minprice)
        return maxprofit

1. Enter an integer array. One or more consecutive integers in the array form a sub array. Find the maximum value of the sum of all subarrays

Analysis: simple questions (lc53)
Dynamic programming: dp[i] represents the maximum sum of successive subarrays ending with I. Therefore, dp[n-1] state transition equation is finally required: dp[i] = max(array[i], dp[i-1]+array[i])

# -*- coding:utf-8 -*-
#Space optimization is O(1)
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        temp = array[0]
        res = temp
        for i in range(1, len(array)):
            temp = max(temp, 0) + array[i]
            if res < temp: res = temp
        return res
        # write code here

1. Given two strings str1 and str2, and three integers ic, dc and rc, respectively representing the cost of inserting, deleting and replacing a character, please output the minimum cost of editing str1 into str2.

Analysis: hard(lc72)
dp(i, j) is the cost of str1[0... i] and str2[0... j] strings for matching
Initial status: dp[i][0] = i, I times deleted; dp[0][i] = i, I inserts
Transfer equation:
When I character is equal to j character: dp[i][j] = dp[i-1][j-1], no additional operation is required
When I character is not equal to j character: DP [i] [J] = math Min (insert, delete, replace), where
insert = dp[i][j-1] + 1; Edit I characters into J-1 characters, and then insert a j
delete = dp[i-1][j] + 1; i-1 is edited into J letters, and then an I is deleted
replace = dp[i-1][j-1] + 1; Edit I-1 to J-1 letters, and then replace I with J

# min edit cost
# @param str1 string the string
# @param str2 string the string
# @param ic int integer insert cost
# @param dc int integer delete cost
# @param rc int integer replace cost
# @return int integer
#
class Solution:
    def minEditCost(self , str1 , str2 , ic , dc , rc ):
        lenth1, lenth2 = len(str1), len(str2)
        dp = [[0] * (lenth2+1) for i in range(lenth1+1)]
        for i in range(1, lenth1+1):
            dp[i][0] = i * dc
        for j in range(1, lenth2+1):
            dp[0][j] = j * ic
        for i in range(1, lenth1+1):
            for j in range(1, lenth2+1):
                #Last discussion position of str1 pair of operations
                if str1[i-1] == str2[j-1]: dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1] + rc, dp[i-1][j] + dc, dp[i][j-1] + ic)
        return dp[-1][-1]
        # write code here

2, Eight part essay

1. The difference between docker image and container and docker command( 1, 2, 3)
2. RNN gradient vanishing problem( 1,  2, 3)
3. Advantages of svm over LR or Perceptron( 1, 2)
4. L1 regular and L2 regular( 1)
5. The main differences between GPT and bert( 1, 2)
6. What is the difference between generative model and discriminant model( 1, 2)
7. Variance and deviation of the model( 1, 2, 3, 4)

3, Other

To be solved (welcome to comment area or private letter)

1. Given an ordered array A and a constant C, find the maximum spacing D in all subsequences with length C.
   Definition of the spacing of an array: the minimum value of the difference between the latter element minus the previous element in all two adjacent elements For example, the spacing of [1,4,6,9] is 2
   Example: A:[1,3,6,10], C:3. The maximum spacing D should be 4, and the corresponding subsequence can be [1,6,10].

2. Given a number matrix and a number target, such as 5. Starting from the number 1 (there may be multiple ones in the matrix), you can choose a direction to move up, down, left and right once at a time. The condition for moving is that the next number must be the previous number + 1. For example, 1 must find the point with the upper, lower, left and right as 2, 2 must find the point with the upper, lower, left and right as 3, and so on. How many paths are there to reach the target.