第一题
给定一个范围在 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
解题思路
- 利用递归的思路为树的根节点和左右字节点赋值即可.