网站页面的滑动怎么做,办公室装修一般价格,做好中心网站建设工作,长沙建站费用leetcode-剑指offer-433.面试题33-二叉搜索树的后序遍历序列34.面试题34-二叉树中和为某一值的路径35.面试题35-复杂链表的复制36.面试题36-二叉搜索树与双向链表37.面试题37-序列化二叉树38.面试题38-字符串的排列39.面试题39-数组中出现次数超过一半的数字40.面试题40-最小的…
leetcode-剑指offer-433.面试题33-二叉搜索树的后序遍历序列34.面试题34-二叉树中和为某一值的路径35.面试题35-复杂链表的复制36.面试题36-二叉搜索树与双向链表37.面试题37-序列化二叉树38.面试题38-字符串的排列39.面试题39-数组中出现次数超过一半的数字40.面试题40-最小的k个数41.面试题41-数据流中的中位数42.面试题42-连续子数组的最大和本系列博文为题库刷题笔记仅在督促自己刷题如有不详之处请参考leetcode官网https://leetcode-cn.com/problemset/lcof/33.面试题33-二叉搜索树的后序遍历序列
输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考思路1如果所有的子树都是二叉搜索树那么此序列为二叉搜索树的后序遍历序列。 step1:确定左右子树区间对左右子树区间再递归调用判断函数递归函数的出口是没有可以判断的节点区间为空 key:确定左右子树区间的方法二叉搜索树左子树节点都小于根节点右子树节点都大于根节点。
class Solution(object):def verifyPostorder(self, postorder)::type postorder: List[int]:rtype: booldef rec(i,j):if ij: # 右边界出口 ij ,左边界出口i jreturn Truemi # i 0, j n-1while(postorder[m]postorder[j]): # i,m-1 左子树m,j-1右子树 递归判断m1pmwhile(postorder[p]postorder[j]):p1return pj and rec(i,m-1) and rec(m,j-1)return rec(0,len(postorder)-1)34.面试题34-二叉树中和为某一值的路径
输入一棵二叉树和一个整数打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
由顶向下的递归查找最后的叶子节点对应的匹配数是否为叶子值。如果对应的值匹配上可以往结果添加一条新的路径。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def pathSum(self, root, sum)::type root: TreeNode:type sum: int:rtype: List[List[int]]def top_down(node,target):if nodeNone:returnpath.append(node.val)if node.leftNone and node.rightNone:if node.valtarget:res.append(list(path)) # 直接res.append(path)加上的是[]top_down(node.left,target-node.val)top_down(node.right,target-node.val)path.pop()res,path[],[]top_down(root,sum)return res路径总和的扩展路径总和要判断是否存一条路径只要存在就行不需要具体路径这个需要列举所有的路径。
35.面试题35-复杂链表的复制
请实现 copyRandomList 函数复制一个复杂链表。在复杂链表中每个节点除了有一个 next 指针指向下一个节点还有一个 random 指针指向链表中的任意节点或者 null。 思路依据原链表新建一个新链表很简单难点随机指针的指向。需要记录一张新链表节点和原链表节点的hash表。重新遍历一遍原链表之找到新链表中对应的链接节点。 # Definition for a Node.
class Node:def __init__(self, x, nextNone, randomNone):self.val int(x)self.next nextself.random randomclass Solution(object):def copyRandomList(self, head)::type head: Node:rtype: Nodeif headNone:return headhas_map{}res_headNode(0)res_currres_headori_currheadwhile(ori_curr):res_curr.nextNode(ori_curr.val,None,None)has_map[ori_curr]res_curr.nextres_currres_curr.nextori_currori_curr.nextori_currheadres_currres_head.nextwhile(ori_curr):if ori_curr.random:res_curr.randomhas_map[ori_curr.random]ori_currori_curr.nextres_currres_curr.nextreturn res_head.next36.面试题36-二叉搜索树与双向链表
输入一棵二叉搜索树将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点只能调整树中节点指针的指向。 特别地我们希望可以就地完成转换操作。当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。 参考题解 step1.二叉搜索树中序遍历为递增序列采用中序遍历遍历二叉搜索树。 step2.构建相邻节点前驱节点pre_node 当前节点curr_node,为了构成双向链表要使得pre_node.rightcurr_node, curr_node.leftpre_node 重新定向节点左右所指向的节点完成4到3的链接 step3.链表头节点和尾部节点head.lefttail,tail.righthead # Definition for a Node.
class Node(object):def __init__(self, val, leftNone, rightNone):self.val valself.left leftself.right rightclass Solution(object):def __init__(self):self.pre_nodeNoneself.headNonedef treeToDoublyList(self, root)::type root: Node:rtype: Nodedef dfs(cur_node):if cur_nodeNone:returndfs(cur_node.left)if self.pre_node:self.pre_node.rightcur_nodecur_node.leftself.pre_nodeelse:self.headcur_nodeself.pre_nodecur_nodedfs(cur_node.right)if rootNone:return rootdfs(root)self.head.leftself.pre_nodeself.pre_node.rightself.headreturn self.head37.面试题37-序列化二叉树
请实现两个函数分别用来序列化和反序列化二叉树。 本题与主站 297 题相同https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/ 注意点序列化和反序列化的遍历方式是一样的。
class Codec:def serialize(self, root):Encodes a tree to a single string.:type root: TreeNode:rtype: strglobal stringdef dfs_pre_ser(node):global stringif nodeNone:stringNone,returnstring{0},.format(node.val)dfs_pre_ser(node.left)dfs_pre_ser(node.right)stringdfs_pre_ser(root)return stringdef deserialize(self, data):Decodes your encoded data to tree.:type data: str:rtype: TreeNodedef dfs_pre_deser(lis):if lis[0]None: # 最右边叶子节点的右儿子也是none操作完lis.pop(0)return NonenodeTreeNode(int(lis[0]))lis.pop(0)node.leftdfs_pre_deser(lis)node.rightdfs_pre_deser(lis)return nodedata_lisdata.split(,)return dfs_pre_deser(data_lis)38.面试题38-字符串的排列
输入一个字符串打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组但里面不能有重复元素。 思路回溯问题注意维护当选择路径遍历选择列表撤销路径, 本质是一个递归问题再稍加注意递归出口 注意字符串中可能包含相同字符所以要维护一个已有路径列表直接用结果列表所搜很慢维护一个hash 表时间快了40倍只有当路径不存在时才加入最后的答案中。
class Solution(object):def permutation(self, s)::type s: str:rtype: List[str]def rec(lis,path):if lis[]:if not path_hash.get(path):res.append(path)path_hash[path]Truereturnfor i in range(len(lis)):# 一句话完成了选择做选择pathlis[i]选择列表更新lis[:i]lis[i1:]语句结束时候path 还是原来的path即实现撤销选择rec(lis[:i]lis[i1:],pathlis[i]) res[]s_lis[]path_hash{}for char in s:s_lis.append(char)rec(s_lis,)return res39.面试题39-数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。 你可以假设数组是非空的并且给定的数组总是存在多数元素。 暴力统计每个数字都统计一次时间复杂度o(n^2) 维护一hash 表,对应键值对为数值出现次数最后统计出现次数最大的即可。题目说存在这样一个数字
class Solution(object):def majorityElement(self, nums)::type nums: List[int]:rtype: intcount_has{}for val in nums:if not count_has.get(val):count_has[val]1else:count_has[val]1return max(count_has.keys(),keycount_has.get)# count_has.keys()获取所有的值# ‘key’为max 函数的参数40.面试题40-最小的k个数
思路1:最小排序排k次,时间复杂度o(nk) 35/38,时间超出限制
class Solution(object):def getLeastNumbers(self, arr, k)::type arr: List[int]:type k: int:rtype: List[int]nlen(arr)for i in range(k):for j in range(i1,n):if arr[i]arr[j]:arr[i],arr[j]arr[j],arr[i]return arr[:k]思路2:快排序时间复杂度o(nlogn)
class Solution(object):def getLeastNumbers(self, arr, k)::type arr: List[int]:type k: int:rtype: List[int]# arr.sort()# 自己写一遍快排序def quick_sort(i,j,nums,flag):if ij:ppartition(i,j,nums)quick_sort(i,p-1,nums,flag1)quick_sort(p1,j,nums,flag1)def partition(l,r,nums): # 分区pivortnums[l]while(lr):while(lr and nums[r]pivort):r-1# 跳出循环的情况是lr or nums[r]pivort, 将nums[r] 放到l 指示的位置nums[l]nums[r] # 每个数在写进去之前已经被拿走了。while(lr and nums[l]pivort):l1# 跳出循环的情况是lr or nums[l]pivort, 将nums[l] 放到r 指示的位置nums[r]nums[l]nums[l]pivortreturn lquick_sort(0,len(arr)-1,arr,1)return arr[:k]41.面试题41-数据流中的中位数
如何得到一个数据流中的中位数如果从数据流中读出奇数个数值那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值那么中位数就是所有数值排序之后中间两个数的平均值。 例如 [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 3) / 2 2.5 设计一个支持以下两种操作的数据结构 void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。
要找中位数就要维护一个有序结构当数字插入时维护至有序位置。在查询中位数时直接返回 难点维护有序位置–两个顶堆顶堆用list存完全二叉树树根节点值最大或最小 Python 中 heapq 模块是小顶堆。实现 大顶堆 方法 小顶堆的插入和弹出操作均将元素 取反 即可。
from heapq import *
class MedianFinder(object):def __init__(self):initialize your data structure here.self.A[]self.B[]def addNum(self, num)::type num: int:rtype: Noneif len(self.A)!len(self.B):heappush(self.A,num)heappush(self.B,-heappop(self.A))else:heappush(self.B,-num)heappush(self.A,-heappop(self.B))def findMedian(self)::rtype: floatif len(self.A)!len(self.B):return self.A[0]else:return (self.A[0]-self.B[0])/2.042.面试题42-连续子数组的最大和
输入一个整型数组数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。 核心要点负数前缀不能要
class Solution(object):def maxSubArray(self, nums)::type nums: List[int]:rtype: intmid_sum0max_sumfloat(-INF)for val in nums:mid_sumvalmax_summax(mid_sum,max_sum) # mid_sum写在归零的上方防止最大和为负数的情况if mid_sum0:mid_sum0return max_sum
