数组与矩阵
5. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例1：
1
2
| 输入：s = "We are happy."
输出："We%20are%20happy."
|
限制：
0 <= s 的长度 <= 10000
在网络编程中，如果URL参数中含有特殊字符，如空格、#等，则可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32,即十六进制的0x20,因此空格被替换成”%20”。再比如#的ASCII码为35，即十六进制的0x23，它在URL中被替换为”%23”。
如果是在原来的字符串上进行替换，就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上进行替换，那么我们可以自己分配足够多的内存。由于有这样两种不同的解决方案，我们应该向面试官问清楚，让他明确告诉我们他的需求。假设面试官让我们在原来的字符串上进行替换，并且保证输入的字符串后面有足够多的空余内存。
最直观的做法是从头到尾扫描字符串，每次碰到空格时进行替换。这样做，每次碰到空格就需要把空格后面的所有字符都后移2字节。假设字符串的长度是n。对每个空格字符，需要移动后面$O(n)$个字符，因此对于含有$O(n)$个空格字符的字符串而言，总的时间效率是$O(n^2)$。这显然不是一个好的解决方案。
那么，怎么操作能减少移动次数呢？—— 试试把从前向后替换改成从后向前替换。(对于Java来说，String是不可变的，因此，严谨地说，OJ题提供的方法头的参数应该由String改为StringBuffer。)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public String replaceSpace(String s) {
StringBuffer str = new StringBuffer(s);
int P1 = str.length() - 1;
for (int i = 0; i <= P1; i++)
if (str.charAt(i) == ' ')
str.append(" ");
int P2 = str.length() - 1;
while (P1 >= 0 && P2 > P1) {
char c = str.charAt(P1--);
if (c == ' ') {
str.setCharAt(P2--, '0');
str.setCharAt(P2--, '2');
str.setCharAt(P2--, '%');
} else {
str.setCharAt(P2--, c);
}
}
return str.toString();
}
|
时间复杂度和空间复杂度都是$O(n)$。
29. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
1
2
| 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
|
示例 2：
1
2
| 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
|
限制：
- 0 <= matrix.length <= 100
- 0 <= matrix[i].length <= 100
矩阵不一定是方阵，四个顶点的坐标是临界点。
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
35
| public int[] spiralOrder(int[][] matrix) {
if (matrix.length == 0) {
return new int[0];
}
int left = 0;
int right = matrix[0].length - 1;
int top = 0;
int bottom = matrix.length - 1;
int[] result = new int[(right + 1) * (bottom + 1)];
int index = 0;
while(true) {
for (int i = left; i <= right; i++)
result[index++] = matrix[top][i];
if (++top > bottom)
break;
for (int i = top; i <= bottom; i++)
result[index++] = matrix[i][right];
if (--right < left)
break;
for (int i = right; i >= left; i--)
result[index++] = matrix[bottom][i];
if (--bottom < top)
break;
for (int i = bottom; i >= top; i--)
result[index++] = matrix[i][left];
if (++left > right)
break;
}
return result;
}
|
50. 第一个只出现一次的字符位置
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
1
2
3
4
5
| s = "abaccdeff"
返回 "b"
s = ""
返回 " "
|
限制：
0 <= s 的长度 <= 50000
统计字符是否仅出现一次，可以用容器存放每个字符是否只出现一次。这个容器可以根据<字符>来存放<是否多次出现>的信息。因此，可以利用哈希表。
1
2
3
4
5
6
7
8
9
10
11
12
| public char firstUniqChar(String s) {
HashMap<Character, Boolean> hm = new HashMap();
char[] s2c = s.toCharArray();
for(char c : s2c) {
hm.put(c, !hm.containsKey(c));
}
for(char c : s2c) {
if(hm.get(c) == true)
return c;
}
return ' ';
}
|
时间复杂度$O(n)$，空间复杂度$O(1)$
栈、队列、堆
9. 用两个栈实现队列
剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode）
- 栈是LIFO（后进先出），队列是FIFO（先进先出）。
- 将一个栈专门用于插入整数，另一个栈专门用于删除整数
- Stack类已被Java不推荐使用，LinkedList基于双向链表实现，只能顺序访问，但可以快速插入和删除元素。LinkedList可用作栈、队列和双向队列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| private LinkedList<Integer> list1, list2;
public CQueue() {
list1 = new LinkedList<>();
list2 = new LinkedList<>();
}
public void appendTail(int value) {
list1.addLast(value);
}
public int deleteHead() {
if (!list2.isEmpty()) {
return list2.removeLast();
}
if (list1.isEmpty()) {
return -1;
}
while (!list1.isEmpty()) {
list2.addLast(list1.removeLast());
}
return list2.removeLast();
}
|
时间复杂度：$O(n)$（deleteHead()函数在N次队首元素删除操作中总共需完成N个元素的倒序），空间复杂度$O(n)$。
30. 包含min函数的栈
剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode）
既然是定义栈，那么push和pop功能显然不用再变动，重点在于实现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
| private LinkedList<Integer> stack, minStack;
public MinStack() {
stack = new LinkedList<>();
minStack = new LinkedList<>();
}
public void push(int x) {
stack.addLast(x);
minStack.addLast(minStack.isEmpty() ? x : Math.min(minStack.getLast(), x));
}
public void pop() {
stack.removeLast();
minStack.removeLast();
}
public int top() {
return stack.getLast();
}
public int min() {
return minStack.getLast();
}
|
31. 栈的压入、弹出序列
剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode）
一个序列是否为栈的弹出序列的规律：
- 如果当前栈顶的数字是下一个弹出的数字，则弹出；
- 如果当前栈顶的数字不是下一个弹出的数字，把还未入栈的数字压入栈中，直至栈顶的数字是下一个弹出的数字
- 如果所有数字都入栈的过程中，栈顶数字始终不是需要弹出的数字，则不可能是弹出序列
- 栈中数字全部顺利出栈，则为弹出序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public boolean validateStackSequences(int[] pushed, int[] popped) {
if(pushed.length == 0)
return true;
LinkedList<Integer> stack = new LinkedList<> ();
int i = 0;
for(int num : pushed) {
stack.addFirst(num);
while(!stack.isEmpty() && stack.getFirst() == popped[i]) {
stack.removeFirst();
i++;
}
}
return stack.isEmpty();
}
|
时间复杂度：$O(n)$（每个元素最多进栈1次，出栈1次，$O(2n)$）；空间复杂度：$O(n)$
40. 最小的K个数
剑指 Offer 40. 最小的k个数 - 力扣（LeetCode）
快速排序每次都能将选定的哨兵置于排序完成后的最终位置，当前的哨兵最终位置索引为K时，比它小的K个数将全在左侧。
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
| public int[] getLeastNumbers(int[] arr, int k) {
if (k >= arr.length)
return arr;
return quickSort(arr, k, 0, arr.length - 1);
}
private int[] quickSort(int[] arr, int k, int left, int right) {
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= arr[left]) {
j--;
}
while (i < j && arr[i] <= arr[left]) {
i++;
}
swap(arr, i, j);
}
swap(arr, i, left);
if (i > k) {
return quickSort(arr, k, left, i - 1);
}
if (i < k) {
return quickSort(arr, k, i + 1, right);
}
return Arrays.copyOf(arr, k);
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
|
- 时间复杂度$O(n)$： 其中n为数组元素数量；对于长度为n的数组执行哨兵划分操作的时间复杂度为$O(N)$；每轮哨兵划分后根据k和i的大小关系选择递归，由于i分布的随机性，则向下递归子数组的平均长度为$\frac{N}{2}$；因此平均情况下，哨兵划分操作一共有$N + \frac{N}{2} + \frac{N}{4} + … + \frac{N}{N} = \frac{N - \frac{1}{2}}{1 - \frac{1}{2}} = 2N - 1$（等比数列求和），即总体时间复杂度为$O(n)$。
- 空间复杂度$O(\log n)$：划分函数的平均递归深度为$O(\log n)$。
41. 数据流中的中位数
剑指 Offer 41. 数据流中的中位数 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| private Queue<Integer> minHeap, maxHeap;
public MedianFinder() {
minHeap = new PriorityQueue<>();
maxHeap = new PriorityQueue<>((x, y) -> (y - x));
}
public void addNum(int num) {
if (minHeap.size() == maxHeap.size()) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
} else {
minHeap.offer(num);
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
return minHeap.size() == maxHeap.size() ? (minHeap.peek() + maxHeap.peek()) / 2.0 : minHeap.peek();
}
|
时间复杂度：
- 查找中位数$O(1)$：获取堆顶元素使用$O(1)$时间；
- 添加数字$O(\log N)$：堆的插入和弹出操作使用$O(\log N)$时间。
空间复杂度：$O(N)$
59.1 滑动窗口的最大值
剑指 Offer 59 - I. 滑动窗口的最大值（单调队列，清晰图解） - 滑动窗口的最大值 - 力扣（LeetCode）
如何在窗口每次滑动时，获取最大值？使用双端队列存储当前滑动窗口中的最大值以及在后续窗口中潜在的最大值。
每轮窗口滑动：
- 如果滑出窗口的数是队首数字，则队首数字也出队（队列的大小必然<=窗口大小）
- 如果新进入窗口的数比队尾的数大，说明队尾的数不可能成为某个窗口的最大值。将队尾元素移除，直到队尾的数字>=新进入窗口的数或队列已空。
- 如果新进入窗口的数比队尾的数小，说明等之前的数滑出窗口后，有可能会成为后续窗口中的最大值，因此，直接加入队尾。
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
| private Deque<Integer> deque;
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0) {
return new int[0];
}
int[] result = new int[nums.length - k + 1];
int index = 0;
deque = new LinkedList<>();
for(int i = 0; i < k; i++) {
while(!deque.isEmpty() && deque.getLast() < nums[i]) {
deque.removeLast();
}
deque.addLast(nums[i]);
}
result[index++] = deque.getFirst();
for(int i = k; i < nums.length; i++) {
if(nums[i - k] == deque.getFirst())
deque.removeFirst();
while(!deque.isEmpty() && deque.getLast() < nums[i]) {
deque.removeLast();
}
deque.addLast(nums[i]);
result[index++] = deque.getFirst();
}
return result;
}
|
时间复杂度：$O(n)$
空间复杂度：$O(n)$
双指针
57.1 和为S的两个数字
剑指 Offer 57. 和为s的两个数字 - 力扣（LeetCode）
递增排序的数组，查找两个数使得和为s——双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left < right) {
if(nums[left] + nums[right] == target) {
return new int[] {nums[left], nums[right]};
} else if (nums[left] + nums[right] < target) {
left++;
} else (nums[left] + nums[right] > target) {
right--;
}
}
return new int[0];
}
|
时间复杂度：$O(n)$
空间复杂度：$O(1)$
57.2 和为s的连续正数序列
剑指 Offer 57 - II. 和为s的连续正数序列 - 力扣（LeetCode）
连续正整数序列 & 求和——双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int[][] findContinuousSequence(int target) {
int left = 1, right = 2;
List<int[]> list = new ArrayList<>();
int sum = 3;
while (left <= target / 2) {
if (sum == target) {
int[] result = new int[right - left + 1];
for(int i = 0; i < right - left + 1; i++) {
result[i] = left + i;
}
list.add(result);
}
if (sum < target) {
sum += ++right;
} else {
sum -= left++;
}
}
return list.toArray(new int[0][]);
}
|
时间复杂度：$O(n)$
空间复杂度：$O(n)$
58.1 翻转单词顺序列
剑指 Offer 58 - I. 翻转单词顺序 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public String reverseWords(String s) {
s = s.trim();
StringBuilder sb = new StringBuilder();
int i = s.length() - 1;
int j = i;
while (i >= 0) {
while(i >= 0 && s.charAt(i) != ' ') {
i--;
}
sb.append(s.substring(i+1, j + 1) + ' ');
while(i >= 0 && s.charAt(i) == ' ') {
i--;
}
j = i;
}
return sb.toString().trim();
}
|
时间复杂度：$O(n)$
空间复杂度：$O(n)$
58.2 左旋转字符串
剑指 Offer 58 - II. 左旋转字符串 - 力扣（LeetCode）
1
2
3
4
5
6
| public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
sb.append(s.substring(n, s.length()));
sb.append(s.substring(0, n));
return sb.toString();
}
|
时间复杂度：$O(n)$
空间复杂度：$O(n)$
链表
6. 从尾到头打印链表
剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
| public int[] reversePrint(ListNode head) {
List<Integer> list = new ArrayList<>();
while(head != null) {
list.add(head.val);
head = head.next;
}
int[] result = new int[list.size()];
for(int i = result.length - 1; i >= 0; i--) {
result[i] = list.get(result.length - 1 - i);
}
return result;
}
|
时间复杂度：$O(n)$
空间复杂度：$O(n)$
18. 删除链表的节点
剑指 Offer 18. 删除链表的节点 - 力扣（LeetCode）
- 无需存储所有节点，找到被删的节点，修改前一个节点的next节点即可——双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
| public ListNode deleteNode(ListNode head, int val) {
if(head.val == val) {
return head.next;
}
ListNode pre = head;
ListNode cur = pre.next;
while(cur.val != val) {
pre = cur;
cur = cur.next;
}
pre.next = cur.next;
return head;
}
|
时间复杂度：$O(n)$
空间复杂度：$O(1)$
22. 链表中倒数第K个节点
剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode）
双指针
1
2
3
4
5
6
7
8
9
10
11
12
| public ListNode getKthFromEnd(ListNode head, int k) {
ListNode right = head;
ListNode left = head;
for(int i = 0; i < k; i++) {
right = right.next;
}
while(right != null) {
right = right.next;
left = left.next;
}
return left;
}
|
时间复杂度：$O(n)$
空间复杂度：$O(1)$
23. 链表中环的入口节点
剑指 Offer II 022. 链表中环的入口节点 - 力扣（LeetCode）
方式一：利用HashSet存储ListNode，判断后续遍历的节点是否已经在集合中。时间复杂度：$O(n\log n)$；空间复杂度$O(n)$。
方式二：一快一慢的双指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && slow != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
return null;
}
|
时间复杂度：$O(n)$
空间复杂度：$O(1)$
24. 反转链表
剑指 Offer 24. 反转链表 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public ListNode reverseList(ListNode head) {
ListNode cur = head;
if(cur == null) {
return null;
}
ListNode nextNode = cur.next;
head.next = null;
ListNode preNode = head;
while(nextNode != null) {
cur = nextNode;
nextNode = nextNode.next;
cur.next = preNode;
preNode = cur;
}
return cur;
}
|
时间复杂度：$O(n)$
空间复杂度：$O(1)$
25. 合并两个排序的链表
剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(1);
ListNode cur = head;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return head.next;
}
|
时间复杂度：$O(n)$
空间复杂度：$O(1)$
35. 复杂链表的复制
剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode）
- 利用哈希表，构建原链表节点和新链表对应节点的映射关系。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public Node copyRandomList(Node head) {
Map<Node, Node> hm = new HashMap<>();
Node cur = head;
while(cur != null) {
hm.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while(cur != null) {
hm.get(cur).next = hm.get(cur.next);
hm.get(cur).random = hm.get(cur.random);
cur = cur.next;
}
return hm.get(head);
}
|
时间复杂度：$O(n)$
空间复杂度：$O(n)$
52. 两个链表的第一个公共节点
剑指 Offer 52. 两个链表的第一个公共节点 - 力扣（LeetCode）
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
| public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int step1 = 0, step2 = 0;
ListNode A = headA, B = headB;
while(A != null) {
step1++;
A = A.next;
}
while(B != null) {
step2++;
B = B.next;
}
int step = step1 - step2;
A = headA;
B = headB;
if(step < 0) {
while(step != 0) {
B = B.next;
step++;
}
} else if(step > 0) {
while (step != 0) {
A = A.next;
step--;
}
}
while (A != B) {
A = A.next;
B = B.next;
}
return A;
}
|
时间复杂度：$O(n+m)$
空间复杂度：$O(1)$
二分查找
11. 旋转数组的最小数字
剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode）
分治
数学
39. 数组中出现次数超过一半的数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int majorityElement(int[] nums) {
int target = nums[0], times = 1;
for(int i = 1; i < nums.length; i++) {
if (target != nums[i]) {
times--;
} else {
times++;
}
if (times == 0) {
target = nums[i];
times = 1;
}
}
return target;
}
|
时间复杂度：$O(n)$
空间复杂度：$O(1)$
43. 1~n整数中1出现的次数
剑指 Offer 43. 1～n 整数中 1 出现的次数 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int countDigitOne(int n) {
int digit = 1, res = 0;
int high = n / 10, cur = n % 10, low = 0;
while(high != 0 || cur != 0) {
if(cur == 0) {
res += high * digit;
} else if(cur == 1) {
res += high * digit + low + 1;
} else {
res += (high + 1) * digit;
}
low += cur * digit;
cur = high % 10;
high /= 10;
digit *= 10;
}
return res;
}
|