剑指 Offer 50. 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。
- 首先通过字典（散列）将所以字符出现的频率保存。再用一个循环输出只出现一次的第一个字符
class Solution:
def firstUniqChar(self, s: str) -> str:
dict = {}
for i in s:
if i in dict:
dict[i] += 1 # 这里也可以中true flase代替
else:
dict[i] = 1
for i in s:
if dict[i] == 1:
return i
return " "
- 在哈希表的基础上，有序哈希表中的键值对是 按照插入顺序排序 的。基于此，可通过遍历有序哈希表，实现搜索首个 “数量为1的字符”
Python 3.6 后，默认字典就是有序的，因此无需使用 OrderedDict()
class Solution {
public:
char firstUniqChar(string s) {
vector<char> keys;
unordered_map<char, bool> dic;
for(char c : s) {
if(dic.find(c) == dic.end())
keys.push_back(c);
dic[c] = dic.find(c) == dic.end();
}
for(char c : keys) {
if(dic[c]) return c;
}
return ' ';
}
};
剑指 Offer 32 - I. 从上到下打印二叉树 :star:
广度优先搜索,通过队列的先入先出特性实现
Python 中使用 collections 中的双端队列deque()，其popleft() 方法可达到 $O(1)$ 时间复杂度
class Solution:
def levelOrder(self, root: TreeNode):
if not root : return []
res,queue = [] ,collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
res.append(node.val)
# 添加左右节点
if node.left : queue.append(node.left)
if node.right : queue.append(node.right)
return res
剑指 Offer 32 - II. 从上到下打印二叉树 II
以广度优先搜索的方式打印二叉树，返回其层次遍历的结果。 通过32-Ⅰ中已经已经知道了可以将二叉树以广度优先方式输出的方法，这里主要确定二叉树的层次。
class Solution:
def levelOrder(self, root: TreeNode):
if not root : return []
res,queue = [] ,collections.deque()
queue.append(root)
while queue:
tmp = []
for i in range(len(queue)):
node = queue.popleft()
tmp.append(node.val)
# 添加左右节点
if node.left : queue.append(node.left)
if node.right : queue.append(node.right)
res.append(tmp)
return res
剑指 Offer 32 - III. 从上到下打印二叉树 III
根据层数不同，左右打印顺序不同。这里添加一个标志位即可。困难在于在循环过程中队列有的节点会出去，又有新的节点加进来。
一直在双端队列的处想办法，但可以在添加tmp出做文章。将tmp做为双端队列层数不同添加顺序也不同
class Solution:
def levelOrder(self, root: TreeNode):
if not root : return []
res,queue = [] ,collections.deque()
queue.append(root)
from_left = True
while queue:
tmp = collections.deque()
for i in range(len(queue)):
node = queue.popleft()
if from_left :
tmp.append(node.val)
else:
tmp.appendleft(node.val)
if node.left :
queue.append(node.left)
if node.right :
queue.append(node.right)
res.append(list(tmp))
from_left = not from_left
return res
- 方法二：层序遍历，双端队列（奇偶层分离）
我也不知道在说什么
每次大循环中嵌套两个循环，按顺序打印奇数层和偶数层。
if not root : return []
res,queue = [] ,collections.deque()
queue.append(root)
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.popleft()
tmp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(tmp)
if not queue:
break
# 如果下一个奇数层没有节点便提前退出
tmp = []
for _ in range(len(queue)):
node = queue.pop()
tmp.append(node.val)
if node.right:
queue.appendleft(node.right)
if node.left:
queue.appendleft(node.left)
res.append(tmp)
return res
- 方法三：层序遍历+倒序
偶数层倒序，若res长度为奇数则对tmp执行倒序操作
if not root : return []
res,queue = [] ,collections.deque()
queue.append(root)
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.popleft()
tmp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if len(tmp) % 2 == 0 :
res.append(tmp)
else:
res.append(tmp[::-1])
return res
