文章目录
一，路径总和
1，程序简介
-
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
-
叶子节点 是指没有子节点的节点。
示例 1：
- 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
- 输出：true
示例 2：
- 输入：root = [1,2,3], targetSum = 5
- 输出：false
示例 3：
- 输入：root = [1,2], targetSum = 0
- 输出：false
提示：
- 树中节点的数目在范围 [0, 5000] 内
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
2，程序代码
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 28 19:37:50 2022
Function: 路径总和
@author: 小梁aixj
"""
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if root is None:
return False
if sum == root.val and root.left is None and root.right is None:
return True
return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
二，单词拆分
1，程序简介
- 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
- 输入: s = “leetcode”, wordDict = [“leet”, “code”]
- 输出: true
- 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
示例 2：
- 输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
- 输出: true
- 解释: 返回 true 因为
"
applepenapple
"
可以被拆分成
"
apple pen apple
"
。
注意你可以重复使用字典中的单词。
示例 3：
- 输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
- 输出: false
2，程序代码
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 28 19:42:32 2022
Function: 单词拆分
@author: 小梁aixj
"""
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
if not s:
return True
lenth = len(s)
dp = [False for i in range(lenth + 1)]
dp[0] = True
for i in range(1, lenth + 1):
for j in range(i):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
return dp[-1]
三，O(1) 时间插入、删除和获取随机元素
1，程序简介
- 设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。
注意:
-
允许出现重复元素。
insert(val)：向集合中插入元素 val。 remove(val)：当 val 存在时，从集合中移除一个 val。 getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。
示例:
// 初始化一个空的集合。
RandomizedCollection collection = new RandomizedCollection();
// 向集合中插入 1 。返回 true 表示集合不包含 1 。
collection.insert(1);
// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
collection.insert(1);
// 向集合中插入 2 ，返回 true 。集合现在包含 [1,1,2] 。
collection.insert(2);
// getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。
collection.getRandom();
// 从集合中删除 1 ，返回 true 。集合现在包含 [1,2] 。
collection.remove(1);
// getRandom 应有相同概率返回 1 和 2 。
collection.getRandom();
2，程序代码
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 28 19:44:35 2022
Function: O(1) 时间插入、删除和获取随机元素
@author: 小梁aixj
"""
class RandomizedSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.dict = {}
self.list = []
def insert(self, val: int) -> bool:
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val in self.dict:
return False
self.dict[val] = len(self.list)
self.list.append(val)
return True
def remove(self, val: int) -> bool:
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val in self.dict:
last_element, idx = self.list[-1], self.dict[val]
self.list[idx], self.dict[last_element] = last_element, idx
self.list.pop()
del self.dict[val]
return True
return False
def getRandom(self) -> int:
"""
Get a random element from the set.
"""
return choice(self.list)