一、翻转二叉树
题目描述
翻转一棵二叉树。
示例
示例： 输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / \ 7 2 / \ / \ 9 6 3 1
解题
# 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
典型二叉树反转，使用递归。
利用一个临时结点，使左右结点进行交换。
交换动作完成后，开始递归，左右两边的子树。
二、三个数的最大乘积
题目描述
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例
示例 1： 输入：nums = [1,2,3] 输出：6 示例 2： 输入：nums = [1,2,3,4] 输出：24 示例 3： 输入：nums = [-1,-2,-3] 输出：-6
解题
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)
如果是一个无序的数组，处理起来没那么快。可以先将数组排序，从小到大。这样一来，3个数的最大乘积
要考虑这几种情况：
- 数组里都是正数，那么3个数最大乘积就是后3位相乘。
- 数组里都是负数，那么3个数最大乘积就是后3位相乘。
- 数组里有正有负，那么3个数最大乘积可能：1.只有1个负数时，仍然为最后3个相乘。2. 大于等于2个负数时，就是最小的2个负数与最大的正数相乘。
所以，总结下来就是2种情况，把两种都计算一遍，然后比较哪个大返回谁。
三、删除有序数组中的重复项
题目描述
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例
示例 1： 输入：nums = [1,1,2] 输出：2, nums = [1,2] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。 不需要考虑数组中超出新长度后面的元素。 示例 2： 输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。 不需要考虑数组中超出新长度后面的元素。
解题
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 slow
题目重点是要原地删除，用双指针解决，分别是fast和slow，初始都指在下标为1的元素。
- fast为遍历的指针，每遍历一个元素，比较
fast与前一个 即fast-1是否相等。 - 如果不相等，就可以把
fast所在的元素，与slow交换，放到前面去。然后slow+=1，指向下一个元素插入
的位置。 - 如果相等，说明
fast与前一个重复，fast+=1，继续往右遍历，直到下一个不一样的元素，继续放到slow位置。
四、删除排序链表中的重复元素
题目描述
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。 返回同样按升序排列的结果链表。
示例
示例 1： 输入：head = [1,1,2] 输出：[1,2]
示例 2： 输入：head = [1,1,2,3,3] 输出：[1,2,3]
解题
# 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
这里是一个升序链表，所以重复的数据是连续排列的。这样，可以一次遍历解决。
- cur指针指向head结点，开始往下遍历。这里先判断下
if not head的情况。 - 如果
cur的值cur.val，与下一个结点的值cur.next.val相等，说明重复，要删除cur.next。
不过这里的删除操作是改变指针指向，cur.next指向cur.next.next即可。被绕开的结点没有引用，会
被自动回收。 - 如果不等于，说明不重复，
cur = cur.next让cur指针继续往右移动。
五、链表的中间结点
题目描述
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例
示例 1： 输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2： 输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
解题
# 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
两次遍历。
- 第一次遍历，知道了链表的长度
n。 - 第二次遍历，只遍历到
n的一半while m < n // 2，返回指针cur
