倬倬吃三碗
0%

剑指offer笔记

发表于 更新于 分类于

1.栈与队列

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

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

1
2
3
4
5
6
7
8
9
输入：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
题目解释：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
要执行的方法的顺序

[[],[3],[],[],[]]
对应参数

CQueue创建队列，返回null
appendTail压3入栈
deleteHead删除栈底元素，返回该元素的值3
deleteHead删除栈底元素，但已经没有元素了，返回-1
deleteHead删除栈底元素，但已经没有元素了，返回-1

两个栈实现一个队列：队列先进先出，栈先进后出 -》 从一个栈进到另一个栈来实现先进先出

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class CQueue:
	def __init__(self):
		self.A, self.B = [], []
	
	def appendTail(self, value: int) -> None:
        self.A.append(value)
        
    def deleteHead(self) -> int:
        if not self.B:
            while self.A:
                self.B.append(self.A.pop())
        if self.B:
            return self.B.pop()
        else:
            return -1

Java

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
class CQueue{
    LinkedList<Integer>A, B;
    public CQueue(){
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    
    public void appendTail(int value){
        A.addLast(value)
    }
    
    public int deleteHead(){
        if(!B.isEmpty()){
            return B.removeLast();
        }
        if(A.isEmpty()){
            return -1;
        }
        while(!A.isEmpty()){
            B.addLast(A.removeLast());
        }
        return B.removeLast();
    }
    
}

剑指30.包含min函数的栈

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

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.
1
2
3
4
5
思路：
辅助栈。一个元素入栈时，在辅助栈中同时压入当前的最小值，使辅助栈min_stack与原栈stack相对应
- 元素入栈时，将辅助栈栈顶与该元素比较得出最小值，将这个最小值压入辅助栈成为该元素对应的最小值
- 元素出栈时，辅助栈栈顶元素同步弹出
- 辅助栈栈顶永远是当前原栈的最小值

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = [math.inf] #给一个无穷大值
        
    def push(self, x: int) -> None:
        self.stack.append(x)
        self.min_stack.append(min(x,self.min_stack[-1]))
        
    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()
        
    def top(self) -> int:
        return self.stack[-1]
    
    def min(self) -> int:
        return self.min_stack[-1]

Java

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
32
33
34
class MinStack {
    Stack<Integer> Stack;
    Stack<Integer> minStack;
    int min = Integer.MAX_VALUE;
    public MinStack() {
        Stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
        minStack.push(min);
    }
    
    public void push(int x) {
        Stack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }
    
    public void pop() {
		Stack.pop();
        minStack.pop();
    }
    
    public int top() {
		return Stack.peek();
    }
    
    public int min() {
		return minStack.peek();
    }
}

/**
Java的Stack作为数据结构却继承了vector，对外暴露了get(index)之类的方法，官方建议使用ArrayDeque双端链表来做
Deque<Integer> Stack;
Deque<Integer> minStack;
**/

2.链表

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

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

1
2
输入：head = [1,3,2]
输出：[2,3,1]

Python3

切片

O(N),append

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#切片来做，步长-1直接转置
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        resList = []
        while head:
            resList.append(head.val)
            head = head.next
        return resList[::-1]

递归

O(N),遍历整个链表,递归N次

1
2
3
4
5
6
class Sulution:
    def reversePrint(self, head: ListNode) -> List[int]:
        if head is not None:
            return self.reversePrint(head.next) + [head.val]
        else:
            return []

Java

辅助栈

和python切片同理,python直接返回倒序，java先进栈，然后用一个res数组来接出栈的元素

1
2
3
4
5
6
7
8
9
10
11
12
class Solution{
    LinkedList<Integer> stack = new LinkedList<Integer>();
    while(head != null){
        stack.addLast(head.val);
    	head = head.next;
    }
    int[] res = new int[stack.size()];
    for(i = 0; i < res.length; i++){
    	res[i] = stack.removeLast();
    }
    return res;
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head){
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i <res.length; i++){
            res[i] = tmp.get(i);
        }
        return res;
    }
    
    void recur(ListNode head){
        if(head == null){
            return;
        }
        recur(head.next);
        tmp.add(head.val);
    }
}

剑指24.反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

Python3

双指针迭代

O(N)，遍历

pre:null, cur:head

1
2
3
4
5
6
7
8
9
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur, pre = head, None
        while cur:
            tmp = cur.next	#临时存后继节点
            cur.next = pre	#修改next指向
            pre = cur		#pre变为cur
            cur = tmp		#前进到下一个节点
        return pre

递归

O(N)，遍历

1
2
3
4
5
6
7
8
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def recur(cur, pre):
            if not cur: return pre		#递归终止条件
            res = recur(cur.next, cur)	#递归后继节点
            cur.next = pre				#修改next指向
            return res					#返回反转链表的头节点
        return recur(head, None)

Java

双指针

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null;
        while(cur != null){
            ListNode tmp = cur.next;	//临时存后继节点
            cur.next = pre;				//修改next指向
            pre = cur;					//pre变为cur
            cur = tmp;					//前进到下一个节点
        }
        return pre;
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution{
	public ListNode reverseList(ListNode head){
		return recur(head, null);
	}
	private ListNode recur(ListNode cur, ListNode pre){
		if(cur == null){
			return pre;		//终止条件
		}
        ListNode res = recur(cur.next, cur);	//递归
        cur.next = pre;		//修改next指向
        return res;		//返回反转链表的头节点
	}
}

3.字符串

剑指05.替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

1
2
输入：s = "We are happy."
输出："We%20are%20happy."

Python3

O(N),遍历

Python和Java中字符串都是不可变类型

创建一个空列表res，遍历字符串s将每一个字符append进列表res，如果遇到空格则append%20，最后””.join将列表转为字符串

1
2
3
4
5
6
7
8
9
class Solution:
    def replaceSpace(self, s: str) -> str:
        res = []
        for i in s:
            if i == ' ':
                res.append('%20')
            else:
                res.append(i)
        return "".join(res)

库函数

1
2
3
class Solution:
    def replaceSpace(self, s: str) -> str:
		return s.replace(' ', '%20')

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String replaceSpace(String s) {
        StringBuilder res = new StringBuilder();
        for(Character c : s.toCharArray()){
            if(c == ' '){
                res.append("%20");
            }else{
                res.append(c);
            }
        }
        return res.toString();
    }
}

库函数

1
2
3
4
5
6
class Solution {
    public String replaceSpace(String s) {
        return s.replace(" ", "%20");
    }

}

剑指58.左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

1
2
3
4
5
输入: s = "abcdefg", k = 2
输出: "cdefgab"

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

Python

O(N),直接用切片

1
2
3
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]

O(N),遍历拼接

创建一个空列表res，先添加n到末位的字符，再添加首位到n的字符，最后’’.join()将列表转换为字符串返回

1
2
3
4
5
6
7
8
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        res = []
        for i in range(n, len(s)):
            res.append(s[i])
        for i in range(n):
            res.append(s[i])
        return ''.join(res)

Java

O(N),substring切片

1
2
3
4
5
class Solution {
    public String reverseLeftWords(String s, int n) {
		return s.substring(n,s.length()) + s.substring(0,n);
    }
}

O(N),遍历拼接

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder();
        for(int i = n; i < s.length; i++){
            res.append(s.charAt(i));
        }
        for(int i = 0; i< n; i++){
            res.append(s.charAt(i));
        }
        return s.toString();
    }
}

4.查找算法

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

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

1
2
3
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

Python3

哈希表/集合

O(N),创建一个空集合，遍历原数组nums，如果当前元素在集合里有就返回该元素，否则将该元素加入集合set

1
2
3
4
5
6
7
8
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        dict = set()
        for num in nums:
            if num in dict:
                return num
            dict.add(num)
        return -1

Java

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> dict = new HashSet<>();
        for(int num: nums){
            if(dict.contains(num)){
                return num;
            }
            dict.add(num);
        }
        return -1;
    }
}

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

统计一个数字在排序数组中出现的次数。

1
2
3
4
5
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

Python3

O(logN),二分查找法

因为排序数组，相同的数字必然在一起，找到这个窗口的左边界left与右边界right，这个窗口的长度(出现的次数)为right - left - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        i = 0
        j = len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] <= target:
                i = m + 1
            else:
                j = m - 1
        right = i
        
        if j >= 0 and nums[j] != target:
            return 0
        
        i = 0
        while i <= j:
            m = (i + j) // 2
            if nums[m] < target: i = m + 1
            else:
                j = m - 1
        left = j
        return right - left -1

Java

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 {
    public int search(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while(i <= j){
            int m = (i + j) / 2;
            if(nums[m] <= target){
                i = m + i;
            }else{
                j = m - 1;
            }
        }
        int right = i;

        if(j >= 0 && nums[j] != target){
            return 0;
        }

        i = 0;
        j = nums.length - 1;
        while(i <= j){
            int m = (i + j) / 2;
            if(nums[m] < target){
                i = m + 1;
            }else{
                j = m - 1;
            }
        }
        int left = j;
        return right - left -1;
    }
}

运行通过，提交超出时间限制，再议

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

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

1
2
3
4
5
输入: [0,1,3]
输出: 2

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

Python3

O(logN)，经典二分

根据题意，下标和元素应该是相同的。二分，左子数组: nums[i] = i, 右子数组:nums[i] != i。 缺失的数字就是右子数组首个元素的下标

1
2
3
4
5
6
7
8
9
10
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

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j){
            int m = (i + j) / 2;
            if(nums[m] == m){
                i = m + 1;
            }else{
                j = m - 1;
            }
        }
        return i;
    }
}