Nreal
2023-11-24
目录

面试高频题

# 滑动窗口

# 3. 无重复字符的最长子串 (opens new window)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] window = new int[256];
        int l=0,r=0;
        int ans = 0;
        while(r<s.length()){
            char c1 = s.charAt(r++);
            window[c1]++;
            while(window[c1]>1){
                char c2 = s.charAt(l++);
                window[c2]--;
            }
            ans = Math.max(ans,r-l);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 76. 最小覆盖子串 (opens new window)

# 567. 字符串的排列 (opens new window)

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        Map<Character,Integer> window = new HashMap<>();
        Map<Character,Integer> need = new HashMap<>();
        for(int i=0;i<s1.length();i++){
            char c1 = s1.charAt(i);
            need.put(c1,need.getOrDefault(c1,0)+1);
        }
        int l=0,r=0;
        int cnt=0;//记录need元素种类
        while(r<s2.length()){
            char c1 = s2.charAt(r++);
            if(need.containsKey(c1)){
                window.put(c1,window.getOrDefault(c1,0)+1);
                if(window.get(c1).equals(need.get(c1))){
                    cnt++;
                }
            }
            while(r-l==s1.length()){
                if(cnt==need.size()){
                    return true;
                }
                char c2 = s2.charAt(l++);
                if(need.containsKey(c2)){
                    if(window.get(c2).equals(need.get(c2))){
                        cnt--;
                    }
                    window.put(c2,window.get(c2)-1);
                }
            }
        }
        return false;
    }
}
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

# 哈希表

# 146. LRU 缓存 (opens new window)

class LRUCache {
    int cap;
    LinkedHashMap<Integer,Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) {
        this.cap = capacity;
    }
    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }
        makeRecent(key);
        return cache.get(key);
    }
    public void put(int key, int value) {
        if(cache.containsKey(key)){
            cache.put(key,value);
            makeRecent(key);
            return ;
        }
        //将最久未使用的删除
        if(cache.size()>=cap){
            int oldKey = cache.keySet().iterator().next();
            cache.remove(oldKey);
        }
        cache.put(key,value);
    }
    void makeRecent(int key){
        int val = cache.get(key);
        cache.remove(key);
        cache.put(key,val);//头插？
    }
}
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

# 1. 两数之和 (opens new window)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            int tmp = target-nums[i];
            if(map.containsKey(tmp)){
                res[0] = map.get(tmp);
                res[1] = i;
            }
            map.put(nums[i],i);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 560. 和为 K 的子数组 (opens new window)

# 128. 最长连续序列 (opens new window)

# 49. 字母异位词分组 (opens new window)

# 41. 缺失的第一个正数 (opens new window)

原地哈希

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i=0;i<n;i++){
            //在数组长度范围内的正数
            while(nums[i]>0 && nums[i]<n && nums[nums[i]-1]!=nums[i]){
                //3放在索引2位置上
                swap(nums,nums[i]-1,i);
            }
        }
        // [1, -1, 3, 4]
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return n+1;
    }
    void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 堆

# 215. 数组中的第K个最大元素 (opens new window)

法一：快排

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int l=0,r=nums.length-1;
        k = nums.length-k;
        while(l<=r){
            int p = partition(nums,l,r);
            if(p<k) l=p+1;
            else if(p>k) r=p-1;
            else return nums[p];
        }
        return -1;
    }
    int partition(int[] nums,int l,int r){
        int base = nums[r];
        int i=l;
        for(int j=l;j<r;j++){
            if(nums[j]<base){
                swap(nums,i,j);
                i++;
            }
        }
        swap(nums,i,r);
        return i;
    }
    void swap(int[] nums,int l,int r){
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }
}
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

法二：优先级队列

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer>pq = new PriorityQueue<>();
        for(int num:nums){
            pq.offer(num);
            if(pq.size()>k){
                pq.poll();
            }
        }
        return pq.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

# 347. 前 K 个高频元素 (opens new window)

# 295. 数据流的中位数 (opens new window)

# 双指针

# 283. 移动零 (opens new window)

class Solution {
    public void moveZeroes(int[] nums) {
        int l = remove(nums,0);
        for(int i=l;i<nums.length;i++){
            nums[i] = 0;
        }
        return ;
    }
    int remove(int[] nums,int v){
        int l=0,r=0;
        while(r<nums.length){
            if(nums[r]!=v){
                nums[l] = nums[r];
                l++;
            }
            r++;
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 15. 三数之和 (opens new window)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0) return res;
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int l=i+1;
            int r=nums.length-1;
            while(l<r){
                int sum = nums[i]+nums[l]+nums[r];
                if(sum>0) r--;
                else if(sum<0) l++;
                else{
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    while(r>l && nums[r]==nums[r-1]){
                        r--;
                    }
                    while(r>l && nums[l]==nums[l+1]){
                        l++;
                    }
                    l++;r--;
                }
            }
        }
        return res;
    }
}
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

# 11. 盛最多水的容器 (opens new window)

class Solution {
    public int maxArea(int[] height) {
        int ans = 0,l = 0,r = height.length-1;
        int area = 0;
        while(l<r){
            area = (r-l)*Math.min(height[l],height[r]);
            ans = Math.max(area,ans);
            //找到高瘦
            if(height[l]<height[r]){
                l++;
            }else{
                r--;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 42. 接雨水 (opens new window)

# 链表

# 25. K 个一组翻转链表 (opens new window)

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int n = 0;
        for(ListNode cur = head;cur!=null;cur = cur.next){
            n++;
        }
        ListNode dummy = new ListNode(0,head),p0 = dummy;
        ListNode pre = null,cur = head;
        for(;n>=k;n-=k){
            for(int i=0;i<k;i++){
                ListNode nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }
            ListNode nxtdummy = p0.next;//p0.next为反转后链表的尾节点，下一段的虚拟头节点
            p0.next.next = cur;//翻转前链表的头节点指向下一段的头节点
            p0.next = pre;//反转后链表的头节点
            p0 = nxtdummy;
        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 92. 反转链表 II (opens new window)

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1,head);
        ListNode p = dummy;
        for(int i=0;i<left-1;i++){
            p = p.next;
        }
        ListNode right_bound = p;
        for(int i=0;i<right-left+1;i++){
            right_bound = right_bound.next;
        }
        ListNode left_bound = p.next;
        ListNode right_head = right_bound.next;
        //切断
        p.next = null;
        right_bound.next = null;
        reverse(left_bound);
        p.next = right_bound;
        left_bound.next = right_head;
        return dummy.next;
    }
    void reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
    }
}
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

# 148. 排序链表 (opens new window)

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode midNode = getMid(head);
        ListNode rightHead = midNode.next;
        midNode.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);
        return merge(left,right);
    }
    ListNode getMid(ListNode head){
        if(head.next==null || head.next.next==null){
            return head;
        }
        ListNode slow=head,fast=head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    ListNode merge(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        if(l1.val<l2.val){
            l1.next = merge(l1.next,l2);
            return l1;
        }else{
            l2.next = merge(l1,l2.next);
            return l2;
        }
    }
}
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

# 21. 合并两个有序链表 (opens new window)

法一：模拟

class Solution {
    public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while(p1!=null&&p2!=null){
            if(p1.val>p2.val){
                p.next = p2;
                p2 = p2.next;
            }else{
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }
        if(p1!=null) p.next=p1;
        if(p2!=null) p.next=p2;
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

法二：递归

ListNode mergeTwoLists(ListNode l1,ListNode l2){
    if(l1==null) return l2;
    if(l2==null) return l1;
    if(l1.val<l2.val){
        l1.next = mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l1,l2.next);
        return l2;
    }
}
1
2
3
4
5
6
7
8
9
10
11

# 23. 合并 K 个升序链表 (opens new window)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0 || lists==null) return null;
        return merge(lists,0,lists.length-1);
    }
    ListNode merge(ListNode[] lists,int l,int r){
        if(l==r) return lists[l];
        int mid = l+(r-l)/2;
        ListNode l1 = merge(lists,l,mid);
        ListNode l2 = merge(lists,mid+1,r);
        return mergeTwo(l1,l2);
    }
    ListNode mergeTwo(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        if(l1.val<l2.val){
            l1.next = mergeTwo(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwo(l1,l2.next);
            return l2;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 143. 重排链表 (opens new window)

class Solution {
    public void reorderList(ListNode head) {
        ListNode mid = getMid(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null;
        l2 = reverse(l2);
        merge(l1,l2);
    }
    ListNode getMid(ListNode head){
        ListNode slow = head,fast = head;
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    ListNode reverse(ListNode head){
        ListNode pre = null,cur = head;
        while(cur!=null){
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
    void merge(ListNode l1,ListNode l2){
        ListNode l1_nxt,l2_nxt;
        while(l1!=null && l2!=null){
            l1_nxt = l1.next;
            l2_nxt = l2.next;
            l1.next = l2;
            l1 = l1_nxt;
            l2.next = l1;
            l2 = l2_nxt;
        }
    }
}
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

# 142. 环形链表 II (opens new window)

# 19. 删除链表的倒数第 N 个结点 (opens new window)

# 82. 删除排序链表中的重复元素 II (opens new window)

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-1,head);
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur!=null){
            ListNode nxt = cur.next;
            while(nxt!=null && nxt.val==cur.val){
                nxt = nxt.next;
            }
            //相邻节点不同，步进
            if(cur.next==nxt){
                pre = cur;
                cur = nxt;
            }else{
                pre.next = nxt;
                cur = nxt;
            }
        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 2. 两数相加 (opens new window)

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        int carry = 0;
        while(l1!=null || l2!=null){
            int x = (l1==null?0:l1.val);
            int y = (l2==null?0:l2.val);
            int sum = x+y+carry;
            carry = sum/10;
            sum %= 10;
            p.next = new ListNode(sum);
            p = p.next;
            if(l1!=null) l1 = l1.next;
            if(l2!=null) l2 = l2.next;
        }
        if(carry == 1){
            p.next = new ListNode(1);
        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 24. 两两交换链表中的节点 (opens new window)

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1,head);
        ListNode p = dummy;
        while(p.next!=null && p.next.next!=null){
            ListNode tmp = head.next.next;
            p.next = head.next;
            head.next.next = head;
            head.next = tmp;
            //步进
            p = head;
            head = head.next;
        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归法：

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        ListNode p3 = head.next.next;
        p2.next = p1;
        p1.next = swapPairs(p3);
        return p2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 动态规划

# 53. 最大子数组和 (opens new window)

记忆化搜索

class Solution {
    int[] memo;
    int[] nums;
    public int maxSubArray(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        memo = new int[n];
        int ans = nums[0];
        //不一定以n结尾的连续子数组就是最大
        for(int i=1;i<n;i++){
            ans = Math.max(ans,dfs(i));
        }
        return ans;
    }
    //i结尾的连续子数组最大和
    int dfs(int i){
        if(i<0) return 0;
        if(memo[i]!=0) return memo[i];
        memo[i] = Math.max(dfs(i-1)+nums[i],nums[i]);
        return memo[i];
    }
}
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 maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ans = nums[0];
        for(int i=1;i<n;i++){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            ans = Math.max(dp[i],ans);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

优化空间

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0],pre = nums[0];
        for(int i=1;i<nums.length;i++){
            //之前的最大值与另起炉灶的值选最大
            pre = Math.max(pre+nums[i],nums[i]);
            res = Math.max(pre,res);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

# 300. 最长递增子序列 (opens new window)

记忆化搜索：

class Solution {
    int[] nums;
    int[] memo;
    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        int n= nums.length;
        this.memo = new int[n];
        Arrays.fill(memo,1);
        int ans = 0;
        for(int i=0;i<n;i++){
            ans = Math.max(ans,dfs(i));
        }
        return ans;
    }
    //以i结尾的最长递增子序列
    int dfs(int i){
        if(i==0) return 1;
        if(memo[i]!=1){
            return memo[i];
        }
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){
                memo[i] = Math.max(memo[i],dfs(j)+1);
            }
        }
        return memo[i];
    }
}
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

动态规划：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n= nums.length;
        int ans = 1;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        for(int i=0;i<n;i++){
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 5. 最长回文子串 (opens new window)

记忆化搜索：

class Solution {
    Boolean[][] memo;
    String s;
    public String longestPalindrome(String s) {
        this.s = s;
        int n = s.length();
        this.memo = new Boolean[n][n];
        String ans = "";
        for(int i=0;i<s.length();i++){
            for(int j=i;j<s.length();j++){
                if(dfs(i,j) && j-i+1>ans.length()){
                    ans = s.substring(i,j+1);
                }
            }
        }
        return ans;
    }
    boolean dfs(int i,int j){
        if(i==j) return true;
        if(i+1==j){
            return s.charAt(i)==s.charAt(j);
        }
        if(memo[i][j]!=null) return memo[i][j];
        boolean res = false;
        if(s.charAt(i)==s.charAt(j)){
            res = dfs(i+1,j-1);
        }
        return memo[i][j]=res;
    }
}
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

动态规划：

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int[] res = new int[2];
        boolean[][] dp = new boolean[n][n];
        for(int i=0;i<n;i++){
            dp[i][i] = true;
        }
        for(int i=n-2;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(s.charAt(i)==s.charAt(j)){
                    if(j-i==1){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }else{
                    dp[i][j] = false;
                }
                //更新结果
                if(dp[i][j]){
                    if(res[1]-res[0]<=j-i){
                        res[0] = i;
                        res[1] = j;
                    }
                }
            }
        }
        return s.substring(res[0],res[1]+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

# 72. 编辑距离 (opens new window)

# 1143. 最长公共子序列 (opens new window)

记忆化搜索：

class Solution {
    char[] s;
    char[] t;
    int[][] memo;
    public int longestCommonSubsequence(String text1, String text2) {
        this.s = text1.toCharArray();
        this.t = text2.toCharArray();
        int m = s.length;
        int n = t.length;
        this.memo  = new int[m][n];
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }
        return dfs(m-1,n-1);
    }
    int dfs(int i,int j){
        if(i<0||j<0) return 0;
        if(memo[i][j]!=-1) return memo[i][j];
        if(s[i]==t[j]){
            return memo[i][j] = dfs(i-1,j-1)+1;
        }else{
            return memo[i][j] = Math.max(dfs(i-1,j),dfs(i,j-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

动态规划：

class Solution {
    public int longestCommonSubsequence(String t1, String t2) {
        int m = t1.length();
        int n = t2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(t1.charAt(i) == t2.charAt(j)){
                    dp[i+1][j+1] = dp[i][j]+1;
                }else{
                    dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 322. 零钱兑换 (opens new window)

记忆化搜索：

class Solution {
    int[] coins;
    int[][] memo;
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        this.coins = coins;
        this.memo = new int[n+1][amount+1];
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }
        int ans = dfs(n-1,amount);
        return ans<Integer.MAX_VALUE/2?ans:-1;
    }
    int dfs(int i,int c){
        if(i<0){
            return c==0?0:Integer.MAX_VALUE/2;
        }
        if(memo[i][c]!=-1){
            return memo[i][c];
        }
        if(c<coins[i]){
            return memo[i][c] = dfs(i-1,c);
        }else{
            return memo[i][c] = Math.min(dfs(i-1,c),dfs(i,c-coins[i])+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

动态规划：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        Arrays.fill(dp[0],Integer.MAX_VALUE/2);
        dp[0][0] = 0;
        for(int i=0;i<n;i++){
            for(int c=0;c<=amount;c++){
                if(c<coins[i]){
                    dp[i+1][c] = dp[i][c];
                }else{
                    dp[i+1][c] = Math.min(dp[i][c],dp[i+1][c-coins[i]]+1);
                }
            }
        }
        int ans = dp[n][amount];
        return ans<Integer.MAX_VALUE/2?ans:-1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 121. 买卖股票的最佳时机 (opens new window)

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = -prices[0];//买
        dp[0][1] = 0;//卖
        for(int i=1;i<n;i++){
            dp[i][0] = Math.max(dp[i-1][0],-prices[i]);//寻找买最小价格
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[n-1][1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for(int i=0;i<prices.length;i++){
            if(prices[i]<minPrice){
                minPrice = prices[i];
            }else if(prices[i]-minPrice>maxProfit){
                maxProfit = prices[i]-minPrice;
            }
        }
        return maxProfit;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 139. 单词拆分 (opens new window)

# 数组

# 75. 颜色分类 (opens new window)

参考：75. 颜色分类 - 力扣（LeetCode） (opens new window)

循环不变量写法一：

nums中：

  • [0,l) = 0 保证初始化为空，l=0，遍历到 0时先交换再加
  • [l,i] = 1
  • [r,n-1] = 2 保证初始化为空，r=n，遍历到 2时先减再交换

循环终止条件 i==r，循环可以继续条件：i<r

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        if(n<2) return ;
        int l=0,r=n;
        int i=0;
        while(i<r){
            if(nums[i]==0){
                swap(nums,i,l);
                l++;
                i++;
            }else if(nums[i]==1){
                i++;
            }else{
                r--;
                swap(nums,i,r);
            }
        }
    }
    void swap(int[] nums,int l,int r){
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }
}
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

循环不变量写法二：

nums中：

  • [0,l] = 0 保证初始化为空，l=-1，遍历到 0时先加再交换
  • (l,i) = 1
  • (r,n-1] = 2 保证初始化为空，r=n-1，遍历到 2时先交换再减

循环终止条件 i==r+1，循环继续条件：i<=r

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        if(n<2) return ;
        int l=-1,r=n-1;
        int i=0;
        while(i<=r){
            if(nums[i]==0){
                l++;
                swap(nums,i,l);
                i++;
            }else if(nums[i]==1){
                i++;
            }else{
                swap(nums,i,r);
                r--;
            }
        }
    }
    void swap(int[] nums,int l,int r){
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }
}
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

# 88. 合并两个有序数组 (opens new window)

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m-1;
        int p2 = n-1;
        //从后向前
        while(p1>=0 && p2>=0){
            nums1[p1+p2+1] = nums1[p1]<=nums2[p2]?nums2[p2--]:nums1[p1--];
        }
        while(p2>=0){
            nums1[p1+p2+1] = nums2[p2--];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 912. 排序数组 (opens new window)

冒泡排序

class Solution {
    int[] nums;
    public int[] sortArray(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        for(int j=n-1;j>0;j--){
            for(int i=0;i<j;i++){
                if(nums[i]>nums[i+1]){
                    swap(i,i+1);
                }
            }
        }
        return nums;
    }
    void swap(int l,int r){
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

快速排序

时间复杂度：O(nlogn)~O(n^2)

当前区间内选择一个轴，区间中所有比轴小的数放到比轴的左边，大的放到轴右边；

  • 最理想情况，选取的轴刚好在这个区间的中位数，就与归并排序一致；
  • 最差情况，每次选取的轴刚好是最大值或最小值，每轮排序都需要进行n次比较，每次时间复杂度为O(n)，总时间复杂度为O(n^2)；
class Solution {
    int[] nums;
    public int[] sortArray(int[] nums) {
        this.nums = nums;
        if(nums==null || nums.length<2)
            return nums;
        shuffle();
        quickSort(0,nums.length-1);
        return nums;
    }
    void quickSort(int l,int r){
        if(l>r) return ;
        int p = partition(l,r);
        quickSort(l,p-1);
        quickSort(p+1,r);
    }
    int partition(int l,int r){
        int base = nums[r];
        int i = l;
        for(int j=l;j<r;j++){
            if(nums[j]<base){
                swap(i,j);
                i++;
            }
        }
        swap(i,r);
        return i;
    }
    void shuffle(){
        Random rand = new Random();
        int n = nums.length;
        for(int i=0;i<n;i++){
            int r = i+rand.nextInt(n-i);
            swap(i,r);
        }
    }
    void swap(int l,int r){
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }
}
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

归并排序

时间复杂度：O(nlogn)，稳定

分治思想，每次将区间对半划分，直到长度为1；然后将相邻两个子区间进行合并;

每一层的时间复杂度为O(n)，共有logn层，总时间复杂度为O(nlogn)；

class Solution {
    int[] nums;
    public int[] sortArray(int[] nums) {
        this.nums = nums;
        if(nums==null || nums.length<2)
            return nums;
        sort(0,nums.length-1);
        return nums;
    }
    void sort(int l,int r){
        if(l==r) return ;
        int mid = l+(r-l)/2;
        sort(l,mid);
        sort(mid+1,r);
        merge(l,mid,r);
    }
    void merge(int l,int m,int r){
        int[] tmp = new int[r-l+1];
        int i=0;
        int p1=l;
        int p2=m+1;
        while(p1<=m && p2<=r){
            tmp[i++] = nums[p1]<=nums[p2]?nums[p1++]:nums[p2++];
        }
        while(p1<=m){
            tmp[i++] = nums[p1++];
        }
        while(p2<=r){
            tmp[i++] = nums[p2++];
        }
        for(i=0;i<tmp.length;i++){
            nums[l+i] = tmp[i];
        }
    }
}
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

# 4. 寻找两个正序数组的中位数 (opens new window)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length,n = nums2.length;
        int[] nums = new int[m+n];
        int i=0,j=0,k=0;
        while(i<m && j<n){
            nums[k++] = nums1[i]<=nums2[j]?nums1[i++]:nums2[j++];
        }
        while(i<m){
            nums[k++] = nums1[i++];
        }
        while(j<n){
            nums[k++] = nums2[j++];
        }
        if(k%2==0){
            return (nums[k/2-1]+nums[k/2])/2.0;
        }else{
            return nums[k/2];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 56. 合并区间 (opens new window)

class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        res.add(intervals[0]);
        for(int i=1;i<intervals.length;i++){
            int[] last = res.getLast();
            int[] cur = intervals[i];
            if(cur[0]<=last[1]){
                last[1] = Math.max(cur[1],last[1]);
            }else{
                res.add(cur);
            }
        }
        return res.toArray(new int[0][0]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 4. 寻找两个正序数组的中位数 (opens new window)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length,n = nums2.length;
        int[] nums = new int[m+n];
        int i=0,j=0,k=0;
        while(i<m && j<n){
            nums[k++] = nums1[i]<=nums2[j]?nums1[i++]:nums2[j++];
        }
        while(i<m){
            nums[k++] = nums1[i++];
        }
        while(j<n){
            nums[k++] = nums2[j++];
        }
        if(k%2==0){
            return (nums[k/2-1]+nums[k/2])/2.0;
        }else{
            return nums[k/2];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 31. 下一个排列 (opens new window)

# 189. 轮转数组 (opens new window)

方法一：创建新数组

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] tmp = new int[n];
        for(int i=0;i<n;i++){
            tmp[(i+k)%n] = nums[i];
        }
        System.arraycopy(tmp,0,nums,0,n);
    }
}
1
2
3
4
5
6
7
8
9
10

方法二：环形数组

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int cnt = 0;
        int start = 0;
        while(cnt<n){
            int cur_idx = start;
            int cur_ele = nums[start];
            do{
                int nxt_idx = (cur_idx+k)%n;
                int tmp = nums[nxt_idx];
                nums[nxt_idx] = cur_ele; 
                cur_ele = tmp;
                cur_idx = nxt_idx;
                cnt++;
            }while(cur_idx!=start);
            start++;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法三：三次反转

nums = "----->-->"; k =3
result = "-->----->";

reverse "----->-->" we can get "<--<-----"
reverse "<--" we can get "--><-----"
reverse "<-----" we can get "-->----->"
1
2
3
4
5
6
class Solution {
    public void rotate(int[] nums, int k) {
        k = k%nums.length;
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);
    }
    void reverse(int[] nums,int a,int b){
        int i=a,j=b;
        while(i<j){
            int t=nums[i];
            nums[i]=nums[j];
            nums[j]=t;
            i++;
            j--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 240. 搜索二维矩阵 II (opens new window)

# 73. 矩阵置零 (opens new window)

# 二分

# 153. 寻找旋转排序数组中的最小值 (opens new window)

class Solution {
    public int findMin(int[] nums) {
        //最右侧要么最小值，要么在最右侧的左侧
        int n = nums.length;
        int l=0,r=n-1;
        while(l<r){
            int mid = l+(r-l)/2;
            if(nums[mid]<nums[r]){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return nums[l];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 162. 寻找峰值 (opens new window)

class Solution {
    public int findPeakElement(int[] nums) {
        //nums[nums.length-1]一定是蓝色
        int l=0,r=nums.length-2;
        while(l<=r){
            int m = l+(r-l)/2;
            if(nums[m]>nums[m+1]){
                r=m-1;//m为峰值，或峰值在m左侧，m蓝色
            }else{
                l=m+1;
            }
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 33. 搜索旋转排序数组 (opens new window)

# 34. 在排序数组中查找元素的第一个和最后一个位置 (opens new window)

# 287. 寻找重复数 (opens new window)

# 回溯

# 200. 岛屿数量 (opens new window)

# 46. 全排列 (opens new window)

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] vis;
    int[] nums;
    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        this.vis = new boolean[nums.length];
        dfs(0);
        return res;
    }
    void dfs(int i){
        if(path.size()==nums.length){
            res.add(new ArrayList<>(path));
        }
        for(int j=0;j<nums.length;j++){
            if(vis[j]){
                continue;
            }
            vis[j] = true;
            path.add(nums[j]);
            dfs(j+1);
            path.remove(path.size()-1);
            vis[j] = false;
        }
    }
}
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

# 78. 子集 (opens new window)

# 93. 复原 IP 地址 (opens new window)

# 22. 括号生成 (opens new window)

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(new StringBuilder(),n,n);
        return res;
    }
    void dfs(StringBuilder sb,int l,int r){
        if(l==0&&r==0){
            res.add(sb.toString());
            return ;
        }
        if(l<0||r<0) return;
        if(l>r) return ;
        //选(
        sb.append('(');
        dfs(sb,l-1,r);
        sb.deleteCharAt(sb.length()-1);
        //选)
        sb.append(')');
        dfs(sb,l,r-1);
        sb.deleteCharAt(sb.length()-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 131. 分割回文串 (opens new window)

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    String s;
    public List<List<String>> partition(String s) {
        this.s = s;
        dfs(0);
        return res;
    }
    void dfs(int i){
        if(i==s.length()){
            res.add(new ArrayList<>(path));
            return ;
        }
        for(int j=i;j<s.length();j++){
            if(helper(s,i,j)){
                String tmp = s.substring(i,j+1);
                path.add(tmp);
            }else{
                continue;
            }
            dfs(j+1);
            path.remove(path.size()-1);
        }
    }
    boolean helper(String s,int l,int r){
        while(l<r){
            if(s.charAt(l)!=s.charAt(r)){
                return false;
            }
            l++;r--;
        }
        return true;
    }
}
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

# 树

# 104. 二叉树的最大深度 (opens new window)

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        return Math.max(l,r)+1;
    }
}
1
2
3
4
5
6
7
8

# 543. 二叉树的直径 (opens new window)

class Solution {
    int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }
    //返回root为根的子树最大深度
    int dfs(TreeNode root){
        if(root==null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        ans = Math.max(ans,left+right);//更新直径
        return 1+Math.max(left,right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 124. 二叉树中的最大路径和 (opens new window)

class Solution {
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root==null) return 0;
        dfs(root);
        return ans;
    }
    //返回root为起点的最大单枝和
    int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int left = Math.max(0,dfs(root.left));
        int right = Math.max(0,dfs(root.right));
        ans = Math.max(ans,root.val+left+right);
        return root.val+Math.max(left,right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 226. 翻转二叉树 (opens new window)

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return null;
        TreeNode l = invertTree(root.left);
        TreeNode r = invertTree(root.right);
        root.left = r;
        root.right = l;
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10

# 101. 对称二叉树 (opens new window)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return dfs(root.left,root.right);
    }
    boolean dfs(TreeNode lt,TreeNode rt){
        if(lt==null && rt==null){
            return true;
        }
        if(lt!=null&&rt==null || lt==null&&rt!=null){
            return false;
        }
        if(lt.val!=rt.val){
            return false;
        }
        boolean outside = dfs(lt.left,rt.right);
        boolean inside = dfs(lt.right,rt.left);
        return outside&&inside;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 236. 二叉树的最近公共祖先 (opens new window)

参考：Krahets (opens new window)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q){
            return root;
        }
        TreeNode lt = lowestCommonAncestor(root.left,p,q);
        TreeNode rt = lowestCommonAncestor(root.right,p,q);
        if(lt!=null && rt!=null){
            return root;
        }
        return lt!=null?lt:rt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 437. 路径总和 III (opens new window)

class Solution {
    int ans;
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null) return 0;
        dfs(root,targetSum);
        // 以左右子树做根节点
        pathSum(root.left,targetSum);
        pathSum(root.right,targetSum);
        return ans;
    }
    // 以根节点开始，到targetSum=0多少种路径
    void dfs(TreeNode root,long targetSum){
        if(root==null) return ;
        targetSum -= root.val;
        if(targetSum==0) ans++;
        dfs(root.left,targetSum);
        dfs(root.right,targetSum);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

记录路径和：

class Solution {
    //记录curSum出现的次数
    Map<Long,Integer> map = new HashMap<>();
    public int pathSum(TreeNode root, int targetSum) {
        map.put(0L,1);
        return dfs(root,targetSum,0L);
    }
    int dfs(TreeNode root,int targetSum,Long curSum){
        if(root==null) return 0;
        int ans = 0;
        curSum += root.val;
        //当targetSum=8,map中已记录了(10,1)，如果能找到一条路径和curSum为18，更新一次结果；
        ans += map.getOrDefault(curSum-targetSum,0);

        map.put(curSum,map.getOrDefault(curSum,0)+1);
        ans += dfs(root.left,targetSum,curSum);
        ans += dfs(root.right,targetSum,curSum);
        map.put(curSum,map.get(curSum)-1);
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 103. 二叉树的锯齿形层序遍历 (opens new window)

# 105. 从前序与中序遍历序列构造二叉树 (opens new window)

# 114. 二叉树展开为链表 (opens new window)

# 108. 将有序数组转换为二叉搜索树 (opens new window)

# 230. 二叉搜索树中第K小的元素 (opens new window)

# 208. 实现 Trie (前缀树) (opens new window)

# 栈&队列

# 20. 有效的括号 (opens new window)

# 32. 最长有效括号 (opens new window)

# 232. 用栈实现队列 (opens new window)

# 155. 最小栈 (opens new window)

# 239. 滑动窗口最大值 (opens new window)

# 32. 最长有效括号 (opens new window)

# 394. 字符串解码 (opens new window)

# 字符串

# 415. 字符串相加 (opens new window)

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int i= num1.length()-1;
        int j= num2.length()-1;
        int carry = 0;
        while(i>=0 || j>=0){
            int n1 = i>=0?num1.charAt(i)-'0':0;
            int n2 = j>=0?num2.charAt(j)-'0':0;
            int sum = n1+n2+carry;
            carry = sum/10;
            sb.append(sum%10);
            i--;
            j--;
        }
        if(carry==1){
            sb.append(1);
        }
        return sb.reverse().toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 43. 字符串相乘 (opens new window)

# 8. 字符串转换整数 (atoi) (opens new window)

# 165. 比较版本号 (opens new window)

# 151. 反转字符串中的单词 (opens new window)

# 179. 最大数 (opens new window)

# 贪心

# 55. 跳跃游戏 (opens new window)

方法一：贪心

class Solution {
    public boolean canJump(int[] nums) {
        int cover = 0;
        for(int i=0;i<=cover;i++){
            //更新最远距离
            cover = Math.max(i+nums[i],cover);
            if(cover>=nums.length-1){
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

方法二：动态规划

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length==1) return true;
        if(nums[0]==0) return false;
        //i点之前能跳的最远距离
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i=1;i<nums.length-1;i++){
            dp[i] = Math.max(dp[i-1],i+nums[i]);
            if(dp[i]>=nums.length-1) return true;
            if(dp[i]==i) return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

定义状态2：

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        //定义是否能跳到该位置
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(dp[j] && (i-j)<=nums[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 45. 跳跃游戏 II (opens new window)

方法一：贪心

class Solution {
    public int jump(int[] nums) {
        int end=0,cover=0;
        int steps=0;
        //每一步更新最远跳跃距离，当到达end，加一步
        for(int i=0;i<nums.length-1;i++){
            cover = Math.max(cover,i+nums[i]);
            if(i==end){
                end = cover;
                steps++;
            }
        }
        return steps;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法二：动态规划

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,Integer.MAX_VALUE/2);
        dp[0] = 0;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(i-j<=nums[j]){
                    dp[i] = Math.min(dp[j]+1,dp[i]);
                }
            }
        }
        return dp[n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 763. 划分字母区间 (opens new window)

二叉树
hot100

← hot100→

Theme by Vdoing | Copyright © 2021-2024