1. 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
输出：2
进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
出处：
https://edu.csdn.net/practice/26466465
代码：
from typing import List class Solution: def majorityElement(self, nums: List[int]) -> int: count, candi = 0, 0 for i in nums: if i == candi: count += 1 else: if count == 0: candi = i count = 1 else: count -= 1 return candi if __name__ == '__main__': s = Solution() nums = [3,2,3] print(s.majorityElement(nums)) nums = [2,2,1,1,1,2,2] print(s.majorityElement(nums))
输出：
3
2
2. 二叉树的层序遍历 II
给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层序遍历为：
[
[15,7],
[9,20],
[3]
]
出处：
https://edu.csdn.net/practice/26466466
代码：
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): res = dict() def forwardSearch(self, root, depth): if root != None: if depth not in self.res.keys(): self.res[depth] = [] self.res[depth].append(root.val) self.forwardSearch(root.left, depth + 1) self.forwardSearch(root.right, depth + 1) def levelOrderBottom(self, root): self.forwardSearch(root, 1) result = [] self.dic = dict() for i in self.res.keys(): result.append(self.res[i]) return result[::-1] def listToTree(lst): if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root if __name__ == '__main__': s = Solution() null = None nums = [3,9,20,null,null,15,7] root = listToTree(nums) print(s.levelOrderBottom(root))
输出：
[[15, 7], [9, 20], [3]]
3. 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4
出处：
https://edu.csdn.net/practice/26466467
代码：
from typing import List class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: nums.sort() cur = 0 closest = nums[0] + nums[1] + nums[2] while cur < len(nums) - 2: left = cur + 1 right = len(nums) - 1 while left < right: n = nums[cur] + nums[left] + nums[right] if abs(target - n) < abs(target - closest): closest = n if n == target: break elif n > target: t = right - 1 while (t > left and nums[t] == nums[right]): t -= 1 right = t else: t = left + 1 while (t < right and nums[t] == nums[left]): t += 1 left = t t = cur + 1 while (t < len(nums) and nums[t] == nums[cur]): t += 1 cur = t return closest # %% s = Solution() print(s.threeSumClosest(nums = [-1,2,1,-4], target = 1))
输出：
2
