董个屁儿

题解

/ 注册

全部文章 / 题解（共39篇）

题解 | #数字在升序数组中出现的次数#

思路：强行使用二分查找方法 1、二分查找找最左k，二分查找找最右k 2、位置间距离既为答案 class Solution: def GetNumberOfK(self , data: List[int], k: int) -> int: if k not in data...

Python3 数组

2022-03-28

0 292

题解 | #数字序列中某一位的数字#

思路：各个区间的数值总个数为（top - bottom）* position_num 1、判断n是其所在区间的第几位：n - 前面区间的总位数，再除以当前区间每位的position_num 2、判断n的val是什么，bottom + n为其所在区间的位数 3、n % position_num为n指...

Python3 字符串

2022-03-28

0 273

题解 | #字符串的排列#

思路：顺序遍历字符串，取当前字符串与除去当前字符串的全排列中的元素组成新的组合作为结果注意：递归出口，当字符串为1时，返回当前字符串 class Solution: def Permutation(self , str: str) -> List[str]: ...

Python3 字符串

2022-03-28

0 245

题解 | #旋转数组的最小数字#

思路：折半查找，把right坐标值作为target，逐渐缩小最小数字的目标范围注意： 1、基于旋转数组特性，一定要以right，而不是left作为target 2、数组中出现重复数字时，要先将其移动过相同数值范围，且只移动一个指针，否则可能会跳过最小值 3、最终最小数字在left、right中出现...

Python3 数组双指针

2022-03-28

1 269

题解 | #二叉树搜索树的最近公共祖先#

思路：同样可以采取二叉树最近公共祖先的算法 1、深度优先遍历dfs，判断当前节点是否为o1、o2，先找到的必为祖先 2、递归左右子树左右子树中均分布o1、o2，则公共祖先为当前节点均在左，则返回左，均在右，则返回右注意：此题有一个小坑，由于存在值为0的val，所以不能用not r...

Python3 二叉树

2022-03-28

2 377

题解 | #二叉搜索树的最近公共祖先#

思路：基于二叉搜索树的特点，左边小于根节点，右边大于根节点 1、o1、o2分布在当前节点两边，则当前节点为公共祖先 2、当前节点为o1或o2，当前节点为祖先 3、o1、o2均在当前节点左边，递归查找左子树 4、o1、o2均在当前节点右边，递归查找右子树 class Solution: def...

Python3 二叉树

2022-03-28

0 250

题解 | #序列化二叉树#

思路： 1、序列化当前节点，序列化左、右子树，返回序列化表示 2、基于序列化表示，找出节点值、节点左子树、右子树的序列化表示形式 3、递归建立当前节点，左子树、右子树，然后拼接后返回当前节点 class Solution: def Serialize(self, root): ...

Python3 二叉树

2022-03-28

2 350

题解 | #对称的二叉树#

思路： 1、两棵树p1、p2, p1与p2，p1的左与p2的右，p1的右与p2的左相同，则对称 2、递归判断全部节点 class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: # write c...

Python3 二叉树

2022-03-28

0 233

题解 | #判断是不是平衡二叉树#

思路： 1、判断当前节点是否平衡：左右子树高度之差小于等于1 2、递归判断全部节点是否平衡 class Solution: def IsBalanced_Solution(self , pRoot: TreeNode) -> bool: return ...

Python3 二叉树

2022-03-28

0 310

题解 | #重建二叉树#

思路：先序遍历首位为根，然后基于根在中序遍历中拆分左、右子树，依次递归构建注意： 1、root：1 2、idx：vin[root.val] 3、len(left) = [:idx] 4、len(right) = [idx+1:] class Solution: def reConstruc...

Python3 二叉树

2022-03-28

0 327