leetcode -- 9+102+104+105
2022/9/17 6:16:26
本文主要是介绍leetcode -- 9+102+104+105,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- 回文数
easy
# 两种写法 # 时间复杂度低 且考虑特殊情况 class Solution: def isPalindrome(self, x: int) -> bool: # first solution follow the answer if x < 0 or ( x % 10 == 0 and x != 0 ): return False revertedNumber = 0 while x > revertedNumber: revertedNumber = revertedNumber * 10 + x % 10 x //= 10 return x == revertedNumber or x == revertedNumber // 10 # 直接暴力结束 且不用考虑情况 def isPalindrome(self, x: int) -> bool: return str(x) == str(x)[::-1]
- 二叉树层序遍历
medium
# 1 钻入死胡同 class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if root == None: return [] rst, stack = [] , [] stack.append(root) stack_1 = [] while stack: ele = [] while stack: cur = stack.pop() if isinstance(cur, TreeNode): stack_1.extend([cur.right, cur.left]) else: stack.pop() continue ele.append(cur.val) if ele: rst.append(ele) ele = [] while stack_1: cur = stack_1.pop() if isinstance(cur, TreeNode): stack.extend([cur.right, cur.left]) else: stack_1.pop() continue ele.append(cur.val) if ele: rst.append(ele) return rst # 2 清醒 # 欣赏一个老哥子的代码 时空复杂度均为O(n) class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: ans = [] # 创建 stack 完成 root 加载 if root == None 则加载 [] stack = [root] if root else [] while stack: # 循环内部创建tmp栈 tmp_stack = [] # 使用推导式直接append所有val节省打字实践 ans.append([i.val for i in stack]) # 顺序读 伪栈 直接 append (node.left) (node.right) for node in stack: if node.left: tmp_stack.append(node.left) if node.right: tmp_stack.append(node.right) # 每次完成 首先更新ans 然后更新外部栈 stack = tmp_stack return ans
- 二叉树的最大深度
easy
# 这不就层序遍历... # 在层序遍历的代码中加入maxSize 这样可以直接返回最大深度 # 使用 bfs class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: maxSize = 0 stack = [root] if root else [] while stack: tmp_stack = [] for node in stack: if node.left: tmp_stack.append(node.left) if node.right: tmp_stack.append(node.right) stack = tmp_stack maxSize += 1 return maxSize # 非常 easy # 使用 dfs class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if root is None: return 0 else: return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1 # 虽然很快 但是递归需要使用栈空间 # 时间复杂度为O(n) 空间复杂度为O(height)依据树的高度而定
- 从前序列与中序遍历序列中构造二叉树
medium
# 思路: preorder开头卡一刀 拿root # inroder中间卡一刀 拿两边的inorder 用两边的inorder来分割preorder的后面部分 # preorder再卡一刀 拆成两个sub-inorder 的 sub-preorder 做成递归形态 返回 # 官方题解讲的太清楚 导致我一点都不想看 class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: # judge if preorder == [] and inorder == []: return root = TreeNode(preorder[0]) i = inorder.index(preorder[0]) root.left = self.buildTree(preorder[1:i+1],inorder[:i]) root.right = self.buildTree(preorder[i+1:],inorder[i+1:]) return root # 递归栈导致内存消耗过大 # 明天使用stack遍历序列重写
这篇关于leetcode -- 9+102+104+105的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享
- 2024-11-22ansible 的archive 参数是什么意思?-icode9专业技术文章分享
- 2024-11-22ansible 中怎么只用archive 排除某个目录?-icode9专业技术文章分享
- 2024-11-22exclude_path参数是什么作用?-icode9专业技术文章分享
- 2024-11-22微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口?-icode9专业技术文章分享
- 2024-11-22uniapp 实现聊天消息会话的列表功能怎么实现?-icode9专业技术文章分享
- 2024-11-22在Mac系统上将图片中的文字提取出来有哪些方法?-icode9专业技术文章分享
- 2024-11-22excel 表格中怎么固定一行显示不滚动?-icode9专业技术文章分享
- 2024-11-22怎么将 -rwxr-xr-x 修改为 drwxr-xr-x?-icode9专业技术文章分享
- 2024-11-22在Excel中怎么将小数向上取整到最接近的整数?-icode9专业技术文章分享