Leetcode HOT面试题目2

面试二轮

76. 最小覆盖子串(x)

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

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
class Solution{
    public String minWindow(String S, String t) {
        int[] cnt = new int[128];
        int less = 0;
        for (char c:t.toCharArray()){
            if (cnt[c]==0){
                less++;
            }
            cnt[c]++;
        }
        char[] s = S.toCharArray();
        int m  = s.length;
        int ansleft  = -1;
        int ansRight = m;
        
        int left =0;
        for (int right = 0;right<m;right++){
            char c =s[right];
            cnt[c]--;
            if (cnt[c]==0){
                less--;
            }
            while (less==0){
                if (right-left<ansRight-ansleft){
                    ansleft = left;
                    ansRight = right;
                }
                char x = s[left];
                if (cnt[x]==0){
                    less++;
                }
                cnt[x]++;
                left++;
            }
        }
        return ansleft<0?"":S.substring(ansleft,ansRight+1);
    }
}

代码使用了滑动窗口的方法，一看他是个window就是滑动窗口

解决思路是进-改-出

先区遍历元素，然后确定要出现的最少的次数

然后进右端端点，需要的出现次数—

然后最少字母次数—

当最小次数为0的时候，这个时候如果滑动窗口的长度小于结果的长度的时候

更新节点位置

然后出左节点，如果需要出现的为0了

那么最少字母次数++

然后左端点对应的字母需要次数++，左端点移动

最后需要的是结果左端点和右端点之间的

也就是我们常说的right-left+1

124. 二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

就是一个贪心算法，我们每一步都选dfs的最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution124A {
    private int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }
    private int dfs(TreeNode root){
        if (root==null){
            return 0;
        }
        int lval = dfs(root.left);
        int rval  =dfs(root.right);
        ans  = Math.max(ans,lval+rval+root.val);
        return Math.max(Math.max(lval,rval)+ root.val,0);
    }
}

就是选左还是选右的问题

208. 实现 Trie (前缀树)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 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
35
class Trie{
    private static class Node{
        Node[] son = new Node[26];
        boolean end;
    }
    private final Node root = new Node();
    public void insert(String word) {
        Node cur = root;
        for (char c:word.toCharArray()){
            c -='a';
            if (cur.son[c]==null){
                cur.son[c] = new Node();
            }
            cur = cur.son[c];
        }
        cur.end = true;
    }
    public boolean search(String word) {
        return find(word)==2;
    }
    public boolean startsWith(String prefix) {
        return find(prefix)!=0;
    }
    private int find(String word){
        Node cur = root;
        for (char c:word.toCharArray()){
            c-='a';
            if(cur.son[c]==null){
                return 0;
            }
            cur = cur.son[c];
        }
        return cur.end?2:1;
    }
}

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder()初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

  • -105 <= num <= 105
  • 在调用 findMedian 之前，数据结构中至少有一个元素
  • 最多 5 * 104 次调用 addNum 和 findMedian
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
class MedianFinder {
    private final PriorityQueue<Integer> left = new PriorityQueue<>((a,b)->b-a);
    private final PriorityQueue<Integer> right = new PriorityQueue<>();


    public MedianFinder() {

    }

    public void addNum(int num) {
        if (left.size()==right.size()){
            right.offer(num);
            left.offer(right.poll());
        }else {
            left.offer(num);
            right.offer(left.poll());
        }
    }

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

我们维护一个最大堆left和一个最小堆right

加元素的时候，如果当前左右数量相等的话，那么优先加入最小堆，然后把最小堆的栈顶给左堆

不想等的话，一般是最大堆需要，然后小的栈顶给最小堆

取中位数的时候，如果是偶数，那么是最大堆和最小堆顶的平均值

不是的话就是最大堆的顶

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

看到这种括号题目，第一个想到就是使用栈来解决

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 Solution32AA{
    public int longestValidParentheses(String s){
        if (s.length()<=1) return 0;
        boolean vaild[] = new boolean[s.length()];
        Stack<Integer> stack = new Stack<>();

        for (int i=0;i<s.length();i++){
            if (s.charAt(i)=='(') stack.push(i);
            if (s.charAt(i)==')'&&!stack.isEmpty()){
                int index = stack.pop();
                vaild[i] = true;
                vaild[index]=true;
            }
        }
        int res = 0;
        int count = 0;
        for (int i=0;i<vaild.length;i++){
            if (vaild[i])
                count++;
            else{
                res = Math.max(res,count);
                count=0;
            }
        }
        res = Math.max(res,count);
        return res;
    }
}

使用栈，记录一个有效值的数字。

然后遍历字符找到有效括号

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution141A {
    public boolean hasCycle(ListNode head) {
        if (head==null) return false;
        ListNode slow = head,fast=head;
        while (fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if (fast==slow){
                return true;
            }
        }
        return false;
        
    }
}

非常easy的环形链表

72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution72A{
    public int minDistance(String text1, String text2){
        char[] t=  text2.toCharArray();
        int m = t.length;
        int[] f= new int[m+1];
        for (int j=0;j<m;j++){
            f[j+1] = j+1;//text2 的前 j + 1 个字符所需的操作数为 j + 1 (即插入 j + 1 个字符)。
        }
        for (char x:text1.toCharArray()){
            int pre = f[0];
            f[0]++;
            for (int j=0;j<m;j++){
                int tmp =f[j+1];
                f[j+1] = x ==t[j]?pre:Math.min(Math.min(f[j+1],f[j]),pre)+1;
                pre = tmp;
            }
        }
        return f[m];
    }
}

如果 text1 的当前字符 x 与 text2 的当前字符 t[j] 相同，那么不需要任何操作

  • f[j + 1]: 表示删除 text1 的当前字符 x。对应于操作”删除”。

  • f[j]: 表示在 text1 中插入一个字符，使得 text1 的当前字符等于 t[j]。对应于操作”插入”。

  • pre: 表示将 text1 的当前字符 x 替换为 t[j]。对应于操作”替换”。 由于需要经过一次编辑(删除/插入/替换)才能让text1前i个字符匹配text2前j+1个字符，所以操作总数要+1。

692. 前K个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

一看到这个题，我就想到用hashmap来做，然后我看又需要顺序，那我直接使用linkedhashmap不久得了。发现并不是的

可以使用优先队列，或者是规定compare的List，这里直接用优先队列吧

然后挑出前k个

放入list即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution692{
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map =new HashMap<>();
        for(String word:words){
            map.put(word,map.getOrDefault(word,0)+1);
        }
        PriorityQueue<String> queue = new PriorityQueue<>(
                (w1,w2)->map.get(w1).equals(map.get(w2))?w2.compareTo(w1):map.get(w1)-map.get(w2)
        );
        for (String word:map.keySet()){
            queue.offer(word);
            if (queue.size()>k){
                queue.poll();
            }
        }
        List<String> res = new ArrayList<>();
        while (!queue.isEmpty()){
            res.add(queue.poll());
        }
        Collections.reverse(res);
        return res;
    }
}

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

又是不重复，直接上hashset,一开始想这样做来，但发现不对，这样做的是字符串的数量

然后就想使用滑动窗口，更新值。如果含有就更新左端点，

不含有就更新最大值，然后放入右端点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution3B {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int left = -1, maxlen = 0;
        for (int right = 0; right < s.length(); right++) {
            if (map.containsKey(s.charAt(right))) {
                left = Math.max(left, map.get(s.charAt(right)));
            }
            map.put(s.charAt(right), right);
            maxlen = Math.max(maxlen, right - left);
        }
        return maxlen;
    }
}

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

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 Solution394A{
    public String decodeString(String s) {
        int num  = 0;
        String  curSting = "";
        Stack<Integer> stack_multi=  new Stack<>();
        Stack<String> stack = new Stack<>();
        for (Character c:s.toCharArray()){
                if (Character.isDigit(c)){
                    num = num*10+c-'0';
                }else if (c=='['){
                    stack_multi.push(num);
                    stack.push(curSting);
                    num = 0;
                    curSting = "";
                }else if (c==']'){
                    int longnum = stack_multi.pop();
                    StringBuilder temp = new StringBuilder(stack.pop());
                    for (int i=0;i<longnum;i++){
                        temp.append(curSting);
                    }
                    curSting=  temp.toString();
                }else {
                    curSting +=c;
                }
            }
        return curSting;
        }
    }

经典的括号和栈的问题

一个放之前的字符，一个放数字。当变成】结束的时候。将里面的字符遍历数字遍

82. 删除排序链表中的重复元素 II

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution82AA{
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0,head);
        ListNode cur  = dummy;
        while (cur.next!=null&&cur.next.next!=null){
            int val = cur.next.val;
            if (cur.next.next.val == val){
                while (cur.next!=null&&cur.next.val == val){
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }

        }
        return dummy.next;
    }
}

就是去检测cur.next和cur和cur.next之后的值是不是想到，想到就只留cur，然后其他的跳过

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

可以使用hash表+定长的滑动窗口试试

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
57
58
59
60
61
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        if (nums == null || nums.length < 4) return res;
        Arrays.sort(nums);
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }//简单去重
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }//最小的都大，直接抛弃
            if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
                continue;
            }//最大的都小直接抛弃
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }//简单去重
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }//最小的三个都大，抛弃
                if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
                    continue;
                }//最大的三个都小抛弃
                int left = j + 1;
                int right = n - 1;//找出左右边界
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));


                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }

                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }

                }

            }

        }
        return res;
    }
    }

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution40A{
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0,target,candidates,ans,path);
        return ans;
    }
    private void dfs(int i,int left,int[] candidates,List<List<Integer>> ans,List<Integer> path){
        if (left==0){
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j=i;j<candidates.length&&candidates[j]<=left;j++){
            if (j>i&&candidates.length==candidates[j-1]){
                continue;
            }
            path.add(candidates[j]);
            dfs(j+1,left-candidates[j],candidates,ans,path);
            path.remove(path.size()-1);
        }
    }
}

就是选与不选的问题，如果j>i且等与j的数都不选

记得回溯哈

415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

就是类似于一个加法的计算器

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 Solution415AAA{
    public String addStringsA(String num1, String num2) {
        String ans= "";
        StringBuilder sb = new StringBuilder();
        sb.append(turn(num1)+turn(num2));
        return sb.toString();
    }
    private long turn(String nums){
        long ans = 0;
        for (int i=nums.length();i>=0;i--){
            ans +=(i-1)*10;
        }
        return ans;
    }
    public String addStrings(String num1, String num2){
        StringBuilder res= new StringBuilder();
        int i = num1.length()-1,j=num2.length()-1,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 tmp  = n1+n2+carry;
            carry = tmp/10;
            res.append(tmp%10);
            i--;j--;
            
        }
        if (carry==1) res.append(1);
        return res.reverse().toString();
    }
}

946. 验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution946{
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i =0;
        for (int num:pushed){
            stack.push(num);
            while (!stack.isEmpty()&&stack.peek()==popped[i]){
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

经典的模拟栈运行的操作

当前栈的栈顶的数，如果是pop序列中的第i个的话，就说明这次成功，然后i++;

最后如果栈为空了，也就是所有的都符合，返回true

146. LRU 缓存(x)

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class LRUCacheAA {
    private static class Node{
        int key,vaule;
        Node prev,next;
        Node(int k,int v){
            key = k;
            vaule = v;
        }
    }
    private final int capacity;
    private final Node dummy = new Node(0, 0); // 哨兵节点
    private final Map<Integer, Node> keyToNode = new HashMap<>();

    public LRUCacheAA(int capacity) {
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node!=null?node.vaule:-1;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        if (node!=null){
            node.vaule = value;
            return;
        }
        node = new Node(key,value);
        keyToNode.put(key,node);
        pushFront(node);
        if (keyToNode.size()>capacity){
            Node backNode = dummy.prev;
            keyToNode.remove(backNode.key);
            remove(backNode);
        }
    }
    private void remove(Node x){
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }
    private void pushFront(Node x){
        x.prev = dummy;
        x.next = dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }
    private Node getNode(int key){
        if (!keyToNode.containsKey(key)){
            return null;
        }
        Node node = keyToNode.get(key);
        remove(node);
        pushFront(node);
        return node;
    }
}

就是实现了按LRU缓存的策略，主要使用的双向链表和hash表来解决的

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
。

快速的时候hashmap来进行查询

如果是更多的话，可以参考固定一个，然后移动另外一个

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution88AA{
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int len1 = m-1,len2=n-1;
        int len = m+n-1;
        while (len1>=0&&len2>=0){
            nums1[len--] = nums1[len1]>nums2[len2]?nums1[len1--]:nums2[len2--];
        }
       System.arraycopy(nums2,0,nums1,0,len2+1);
    }
}

简单的排序，就是从后面开始遍历，看谁大就行了

143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

1
L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

1
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 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
class Solution143B{
    public void reorderList(ListNode head) {
        ListNode mid = middle(head);
        ListNode head2 = reverseList(mid);
        while (head2.next!=null){
            ListNode next = head.next;
            ListNode next2 = head2.next;
            head.next = head2;
            head2.next = next;
            head = next;
            head2 = next2;
        }
    }
    private ListNode reverseList(ListNode head){
        ListNode pre = null,cur = head;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre=  cur;
            cur = next;
        }
        return pre;
    }
    private ListNode middle(ListNode head){
        ListNode slow =head,fast = head;
        while (fast!=null&&fast.next!=null){
            slow  = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

1
"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。

例如，"11106" 可以映射为：

  • "AAJF" ，将消息分组为 (1, 1, 10, 6)
  • "KJF" ，将消息分组为 (11, 10, 6)
  • 消息不能分组为 (1, 11, 06) ，因为 "06" 不是一个合法编码（只有 “6” 是合法的）。

注意，可能存在无法解码的字符串。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0。

题目数据保证答案肯定是一个 32 位 的整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution91AA{
    public int numDecodings(String s) {
        int n = s.length();
        s=  " "+s;
        char[] cs = s.toCharArray();
        int[] f = new int[n+1];
        f[0] = 1;
        for (int i=1;i<=n;i++){
            int a = cs[i]-'0',b = (cs[i-1]-'0')*10+(cs[i]-'0');
            if (1<=a&&a<=9) f[i] = f[i-1];
            if (10<=b&&b<=26) f[i]+=f[i-2];
        }
        return f[n];
    }
}

就是一个简单的动态规划

就只有俩选择，如果是1-9之内的就说明是a,也就是选择前面的一个就够了

如果是10-26之内，就说明要前面的两个才行

如果都可以的话，这俩都要。所以是+=f[i-2]

转移 f[i] 时只依赖 f[i-1] 和 f[i-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
class Solution91AA{
    public int numDecodings(String s) {
        int n = s.length();
        s=  " "+s;
        char[] cs = s.toCharArray();
        int[] f = new int[n+1];
        f[0] = 1;
        for (int i=1;i<=n;i++){
            int a = cs[i]-'0',b = (cs[i-1]-'0')*10+(cs[i]-'0');
            if (1<=a&&a<=9) f[i] = f[i-1];
            if (10<=b&&b<=26) f[i]+=f[i-2];
        }
        return f[n];
    }
    public int numDecodingsA(String s){
        int n = s.length();
        s = " "+s;
        char[] cs = s.toCharArray();
        int[]f = new int[n+1];
        f[0]  =1;
        for (int i=1;i<=n;i++){
            f[i%3] = 0;
            int a = cs[i]-'0',b = (cs[i-1]-'0')*10+(cs[i]-'0');
            if (1<=a&&a<=9) f[i%3] = f[(i-1)%3];
            if (10<=b&&b<=26) f[i%3] +=f[(i-2)%3];
        }

        return f[n%3];
    }
}

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

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

1
2
3
4
5
6
class Solution215{
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}

哈哈哈两行直接解决，虽然不是最合适的。

25. K 个一组翻转链表（x暂时有点懵逼啊）

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

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
34
class Solution215{
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}
class Solution25AAa{
    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);
        ListNode p0 = dummy;
        ListNode pre  =null;
        ListNode cur = head;

        for (;n>=k;n-=k){
            for(int i=0;i<k;i++){
                ListNode next =cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }

            ListNode next = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = next;
        }
        return dummy.next;
    }
}

首先先按k个数字分开好几组，然后k个数字的内部就是简单的交换

然后外部的话，p0=dummy

ListNode next = p0.next;下一部分的起始节点

p0.next.next = cur，下一部分的起点。

p0.next = pre;真起点

p0 = next往下移动，将 p0 移动到下一组待翻转节点的前面。

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 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
26
27
28
29
class Solution15AAA{
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int k =0;k<nums.length-2;k++){
            if (nums[k]>0) break;
            if(k>0&&nums[k]==nums[k-1]) continue;
            int i=k+1,j=nums.length-1;
            while (i<j){
                int sum = nums[k]+nums[i]+nums[j];
                if(sum<0){
                    while (i<j&&nums[i]==nums[++i]);
                }else if (sum>0){
                    while (i<j&&nums[j]==nums[--j]);
                }else {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k],nums[i],nums[j])));
                    i++;j--;
                    while (i<j&&nums[i]==nums[i-1]){
                        i++;
                    }
                    while (i<j&&nums[j]==nums[j+1]){
                        j--;
                    }
                }
            }
        }
        return res;
    }
}

跟前面的四个组合是用的一样的方法，就是双指针，从头开始，然后去遍历，确定最大的和最小的，然后在里面去寻找。

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution53B {
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int minpresum = 0,presum = 0;
        for(int x:nums){
            presum +=x;
            ans = Math.max(ans,presum-minpresum);
            minpresum = Math.min(minpresum,presum);
            
        }
        return ans;
    }
}

维护一个最大值和一个最小值，最大值就是和-小的。

可以扩展为乘法，最大值可能就是最小值乘出来的

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution21B {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
       if(list1==null){
           return list2;
       }else if (list2==null){
           return list1;
       }else if(list1.val<list2.val){
           list1.next = mergeTwoLists(list1.next,list2);
           return list1;
       }else {
           list2.next = mergeTwoLists(list1,list2.next);
           return list2;
       }
    }
}

简洁的使用递归直接完成

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

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 Solution5B{
    public String longestPalindrome(String s) {
     if (s==null||s.length()<2){
         return s;
     }
     int strlen = s.length();
     int maxStart = 0;
     int maxEnd = 0;
     int maxLen = 1;
     
     boolean[][] dp  =new boolean[strlen][strlen];
     for (int r= 1;r<strlen;r++){
         for (int l = 0;l<r;l++){
             if (s.charAt(l)==s.charAt(r)&&(r-l<=2||dp[l+1][r-1])){
                 dp[l][r] = true;
                 if (r-l+1>maxLen){
                     maxLen = r-l+1;
                     maxStart = l;
                     maxEnd = r;
                 }
             }
         }
     }
     return s.substring(maxStart,maxEnd+1);
        
    }
}

就是使用 动态规划来完成，

(r-1<=2||dp l+1 r-1这个很好玩成了这个

如果r-l<=2的话，就说明就一个数 了，肯定是回文。就是基数的时候

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution102B {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if (root!=null) queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            for (int i=queue.size();i>0;i--){
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if (node.left!=null) queue.add(node.left);
                if (node.right!=null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

因为他是层序遍历，遍历完这一层才进行下一次遍历。所以我们要把这一层的节点全都放进队列。

然后一个一个取出来，记录值。然后再左右的去遍历

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log 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
class Solution33B{
    public int search(int[] nums, int target) {
        int n = nums.length;
        int end = nums[n-1];
        int left =0;
        int right  = n-1;
        while (left<right){
            int mid = (left+right)>>>1;
            if (target<=end&&nums[mid]>end){
                left = mid+1;
            }else if (target>end&&nums[mid]<=end){
                right =mid;
            }else {
                if (nums[mid]<target){
                    left = mid+1;
                }else {
                    right = mid;
                }
            }
        }
        return nums[left]!=target?-1:left;
    }
}

一看到这个时间复杂度，我们第一时间想到的就是我们最喜欢的二分查找哈哈。

然后一看到这个旋转数组，我们肯定要关注最后一个数字，因为就是从他这旋转的

然后有三种大情况

目标值小于最后一个数，中位大于最后一个数，也就是说目标值在右边，中位在左。我们移动left指针到mid+1

然后都在一遍的话，就是普通的二分查找了

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

看到这个题，一个矩阵，直接进行遍历，就可以了。如果是求最大面积的话，再加上动态规划即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution200B{
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i=0;i<grid.length;i++){
            for(int j =0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    dfs(grid,i,j);
                    count++;
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid ,int i,int j){
        if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]=='0') return;
        grid[i][j] ='0';
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
}

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

看到这种排列的题目，首先想到的就是回溯法+dfs哈

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 Solution46{
    List<List<Integer>> ans= new ArrayList<>();
    List<Integer> nums = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        this.ans = new ArrayList<>();
        this.nums = new ArrayList<>();
        for (int num:nums){
            this.nums.add(num);
        }
        dfs(0);
        return ans;



    }
    void swap(int a,int b){
        int tmp  = nums.get(a);
        nums.set(a,nums.get(b));
        nums.set(b,tmp);
    }
    void dfs(int x){
        if (x== nums.size()-1){
            ans.add(new ArrayList<>(nums));
            return;
        }
        for (int i=x;i<nums.size();i++){
            swap(i,x);
            dfs(x+1);
            swap(i,x);//这就是回溯
        }
    }
}

就是固定一位，然后去移动他后面的位置。

然后移动完，再给他恢复。这就是回溯算法的所在

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution20AB{
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c:s.toCharArray()){

                if (c=='('||c=='['||c=='{'){
                    stack.push(c);
                }
               else if (c==')'||c==']'||c=='}') {
                    if (stack.isEmpty()) return false;

                    char top = stack.pop();
                    if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                        return false;
                    }
                }

        }
        return stack.isEmpty();
    }
}

一看到这个题目我就知道要使用栈，之前的哪些题都是差不多的

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1
2
3
4
5
6
7
8
9
10
class Solution121B{
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE,profit = 0;
        for (int price:prices){
            cost = Math.min(cost,price);
            profit = Math.max(profit,price-cost);
        }
        return profit;
    }
}

比较easy的一道题目了

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

1
2
3
4
5
6
7
8
9
10
class Solution236B{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null||root==p||root==q) return root;
        TreeNode left =lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if (left==null) return right;
        if (right==null) return left;
        return root;
    }
}

也是比较简单的一道递归题目

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution103B {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res= new ArrayList<>();
        Queue<TreeNode> queue =new LinkedList<>();
        if (root!=null) queue.add(root);
        while (!queue.isEmpty()){
            LinkedList<Integer> tmp  =new LinkedList<>();
            for (int i=queue.size();i>0;i--){
                TreeNode node = queue.poll();
                if (res.size()%2==0) tmp.addLast(node.val);
                else tmp.addFirst(node.val);
                if(node.left!=null) queue.add(node.left);
                if (node.right!=null) queue.add(node.right); 
            }
            res.add(tmp);
        }
        return res;

    }
}

重要的是一个达到锯齿状层序遍历的目的，普通的层序遍历直接使用一个队列就ok

现在的如果现在比如我们里面的是奇数的话，就说明当前是偶数层，从右到左开始遍历，就是往前面加，

如果是偶数的话，就从左往右开始遍历，就是往后面开始加

一个层一个List

手撕快速排序(x)

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
57
58
59
60
61
62
63
class  OptimizedQuickSort{
    private static final Random random  = new Random();
    private static final int INSERTION_SORT_THRESHOLD = 16;

    public int [] sortArry(int[] nums){
        if (nums==null||nums.length<=1) return nums;
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    private void quickSort(int[] nums, int left, int right){
        if (left>=right) return;
        if (right-left+1<=INSERTION_SORT_THRESHOLD){
            insertionSort(nums,left,right);//小数字使用插入排序
            return;
        }
        int[] pivots = partition3Way(nums,left,right);
        quickSort(nums,left,pivots[0]-1);//只递归小于的部分
        quickSort(nums,pivots[1]+1,right);//只递归大于的部分

    }
    private void swap(int[] nums,int i,int j){
        if (i!=j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j]  = temp;
        }
    }
    //插入排序
    private void insertionSort(int[] nums,int left,int right){
        for (int i=left+1;i<=right;i++){
            int key = nums[i];
            int j  = i-1;
            while (j>=left&&nums[j]>key){
                nums[j+1]  = nums[j];
                j--;
            }
            nums[j+1] = key;
        }
    }
    private int[] partition3Way(int[] nums,int left,int right){
        int randomIndex = left+random.nextInt(right-left+1);
        swap(nums,left,randomIndex);//一个随机值，交换left和随机值

        int pivot = nums[left];
        int lt = left;
        int i  = left+1;
        int gt =right +1;

        while (i<gt){
            if (nums[i]<pivot){//小于pivot放入左区域
                swap(nums,++lt,i++);
            }else if (nums[i]>pivot){//放入右区域
                swap(nums,--gt,i);
            }else {
                i++;//只需要移动指针即可
            }
        }
        swap(nums,left,lt);//最后交换回来
        return new int[]{lt,gt-1};
    }

}

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

使用头插法真的得劲

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution92B {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode g = dummy;
        ListNode p = dummy.next;
        for (int step = 0;step<left-1;step++){
            g = g.next;
            p = p.next;
        }
        for (int i=0;i<right-left;i++){
            ListNode removed = p.next;
            p.next = p.next.next;

            removed.next  = g.next;
            g.next =removed;
        }
        return dummy.next;
    }
}

我们先设一个虚拟节点，这样的话，就不用考虑边界值的问题了

然后g指针式left前面的

p指针指向left节点

然后我们这样把指针移动到该有的位置

然后反转的时候要反转的是right-left个节点

然后我们从把他们使用头插相继的插入到g节点的后面，因为g节点不动，动的是p节点。头插的话，先插的就在后面了。实现 了反转的效果

这样的就完成了。

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution141B{
    public boolean hasCycle(ListNode head) {
        if (head==null) return false;
        ListNode slow = head;
        ListNode fast  = head;
        while (fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if (fast==slow){
                return true;
            }
        }
        return false;
    }
}

还是经典快慢节点完成哈哈

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution54B {
    public List<Integer> spiralOrder(int[][] matrix) {
        if(matrix.length==0) return new ArrayList<Integer>();
        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
        Integer[] ans = new Integer[(r+1)*(b+1)];
        while (true){
            for (int i=l;i<=r;i++) ans[x++]  = matrix[t][i];
            if(++t>b) break;
            for (int i=t;i<=b;i++) ans[x++] = matrix[i][r];
            if (l>--r) break;
            for (int i = r;i>=l;i--) ans[x++] = matrix[b][i];
            if (t>--b) break;
            for(int i=b;i>=t;i--) ans[x++]  = matrix[i][l];
            if (++l>r) break;
        }
        return Arrays.asList(ans);
    }
}

就是设定好边界值只会然后进行遍历即可

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

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

就是简单的动态规划，如果相等就+1，然后统计数量

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution23B{
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b)->a.val-b.val);
        for (ListNode head:lists){
            if (head!=null){
                pq.offer(head);
            }
        
        }
        ListNode dummy = new ListNode(0);
        ListNode cur  = dummy;
        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            if (node.next!=null){
                pq.offer(node.next);
            }
            cur.next = node;
            cur = cur.next;
        }
        return dummy.next;
    }
}

就是使用最小堆，因为每个链表之中的head肯定是最小的

那我们就一直遍历里面的head，然后放入最小堆，然后将最小堆里面的取出来，放进我们的新的链表

可以加上dummy哨兵节点

415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

经典计算器类型的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution415B {
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder("");
        int i=num1.length()-1,j = num2.length()-1,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 tmp = n1+n2+carry;
            carry = tmp/10;
            sb.append(tmp%10);
            i--;j--;
        }
        if (carry==1) sb.append(1);
        return sb.reverse().toString();
    }
}

一般这种的题目都要使用StringBuilder这一个单线程的

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution56B {
    public int[][] merge(int[][] intervals) {
        List<int[]> ans = new ArrayList<>();
        Arrays.sort(intervals,(p,q)->p[0]-q[0]);
        for (int[] p:intervals){
            int m  =ans.size();
            if (m>0&&p[0]<=ans.get(m-1)[1]){
                ans.get(m-1)[1] = Math.max(ans.get(m-1)[1],p[1]);
            }else {
                ans.add(p);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

就是按头上第一个排序之后，然后看最后面1的位置的数，是不是小于下一个的头上的数，小于的话，就可以合并

然后更新新的值

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

1
2
3
4
5
6
7
8
9
10
11
12
 class Solution160B {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null||headB==null) return null;
        ListNode pA= headA;
        ListNode pB=  headB;
        while (pA!=pB){
            pA = (pA==null)?headB:pA.next;
            pB = (pB==null) ?headA:pB.next;
        }
        return pA;
    }
}

因为我们是有公共部分的，如果我们其中一个遍历完之后，再从另一个链表的起点继续遍历

等他们相遇的时候，就是我们需要的那个交点

42. 接雨水(x)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution42B{
    public int trap(int[] height){
        int ans = 0;
        int left= 0,right = height.length-1;
        int preMax = 0,sufMax = 0;
        while (left<right){
            preMax = Math.max(preMax,height[left]);
            sufMax = Math.max(sufMax,height[right]);
            ans +=preMax<sufMax?preMax-height[left++]:sufMax-height[right--];
        }
        return ans;
    }
}

使用双指针谁小就移动谁，算是1D接雨水的最优解

2D接雨水

转换为了矩阵，但还是之前使用的木桶效应。

我们可以从这个最矮的方块出发，向其内部（上下左右）相邻的、未访问过的方块进行探索：

  • 如果相邻的方块 (nr, nc) 比 h 还矮，说明水可以把它淹没。这个方块能接的水量就是 h - height[nr][nc]。然后将这个方块也视为新的海岸线（因为它现在是水能到达的边界了），其有效高度是h（因为水是从h处漫灌过来的），把它加入我们的“海岸线”集合。
  • 如果相邻的方块比 h 高，它自己就成了一堵新墙，无法积水。但它也成为了新的边界，需要加入“海岸线”集合。

看到这个我们就要用我们的优先队列，也就是最小堆了，不断更新

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
class Solution407 {
    private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    public int trapRainWater(int[][] heightMap) {
        if (heightMap==null||heightMap.length<=2||heightMap[0].length<=2){
            return 0;
        }
        int rows = heightMap.length;
        int cols  = heightMap[0].length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->(a[0]-b[0]));
        for (int i=0;i<rows;i++){
            for (int j=0;j<cols;j++){
                if (i==0||i==rows-1||j==0||j==cols-1){
                    pq.add(new int[]{heightMap[i][j],i,j});
                    heightMap[i][j] = -1;
                }
            }
        }
        int ans=  0;
        while (!pq.isEmpty()){
            int[] t = pq.poll();
            int minHeight = t[0],i=t[1],j=t[2];
            for (int[] d:DIRS){
                int x= i+d[0],y = j+d[1];//i,j的邻居
                if (0 <= x && x < rows && 0 <= y && y < cols && heightMap[x][y] >= 0){
                    ans +=Math.max(minHeight-heightMap[x][y],0);
                    pq.add(new int[]{Math.max(minHeight, heightMap[x][y]), x, y});
                    heightMap[x][y] = -1;
                }
            }
        }
        return ans;
    }

}

1143. 最长公共子序列(x)

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution1143B{
    public int longestCommonSubsequence(String text1, String text2) {
        char[] t = text2.toCharArray();
        int m  = t.length;
        int[]f = new int[m+1];
        for (char x:text1.toCharArray()){
            int pre = 0;
            for(int j=0;j<m;j++){
                int tmp = f[j+1];
                f[j+1] = x==t[j]?pre+1:Math.max(f[j+1],f[j]);
                pre = tmp;
            }
        }
        return f[m];
    }
}

我们使用动态规划，这种的题目一般都是使用动态规划或者使用滑动窗口进行解决的

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和"192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

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 Solution93B{
    public List<String> restoreIpAddresses(String s) {
        int n  = s.length();
        List<String> ans = new ArrayList<>();
        for (int i =1;i<n&&isvalid(s,0,i);i++){
            for (int j=i+1;j<n&&isvalid(s,i,j);j++){
                for (int k =j+1;k<n&&isvalid(s,j,k);k++){
                    if (isvalid(s,k,n)){
                        ans.add(String.format("%s.%s.%s.%s",s.substring(0,i),s.substring(i,j),s.substring(j,k),s.substring(k)
                                ));
                    }
                }
            }
        }
        return ans;
    }
    private boolean isvalid(String s,int i,int j){
        if (j-i>3||j-i>1&&s.charAt(i)=='0'){
            return false;
        }
        return Integer.parseInt(s.substring(i,j))<=255;
    }
}


就是相当于将这一串数分割成4段，我们需要切三次，然后这里面的每一个都要符合ip的定义就可以

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution142A{
    public ListNode detectCycle(ListNode head) {
        if (head==null)return null;
        ListNode fast = head,slow = head;
        while (fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast==slow){
                break;
            }
        }
        if (fast==null||fast.next==null) return null;
        fast = head;
        while (slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

就是我们第一次循环之后，如果这个适合fast节点空了，就说明是没有环了

然后我们进行第二次循环，fast从头开始，然后继续遍历。我们下一次fast和slow相遇的节点就是我们需要的环的开始的节点

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution19AA {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);
        ListNode left = dummy,right = dummy;
        while (n-->0){
            right = right.next;
        }
        while (right.next!=null){
            right = right.next;
            left = left.next;
        }
        left.next = left.next.next;
        return dummy.next;
    }
}

这个方法非常的巧妙，就是一把尺子，右节点先走n步，然后两个节点一块走，右节点走到头的适合，左节点就是我们需要的倒数第n个节点的前一个节点。

然后跳过该节点就Ok

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

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

算法的时间复杂度应该为 O(log (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
class Solution4A{
    public double findMedianSortedArrays(int[] nums1, int[] nums2){
        //确保num1是较短的数组
        if (nums1.length>nums2.length){
            int[] tmp  = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        int m = nums1.length;
        int n = nums2.length;
        //哨兵值
        int[] a = new int[m+2];
        int[] b = new int[n+2];
        a[0] = b[0] = Integer.MIN_VALUE;
        a[m+1] = b[n+1] = Integer.MAX_VALUE;
        System.arraycopy(nums1,0,a,1,m);
        System.arraycopy(nums2,0,b,1,n);


        int left =0,right = m;
        while (left<=right){
            int i = (left+right)>>>1;
            int j = (m+n+1)/2-i;//总的
            if (a[i]<=b[j+1]&&b[j]<=a[i+1]){
                int max1 = Math.max(a[i],b[j]);
                int min2 =Math.min(a[i+1],b[j+1]);
                return (m+n)%2>0?max1:(max1+min2)/2.0;
            }else if (a[i]>b[j+1]){
                right = i-1;
            }else {
                left=i+1;
            }
        }
        return 0.0;
    }
}

i是我们变得，j是我们合起来得中间的数

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution199A{
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans  = new ArrayList<>();
        dfs(root,0,ans);
        return ans;
    }
    private void dfs(TreeNode root,int depth,List<Integer> ans){
        if (root==null) return;
        if (depth==ans.size()){
            ans.add(root.val);
        }
        dfs(root.right,depth+1,ans);
        dfs(root.left,depth+1,ans);
    }
}

右视图就是我们当前的深度等于我们的ans里面的数目的时候就是。

然后递归即可

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution94B{
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans= new ArrayList<>();
        dfs(root,ans);
        return ans;
    }
    private void dfs(TreeNode root,List<Integer> ans){
        if (root==null)return;
        dfs(root.left,ans);
        ans.add(root.val);
        dfs(root.right,ans);
    }
}

递归中序遍历

165. 比较版本号

给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。

比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。

返回规则如下：

  • 如果 *version1* < *version2* 返回 -1，
  • 如果 *version1* > *version2* 返回 1，
  • 除此之外返回 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution165A{
    public int compareVersion(String version1, String version2) {
        int i =0,j=0;
        int n = version1.length(),m = version2.length();
        while (i<n||j<m){
            int num1=0,num2 = 0;
            while (i<n&&version1.charAt(i)!='.') num1 = num1*10+version1.charAt(i++)-'0';
            while (j<m&&version2.charAt(j)!='.') num2 =num2*10+version2.charAt(j++)-'0';
            if (num1>num2) return 1;
            else if (num1<num2)  return -1;
            i++;j++;
            
        }
        return 0;
    }
}

就是把字符串转换为数字然后进行比较。.前面是一部分，后面是一部分

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有 O(log n) 时间复杂度的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution704B{
    public int search(int[] nums, int target) {
        int left =0,right  = nums.length-1;
        while (left<=right){
            int mid = (left+right)>>>1;
            if (nums[mid]==target) return mid;
            else if (nums[mid]>target){
                right = mid-1;
            }
            else {
                left = mid+1;
            }
        }
        return -1;
    }
}

注意边界的问题

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 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
class MyQueueAB {
    private Stack<Integer> A;
    private Stack<Integer> B;

    public MyQueueAB() {
        A = new Stack<>();
        B = new Stack<>();
    }

    public void push(int x) {
        A.push(x);
    }

    public int pop() {
        int peek = peek();
        B.pop();
        return peek;
    }

    public int peek() {
        if(!B.isEmpty()) return B.peek();
        if (A.isEmpty()) return -1;
        while (!A.isEmpty()){
            B.push(A.pop());
        }
        return B.peek();
    }

    public boolean empty() {
        return A.isEmpty()&&B.isEmpty();
    }
}

非常简单的一道题目，就是我们使用两个栈来完成队列的先进先出的实现

一个栈A，一个栈B

我们进队列的时候先进入A栈，然后将A栈的元素，逐个放入B栈，我们从B栈里面pop元素，这样的话，就是按照顺序出栈的

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

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 Solution148AA{
    public ListNode sortList(ListNode head) {
        if (head==null||head.next==null) return head;
        ListNode head2 = middle(head);
        head = sortList(head);
        head2 = sortList(head2);
        return mergeTowLists(head,head2);
    }
    private ListNode middle(ListNode head ){
        ListNode pre=  head;
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast!=null&&fast.next!=null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        return slow;
    }
    private ListNode mergeTowLists(ListNode list1,ListNode list2){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (list1!=null&&list2!=null){
            if (list1.val<list2.val){
                cur.next = list1;
                list1  = list1.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1!=null?list1:list2;
        return dummy.next;
    }
}

这个题目类似于第k个反转链表的那个题目。都是先找中点，这个只不过是直接排序了

那个还有一个反转的操作

22. 括号生成

数字 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
class Solution22B{
    public List<String> generateParenthesis(int n) {
        List<String> ans= new ArrayList<>();
        char[] path = new char[n*2];
        dfs(0,0,n,path,ans);
        return ans;
    }
    private void dfs(int left,int right,int n,char[] path,List<String> ans){
        if (right==n){
            ans.add(new String(path));
            return;
        }
        if (left<n){
            path[left+right] = '(';
            dfs(left+1,right,n,path,ans);
        }
        if (right<left){
            path[left+right] = ')';
            dfs(left,right+1,n,path,ans);
        }
        
    }
}



left代表左括号的，right代表右括号。使用选与不选的方法