笔记

03，数组中重复的数字

set，自动去重
原地交换：在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。此说明含义：数组元素的索引和值是 一对多 的关系。

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
# solution 1
        # var_set = set()
        # for i in range(len(nums)):
        #     if nums[i] in var_set:
        #         return nums[i]
        #     else:
        #         var_set.add(nums[i])
        # 时间复杂度O(N)，空间复杂度：O(N)
# solution 2
        i = 0
        while i < len(nums):
            if nums[i] == i:
                i += 1
                continue
                # 若 nums[i] = i ： 说明此数字已在对应索引位置，无需交换，因此跳过；
            if nums[nums[i]] == nums[i]:
                return nums[i]
				# 若 nums[nums[i]] = nums[i]： 代表索引 nums[i] 处和索引 ii 处的元素值都为 nums[i] ，即找到一组重复值，返回此值 nums[i];
                
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]] 
    			# 否则： 交换索引为 i 和 nums[i]的元素值，将此数字交换至对应索引位置。
        return -1
    # 时间复杂度O(N)，空间复杂度：O(1)

Python 中， a, b = c, d 操作的原理是先暂存元组 (c, d)，然后 “按左右顺序” 赋值给 a 和 b 。因此，若写为：
nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
，则左nums[i] 会先被赋值，之后左nums[nums[i]]指向的元素则会出错。

09，两个栈实现一个队列

请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

def __init__(self):
	self.A, self.B = [], []
def appendTail (self, value: int) -> None:
	self.A.append(value)
def deleteHead(self) -> int:
	if not self.A: return -1
	if self.B return self.B.pop()
	while self.A:
		self.B.append(self.A.pop())
    return self.B.pop()

30，包含min函数的栈（栈与队列）

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

普通栈的 push() 和 pop() 函数的复杂度为 O(1)O(1) ；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)O(N) 。

本题难点：

将 min() 函数复杂度降为 O(1)O(1) ，可通过建立辅助栈实现；数据栈 AA ：栈 AA 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
辅助栈 BB ：栈 BB 中存储栈 AA 中所有非严格降序的元素，则栈 AA 中的最小元素始终对应栈 BB 的栈顶元素，即 min() 函数只需返回栈 BB 的栈顶元素即可。

因此，只需设法维护好栈 BB 的元素，使其保持非严格降序，即可实现 min() 函数的 O(1)O(1) 复杂度。

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.A, self.B = [], []

    def push(self, x: int) -> None:
        self.A.append(x)
        if not self.B or self.B[-1] >= x: #如果不把和栈顶元素相等的新最小元素放进去的话，弹栈后A会和B不相等
            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]

24. 反转链表（链表）

迭代（双指针） / 递归，题解

我们要把上图列表反转，有两种方法迭代（双指针） / 递归：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
    	cur, pre = head, None
   		while cur:
   			tmp = cur.next # 先把cur指针的下个位置缓存
   			cur.next=pre # 修改cur指针的指向位置，从默认的指向后改为指向前
   			pre = cur # 把pre指针指向当前位置
   			cur = tmp # 把当前位置的cur指针指向下个位置

链表具有天然的递归性
一个链表例如 1->2->3->4->5->NULL，可以看成头节点(节点值为 1 的节点)后面挂接一个更短的链表(缺少节点值为 1 的节点，以节点值为 2 的节点为头节点) 1->更短的链表，依次类推。如下如示：
这样的话，就可以先翻转头节点后面挂接的链表，然后把翻转后的链表的后面再挂接头节点，这样就实现了链表的翻转，如下图示：
先翻转以节点值为 2 的节点作为头节点的链表
将原头节点(节点值为 1 的节点)挂接在翻转之后的链表的后面
例子：
以链表 1->2->3->null 为例子，其递归反转过程如下动图示：
递归结束条件：
1. 节点是空节点；
2. 当前只有这一个节点，无需再翻转。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
    	# if not head.next: return []
    	# return reverseList(head.next) + [head.val] #06，从后到前打印链表
    	if not head or not head.next:
    		return head
        node = self.reverseList(head.next)
        head.next.next=head
        head.next=null
        return

Previous剑指offer Next工程

Last updated 3 years ago

Was this helpful?