Invert the binary tree

Topic describes

Flip a binary tree.Copy the code

The sample

Example: Input: 4 / \ 27 / \ / \ 13 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1Copy the code

The problem solving

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        
        temp = root.left
        root.left =  root.right
        root.right = temp

        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
Copy the code

Typical binary tree inversion, using recursion.

The left and right nodes are swapped using a temporary node.

Once the swap is done, recurse to the left and right subtrees.

The largest product of two and three numbers

Topic describes

Given an integer array nums, find the largest product of three numbers in the array and print the product.Copy the code

The sample

Example 1: Input: nums = [1,2,3] Output: 6 Example 2: Input: nums = [1,2,3,4] Output: 24 Example 3: Input: nums = [-1,-2,-3] Output: -6Copy the code

The problem solving

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        max1 = nums[-1]* nums[-2]* nums[-3]
        max2 = nums[0]* nums[1]* nums[-1]
        return max(max1, max2)
Copy the code

If it’s an unordered array, it’s not that fast. You can sort the array from small to large. In this way, the largest product of three numbers takes into account these situations:

  • The array is full of positive numbers, so the maximum product of three numbers is the product of the last three digits.
  • The array is full of negative numbers, so the maximum product of three numbers is the last three digits multiplied.
  • If there is only one negative number, we still multiply the last three numbers. 2. When there are more than or equal to two negative numbers, the smallest two negative numbers are multiplied by the largest positive number.

So, it boils down to 2 cases, do both, and compare which one returns which one.

Delete duplicates from an ordered array

Topic describes

Give you an ordered array nums, ask you to delete the repeated elements in place, so that each element appears only once, return the deleted array after the new length. Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.Copy the code

The sample

Example 1: Input: nums = [1,1,2] Output: 2, nums = [1,2] Explanation: The function should return a new length of 2, and the first two elements of the original array nums are changed to 1,2. You don't need to worry about the element after the new length in the array. Example 2: Input: nums = [0,0,1,1, 2,2,3,3,4] Output: 5, nums = [0,1,2, 2,3,4] Explanation: The function should return a new length of 5, and the first five elements of the original nums array are modified to 0,1,2,3,4. You don't need to worry about the element after the new length in the array.Copy the code

The problem solving

class Solution: def removeDuplicates(self, nums: List[int]) -> int: fast = 1 slow = 1 for fast in range(1, len(nums)): if nums[fast] ! = nums[fast-1]: nums[slow] = nums[fast] slow += 1 fast += 1 return slowCopy the code

Delete in place. Use two Pointers, fast and slow, to start with elements with subscript 1.

  • Fast is the traversal pointer, traversal one element at a time, comparefastAnd the previous onefast-1Is it equal?
  • And if they’re not equal, we can takefastElement, andslowSwap, put it in front. thenslow+=1, pointing to the next element to insert

    The location of the.
  • If they are equal, statefastRepeat with the previous one,fast+=1, keep going to the right until the next different element, keep going toslowPosition.

Delete duplicate elements from sorted list

Topic describes

There is a linked list in ascending order. Given the head node of the linked list, remove all duplicate elements so that each element appears only once. Returns a linked list of results, also in ascending order.Copy the code

The sample

Example 1: Input: head = [1,2] Output: [1,2]Copy the code

Example 2: input: head = [1,1,2,3,3] output: [1,2,3]Copy the code

The problem solving

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head
        cur = head
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head
Copy the code

Here is an ascending linked list, so the repeated data is arranged consecutively. This way, you can do it once.

  • Cur points to head and starts traversing down. So let’s make a judgment hereif not headIn the case.
  • ifcurThe value of thecur.val, and the value of the next nodecur.next.valIf it is equal, it is repeated and should be deletedcur.next.

    But what we’re doing here is changing the pointer,cur.nextPoint to thecur.next.nextCan. The bypassed node does not have a reference and will

    It is automatically recycled.
  • If it is not equal to, it does not repeat,cur = cur.nextletcurThe pointer continues to move to the right.

Intermediate nodes of the linked list

Topic describes

Given a non-empty singly linked list with head, return the middle node of the list.

If there are two intermediate nodes, the second intermediate node is returned.

The sample

Example 1: Input: [1,2,3,4,5] Output: Node 3 in this list (serialized form: [3,4,5]) returns the value of node 3. (the serialization statement of this node in the evaluation system is [3,4,5]). Val = 3, ans.next-val = 4, ans.next-next-val = 5, and ans.next-next-next = NULL. Example 2: input: [1,2,3,4,5,6] output: node 4 in this list (serialized form: [4,5,6]) since the list has two intermediate nodes with values 3 and 4, we return the second node.Copy the code

The problem solving

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next
        
        m = 0
        cur = head
        while m < n // 2:
            m += 1
            cur = cur.next
        return cur
Copy the code

Double traversal.

  • The first time I go through it, I know the length of the listn.
  • The second time I go, I only go tonHalf of the while m < n // 2, returns a pointercur.