yyyying的blog

好好学习 天天向上

0%

剑指offer力扣

发表于 更新于 分类于 Valine：
本文字数： 8k 阅读时长 ≈ 7 分钟

力扣 剑指offer 题库

重启每日刷题

2022.3.9

剑指 Offer 09. 用两个栈实现队列

我的答案 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class CQueue:
    def __init__(self):
        self.queueA = []
        self.queueB = []

    def appendTail(self, value: int) -> None:
        self.queueA.append(value)

    def deleteHead(self) -> int:
        if len(self.queueB) != 0:
            return self.queueB.pop()
        if len(self.queueA) == 0:
            return -1
        else:
            while len(self.queueA) > 0:
                self.queueB.append(self.queueA.pop())
        return self.queueB.pop()

参考题解 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class CQueue:
    def __init__(self):
        self.A, self.B = [], []

    def appendTail(self, value: int) -> None:
        self.A.append(value)

    def deleteHead(self) -> int:
        if self.B: return self.B.pop()
        if not self.A: return -1
        while self.A:
            self.B.append(self.A.pop())
        return self.B.pop()

作者：jyd
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

差距：
整体算法逻辑相同，题解书写更为简单明了。

剑指 Offer 30. 包含min函数的栈

我的答案 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.A = []
        self.B = []

    def push(self, x: int) -> None:
        self.A.append(x)
        if len(self.B) == 0:
            self.B.append(x)
        else:
            self.B.append(min(self.B[-1],x))

    def pop(self) -> None:
        self.B.pop()
        return self.A.pop()

    def top(self) -> int:
        return self.A[-1]

    def min(self) -> int:
        return self.B[-1]
参考题解 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class MinStack:
    def __init__(self):
        self.A, self.B = [], []

    def push(self, x: int) -> None:
        self.A.append(x)
        if not self.B or self.B[-1] >= x:
            self.B.append(x)

    def pop(self) -> None:
        if self.A.pop() == self.B[-1]:
            self.B.pop()

    def top(self) -> int:
        return self.A[-1]

    def min(self) -> int:
        return self.B[-1]

作者：jyd
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

差距：
整体算法逻辑相同，题解通过比较减少B的内存占用。

2022.3.10

剑指 Offer 06. 从尾到头打印链表

我的答案 
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        a = []
        while head:
            stack.append(head.val)
            head = head.next
        return a[-1::-1]
与题解大致相同

剑指 Offer 24. 反转链表

我的答案 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None:
            return head
        last = None
        while head.next:
            buf = copy.copy(head)
            buf.next = last
            last = buf
            head = head.next
        head.next = last
        return head
参考题解 
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur, pre = head, None
        while cur:
            cur.next, pre, cur = pre, cur, cur.next
        return pre

作者：jyd
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/jian-zhi-offer-24-fan-zhuan-lian-biao-die-dai-di-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

差距：
题解写法更加精简

剑指 Offer 35. 复杂链表的复制

我的答案 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        a = {}
        if head == None:
            return None
        buf = head
        while buf != None:
            a[buf] = Node(buf.val)
            buf = buf.next
        buf = head
        while buf != None:
            a[buf].next = a.get(buf.next)
            a[buf].random = a.get(buf.random)
            buf = buf.next
        return a[head]
参考题解 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return
        cur = head
        # 1. 复制各节点，并构建拼接链表
        while cur:
            tmp = Node(cur.val)
            tmp.next = cur.next
            cur.next = tmp
            cur = tmp.next
        # 2. 构建各新节点的 random 指向
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        # 3. 拆分两链表
        cur = res = head.next
        pre = head
        while cur.next:
            pre.next = pre.next.next
            cur.next = cur.next.next
            pre = pre.next
            cur = cur.next
        pre.next = None # 单独处理原链表尾节点
        return res      # 返回新链表头节点

作者：jyd
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/jian-zhi-offer-35-fu-za-lian-biao-de-fu-zhi-ha-xi-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

差距：
我的方法使用字典保存新节点，题解有相同方法，这个为方法二，优化空间复杂度，稍微提升时间复杂度

2022.3.11

今日过于简单

剑指 Offer 05. 替换空格

我的答案 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def replaceSpace(self, s):
        """
        :type s: str
        :rtype: str
        """
        result = ''
        for i in s:
            if i == ' ':
                result += '%20'
            else:
                result += i
        return result

剑指 Offer 58 - II. 左旋转字符串

我的答案 
1
2
3
4
5
6
7
8
class Solution(object):
    def reverseLeftWords(self, s, n):
        """
        :type s: str
        :type n: int
        :rtype: str
        """
        return s[n:]+s[:n]

2022.3.12

剑指 Offer 03. 数组中重复的数字

简单没有题解

我的答案 
1
2
3
4
5
6
7
8
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        answer = {}
        for i in nums:
            if answer.get(i,0) != 0:
                return i
            answer[i] = 1
        return 0

剑指 Offer 53 - I. 在排序数组中查找数字 I

我的答案 
1
2
3
4
5
6
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        answer = {}
        for i in nums:
            answer[i] = answer.get(i,0) + 1
        return answer.get(target,0)
参考题解 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def search(self, nums: [int], target: int) -> int:
        def helper(tar):
            i, j = 0, len(nums) - 1
            while i <= j:
                m = (i + j) // 2
                if nums[m] <= tar: i = m + 1
                else: j = m - 1
            return i
        return helper(target) - helper(target - 1)

作者：jyd
链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

差距：
没有仔细审题！！审题！！数组有序直接二分搜索

剑指 Offer 53 - II. 0～n-1中缺失的数字

我的答案 
1
2
3
4
5
6
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if nums[i] != i:
                return i
        return i+1
参考题解 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] == m: i = m + 1
            else: j = m - 1
        return i

作者：jyd
链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/solution/mian-shi-ti-53-ii-0n-1zhong-que-shi-de-shu-zi-er-f/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

差距：
有序啊，应该二分的！

2022.3.13

加班 后边补档

2022.3.14

面试题32 - I. 从上到下打印二叉树

BFS

我的答案 
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root: return []
        result, q = [], collections.deque()
        q.append(root)
        while q:
            node = q.popleft()
            result.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        return result

剑指 Offer 32 - II. 从上到下打印二叉树 II

我的答案 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        result, q = [],collections.deque()
        q.append([0,root])
        while q:
            deep,node = q.popleft()
            if deep < len(result):
                result[deep].append(node.val)
            else:
                result.append([node.val])
            if node.left: q.append([deep+1,node.left])
            if node.right: q.append([deep+1,node.right])
        return result
参考题解 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        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)
        return res

作者：jyd
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solution/mian-shi-ti-32-ii-cong-shang-dao-xia-da-yin-er-c-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

差别：
我是引入deep，题解直接根据队列长度输出，省时省力

剑指 Offer 32 - III. 从上到下打印二叉树 III

我的答案 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        result, q = [],collections.deque()
        q.append([0,root])
        while q:
            deep,node = q.popleft()
            if deep < len(result):
                result[deep].append(node.val)
            else:
                result.append([node.val])
            if node.left: q.append([deep+1,node.left])
            if node.right: q.append([deep+1,node.right])
        for i in range(len(result)):
            if i % 2 != 0:
                result[i] = result[i][::-1]
        return result
参考题解 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res, deque = [], collections.deque([root])
        while deque:
            tmp = collections.deque()
            for _ in range(len(deque)):
                node = deque.popleft()
                if len(res) % 2: tmp.appendleft(node.val) # 偶数层 -> 队列头部
                else: tmp.append(node.val) # 奇数层 -> 队列尾部
                if node.left: deque.append(node.left)
                if node.right: deque.append(node.right)
            res.append(list(tmp))
        return res

作者：jyd
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/mian-shi-ti-32-iii-cong-shang-dao-xia-da-yin-er--3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

差别：同上

2022.3.15

摸

2022.3.16

前两道斐波那契简单

剑指 Offer 63. 股票的最大利润

简单

我的答案 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        m1 = 10000000
        m2 = -1
        for i in prices:
            if i < m1:
                result = max(result, (m2 - m1))
                m1 = i
                m2 = i
            if i > m2:
                m2 = i
        return max(result, (m2 - m1))