第一题

给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。

解

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1])
        res = []
        for i in range(len(nums)):
            if nums[i]>0:
                res.append(i+1)
        return res

解题思路

• 题目要求不适应额外空间,所以这题不能使用dict来标记是否出现,所以只能通过对出现过的数字找到对应的索引,把这个索引位置的数字置为绝对值的负数,然后重新再遍历取出为负数的索引大小,就是没有出现的数字.

第二题

给定一个未经排序的整数数组，找到最长且连续的的递增序列

解`

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        cur = nums[0]
        count=1
        maxcount=0
        for pre in nums[1:]:
            if pre>cur:
                count+=1
            else:
                if count>maxcount:
                    maxcount=count
                count=1
            cur = pre
        return max(count,maxcount)

解题思路

• 每次遇到不符合的重新计数即可,只是注意最后需要再次比较count和maxcount的大小.

第三题

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

解

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

        if not nums:
            return None
  
        mid = len(nums)//2
        num1 = nums[0:mid]
        num2 = nums[mid+1:]
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(num1)
        root.right = self.sortedArrayToBST(num2)
        return root

解题思路

• 利用递归的思路为树的根节点和左右字节点赋值即可.