Fibonacci
The Fibonacci sequence refers to the sequence 0, 1, 1, 2, 3, 5, 8, 13, specifically: the 0th term is 0, and the first term is the first 1. Starting with the third term, each term is equal to the sum of the first two terms. Write a function, input n, to find the NTH term of the Fibonacci sequence. The Fibonacci sequence is defined as follows: F(0) = 0, F(1) = 1 F(N) = F(n-1) + F(n-2), where N > 1. The Fibonacci sequence starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers. 1e9+7 (1000000007) is required for the answer. If the initial calculation result is 1000000008, return 1.Copy the codemethods1Recursion Principle: Divide the calculation of f(n) problem into F (N −1) and f (n -2) two subproblems, and recursively, f(0) and f (1) is the termination condition. Disadvantages: lots of repetitive recursive calculations, such as f(n) and f(n−1) Both downward recursions require the computation of f(n− respectively2The value of).class Solution:
def fib(self, n: int) - >int:
a,b=0.1
for i in range(n):
a,b=b,a+b
return a
Copy the code
methods2Dynamic programming dynamic programming:1State definition: let dp be a one-dimensional array, where the value of dp[I] represents the ith number in the Fibonacci sequence.2, transfer equation: DP [I +1[I] = dp [I] + dp -1], the corresponding sequence definition f(n+1)=f(n)+f(n-1);3, initial state: DP [0] =0, dp[1] =1, that is, initialize the first two digits;4, return value: dp[n], that is, the NTH number of Fibonacci sequence. Reduced space complexity:1, if a DP list with length n is created, the space complexity is O(n).2, because the i-th item in the DP list is only the i-th −1And the first I -2Item, so only three integer variables need to be initializedsumA, b, using auxiliary variablessumMake a, B two digits forward alternately (see the code for concrete implementation).3, save dp list space, so the space complexity is reduced to O(1). Loop remainder method: Large number out of bounds: as n increases, f(n) will exceed the value range of Int32 or even Int64, resulting in the final return value error. Rule of complementation operation: set positive integers x, y, p, the complementation sign is ⊙, then (x+y)⊙p=(x⊙p+y⊙p)⊙p. F (n)⊙p=[f(n−1) it's p + f (n -2)⊙p]⊙p so that it can be calculated each time in the loopsumIt = (a + b)1000000007, this operation is equivalent to finalizing before returning. Complexity analysis: Time complexity O(n) : calculation of f(n) needs n cycles, and calculation operations within each cycle use O(1). Space complexity O(1) : Several flag variables use extra space of constant size.class Solution:
def fib(self, n: int) - >int:
a, b = 0.1
for _ in range(n):
a, b = b, (a + b) % 1000000007
return a
Copy the code2 Binary search
Binary search is a search algorithm that looks for a particular element in an ordered array. The search process starts with the middle element of the array, and ends if the middle element is exactly the element being searched.
If a particular element is greater than or less than the middle element, it looks in the half of the array that is greater than or less than the middle element, and compares from the middle element as it began. If the array is empty at any step, it cannot be found.
# This search algorithm halves the search area with each comparison.
def binarySearch(nums, target) :
if len(nums) == 0:
return -1
left, right = 0.len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target: # Look right
left = mid + 1
else:
right = mid - 1 # Search left
Data does not exist, return -1
return -1
re = binarySearch(nums=[-1.0.3.5.9.12], target=2)
print(re)
Copy the code3 The oldest string without repeating characters
Given a string, find the length of the smallest string that does not contain repeating characters.
Example 1:
Explanation: Since the oldest string without repeating characters is "ABC", its length is 3.Copy the codeExample 2:
Input: "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1.Copy the codeExample 3:
Input: "pwwkew" Output: 3 Explanation: Since the oldest string without repeating characters is "wke", its length is 3. Note that your answer must be the length of the substring, "pwke" is a subsequence, not a substring.Copy the codeSolution 1: dynamic programming + hash table
State definition: Let the dynamic programming list dp, where dp[j] represents the length of the longest non-repeating substring ending with character s[j]. Transfer equation: fix the right boundary j, and let s[I] be the closest same character to the left of character S [j], that is, S [I] = s[j]. 1. If I < 0, dp[j] = dp[j-1] + 1; Dp [j] = dp[j-1]+1; dp[j] = dp[j-1]+1; 3. If dp[j] ≥j− I is in the interval of substring dp[j], then the left boundary of dp[j] is determined by s[I], that is, dp[j]=j− I; Therefore, when I < 0, dp[j−1]≤j is always valid, so DP [j−1]<j− I is always valid, so branch 1. And 2. Can be combined. Return value: Max (dp), the length of the global longest unrepeatable substring.Copy the code
class Solution:
def lengthOfLongestSubstring(self, s: str) - >int:
dic = {}
res = tmp = 0
for j in range(len(s)):
i = dic.get(s[j], -1) #
dic[s[j]] = j #
tmp = tmp + 1 if tmp < j - i else j - i # dp[j - 1] -> dp[j]
res = max(res, tmp) # max(dp[j - 1], dp[j])
return res
Copy the codeSolution 2: Sliding Windows
class Solution2:
def lengthOfLongestSubstring(self, s: str) - >int:
Hash set, which records whether or not each character has ever appeared
occ = set()
n = len(s)
The right pointer, which starts at -1, corresponds to the left side of the string's left boundary and has not yet started moving
rk, ans = -1.0
for i in range(n):
ifi ! =0:
Move the left pointer one space to the right to remove a character
occ.remove(s[i - 1])
while rk + 1 < n and s[rk + 1] not in occ:
# Keep moving the right pointer
occ.add(s[rk + 1])
rk += 1
# the i-th to rk characters are an extremely long non-repeating character substring
ans = max(ans, rk - i + 1)
return ans
Copy the codeSolution 3: dynamic programming + dual Pointers
Dic statistics: pointer J traverses character s, hash table statistics character s[j] last occurrence of the index. Update the left pointer I: according to the left pointer I of the previous round and DIC [s[j]], update the left boundary I of each round to ensure the interval [I +1,j] contains no repeated characters and the maximum. i=max(DIC [S [J]], I) Update result RES: The last round RES and the double pointer interval of the current round [I +1, the maximum value in the width of j] (i.e. J − I). res=max(res,j− I) Complexity analysis: Time complexity O(N) : N is a string length. Dynamic planning requires iterating the DP list. Space complexity O(1) : the ASCII range of characters is0 ~ 127, dic hash table at most use O(128)=O(1) size of extra space.class Solution:
def lengthOfLongestSubstring(self, s: str) - >int:
dic, res, i = {}, 0, -1
for j in range(len(s)):
if s[j] in dic:
i = max(dic[s[j]], i) Update the left pointer I
dic[s[j]] = j Hash table records
res = max(res, j - i) # Update results
return res
Copy the code4 Integer Inversion
To give you one32A signed integer x of bits that returns the result of reversing the numeric portion of x. If the integer after inversion exceeds32The range of signed integers of bits [−231.231 − 1] and return0. The sample1: Enter x =123Output:321The sample2: Enter x = -123Output: -321The sample3: Enter x =120Output:21The sample4: Enter x =0Output:0
class Solution:
def reverse(self, x: int) - >int:
str1 = str(x)
if str1[0] = =The '-':
str1 = str1[0] + str1[:0: -1]
a = int(str1)
if (1 << 31) < abs(a):
return 0
else:
str1 = str1[::-1]
a = int(str1)
if a > (1 << 31) - 1:
return 0
return a
Copy the code5 Ugly number problem: Determine whether the data is ugly
Ugly number: Write a program to determine whether a given number is ugly. Ugly numbers contain only prime factors2.3.5Is a positive integer.class Soluation:
def chouShu(self, num: int) :
if num <= 0:
return False
focues = [2.3.5]
for focue in focues:
while num % focue == 0: Modulo - Returns the remainder of the division
num //= focue C //= a is equivalent to c = c // a
return num == 1
Copy the codeUgly number problem: find the number of ugly number
Write a program to find the NTH ugly number. Ugly numbers are prime factors that only contain2.3.5Is a positive integer. Example: Enter n =10Output:12Explanation:1.2.3.4.5.6.8.9.10.12Is the former10A number of ugly. Description:1Is ugly. N is less than1690.class Solution:
def nthUglyNumber(self, n: int) - >int:
dp, a, b, c = [1] * n, 0.0.0
for i in range(1, n):
n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5
dp[i] = min(n2, n3, n5)
if dp[i] == n2: a += 1
if dp[i] == n3: b += 1
if dp[i] == n5: c += 1
return dp[-1]
Copy the code7 Palindrome character string
Given a string, determine whether the string can be rearranged to form a palindrome string. The sample1Input:"code"Output: false example2Input:"aab"Output: true example3Input:"carerac"Output: true,class Solution:
def canPermutePalindrome(self, s: str) - >bool:
dic = {} {'a':2,'b':1}
for c in s: # Values loop through the string
if dic.get(c) == None: # if the specified k-v value is null
dic[c] = 1
else:
dic[c] += 1 Write value to the DIC dictionary
count = 0
for num in dic.values(): # return an iterator that can be converted to a list using list()
if num % 2= =0: If the num value is divisible by 2
continue
else: # If num is not divisible by 2
count += 1 + 1 # cycle
if count > 1:
return False
return True
Copy the codePalindrome arrangement
Given a string s, returns all possible palindromic strings rearranged and combined, removing duplicate combinations. If no palindrome can be formed, an empty list is returned. The sample1Input:"aabb"Output:"abba"."baab"] example2Input:"abc"Output: []class Solution:
def generatePalindromes(self, s: str) - >List[str] :
dic = collections.Counter(s)
odd, h = [], ' '
for k in dic:
if dic[k]%2= =1: odd.append(k)
h += k*(dic[k]//2)
if len(odd) > 1: return []
def dfs(cur, path) :
if not cur:
res.add(path)
for i in range(len(cur)):
if i == 0 orcur[i] ! = cur[i-1]:
dfs(cur[:i] + cur[i+1:], path + cur[i])
res = set()
dfs(h, ' ')
return [p + p[::-1] for p in res] if not odd else [p + odd[0] + p[::-1] for p in res]
Copy the code9 Look for the missing number
Given a containing [0, n] array nums of n numbers, find [0N] the number in the range that does not appear in the array. The sample1: Input: nums = [3.0.1] output:2Explanation: n =3Because there are3Number, so all numbers are in the range [0.3].2Is the missing number because it does not appear in NUMS. The sample2: Input: nums = [0.1] output:2Explanation: n =2Because there are2Number, so all numbers are in the range [0.2].2Is the missing number because it does not appear in NUMS.class Solution:
def missingNumber(self, nums: List[int]) - >int:
return int(len(nums)*(len(nums)+1) /2-sum(nums))
Copy the code10 Obtain the column name of a positive integer in Excel
Given a positive integer, return its corresponding column name in the Excel table. The sample1Input:1Output:"A"The sample2Input:28Output:"AB"The sample3Input:701Output:"ZY"
class Solution:
def convertToTitle(self, n: int) - >str:
res=' '
while n:
res=chr((n-1) %26+ord('A'))+res
n=(n-1) / /26
return res
Copy the code11 Gets all combinations between two numbers
Find all the combinations of k numbers that add up to n. Only contain is allowed in the combination1 - 9Is a positive integer, and there are no duplicate digits in each combination. Note: All numbers are positive integers. The solution set cannot contain repeated combinations. The sample1: Enter k =3, n = 7Output: [[1.2.4]] sample2: Enter k =3, n = 9Output: [[1.2.6], [1.3.5], [2.3.4]]
from itertools import combinations
class Solution:
def combinationSum3(self, k: int, n: int) - >List[List[int]] :
nums=[1.2.3.4.5.6.7.8.9]
res=[]
for i in range(len(nums)):
res += list(combinations(nums,i))
res=[x for x in res if len(x) == k]
a=[]
for j in res:
if sum(j) ==n :
a.append(list(j))
return a
Copy the code12 array problem 1
Given a binary array, calculate its maximum contiguity1The number of. Example: Enter: [1.1.0.1.1.1] output:3Explanation: The first two and the last three are consecutive1, so maximum continuous1The number of is3.Tip: The input array contains only0 和 1. The length of the input array is a positive integer and does not exceed10.000.class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) - >int:
count,result=0.0 # counter
for i in range(len(nums)):
if nums[i]==1: If the value is 1, increment the value of count by 1
count+=1
else:
result=max(count,result) # when not 1, get the maximum value
count=0 Set the counter to 0 and recount
return max(result,count)
Copy the code13 array problem 2
Given an array nums, write a function that will take all0Moves to the end of the array while preserving the relative order of the non-zero elements. Example: Enter: [0.1.0.3.12] output: [1.3.12.0.0] Note: must operate on the original array, cannot copy additional arrays. Minimize the number of operations.class Solution:
def moveZeroes(self, nums: List[int]) - >None:
index=0
for i in range(len(nums)):
ifnums[i] ! =0: # when num[I] is not 0
nums[index]=nums[i] # num[index]赋值为num[i]
index +=1
for j in range(len(nums)): # walk through the list
if j>=index: # when j is greater than index, num[j] is set to 0
nums[j]=0
return nums
Copy the code14 Search for the insertion position
Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order. You can assume that there are no duplicate elements in the array. The sample1: Input: [1.3.5.6].5Output:2The sample2: Input: [1.3.5.6].2Output:1The sample3: Input: [1.3.5.6].7Output:4The sample4: Input: [1.3.5.6].0Output:0The problem solving method1:class Solution:
def searchInsert(self, nums: List[int], target: int) - >int:
if target in nums:
for i in range(len(nums)):
if nums[i]==target:
return i
else:
if target<nums[0] :return 0
elif target>nums[-1] :return len(nums)
else:
for i in range(len(nums)-1) :if nums[i]<target<nums[i+1] :return i+1
Copy the codeThe problem solving method2:class Solution:
def searchInsert(self, nums: List[int], target: int) - >int:
nums.append(target) Add elements directly to the array
nums.sort() # sort the array
return nums.index(target) Get the index of the data element
Copy the code15 Remove list elements
Val == val; delete all nodes in the list where node. val == val and return the new head Node. The sample1: Enter: head = [1.2.6.3.4.5.6], val = 6Output:1.2.3.4.5]
Copy the code
Example 2: Input: head = [], val = 1 Output: [] Example 3: Input: head = [7,7,7], val = 7 Output: []Copy the codeclass ListNode:
def __init__(self, val=0.next=None) :
self.val = val
self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
prev=temp=ListNode() # prev is a pointer, temp is temporary
temp.next=head The next temporary value is the head node
while head is not None: # when head is not empty
if head.val==val: # if head is equal to val
prev.next=head.next The next value of # prev is equal to the next value of head
else: # if head is not equal to val
prev=prev.next # prev assigns the next value of prev
head=head.next
return temp.next
Copy the codeReverse the linked list
Reverse a single linked list. Example: Input:1->2->3->4->5- > NULL output:5->4->3->2->1->NULL Advanced: You can iterate or recursively reverse linked lists. Can you solve the problem in two ways?class ListNode:
def __init__(self, val=0.next=None) :
self.val = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
n1,n2=head,None
while n1:
temp=n1.next The # temp temp pointer assigns the next value to head
n1.next=n2 # n1.next=n2
n2=n1 # n2=n1
n1=temp # n1 = temp temp: [2, 3]
return n2
Copy the code17 double pointer
Title: Enter two incrementally sorted lists and merge them so that the nodes in the new list are still incrementally sorted.
The sample1Input:1->2->4.1->3->4Output:1->1->2->3->4->4
Copy the codeclass ListNode:
def __init__(self, x) :
self.val = x
self.next = None
class Solution:
def mergeTwoLists(self, L1: ListNode, L2: ListNode) -> ListNode:
cur=tep=ListNode(0)
while L1 and L2:
if L1.val<L2.val:
cur.next,L1=L1,L1.next
else:
cur.next,L2=L2,L2.next
cur=cur.next
cur.next = L1 if L1 else L2
If x else B, execute A if x = True, execute B otherwise
return tep.next
Copy the code18 Alternately prints integers between 1 and 100
Print 1,2,3,4,5... An integer between 100
import threading
import time
def threadA() :
""" Print an odd number """
for i in range(1.100 + 1) :if i % 2! =0:
lockb.acquire()
print(i),
locka.release()
time.sleep(0.1)
def threadB() :
""" Print even numbers """
for i in range(1.100 + 1) :if i % 2= =0:
locka.acquire()
print(i),
lockb.release()
time.sleep(0.1)
if __name__ == "__main__":
locka = threading.Lock()
lockb = threading.Lock()
ta = threading.Thread(None, threadA)
tb = threading.Thread(None, threadB)
locka.acquire() Ensure that A is executed first
ta.start()
tb.start()
ta.join()
Copy the codeThe maximum profit of the stock
Suppose the price of a stock is stored in an array in chronological order. What is the maximum profit that can be made by trading the stock at one time?
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 greater than the buying price.Copy the codeExample 2:
Input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the codeMethod 1: Violence
class Solution:
def maxProfit(self, prices: List[int]) - >int:
ans=0
for i in range(len(prices)):
for j in range(i+1.len(prices)):
ans=max(ans,prices[j]-prices[i])
return ans
Copy the codeMethod 2: Dynamic programming
Suppose there are n days in total, buy on day A and sell on day B, then ensure that a< B; Can launch trading scheme for a total of: (n - 1) + (n - 2) +. + 2 + 1 = n (n - 1) / 2, therefore, violent method of time complexity is O (n ^ 2). Consider using dynamic programming to reduce time complexity and solve the problem as follows. Set the dynamic programming list dp, where dp[I] represents the maximum profit of the subarray ending with prices[I] (hereinafter referred to as the maximum profit of the day before I). Transfer equation: since the problem is limited to "buy and sell the stock once", the maximum profit dp[I] on the previous I day is equal to the maximum profit DP [i-1] on the previous I −1 day and the maximum profit sold on the I day. Dp [I]= Max (dp[I −1],prices[I]−min(prices[0: I]) prices[0]=0. The returned value is dp[n−1], where n is the length of the DP list.Copy the code
class Solution:
def maxProfit(self, prices: List[int]) - >int:
minprice,maxprofit= int(1e9),0 Ten to the ninth
for price in prices:
minprice = min(price, minprice) # Get the lowest price
maxprofit = max(price - minprice, maxprofit) # Maximize profit
return maxprofit
Copy the code20 Stock maximum profit II
Given an array prices, prices[I] is the price of a given stock on day I.
Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.
Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 7 Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.Copy the codeExample 2:
Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), this transaction will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the codeExample 3:
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 codeGreedy algorithm stock buying and selling strategies:
- Single trading day: if today’s price is P1 and tomorrow’s price is P2, then the profit earned by buying today and selling tomorrow is P2-P1 (negative value represents loss).
- Continuous rising trading day: set the stock price of this rising trading day as P1, P2… Pn-p1 =(P2-P1)+(P3-P2)+… +[Pn-P(n-1)]
- Continuous decline trading day: do not buy and sell the biggest gain, that is, will not lose money.
Algorithm flow:
- The strategy is to buy and sell on all up days (make all profits) and not buy and sell on all down days (never lose money).
- TMP = prices[I] -prices [i-1];
- When the profit is positive TMP > 0, the profit is added to the total profit. When the profit is 00 or negative, skip directly;
- After traversal, total profit is returned.
Complexity analysis:
- Time complexity O(N)O(N) : price is traversed only once;
- Space complexity O(1)O(1) : Variables use constant extra space.
class Solution:
def maxProfit(self, prices: List[int]) - >int:
profit = 0
for i in range(1.len(prices)):
tmp = prices[i] - prices[i-1]
if tmp > 0: profit += tmp
return profit
Copy the code21 interview questions
For example, the longest continuous substring in the array [1, 2,4, 3,4,5, 7] is [3,4,5]. Then the largest element in stack A always corresponds to the top element in stack B. Write nums[I] to stack B (2) when stack B is empty, write nums[I] to stack B (3) when stack B is empty, empty nums[I] to stack B. def maxSubArray(self, nums: list): stack, res = [], [] for i in range(0, len(nums)): if not stack or stack[-1] + 1 == nums[i]: stack.append(nums[i]) else: res = stack stack = [] return resCopy the code