Leetcode刷题记录
2026-11-04 22:18:17

20. 有效的括号

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 Solution {
public boolean isValid(String s) {
int n = s.length();
if(n%2==1)return false;

Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')','(');
put(']','[');
put('}','{');
}};
Deque<Character> st = new LinkedList<Character>();
for(int i=0;i<n;i++) {
char ch = s.charAt(i);
if(pairs.containsKey(ch)) {
if(st.isEmpty() || st.peek()!=pairs.get(ch)) {
return false;
}
st.pop();
} else {
st.push(ch);
}
}
return st.isEmpty();
}
}

295. 数据流的中位数

先插入后调整的做法

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
36
class MedianFinder {
Queue<Integer> left;
Queue<Integer> right;

public MedianFinder() {
left = new PriorityQueue<>((a, b) -> b - a);
right = new PriorityQueue<>((a, b) -> a - b);
}

public void addNum(int num) {
// 1. 默认加入左堆
if (left.isEmpty() || num <= left.peek()) {
left.offer(num);
} else {
right.offer(num);
}

// 2. 平衡两个堆的大小
if (left.size() > right.size() + 1) {
right.offer(left.poll());
} else if (right.size() > left.size()) {
left.offer(right.poll());
}
}

public double findMedian() {
if (left.isEmpty()) {
return -1;
}
if (left.size() > right.size()) {
return left.peek();
} else {
return (left.peek() + right.peek()) / 2.0;
}
}
}

第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
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
return qsort(nums,0,n-1,n-k);
}

int qsort(int[] nums,int l,int r,int k) {
if(l==r) return nums[k];
int x = nums[l],i = l-1,j=r+1;
while(i < j) {
do i++; while(nums[i] < x);
do j--; while(nums[j] > x);
if(i<j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
//j是最后一个小于等于x的元素,所以j+1就是第一个大于x的元素

if(k <= j)return qsort(nums,l,j,k);
else return qsort(nums,j+1,r,k);
}
}

链表排序

  1. 快慢指针找中点
  2. 快慢指针找中点,然后递归分割
  3. 归并排序
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head,null);
}
public ListNode sortList(ListNode head,ListNode tail) {
// 递归终止条件
if(head == null) return head;
if(head.next == tail) {
head.next = null;
return head;
}

// 快慢指针找中点
ListNode slow = head,fast = head;
while(fast != tail) {
slow = slow.next;
fast = fast.next;
if(fast!=tail) fast = fast.next;
}

ListNode mid = slow;
ListNode list1 = sortList(head,mid);
ListNode list2 = sortList(mid,tail);
ListNode sorted = merge(list1,list2);
return sorted;
}

public ListNode merge(ListNode head1,ListNode head2) {
ListNode preHead = new ListNode(0);//这里需要一个虚拟头节点,因为有可能head1或者head2为空,
ListNode temp = preHead,temp1 = head1,temp2 = head2;
while(temp1!=null && temp2 != null) {
if(temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}

if(temp1 != null) {
temp.next = temp1;
} else if(temp2!=null) {
temp.next = temp2;
}
//这里需要返回preHead.next,因为preHead是虚拟头节点,所以需要返回它的下一个节点,即真正的头节点。
return preHead.next;
}
}

76. 最小覆盖子串

思路,维护字符的个数的map,先统计t中的字符的个数,做一个map,然后记录个数;

对s使用滑动窗口,每次移动右指针,如果当前字符在t中,则将当前字符的个数加1,如果当前字符的个数小于等于t中对应字符的个数,则计数加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
25
26
27
28
29
30
31
32
class Solution {
public String minWindow(String s, String t) {
int[] need = new int[128];
int[] win = new int[128];

for(char c : t.toCharArray()) {
need[c]++;
}

int minL = Integer.MAX_VALUE;
int minStratL = -1;
int count = 0;

for(int l=0, r=0;r<s.length();r++) {
char rc = s.charAt(r);
win[rc]++;
if(win[rc]<=need[rc])count++;

while(count == t.length()) {
if(r-l+1<minL) {
minL = r-l+1;
minStratL = l;
}
char lc = s.charAt(l);
if(win[lc]<=need[lc])count--;
win[lc]--;
l++;
}
}
return minStratL == -1? "" : s.substring(minStratL,minStratL+minL);
}
}

239. 滑动窗口最大值

维护一个单调队列,左右都可弹出,满足数值大小是从队首到队尾是单调减的,但是存的具体的是下标;
先使用前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
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> dq = new LinkedList<>();
for(int i=0;i<k;i++) {
//这里注意是大于等于,因为要保证队列是单调递减的,
while(!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
dq.pollLast();
}
dq.offerLast(i);
}
int ans[] = new int[n-k+1];
ans[0] = nums[dq.peekFirst()];
for(int i=k;i<n;i++) {
while(!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
dq.pollLast();
}
dq.offerLast(i);
while( dq.peekFirst() <= i-k) {//这里注意是小于等于,因为要保证队列是单调递增的,
dq.pollFirst();
}
ans[i-k+1] = nums[dq.peekFirst()];
}
return ans;
}

560. 和为 K 的子数组

思路就是查所有子区间,先枚举尾部坐标,再枚举头部坐标,然后计算和,如果和等于k,则计数加1。

但是这种是n2的时间复杂度,可以优化。第二轮枚举头部坐标的时候,可以使用一个Map来记录前缀和,这样就可以在O(1)的时间复杂度内计算和。

整体是O(n)的时间复杂度,O(n)的空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
int preSum = 0;
int sum = 0;
map.put(0,1);
for(int num:nums) {
preSum += num;
//先加和再写Map,否则会计算空数组,出现不必要的0
sum+=map.getOrDefault(preSum-k,0);
map.put(preSum,map.getOrDefault(preSum,0)+1);
}
return sum;
}
}

42. 接雨水

遍历每一个柱子,向左向右找到最高的柱子,然后取左右最高柱子中较小的那个,减去当前柱子的高度,就是当前柱子能接的雨水。

优化点:找最高柱子的过程可以优化,用空间换时间。

如果用数组来存储这个数据,需要O(n)的空间,但是观察可以发现,每个位置的数据只用了一次,而不同位置的数字之间也存在着某种联系。

所以可以使用双指针来优化,一个指向左边最高的柱子,一个指向右边最高的柱子,然后向中间移动,直到两指针相遇,此时两指针所指的柱子就是最高的柱子。在这个移动的过程中,边移动边计算当前位置能接的雨水。这样可以将空间复杂度降低到O(1)。

24. 两两交换链表中的节点

一个链表,交换相邻的两个节点,直到没有相邻的两个节点可以交换。

思路:从头到尾,每两个为一组(不足两个的不用交换),步长为2,遍历链表,使用临时变量保存当前节点的下一个节点,然后交换当前节点和下一个节点的指针,然后移动到下一个节点的下一个节点。

要注意使用last 来更新最后一个交换的节点,否则会出现链表断裂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
while(cur!=null && cur.next!=null) {
if(first!=1)last.next=cur.next;
else first=0;
//记录并更新上一个
last = cur;

//调整指针
temp=cur.next.next;
cur.next.next = cur;
cur.next=temp;

//这里要注意的是,链表已经交换了,cur位于后位,所以要更新cur到cur的下一个节点,而不是最开始的last.next.next。

//不过这里形式上是下一个,要明白这是下一个的下一个。
cur = cur.next;
}

指针交换如下图所示:

指针交换指针交换

51. N 皇后

N皇后,不能再经典的回溯题,逻辑很好理解,即使用回溯的方式枚举所有的可能,然后判断可行性,得到所有的可行解。
不过这个输出格式实在是想吐槽,莫名其妙的格式(不过应该是我对字符串以及组织不熟悉)。

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0;i<n;i++) {
if(c[i]==0 && x[i+num]==0 && xx[i-num+n-1]==0) {
c[i]=1; //column
x[i+num]=1; //left diagonal
xx[i-num+n-1]=1; //right diagonal
ans[num]=i;
f(ans,num+1);
c[i]=0;
x[i+num]=0;
xx[i-num+n-1]=0;
}
}

题目中要求的 字符串格式

1
2
3
4
5
6
7
8
9
10
11
//[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
if(num==n){
List<String> temp=new ArrayList<>();
for(int i=0;i<n;i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[ans[i]] = 'Q';
temp.add(new String(row));
}
list.add(temp);
}

98. 验证二叉搜索树

1.中序遍历

排序二叉树的中序遍历是升序的。

所以可以将中序遍历输出到一个数组,再检查数组是否是升序的即可。
可以对其进行空间优化。遍历中进行判断,记录上一个节点的值,如果当前节点的值小于等于上一个节点的值,则不是二叉搜索树。

但是第一个点不是很好判断,如果设置一个初始值last=Long.MIN_VALUE, 可以解决这个问题。
也可以用一个组合节点来判断,如果是第一个就跳过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
long last = 0;//Long.MIN_VALUE;
public boolean isbigger = true;
public boolean first = true;
public boolean isValidBST(TreeNode root) {
if(root==null)return true;
boolean l = isValidBST(root.left);

if(first){first = false;}
else isbigger = isbigger && root.val > last;
//System.out.println(root.val+" "+isbigger);
last = root.val;

boolean r = isValidBST(root.right);

return isbigger;
}
}

2.递归检查

递归检查,设置上下限,递归检查左右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public boolean isValidBST(TreeNode root) {
"""
注意这里的上下限,如果是Integer.MIN_VALUE,则会导致死循环。
所以这里设置成null,表示无穷小。
其实我没有验证过,但是应该是可以的,思路是一样的。
"""
return check(root, null, null);
}
public boolean check(TreeNode root, Integer lower, Integer upper) {
if(root == null) return true;
if(lower!= null && root.val <= lower) return false;
if(upper!= null && root.val >= upper) return false;
return check(root.left, lower, root.val) && check(root.right, root.val, upper);
}
}

102. 二叉树的层序遍历

二叉树的遍历方式有很多种,深度优先搜索,广度优先搜索,层序遍历。深搜还可以分为前序遍历,中序遍历,后序遍历。广搜可以分为层序遍历,宽度遍历。

层序遍历就是先把根节点放入队列,然后依次弹出队列中的节点,并将其左右子节点放入队列,直到队列为空。

层次遍历和广搜的区别是,层序遍历是按层次遍历,广搜是按宽度遍历。
尽管都是使用队列,但是层次遍历会在每一层加入队列后停下一个间隔,记录一下这个层的宽度(通常是队列的大小),而广搜则是一次性将所有节点都加入队列,然后按宽度遍历。

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root ==null)return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
List<Integer>list =new ArrayList<>();
int Size = queue.size();
for(int i=1;i<=Size;i++) {
TreeNode temp =queue.poll();
list.add(temp.val);
if(temp.left!=null)queue.offer(temp.left);
if(temp.right!=null)queue.offer(temp.right);
}
res.add(list);
}
return res;
}
}

105. 从前序与中序遍历序列构造二叉树

也是经典题,如果能明白中序遍历和前序遍历的特点,那么这道题就很简单。

递归

很显然,中序遍历的左右子树是由根节点分开的。而前序遍历的第一个节点就是根节点。前序遍历的第二个节点到倒数第二个节点就是左子树,倒数第二个节点到最后一个节点就是右子树。

所以,我们可以先找到根节点在中序遍历中的位置,然后递归地构造左右子树。
在中序遍历中寻找根节点的算法可以使用MAP,也可以使用线性查找。

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
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return work(0,preorder.length,0,preorder.length,preorder,inorder);
}
public TreeNode work(int pl,int pr,int il,int ir,int[] preorder,int[] inorder) {
if(pl>=pr){
return null;
}
TreeNode res = null;
int val = preorder[pl];
//这里可以使用map对索引查找进行优化
for(int i=il;i<ir;i++) {
if(inorder[i]==val){
res = new TreeNode(val);
int leftsize = i - il;
//rightsize = ir - i;
//System.out.println(pl+1+" "+(pl+1+leftsize)+" "+il+" "+i);
//System.out.println(pl+1+leftsize+" "+(pr)+" "+(i+1)+" "+ir);
res.left = work(pl+1,pl+1+leftsize,il,i,preorder,inorder);
res.right = work(pl+1+leftsize,pr,i+1,ir,preorder,inorder);
//if(res.left==null) System.out.println("NULL");
//else System.out.println(res.left.val+" "+res.right.val);
}
}
return res;
}
}

迭代

没看看懂这一块

215. 数组中的第K个最大元素

1.堆排序

本来我看那个数据规模,K次找最大,复杂度就是O(K * N),10^9应该能过的,结果没有,就是复杂度还不够。

标签里有堆排序,所以用堆排序来做。(很长时间没看堆排序,所以有些生疏,在更新堆的时候搞错了边界,需要注意)

堆排序的代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Solution {
int [] heap = new int[100005];
int cur=1;
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
int ans = -1;
for(int i=0;i<len;i++){
insert(nums[i]);
}
for(int i=0;i<k;i++) {
ans = deleteTop();
}
return ans;
}
void insert(int num) {
heap[cur]=num;
int tmp = cur;
boolean flag = true;
while(flag && tmp/2>=1) {
if(heap[tmp]>heap[tmp/2]) {
swap(tmp,tmp/2);
}
else {
flag = false;
}
tmp/=2;
}
cur++;
}

int deleteTop() {
int res = heap[1];
heap[1] = heap[cur-1];
cur--;
int tmp = 1;
while(tmp*2<cur && (heap[tmp]<heap[tmp*2] || heap[tmp]<heap[tmp*2+1])) {
if(heap[tmp*2]>heap[tmp*2+1]) {
swap(tmp,tmp*2);
tmp = tmp*2;
}
else {
swap(tmp,tmp*2+1);
tmp = tmp*2+1;
}
}
return res;
}
void swap(int i,int j) {
int temp =heap[i];
heap[i]=heap[j];
heap[j]=temp;
}
}

堆排序其实很简单,只有两个操作,插入和删除。

  • 插入就往堆的末尾插入一个元素,然后从堆的最后向上更新堆。
  • 删除就是删除堆顶元素,将最后一个元素放到堆顶,然后从堆顶向下更新堆。

堆是一棵顺序存储的完全二叉树。

其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆为小根堆。反之,每个结点的关键字都不小于其孩子结点的关键字,这样的堆为大根堆。

实现起来很简单,就是维护一个数组和数据个数,然后每次插入和删除的时候,都更新堆。(更新的时候好像还可以使用递归的写法,以后再研究)

堆排序的时间复杂度是O(NlogN),N是数组的长度,logN是堆的高度。
对于本题,时间复杂度是O(NlogN),非常接近于O(N)。

2.快速选择算法

快排每次都选择一个元素作为基准,然后将比基准小的放左边,比基准大的放右边。按这个基准分割,左边的元素都比基准小,右边的元素都比基准大。这个基准的位置就不会变了,即最终的位置。在排序过程中,只要这个位置是第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
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
return qsort(nums,0,n-1,n-k);
}

int qsort(int[] nums,int l,int r,int k) {
if(l==r) return nums[k];
int x = nums[l],i = l-1,j=r+1;
while(i < j) {
do i++; while(nums[i] < x);
do j--; while(nums[j] > x);
if(i<j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}

if(k <= j)return qsort(nums,l,j,k);
else return qsort(nums,j+1,r,k);
}
}

279. 完全平方数

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4

思路

最简单的思路就是枚举所有的平方数的组合,查看是否和n相等,寻找最小的组合;
但这样会很差,很多重复的判断,很多不必要的判断。
显然,可以察觉到,尽量用大的平方数进行相加,能减少数量。

所以在使用搜索的方式时,需要从大数开始枚举,通过回溯的方式,完成对组合的枚举(然后再加一些剪枝优化)

但是,很明显有重复搜索(重叠子问题),所以可以进行记忆化搜索。
同时发现,f[n]只与f[m] (m<n)有关,满足最优子结构。
可以用动态和规划,直接进行迭代。(实际上这就是一个完全背包问题)

1.直接搜索(ai)

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.ArrayList;
import java.util.List;

class Solution {
// 全局变量记录最小数量,初始为最大值
private int minCount;

public int numSquares(int n) {
// 初始化最小数量为极大值
minCount = Integer.MAX_VALUE;

// 步骤1:收集所有不超过n的平方数(从大到小,优先选大的减少递归)
List<Integer> squares = new ArrayList<>();
for (int i = (int) Math.sqrt(n); i >= 1; i--) {
squares.add(i * i);
}

// 步骤2:回溯(起始索引0,剩余值n,已选数量0)
backtrack(squares, 0, n, 0);

return minCount;
}

/**
* 回溯核心方法
* @param squares 所有不超过n的平方数(从大到小)
* @param start 当前枚举的起始索引(避免重复组合)
* @param remain 剩余需要凑的数值
* @param count 已选的平方数数量
*/
private void backtrack(List<Integer> squares, int start, int remain, int count) {
// 剪枝1:当前数量已≥已知最小值,无需继续递归(不可能更优)
if (count >= minCount) {
return;
}

// 终止条件:剩余值为0,找到有效组合,更新最小值
if (remain == 0) {
minCount = count;
return;
}

// 枚举平方数(从start开始,避免重复组合)
for (int i = start; i < squares.size(); i++) {
int square = squares.get(i);

// 剪枝2:当前平方数超过剩余值,跳过(选了会超,无意义)
if (square > remain) {
continue;
}

// 选择当前平方数:递归(剩余值-平方数,数量+1)
backtrack(squares, i, remain - square, count + 1);
}
}
}

2.记忆化搜索

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
class Solution {
int[] memo; // 备忘录:memo[remain] = 凑出remain的最少数量
public int numSquares(int n) {
// 初始化备忘录:-1表示未计算
memo = new int[n + 1];
Arrays.fill(memo, -1);
memo[0] = 0; // 边界:0需要0个平方数
// 收集平方数
List<Integer> squares = new ArrayList<>();
for (int i = 1; i*i <= n; i++) squares.add(i*i);
// 记忆化递归
return dfs(squares, n);
}
// 递归函数:返回凑出remain的最少数量
private int dfs(List<Integer> squares, int remain) {
if (memo[remain] != -1) return memo[remain]; // 直接返回已计算的解
int minCount = Integer.MAX_VALUE;
for (int s : squares) {
if (s > remain) continue;
// 递归计算子问题:remain-s的最少数量
int subCount = dfs(squares, remain - s);
if (subCount != Integer.MAX_VALUE) {
minCount = Math.min(minCount, subCount + 1);
}
}
memo[remain] = minCount; // 记录到备忘录
return minCount;
}
}

3.动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
// 初始化:默认极大值(表示初始无法凑出)
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0; // 基础子问题

// 收集所有平方数
List<Integer> squares = new ArrayList<>();
for (int i = 1; i*i <= n; i++) squares.add(i*i);

// 从底向上计算每个j的最优解
for (int j = 1; j <= n; j++) {
for (int s : squares) {
if (j >= s) {
dp[j] = Math.min(dp[j], dp[j - s] + 1);
}
}
}
return dp[n];
}
}

这套代码的循环不太一样。具体见‘背包’中的完全背包问题

4.数学分析

奇技淫巧
根据「四平方和定理」:
任何自然数都可以表示为最多 4 个完全平方数的和。
如果 n 是 4^k*(8m+7) 形式,则必须用 4 个平方数。
否则,判断是否能由 1 个、2 个平方数组成,剩下的都是 3 个。
这种方法时间复杂度为 O(√n),远优于 DP 的 O(n√n):

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
class Solution {
public int numSquares(int n) {
// 1. 判断是否是完全平方数(1个)
if (isPerfectSquare(n)) {
return 1;
}

// 2. 判断是否是4^k*(8m+7)形式(必须4个)
while (n % 4 == 0) {
n /= 4;
}
if (n % 8 == 7) {
return 4;
}

// 3. 判断是否能由2个平方数组成
int maxBase = (int) Math.sqrt(n);
for (int i = 1; i <= maxBase; i++) {
if (isPerfectSquare(n - i * i)) {
return 2;
}
}

// 剩下的都是3个
return 3;
}

// 辅助函数:判断是否是完全平方数
private boolean isPerfectSquare(int x) {
int sqrt = (int) Math.sqrt(x);
return sqrt * sqrt == x;
}
}

这种完全背包问题,322.零钱兑换也是相似的解法

41 缺失的第一个正数

给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。

输入:nums = [1,2,0]
输出:3

输入:nums = [3,4,-1,1]
输出:2

输入:nums = [7,8,9,11,12]
输出:1

思路

  1. 朴素浅显的思路是,遍历数组,依次将每个数加入HashSet。完成后,遍历HashSet,找到最小的正整数。
    时间复杂度是O(n),空间复杂度是O(n)。

  2. 但这样会有空间上的浪费,浪费一个hashset的空间。这样就可以自己依赖原本的数组,来记录每个数是否出现过,自己实现一个hashset。但是数组是覆盖整个int范围的,没办法进行特殊标记。
    但题目要求的不是最小的数,而是最小的正整数。所以可以先过滤一遍,将所有负数和0都过滤掉,变为超出长度的数值。
    然后再遍历数组,记录每个数是否出现,将对应下标的数字变为负数,表示已经出现过。
    最后再遍历数组,找到第一个正数,该数的下标就是最小的正整数。
    (提醒,由于0不考虑在内,所以下标映射要减一)

标签: 哈希表 数组 负数 最小正整数

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 Solution {
//规定了正数,就是突破点
public int firstMissingPositive(int[] nums) {
int MAX = nums.length;

for(int i = 0;i<nums.length;i++) {
if(nums[i]<=0)nums[i]=MAX+1;
//将负数转化成超出范围的正数,这里设定为 长度+1;这样就全都是正数了,可以用负数对下标进行标记了
}

for(int i = 0;i<nums.length;i++) {
int temp = Math.abs(nums[i]);
// 负数变为正数,再判断范围,这样可以圈定1~n范围的数
// 出现过的数标记为负数(如果原本就是负数,说明已经被标记了)
if(temp <= MAX) nums[temp-1]= - Math.abs(nums[temp-1]);
}

for(int i = 0;i<nums.length;i++) {
if(nums[i]>0)return i+1;
}
//都是负数,就说明1~n都有,就返回n+1
return nums.length+1;
}
}

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。

注意:如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:”BANC”

示例 2:
输入:s = “a”, t = “a”
输出:”a”

示例 3:
输入:s = “a”, t = “aa”
输出:”aa”

思路

暴力法:枚举子串,判断是否包含t的所有字符,时间复杂度是O(n^3),空间复杂度是O(1)。

滑动窗口法:一种更简单、剪枝后的暴力法。

1
2
3
4
5
6
7
8
/*
* @lc app=leetcode.cn id=76 lang=java
*
* [76] 最小覆盖子串
*/

// @lc code=start

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

进阶:你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗?

示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

示例 3:

输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000

思路

处理边界情况的地方非常多,需要考虑到各种边界情况!
多看、多验证、多思考!

1.二分 + kth元素

找第 k 小的数,可以用二分法,时间复杂度是 O(log(min(m,n)))。

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
36
37
38
39
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int total = m + n;

if (total % 2 == 1) {
// 奇数:找第 (total+1)/2 小的数
return findKth(nums1, 0, nums2, 0, (total + 1) / 2);
} else {
// 偶数:找第 total/2 和 total/2+1 小的数的平均值
double left = findKth(nums1, 0, nums2, 0, total / 2);
double right = findKth(nums1, 0, nums2, 0, total / 2 + 1);
return (left + right) / 2.0;
}
}

// 寻找两个有序数组中第k小的数(k从1开始)
private double findKth(int[] nums1, int i, int[] nums2, int j, int k) {
// 如果nums1已经用完,直接从nums2中取
if (i >= nums1.length) return nums2[j + k - 1];
// 如果nums2已经用完,直接从nums1中取
if (j >= nums2.length) return nums1[i + k - 1];
// 如果k==1,返回两个数组当前元素的最小值
if (k == 1) return Math.min(nums1[i], nums2[j]);

// 找到两个数组中的第k/2个元素
int mid1 = (i + k/2 - 1 < nums1.length) ?
nums1[i + k/2 - 1] : Integer.MAX_VALUE;
int mid2 = (j + k/2 - 1 < nums2.length) ?
nums2[j + k/2 - 1] : Integer.MAX_VALUE;

// 比较并舍弃较小的那一半
if (mid1 < mid2) {
return findKth(nums1, i + k/2, nums2, j, k - k/2);
} else {
return findKth(nums1, i, nums2, j + k/2, k - k/2);
}
}
}

2.分割数组

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
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 确保nums1是较短的数组,简化逻辑
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}

int m = nums1.length, n = nums2.length;
int totalLeft = (m + n + 1) / 2; // 分割线左边应该有多少个元素

// 在nums1中二分查找合适的分割线
int left = 0, right = m;

while (left < right) {
// i: nums1中分割线右边的第一个元素下标
// j: nums2中分割线右边的第一个元素下标
int i = left + (right - left + 1) / 2;
int j = totalLeft - i;

if (nums1[i - 1] > nums2[j]) {
// 分割线需要左移
right = i - 1;
} else {
left = i;
}
}

int i = left;
int j = totalLeft - i;

// 处理边界情况
int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];

if ((m + n) % 2 == 1) {
// 奇数:中位数在分割线左边
return Math.max(nums1LeftMax, nums2LeftMax);
} else {
// 偶数:中位数是左右两边的平均值
return (Math.max(nums1LeftMax, nums2LeftMax) +
Math.min(nums1RightMin, nums2RightMin)) / 2.0;
}
}
}

下一个排列

分三步

  1. 从右往左找到第一个升序对(i, j),(i+1=j && nums[i] < nums[j]),如果没有,即是最后一个排列,直接反转整个数组得到第一个排列。
  2. 从右往左找到第一个比i位置的数大的位置,交换i, k(k有可能是在i的左边)。
  3. 反转j位置到末尾的部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length, i = n - 2, j = n - 1, k = n - 1;
while (i >= 0 && nums[i] >= nums[j]) { i--; j--; }
if (i >= 0) {
while (nums[k] <= nums[i]) k--;
swap(nums, i, k);
}
reverse(nums, j);
}
private void swap(int[] a, int l, int r) {
int t = a[l]; a[l] = a[r]; a[r] = t;
}
private void reverse(int[] a, int start) {
for (int l = start, r = a.length - 1; l < r; l++, r--) swap(a, l, r);
}
}