机械技术支持中山网站建设,seo是什么意思中文,怎么开发一款app软件,资产管理系统源码leetcode-剑指offer-545.面试题55- 二叉树的深度46.面试题55-2-平衡二叉树47.面试题57-1-和为s的两个数字-双指针48.面试题57-2-和为s 的连续正数序列-双指针49.面试题56-数组中出现数字的次数-位运算leetcode-136 只出现一次的数字Ileetcode-137 只出现一次的数字IIleetcode-2…
leetcode-剑指offer-545.面试题55- 二叉树的深度46.面试题55-2-平衡二叉树47.面试题57-1-和为s的两个数字-双指针48.面试题57-2-和为s 的连续正数序列-双指针49.面试题56-数组中出现数字的次数-位运算leetcode-136 只出现一次的数字Ileetcode-137 只出现一次的数字IIleetcode-260 只出现一次的数字III50.面试题51-数组中的逆序对-归并排序51.面试题54-二叉搜索树的第k大节点-中序遍历52.面试题58-翻转单词的顺序-库函数53.面试题58-左旋转字符串54.面试题59-滑动窗口的最大值-左右dp55.面试题60-n个骰子的点数-dp56.面试题61-扑克牌中的顺子57.面试题62-圆圈中最后剩下的数字--约瑟夫环问题58.面试题63-股票的最大利润-最大谷峰值本系列博文为题库刷题笔记仅在督促自己刷题如有不详之处请参考leetcode官网https://leetcode-cn.com/problemset/lcof/45.面试题55- 二叉树的深度
输入一棵二叉树的根节点求该树的深度。从根节点到叶节点依次经过的节点含根、叶节点形成树的一条路径最长路径的长度为树的深度。 自顶向下递归父亲节点给叶子节点提供信息,不断往下递归到达每一个叶子节点之后更新目前的最大深度。递归出口还是if nodeNone return 框架是不变的。从上往下灵魂底层出口。
class Solution(object):def __init__(self):self.deep0def maxDepth(self, root)::type root: TreeNode:rtype: intdef top_down(node,l):if nodeNone:returnif node.leftNone and node.rightNone: # 灵魂self.deepmax(self.deep,l)top_down(node.left,l1)top_down(node.right,l1)top_down(root,1)return self.deep自底向上对于某一个节点只要左右子树的深度知道了(l,r)该节点的深度为max(l,r)1 不断从下往上最终输出根节点的深度。从下往上的灵魂最底层信息如何传递给上层本质是后序遍历。
class Solution(object):def maxDepth(self, root)::type root: TreeNode:rtype: intdef bottom_up(node):if nodeNone:return 0 l_deepbottom_up(node.left)r_deepbottom_up(node.right)return max(l_deep,r_deep)1return bottom_up(root)46.面试题55-2-平衡二叉树
输入一棵二叉树的根节点判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1那么它就是一棵平衡二叉树。 思路要确认每个节点的左右子树的深度然后比较两个的大小相差不超过1。自底向上的可解释性高。 1.当节点root 左 / 右子树的深度差 ≤1 则返回当前子树的深度即节点 2.root 的左 / 右子树的深度最大值 1 max(left, right) 1 当节点root 左 / 右子树的深度差 2 则返回 −1 代表 此子树不是平衡树 。
class Solution(object):def isBalanced(self, root)::type root: TreeNode:rtype: booldef bottom_up(node):if nodeNone:return 0l_deepbottom_up(node.left)if l_deep-1:return -1r_deepbottom_up(node.right)if r_deep-1:return -1if abs(l_deep-r_deep)1: # 返回值的类型应该要一致 如何将这两个统一在一起return -1else:return max(l_deep,r_deep)1return bottom_up(root)!-1自顶向下检查每个节点的是否满足平衡二叉树的要求在递归遍历左右子树的情况。设置单独的函数求解二叉树节点的深度。–效率低运行时间是自底向上的70倍
class Solution(object):def isBalanced(self, root)::type root: TreeNode:rtype: boolif rootNone:return True # 空节点默认为是符合平衡二叉树的要求的flag1abs(self.tree_deep_bu(root.left)-self.tree_deep_bu(root.right))flag2self.isBalanced(root.left)flag3self.isBalanced(root.right)return flag12 and flag2 and flag3def tree_deep_bu(self,node):if nodeNone:return 0return max(self.tree_deep_bu(node.left),self.tree_deep_bu(node.right))147.面试题57-1-和为s的两个数字-双指针
输入一个递增排序的数组和一个数字s在数组中查找两个数使得它们的和正好是s。如果有多对数字的和等于s则输出任意一对即可。 双指针技巧两个指针分别指向数组的头和尾如果两数之和大于目标值则移动右指针两数之和小于目标值则移动左指针。直至找到目标值。 正确性所有和为上三角移动i-i1,会消除不符合要求的一行数字移动j-j-1会消除不满足要求的一列数字。直至搜索到正确答案。
class Solution(object):def twoSum(self, nums, target)::type nums: List[int]:type target: int:rtype: List[int]l,r0,len(nums)-1while(lr):if nums[l]nums[r]target:return (nums[l],nums[r])elif nums[l]nums[r]target:l1else:r-1return (-1,-1)48.面试题57-2-和为s 的连续正数序列-双指针
输入一个正整数 target 输出所有和为 target 的连续正整数序列至少含有两个数。 序列内的数字由小到大排列不同序列按照首个数字从小到大排列。 例如 输入target 9 输出[[2,3,4],[4,5]] 连续序列双指针技巧快慢指针分别指向序列的两个端点利用求和公式求此时的和:如果和小于目标值移动右指针如果和大于目标值更新起始左指针和等于目标值更新左指针。退出条件为lr。
循环结束条件lr,当l r 说明r 后面没有两个数字的和可以比target小。
class Solution(object):def findContinuousSequence(self, target)::type target: int:rtype: List[List[int]]res[]l,r1,2while(lr):sum_val(lr)*(r-l1)/2#print(l,r,sum_val,target)if sum_valtarget:res.append([])for j in range(l,r1):res[-1].append(j)l1elif sum_valtarget:r1else:l1return res49.面试题56-数组中出现数字的次数-位运算
位运算系列题目leetcode 260,136,137,645 异或操作解题思路 异或操作 数字a与数字b的异或操作为两个数字的二进制上每一位进行对位异或操作如果同一位置上两个数字相同异或结果为0否则为1. 异或规律 1.任何数字和本身异或为0 2.任何数字和0异或为本身 3.异或满足交换律 异或草用于检测出现135次的数字。
leetcode-136 只出现一次的数字I
给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素
解题思路异或操作的三条性质保证使用对所有数字进行异或操作可以找到不同的那个数字因为异或满足交换律所以可以看成将所有的相同数字进行异或得到0再与不同数字进行异或操作得到不同的那个数字。
class Solution(object):def singleNumber(self, nums)::type nums: List[int]:rtype: intsingle_num0for val in nums:single_num^valreturn single_numleetcode-137 只出现一次的数字II
给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现了三次。找出那个只出现了一次的元素。 解题思路1: 位运算 为了区分出现一次的数字和出现三次的数字使用两个位掩码seen_once 和 seen_twice。两个掩码的变换规则为不是很懂 仅seen_twice 为0时改变seen_once 仅seen_once 为0时改变seen_twice
class Solution(object):def singleNumber(self, nums)::type nums: List[int]:rtype: intseen_once,seen_twice0,0for num in nums:seen_once~seen_twice(seen_once^num)seen_twice~seen_once(seen_twice^num)return seen_once解题思路2:数学计算 [a,b,b,b]-set 操作[a,b]- 求和ab- 乘三3(ab)- 减原数组的和3(ab)-(a3b)- 除以2即可得到a
class Solution(object):def singleNumber(self, nums)::type nums: List[int]:rtype: List[int]tempset(nums)return (sum(temp)*3-sum(nums))//2leetcode-260 只出现一次的数字III
一个整型数组 nums 里除两个数字ab表示之外其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)空间复杂度是O(1)。 思路时间复杂度是o(n), 要求一次遍历。空间复杂度是o(1) 只能有常数个空间限制。
分组异或将只出现了一次的两个数字分到两组每组中其他元素为成对出现的相同数字。
核心是如何分组全部数字异或的结果将是ab两个数字异或的结果。异或结果中某一位为1主要是由于ab在该位置二进制表示不同导致的。所以可以依据该位置将数字分为两组其分组满足上面的要求因为相同的数字在该位肯定要么同时为0要么同时为1.
异或结果如何取到为1的那一位呢不为零的最低位
class Solution(object):def singleNumber(self, nums)::type nums: List[int]:rtype: List[int]bitmask0for num in nums:bitmaskbitmask^num # 保存两个出现一次数字xy的异或结果diffbitmask(-bitmask) # 异或结果中最每个位置上的1要么来自x 要么来自y取最右边的1.x0for num in nums:if num diff: # 将最右边有1的所有数字拿出来再做一次异或就能找到xxx^numreturn (x,x^bitmask)50.面试题51-数组中的逆序对-归并排序
在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组求出这个数组中的逆序对的总数。 思路归并排序解逆序数。在归并的过程中计算逆序对的数量。 归并是分治思想的典型应用不断二分到单个元素然后两两合并。在求逆序数的情况下就是两个两个求逆序数然后四个四个求逆序数把所有的逆序数相加即可。 核心在两个需要合并merge的序列中逆序数如何求如下 在左指针lPtr 发生右移动的时候当前 lPtr 指向的数字比 rPtr 小但是比 R 中 [0 … rPtr - 1] 的其他数字大[0 … rPtr - 1] 的其他数字本应当排在 lPtr 对应数字的左边但是它排在了右边所以这里就贡献了 rPtr 个逆序对。
class Solution(object):def reversePairs(self, nums)::type nums: List[int]:rtype: intdef merge_sort(nums,l,r):if lr:mid(lr)//2countmerge_sort(nums,l,mid)merge_sort(nums,mid1,r)#print(a,count)i,j,tmpl,mid1,[]while(imid and jr):if nums[j]nums[i]:tmp.append(nums[j])countmid-i1j1else:tmp.append(nums[i])i1while(imid):tmp.append(nums[i])i1while(jr):tmp.append(nums[j])j1nums[l:r1]tmp#print(nums,count)return countelse:return 0resmerge_sort(nums,0,len(nums)-1)return resclass Solution(object):def reversePairs(self, nums)::type nums: List[int]:rtype: intdef cout_rev(l,r):if l r:mid (l r) // 2count cout_rev(l,mid) cout_rev(mid1, r)i, j, tmp l, mid1, []while(imid or j r):if i mid or (j r and nums[i] nums[j]):tmp.append(nums[j])j 1else:count j - (mid 1)tmp.append(nums[i])i 1 nums[l:r1] tmp[:]return countelse:return 0res cout_rev(0, len(nums)-1)return res51.面试题54-二叉搜索树的第k大节点-中序遍历
给定一棵二叉搜索树请找出其中第k大的节点。 思路二搜索树的中序遍历序列为升序中序遍历res返回res[-k] 即可。
class Solution(object):def kthLargest(self, root, k)::type root: TreeNode:type k: int:rtype: intdef in_order_dfs(node):if nodeNone:return in_order_dfs(node.left)res.append(node.val)in_order_dfs(node.right)res[]in_order_dfs(root)return res[-k]52.面试题58-翻转单词的顺序-库函数
调用内置函数
class Solution(object):def reverseWords(self, s)::type s: str:rtype: strs_liss.split() # 将字符串按空格划分成列表多个空格看作一个s_lis.reverse() # 将列表逆序res .join(s_lis) # 将链表中字符串按空格链接return res53.面试题58-左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如输入字符串abcdefg和数字2该函数将返回左旋转两位得到的结果cdefgab。 左移没有顺序变换问题。 思路1每次左移动一位 移动k次
class Solution(object):def reverseLeftWords(self, s, n)::type s: str:type n: int:rtype: strllen(s)nn%lfor i in range(n):ss[1:]s[0]return s思路2:拼接s[n:]与s[:n]
class Solution(object):def reverseLeftWords(self, s, n)::type s: str:type n: int:rtype: strllen(s)nn%ls_rs[n:]s_ls[:n]return s_rs_l54.面试题59-滑动窗口的最大值-左右dp
给定一个数组 nums 和滑动窗口的大小 k请找出所有滑动窗口里的最大值。 leetcode 239动态规划法-那题标为困难这里标为简单神奇。 左右两个dp 数组比较得到答案。 nlen(nums)if n*k0:return []if k1:return numsleft[nums[0]]*nright[nums[-1]]*nfor i in range(1,n): # i:[0,n-1]if i%k0:left[i]nums[i]else:left[i]max(left[i-1],nums[i])indn-i-1if ind%k0:right[ind]nums[ind]else:right[ind]max(right[ind1],nums[ind])res[]for i in range(n-k1):res.append(max(left[ik-1],right[i]))return res55.面试题60-n个骰子的点数-dp
把n个骰子扔在地上所有骰子朝上一面的点数之和为s。输入n打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
class Solution(object):def twoSum(self, n)::type n: int:rtype: List[float]dp[[0]*(6*111) for _ in range(n)]for j in range(1,7):dp[0][j]1 # 一个骰子价值为j 的个数for i in range(1,n): # i1个骰子for j in range(i1,6*(i1)1): # i1个骰子点数和的范围 [i1,6(i1)]for k in range(max(j-6,1),j): # dp[i][j]sum_{i1}^{j-1}dp[i-1][j-i]#print(i,j,k)dp[i][j]dp[i-1][k]res[]#print(dp)for j in range(6*111):if dp[n-1][j]!0:res.append(dp[n-1][j]/ float(6**n))return res
56.面试题61-扑克牌中的顺子
从扑克牌中随机抽5张牌判断是不是一个顺子即这5张牌是不是连续的。210为数字本身A为1J为11Q为12K为13而大、小王为 0 可以看成任意数字。A 不能视为 14。 输入数组长度为 5 数组的数取值为 [0, 13] 。 思路判断所给的5个数字是否能构成一个顺子 身为大小王的0可以为任何数字,将数组排序后检查缺失数字的个数如果缺失数字的个数少于0的个数则可以构成顺子。
class Solution(object):def isStraight(self, nums)::type nums: List[int]:rtype: boolnums.sort()num_00i,index_z0,0while(i5):if nums[index_z]0:num_01index_z1i1gap0for i in range(index_z,4):if nums[i1]-nums[i]1:continueelif nums[i1]-nums[i]0:return Falseelse:gapnums[i1]-nums[i]-1print(num_0,gap,nums)if gapnum_0: # gap 可以比0的个数少0可以无中生有return True # [0,0,0,9,11]-[9,10,11,..]else:return Falseclass Solution(object):def isStraight(self, nums)::type nums: List[int]:rtype: boolnums.sort()res [nums[-1]] * 5l, r, res_Index 0, 3, 3# l 指向nums左边待处理元素# l 指向nums右边待处理元素# res_index 当前这个元素应该为多少while(l r):if nums[r] 1 res[res_Index1]:res[res_Index] nums[r]r -1res_Index-1else:if nums[l] 0:res[res_Index] res[res_Index1] -1l 1 res_Index - 1else:return Falsereturn True
57.面试题62-圆圈中最后剩下的数字–约瑟夫环问题
0,1,n-1这n个数字排成一个圆圈从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如0、1、2、3、4这5个数字组成一个圆圈从数字0开始每次删除第3个数字则删除的前4个数字依次是2、0、4、1因此最后剩下的数字是3。 参考博文递归https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/ 核心是如何从n-1恢复到n的编号f (fm)%n
class Solution(object):def lastRemaining(self, n, m)::type n: int:type m: int:rtype: intpre_pos0for i in range(1,n1):pos(pre_posm)%i # 加m 是在右移动pre_posposreturn pos58.面试题63-股票的最大利润-最大谷峰值
给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易即买入和卖出一支股票一次设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。
解题思路一次买卖找最大的峰谷值
class Solution(object):def maxProfit(self, prices)::type prices: List[int]:rtype: intif len(prices)0:return 0min_priceprices[0]max_pro0for val in prices[1:]:max_promax(max_pro,val-min_price)min_pricemin(min_price,val)return max_pro
