leetcode练习-6

剑指 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

引用

图解算法数据结构 - LeetBook - 力扣(LeetCode)全球极客挚爱的技术成长平台

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇