Data structure and algorithm

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]
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)))"
```

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