1. * * * the sum of the two numbers is the specified value
-
Given an integer array, can you find two numbers so that their sum is a specified value?
-
Example: if the input array is {1, 5, 7, 3} and the specified value is 10, we can find two numbers 3 and 7, and the sum is equal to 10.
-
# The function call format is as follows # -*- coding: UTF-8 -*- def hasSum(array, target): sorted_array = sorted(array) length = len(sorted_array) i, j = (0, length - 1) while i < j: if sorted_array[i] + sorted_array[j] > target: j -= 1 elif sorted_array[i] + sorted_array[j] < target: i += 1 else: break if i < j: return sorted_array[i], sorted_array[j] if __name__ == '__main__': array = [1, 5, 3, 7] target = 4 res = hassum(array, target) print(res) -
The above method can only find a pair of values with sum as the target value. For the case where multiple pairs may occur
def hassum(array, target)；
sorted_array = sorted(array) # The default is ascending
i, j = 0, len(array) - 1
result = []
while i < j:
if sorted_array[i] + sorted_array[j] > target:
j -= 1
elif sorted_array[i] + sorted_array[j] < target:
i += 1
else:
result.append([sorted_array[i], sorted_array[j]])
return list(set(result)) # duplicate removal
if __name__ == "__main__":
array = [0, 0, 4, 1, 2, 3, 5, 7]
target = 7
res = hassum(array, target)
print(res)
2. * * * stock trading
Given an array, the ith element represents the stock price on day i. Assuming that at most one transaction is allowed, what is the maximum possible profit?
-
Example: if you enter price = [12, 15, 14, 8, 11, 10, 12], the maximum output profit is 4.
-
def get_max_profit(price): if price is None or len(price) == 0: return 0 max_profit = 0 min_price = price[0] length = len(price) # Traverse to select the minimum price and calculate the maximum price difference for i in range(1, length): min_price = min(min_price, price[i]) max_profit = max(max_profit, price[i] - min_price) return max_profit # The function call format is as follows if __name__ == '__main__': price = [12, 15, 14, 8, 11, 10, 12] result = get_max_profit(price) print(result)
3. * * * quick sort
-
def quick_sort(array, start, end): # Recursive condition if start >= end: return left, right = start, end pivot = array[start] while left < right: while array[right] >= pivot and left < right: right -= 1 array[left] = array[right] while array[left] <= pivot and left < right: left += 1 array[right] = array[left] # Confirm the position of the benchmark. The left side of the array is smaller than the benchmark and the right side is larger than the benchmark array[left] = pivot quick_sort(array, start, left - 1) quick_sort(array, right + 1, end) if __name__ == '__main__': array = [4, 5, 5, 3, 3, 1, 6, 8, 7, 2] quick_sort(array, 0, len(array) -1) print(array)
4. Leapfrog
Frog jump gives an array of one-dimensional non negative elements, and each element represents the longest distance that the element position can jump. Assuming that the initial position is in the first element, please judge whether you can jump to the end of the array according to the input array.
-
Example:
- Input array A = [2, 1, 3, 1, 1], output True
- Input array A = [3, 2, 1, 0, 1], output False
-
A = [6, 2, 1, 1, 2, 1, 1, 0, 1]
-
# Idea: double pointer # Two pointers moving in the same direction: the first pointer scans the current value, and the second pointer records the current farthest destination. # While scanning, the current farthest destination is updated in real time. If the current farthest destination can reach the end of the array, the program returns # Return true. If the current farthest destination cannot reach the tail end and cannot move forward, we don't think so # The program returns false when the destination may be reached. def frog_jump(arr): # Array length length = len(arr) # Returns False if the array length is less than or equal to 1 if length <= 1: return False # Set double pointers, one to record the current position value and one to record the maximum distance that can be jumped at present curMax = 0 for i in range(length - 1): # If the current position value is zero, the current maximum distance cannot be moved back # The frog cannot continue to jump forward if arr[i] == 0 and curMax < i + 1: return False # If the current position element is non-zero and the current maximum distance is greater than the previous maximum distance # The frog can continue to jump back if arr[i] > 0 and arr[i] + i > curMax: curMax = arr[i] + i # When the farthest position is greater than or equal to the length of the array, it is considered that the frog can jump to the end if curMax >= length - 1: return True # If none of the above conditions are met, False is returned return False if __name__ == '__main__': a = [2, 1, 3, 1, 1] b = [3, 2, 1, 0, 1] res = frog_jump(b) print(res) res = frog_jump(a) print(res)
5. Digital Watershed
In a one-dimensional array, find a point so that all the numbers on the left are less than or equal to it and all the numbers on the right are greater than or equal to it, and return the subscript where the point is located.
-
Example: enter one-dimensional array A = [1, 0, 1, 0, 1, 2, 3], and return subscript 4 or 5.
def get_point_number(arr): arrLen = len(arr) if arr == None or arrLen == 0: return False #The position used to record values whose left pass duration is greater than the number on the left isCurMax = [False for i in range(arrLen)] # First pointer: left traversal maximum leftMax = arr[0] for i in range(arrLen - 1): if arr[i] >= leftMax: leftMax = arr[i] # If it is greater than the previous maximum, it is considered to be greater than all the numbers on the left isCurrMax[i] = True res = [] # The second pointer records values smaller than those on the right rightMin = arr[arrLen - 1] for i in range(arrLen - 1, -1, -1): if arr[i] <= rightMin: rightMin = arr[i] # The value is smaller than its right side and larger than its left side if isCurrMax[i]: res.append(i) return sorted(res) if len(res) > 0 else False if __name__ == '__main__': a = [1, 0, 1, 0, 1, 2, 3] res = get_point_number(a) print(res)
6. Find the value that appears only once
Given a one-dimensional integer array, only one number appears once and other numbers appear twice. Please find the only number that appears once.
-
Example: given array A = [2, 35, 8, 16, 8, 2, 7, 16, 35], returns the only 7 that occurs only once
-
XOR operation properties:
-
Any number and 0 do XOR operation, and the result is still the original number, that is, a ⊕ \oplus ⊕ 0=a.
-
Any number does XOR with itself, and the result is 0, that is, a ⊕ \oplus ⊕ a=0.
-
XOR operation satisfies commutative law and associative law, that is, a ⊕ \oplus ⊕b ⊕ \oplus ⊕ a=b ⊕ \oplus ⊕ a ⊕ \oplus ⊕ a=b ⊕ \oplus ⊕ (a ⊕ \oplus ⊕ a)=b⊕0=b.
-
-
def onlyOneTimeNumber(arr): arrLen = len(arr) if arrLen < 2: return -1 res = 0 for i in range(arrLen): # XOR expression res ^= arr[i] return res # The function call format is as follows if __name__ == '__main__': array = [2, 35, 8, 16, 8, 2, 7, 16, 35] num = onlyOneTimeNumber(array) print("num=%d," % num)
# from functools import reduce # def singlenum(array): # return reduce(lambda x, y: x ^ y, array)
7. Find the maximum depth of a binary tree.
-
# Class is defined as follows class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None def maxDepth(root): if root is None: return 0 l = maxDepth(root.left) r = maxDepth(root.right) return max(l, r) + 1 # The function call format is as follows if __name__ == '__main__': root = TreeNode(5) root.left = TreeNode(3) root.right = TreeNode(4) root.right.right = TreeNode(0) res = maxDepth(root) print(res) -
Find the minimum depth of binary tree
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
min_depth = 10**9
if root.left:
min_depth = min(self.minDepth(root.left), min_depth)
if root.right:
min_depth = min(self.minDepth(root.right), min_depth)
return min_depth + 1
8. * * * longest palindrome substring
Longest palindrome substring. Given a string s, find the longest palindrome substring in s, assuming that the maximum length of S is 1000
-
Example: s = "helloollyyd", then the longest palindrome substring is "llooll", and the length is 6
-
thinking
-
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-eSgsvJad-1628333885058)(.\image \ longest palindrome substring. png)]
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-27WF6C57-1628333885062)(.\image \ longest palindrome substring dynamic programming matrix. png)]
-
-
def longestPalindrome(s): n = len(s) if n < 2: return s max_len = 1 begin = 0 # dp[i][j] indicates whether s[i..j] is a palindrome string dp = [[False] * n for _ in range(n)] for i in range(n): dp[i][i] = True # Recurrence start # Enumerate substring length first for L in range(2, n + 1): # Enumerate the left boundary. The upper limit setting of the left boundary can be relaxed for i in range(n): # The right boundary can be determined by L and I, i.e. j - i + 1 = L j = L + i - 1 # If the right boundary is out of bounds, you can exit the current loop if j >= n: break if s[i] != s[j]: dp[i][j] = False else: if j - i < 3: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] # As long as dp[i][L] == true, it means that the substring s[i..L] is a palindrome. At this time, the palindrome length and starting position are recorded if dp[i][j] and j - i + 1 > max_len: max_len = j - i + 1 begin = i return s[begin:begin + max_len] # The function call format is as follows if __name__ == '__main__': s = "helloollyyd" res = longestPalindrome(s) print("res=," res)
-
9. Keep the order and move 0 to the end
-
Given an array num, write a function to move all zeros to the end of the array while keeping the relative order of non-zero elements unchanged.
- Example: input array num = [0, 1, 0, 3, 12], output result: [1, 3, 12, 0, 0]
- Ideas and Solutions
Double pointers are used. The left pointer points to the tail of the currently processed sequence and the right pointer points to the head of the sequence to be processed.
The right pointer constantly moves to the right. Each time the right pointer points to a non-zero number, the numbers corresponding to the left and right pointers are exchanged, and the left pointer moves to the right at the same time.
Noting the following nature:
The left of the left pointer is a non-zero number;
Zero from the left of the right pointer to the left pointer.
Complexity: O(n)
class Solution: def moveZeroes(self, nums: List[int]) -> None: n = len(nums) left = right = 0 while right < n: if nums[right] != 0: nums[left], nums[right] = nums[right], nums[left] left += 1 right += 1-
def move_array(nums): for num in nums: if num == 0: nums.remove(num) nums.append(num) return nums if __name__ == '__main__': nums = [0, 1, 0, 3, 12] res = move_array(nums) print(res)
10. Leapfrog 2.0
Frog jump 2.0 is implemented on the basis of the previous operation, and an array of one-dimensional non negative elements is given. Each element represents the longest distance that the element position can jump. Assuming that the initial position is in the first element and that the input array can reach the end of the array, what is the minimum number of hops?
-
Example: input array A = [2, 1, 3, 1, 1], output 2
-
def main(): a = [2, 1, 3, 1, 1] res = frog_jump(a) print(res) def frog_jump(arr): result = 0 # Use two pointers to record the farthest destinations of the previous round and the current round respectively last = 0 curr = 0 for i in range(len(arr)): if i > last: # If the current pointer crosses the farthest destination of the previous round # Then update the last round pointer and implement a hop last = curr result += 1 # Save the farthest destination value of this round curr = max(curr, i + arr[i]) return result if __name__ == '__main__': main() # The function call format is as follows def main(): a = [2, 1, 3, 1, 1] res = frog_jump(a) print(res) if __name__ == '__main__': main()
11. Robot path
-
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 down or right one step at a time, and the robot attempts to reach the lower right corner of the grid (marked "Finish" in the figure below)
-
How many different paths are there altogether?
-
Example 1: input: m = 3, n = 2 output: 3 explain: Starting from the upper left corner, there are a total of 3 paths to the lower right corner. 1. towards the right -> towards the right -> down 2. towards the right -> down -> towards the right 3. down -> towards the right -> towards the right Example 2: input: m = 7, n = 3 output: 28 be careful: 1 <= m, n <= 100
-
# The function call format is as follows def main(): number = allPaths(m=3, n=2) print("number=%d," % number) if __name__ == '__main__': main()
# The function call format is as follows
def allPaths(m, n):
# dynamic programming
matrix = [[0 for i in range(n)] for i in range(m)]
"""
matrix[0][0] = 1
matrix[1][n] = 1
matrix[n][1] = 1
"""
matrix[0][0] = 1
for i in range(1, m):
for j in range(1, n):
if i == 1:
matrix[0][j] = 1
if j == 1:
matrix[i][0] = 1
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1]
return matrix[m - 1][n - 1]
def main():
number = allPaths(m=7, n=3)
print("number=%d," % number)
if __name__ == '__main__':
main()
12. Maximum subscript distance
Given an integer array, find the maximum subscript distance j - i if and only if a [i] < a [J] and I < J.
-
Example: if the input array is [5, 3, 4, 0, 1, 4, 1], then the maximum subscript distance is generated when A[i]=3, i=1 and A[j]=4, j=5. At this time, j - i = 4. This 4 is the maximum subscript distance satisfying the condition.
-
# The function call format is as follows def main(): array = [5, 3, 4, 0 ,1, 4, 1] dis = maxDistance(array) print("dis=%d," % dis) if __name__ == '__main__': main()
13. * * * climb stairs
Suppose you are climbing stairs, you need n steps to reach the roof You can climb one or two steps at a time How many different ways can you climb to the roof?
-
**Note: * * given n is a positive integer
-
Example 1: Input: 2 Output: 2 Explanation: there are two ways to climb to the roof. 1. 1 rank + 1 rank 2. 2 rank Example 2: Input: 3 Output: 3 Explanation: there are three ways to climb to the roof. 1. 1 rank + 1 rank + 1 rank 2. 1 rank + 2 rank 3. 2 rank + 1 rank
'''
Labels: dynamic programming
In fact, the conventional solution of this problem can be divided into several sub problems n The number of steps is equal to the sum of two parts
The penultimate step is to climb up n-1 Number of methods for stair steps. Because you can climb one more step to the third n rank
The penultimate step is to climb up n-2 There are many ways to climb stairs, because you can climb another 2 steps to the third floor n rank
So we get the formula arr[n] = arr[n-1] + arr[n-2]
Initialization is also required arr[1]=1 and arr[2]=2
Time complexity: O(n)
'''
def methods(n):
if n == 1:
return 'input %d Not in accordance with the meaning of the question' % n
arr = [0 for i in range(n + 1)]
i = 0
while i <= n:
if i == 0 or i == 1:
arr[i] = 1
i += 1
continue
arr[i] = arr[i - 1] + arr[i - 2]
i += 1
# print(arr)
return arr[n]
def main():
variable = methods(n=3)
print("dis=%d," % variable)
if __name__ == '__main__':
main()
14. * * * longest common subsequence
Given two strings S1 and S2, find the longest common subsequence of the two strings
-
Recursive Method
- The comparison is made from the end of the string because it is the longest
- If the end is the same, keep it
- Then start the comparison from the penultimate place
- If different, there are two cases
- Delete the last element of S1 and compare the penultimate bit with the last element of S2
- Delete the last element of S2 and compare the penultimate bit with the last element of S1
- Repeat the above steps
def LCS(s1, s2): # Judge whether the bit is empty if s1 == '' or s2 == '': return '' # Compare last element elif s1[-1] == s2[-1]: return LCS(s1[:-1],s2[:-1]) + s1[-1] else: # If not, there are two cases res_a = LCS(s1[:-1], s2) res_b = LCS(s1, s2[:-1]) if len(res_a) > len(res_b): return res_a return res_b if __name__ == "__main__": a = 'abcd' b = 'aebd' print(LCS(a, b)) -
dynamic programming
- L
15. Zigzag hierarchical traversal of binary tree (Z-shaped traversal algorithm)
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def zigzaglevelorder(self, root):
res = []
que = [root]
if root == None:
return res
while que:
tempList = []
for i in range(len(que)):
node = que.pop(0)
tempList.append(node.val)
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
res.append(tempList)
temp = []
for i in range(len(que)):
if i % 2 == 0:
temp.append(res[i])
else:
temp.append(res[i][::-1])
return (temp)
16. Judge the pop-up order of stack pressing
Enter two integer sequences. The first sequence represents the push in sequence of the station. Please judge whether the second sequence is the pop-up sequence of the stack. Assume that all the numbers pushed into the stack are not equal. For example, sequences 1, 2, 3, 4 and 5 are the push in sequence of a stack, and sequences 4, 5, 3, 2 and 1 are a pop-up sequence corresponding to the stack sequence, but 4, 3, 5, 1 and 2 cannot be the pop-up sequence of the push stack sequence (note: the lengths of these two sequences are equal)
- Stack features: first in first out - stack top element first out
- Idea:
- Borrow an auxiliary stack, traverse the stack pressing sequence, first put the first one into the stack, here is 1, and then judge whether the element at the top of the stack is the first element in the stack pressing sequence, here is 4. Obviously, 1 ≠ 4, so we continue to press the stack until it is equal and start to stack. If an element is out of the stack, move the out of the stack sequence backward one bit until it is not equal. In this way, the cyclic isobaric stack sequence traversal is completed. If the auxiliary stack is not empty, it indicates that the pop-up sequence is not the pop-up sequence of the stack.
def validateStackSequences(self, pushed, popped):
stack, i = [], 0
for num in pushed:
stack.append(num) # num stack
while stack and stack[-1] == popped[i]: # Loop judgment and out of stack
stack.pop()
i += 1
# If stack is empty, it returns True; if it is not empty, it returns false
return not stack
if __name__ == '__main__':
pushed = [1,2,3,4,5]
poped = [4,3,5,1,2]
res = validateStackSequences(pushed, poped)
print(res)
17. Convert string to tree structure
The input is a tree expressed in string form, which needs to be transformed into a real tree structure.
For example: a # b c # d e f <---"(a(b(de)c(f)))"
18. Find the K-th largest number in an out of order array
19. Reverse linked list
Define a function, input the head node of a linked list, invert the linked list and output the head node of the inverted linked list
class ListNode:
"""Linked list data structure"""
def __init__(self, x, next=None):
self.val = x
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# Define the tail node, which defaults to None
last = None
# When the incoming header node is not None, that is, no inversion is completed
while head:
# Continuous assignment is equivalent to: all variables on the right of the equal sign are temporarily stored as intermediate variables, and then assigned to the right, from left to right
# eg: l = last, h = head, hn = head.next, head.next = l, last = h, head = hn
# According to the definition of inverted linked list, the last node of the new linked list after inversion is the current head node, so for the new linked list head Next = none (default value of last)
# Last is always changing. After processing the tail of the new linked list, start from head, so last=head
# The last traversal process is changing the linked list. We use head to limit when it should end, so the head should also change step by step until head Next points to None
# Therefore, head changes to: head = head next
head.next, last, head = last, head, head.next
return last