研发高频算法题

Marlowe
题解

发布于：Apr 1, 2021
次浏览

12.3k words

64 min

牛客研发最爱考、剑指offer经典题目

字符串

进制转换

题目链接
20210408221854

代码如下：

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
import java.util.*;


public class Solution {
    /**
     * 进制转换
     * @param M int整型 给定整数
     * @param N int整型 转换到的进制
     * @return string字符串
     */
    public String solve (int M, int N) {
        if(M == 0){
            return "0";
        }
        // 存储各进制转换后的字符
        String s = "0123456789ABCDEF";
        // 判断是否为负数，如果为负数，则需要添加负号
        boolean f = false;
        if(M < 0){
            f = true;
            M = -M;
        }
        StringBuilder sb = new StringBuilder();
        // 得到进制转换逆序的结果
        while(M != 0){
            sb.append(s.charAt(M%N));
            M /= N;
        }
        // 如果是负数，则添加负号
        if(f){
            sb.append("-");
        }
        return sb.reverse().toString();
    }
}

字符串解码

题目链接
20210415211812

代码如下：

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 decodeString(String s) {
        char[] chars = s.toCharArray();
        Deque<Integer> stackNum = new ArrayDeque<>();
        Deque<String> stack = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        int num = 0;
        for (int i = 0; i < chars.length ; i++) {
            if (chars[i] >= '0' && chars[i] <= '9') {
                num = num * 10 + Integer.parseInt(chars[i] + ""); //两位数以上的数字计算
            } else if (chars[i] == '[') {
                stackNum.addLast(num); //不能在上一步加入数字队列，可能会有两位数以上的数字
                stack.addLast(sb.toString()); //第一个待处理的字符串
                sb = new StringBuilder(); //清空结果
                num = 0; 
            } else if (chars[i] == ']') {
                StringBuilder temp = new StringBuilder();
                int n = stackNum.removeLast(); //上一步的结果，从栈弹出
                while (n > 0) {
                    temp.append(sb);
                    n--;
                }
                sb = new StringBuilder(stack.removeLast() + temp); //更新原来的字符串结果
            } else {
                sb.append(chars[i]);
            }
        }
        return sb.toString();
    }
}

数组

数组中未出现的最小正整数

题目链接

20210420201831

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    /**
     * return the min number
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int minNumberdisappered (int[] arr) {
        if(arr == null){
            return 1;
        }
        // 找到连续区间的最小值和最大值
        int min = arr[0];
        int max = arr[0];
        // 求出当前数组和
        int sum1 = arr[0];
        for(int i = 1; i < arr.length; i++){
            min = Math.min(min,arr[i]);
            max = Math.max(max,arr[i]);
            sum1 += arr[i];
        }
        // 求出连续区间的和
        int sum2 = 0;
        for(int i = min; i <= max; i++){
            sum2 += i;
        }
        // 判断两次的值是否相等，相等返回最大值+1，否则计算差值
        int num = sum2 - sum1 == 0? max + 1 : sum2 - sum1;
        // 返回最小正整数
        return Math.max(1,num);
    }
}

顺时针旋转矩阵

题目链接

20210421212558

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // 原地旋转，注意循环结束条件
        for(int i = 0; i < n / 2; i++){
            for(int j = 0; j < (n+1) / 2; j++){
                // 依次交换四个位置的值
                int tmp = mat[i][j];
                mat[i][j] = mat[n - j - 1][i];
                mat[n - j - 1][i] = mat[n - i - 1][n - j - 1];
                mat[n - i - 1][n - j - 1] = mat[j][n - i - 1];
                mat[j][n - i - 1] = tmp;
            }
        }
        return mat;
    }
}

重排数组元素，奇数放在奇数位，偶数放在偶数位

题目链接

20210529120232

思路： 找到不符合条件的奇数和偶数进行交换。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void sort(int[] arr){
       int i = 0;
       int j = 1;
       int len = arr.length;
       while(i < len && j < len){
           // 找到不符合条件的偶数
           while(i < len && (arr[i] & 1) == 0) i += 2;
           // 找到不符合条件的奇数
           while(j < len && (arr[j] & 1) == 1) j += 2;
           // 交换不符合条件的奇数和偶数
           if(i < len && j < len) {
               swap(arr[i], arr[j]);
           }
       }
   }

连续的子数组和

题目链接

20210602222229

思路： 前缀和+HashMap

代码如下：

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 Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        if(n < 2){
            return false;
        }
        // 记忆前缀和为i的下标j
        Map<Integer,Integer> map = new HashMap();
        map.put(0,-1);
        int res = 0;
        for(int i = 0; i < n; i++){
            // 计算当前前缀和
            res = (res + nums[i]) % k;
            // 如果当前位置前缀和和之前一样，则看长度是否大于等于2
            if(map.containsKey(res)){
                if(i - map.get(res) >= 2){
                    return true;
                }
            }else{
                // 将当前前缀和信息记录到map中
                map.put(res,i);
            }
        }
        return false;
    }
}

连续数组

题目链接

20210603214001

思路： 前缀和+HashMap

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int findMaxLength(int[] nums) {
        int maxLen = 0;
        // 记忆化之前的值
        Map<Integer,Integer> map = new HashMap();
        int cnt = 0;
        // 初始化map
        map.put(0,-1);

        for(int i = 0; i < nums.length; i++){
            int num = nums[i];
            // 统计0，1的值
            if(num == 1){
                cnt++;
            }else{
                cnt--;
            }
            // 如果之前出现过，更新当前最大值
            if(map.containsKey(cnt)){
                int pre = map.get(cnt);
                maxLen = Math.max(maxLen,i-pre);
            }else{
                // 将当前值放入map中记忆
                map.put(cnt,i);
            }
        }
        return maxLen;
    }
}

长度最小的子数组

题目链接
20210819222727

代码如下:

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 minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        int start = 0;
        int end = 0;
        int sum = 0;
        int res = Integer.MAX_VALUE;
        while(end < n){
            // 求当前窗口总和
            sum += nums[end];
            // 如果当前总和比target大，左指针可以向右移
            while(sum >= target){
                res = Math.min(res,end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        // 判断是否有结果
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

三个数的最大乘积

628. 三个数的最大乘积

20210905201802

代码如下：

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 Solution {
    public int maximumProduct(int[] nums) {
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;

        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        for(int num : nums){
            if(num > max1){
                // 如果当前数最大，则给当前数安排第一
                max3 = max2;
                max2 = max1;
                max1 = num;
            }else if(num > max2){
                // 如果当前数第二大，则给当前数安排第二
                max3 = max2;
                max2 = num;
            }else if(num > max3){
                // 如果当前数最小，则给当前数安排第三
                max3 = num;
            }

            if(num < min1){
                // 如果当前数最小，则给当前数安排最小
                min2 = min1;
                min1 = num;
            }else if(num < min2){
                // 如果当前数第二小，则给当前数安排第二小
                min2 = num;
            }
        }
        int res = Math.max(max1 * max2 * max3,max1 * min1 * min2); 
        return res;
    }
}

二分查找

在转动过的有序数组中寻找目标值

题目链接

20210404141152

代码如下：

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
import java.util.*;


public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] A, int target) {
        // 如果没有翻转，则直接二分查找
        if(A[0] < A[A.length - 1]){
            return bsearch(A,target,0,A.length - 1);
        }
        int left = 0;
        int right = A.length - 1;
        int mid;
        // 找到翻转点
        while(left <= right){
            mid = (left + right) / 2;
            if(A[mid] >= A[0]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        // 如果要查找的值比最左边的大，则在翻转点左边二分查找
        if(target >= A[0]){
            return bsearch(A,target,0,right);
        }else{// 反之
            return bsearch(A,target,left,A.length - 1);
        }
    }
    
    // 二分查找标准代码
    public int bsearch(int[] A,int target,int left, int right){
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            if(target == A[mid]){
                return mid;
            }else if(target > A[mid]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return -1;
    }
}

搜索旋转排序数组

题目链接

20210407145332

代码如下：

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 Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if(nums == null || n == 0){
            return -1;
        }
        if(n == 1){
            return nums[0] == target ? 0 : -1;
        }
        int left = 0;
        int right = n - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            }
            // 左边是有序的
            if(nums[0] <= nums[mid]){
                if(nums[mid] > target && target >= nums[0]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{
                // 右边是有序的
                if(nums[mid] < target && target <= nums[n-1]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

搜索旋转排序数组 II

题目链接
20210407150627

代码如下：

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
class Solution {
    public boolean search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        while(start <= end){
            int mid = start + (end - start) / 2;
            if(nums[mid] == target){
                return true;
            }
            // 去掉重复的
            if(nums[start] == nums[mid]){
                start++;
                continue;
            }
            // 左边部分有序
            if(nums[start] < nums[mid]){
                // target在左边
                if(nums[mid] > target && nums[start] <= target){
                    end = mid - 1;
                }else{
                    start = mid + 1;
                }
            }else{
                // target在右边
                if(nums[mid] < target && target <= nums[end]){
                    start = mid + 1;
                }else{
                    end = mid - 1;
                }
            }
        }
        return false;
    }
}

寻找旋转排序数组中的最小值 II

题目链接
20210409210819

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findMin(int[] nums) {
        int left= 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == nums[right]){
                right--;
            }else if(nums[mid] < nums[right]){
                // 中间值比最右边的值小，而中间这个值可能是最小值，所以右指针为mid，不能为mid - 1
                right = mid;
            }else{
                // 中间值比最右边的值大，因此左指针为mid + 1
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

二分查找-II

题目链接

20210529115726

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int search (int[] nums, int target) {
        // write code here
        int low = 0;
        int high = nums.length - 1;
        int mid = 0;
        while(low <= high){
            mid = low + (high - low) / 2;
            if(nums[mid] == target){
                // 去重，找到最左边的解
                while(mid != 0 && nums[mid] == nums[mid - 1]){
                    mid--;
                }
                return mid;    
            }
            else if(nums[mid] > target){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        return -1;
    }

双指针

删除排序数组中的重复项

题目链接

20210415225542

代码如下：

1
2
3
4
5
6
7
8
9
10
11
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

回文数字

题解

20210527151559

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    /**
     * 
     * @param x int整型 
     * @return bool布尔型
     */
    public boolean isPalindrome (int x) {
        // write code here
        if(x == 0){
            return true;
        }
        // 如果是负数，或者能被10整除，就不是回文
        if(x < 0 || x % 10 == 0){
            return false;
        }
        int reverse = 0;
        while(x > reverse){
            reverse = reverse * 10 + x % 10;
            x /= 10;
        }
        // 判断的关键点
        return (reverse == x) || (reverse / 10 == x);
    }
}

无重复字符的最长子串

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

20210826165028

代码如下：

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 lengthOfLongestSubstring(String s) {
        int len = s.length();
        if(len == 0){
            return 0;
        }
        int left = 0;
        int max = 0;
        Map<Character,Integer> map = new HashMap();
        for(int i = 0; i < len; i++){
            char ch = s.charAt(i);
            // 如果当前窗口包含字符，更新左边界
            if(map.containsKey(ch)){
                left = Math.max(left,map.get(ch) + 1);
            }
            // 将当前字符放到窗口中
            map.put(ch,i);
            max = Math.max(max,i - left + 1);
        }
        return max;
    }
}

链表

两个链表生成相加链表

20210401215738

代码如下:

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
64
65
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // 将两个链表反转
        ListNode p1 = reverse(head1);
        ListNode p2 = reverse(head2);
        // 定义结果链表
        ListNode res = new ListNode(-1);
        ListNode curr = res;
        // 进位
        int carry = 0;
        while(p1 != null || p2 != null){
            int sum = 0;
            if(p1 != null){
                sum += p1.val;
                p1 = p1.next;
            }
            if(p2 != null){
                sum += p2.val;
                p2 = p2.next;
            }
            // 低位+进位
            sum += carry;
            
            curr.next = new ListNode(sum % 10);
            // 从新计算进位
            carry = sum / 10;
            curr = curr.next;
        }
        // 如果有进位，直接加到结果链表尾部
        if(carry > 0){
            curr.next = new ListNode(carry);
        }
        // 将结果链表反转
        return reverse(res.next);
        
    }
    // 翻转链表
    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

合并k个已排序的链表

题目链接

20210406162347

代码如下：

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
import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null || lists.size() == 0){
            return null;
        }
        return mergeKList(lists,0,lists.size() - 1);
    }
    
    public ListNode mergeKList(ArrayList<ListNode> lists,int low, int high) {
        // 左右相等说明不能再分
        if(low >= high){
            return lists.get(low);
        }
        // 计算mid
        int mid = low + (high - low) / 2;
        ListNode l1 = mergeKList(lists,low,mid);
        ListNode l2 = mergeKList(lists,mid + 1,high);
        return merge(l1,l2);
    }
    
    // 合并两个有序链表
    public ListNode merge(ListNode node1,ListNode node2){
        ListNode node = new ListNode(-1);
        ListNode tmp = node;
        while(node1!=null && node2!=null){
            if(node1.val <= node2.val){
                tmp.next = node1;
                node1 = node1.next;
            }else{
                tmp.next = node2;
                node2 = node2.next;
            }
            tmp = tmp.next;
        }
        tmp.next = node1!=null?node1:node2;
        return node.next;
    }
}

单链表的排序

题目链接

20210407151743

代码如下(方法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
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        // 使用快慢指针找到链表中间部分
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 截取第二部分链表
        ListNode newList = slow.next;
        slow.next = null;
        // 递归继续分割两个链表
        ListNode left = sortInList(head);
        ListNode right = sortInList(newList);
        // 合并两个有序链表
        ListNode dummy = new ListNode(-1);
        ListNode res = dummy;
        while(left != null && right != null){
            if(left.val < right.val){
                res.next = left;
                left = left.next;
            }else{
                res.next = right;
                right = right.next;
            }
            res = res.next;
        }
        res.next = left == null? right : left;
        return dummy.next;
    }
}

代码如下(方法2 插入排序)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        // 如果头节点为空，直接返回
        if(head == null){
            return head;
        }
        // 新建哑节点，保存头结点信息
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 排序好部分最后一个元素
        ListNode lastSorted = head;
        // 当前节点（待排序元素）
        ListNode curr = head.next;
        while(curr != null){
            // 如果当前元素不用排序，将排序链表增长，也即lastSorted后移
            if(lastSorted.val <= curr.val){
                lastSorted = lastSorted.next;
            }else{
                // 从头结点开始找，pre保存前一个元素
                ListNode pre = dummy;
                while(pre.next.val <= curr.val){
                    pre = pre.next;
                }
                // 将curr节点插入到对应位置
                lastSorted.next = curr.next;
                curr.next = pre.next;
                pre.next = curr;
            }
            // 更新当前节点为排序好链表下一个节点
            curr = lastSorted.next;
        }
        return dummy.next;
    }
}

链表内指定区间反转

题目链接

20210412155346

代码如下：

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
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        for(int i = 0; i < m-1; i++){
            pre = pre.next;
        }
        // 先获得翻转链表pre部分的头指针
        head = pre.next;
        ListNode next = null;
        for(int i = m; i < n; i++){
            next = head.next;
            // head节点连接next节点之后链表部分，也就是向后移动一位
            head.next = next.next;
            // next 每次移动到头结点位置
            next.next = pre.next;
            // 翻转部分头结点的前驱指向当前节点
            pre.next = next;
        }
        return dummy.next;
    }
}

删除有序链表中重复出现的元素(将重复出现的元素删完)

题目链接

20210420194927

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 前驱结点
        ListNode pre = dummy;
        // 当前结点
        ListNode curr = head;
        while(curr != null && curr.next != null){
            // 如果两个结点相等，说明结点重复
            if(curr.val == curr.next.val){
                // 找到最后一个不重复的结点
                ListNode tmp = curr.next;
                while(tmp != null && tmp.val == curr.val){
                    tmp = tmp.next;
                }
                // 将当前前驱结点接最后一个不重复的结点后面
                pre.next = tmp;
                // 更新当前结点
                curr = tmp;
            }else{
                pre = pre.next;
                curr = curr.next;
            }
        }
        return dummy.next;
    }
}

删除有序链表中重复的元素(使每个元素只出现一次)

题目链接

20210525153116

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null){
            return null;
        }
        ListNode tmp = head;
        while(tmp.next != null){
            if(tmp.val == tmp.next.val){
                tmp.next = tmp.next.next;
            }else{
                tmp = tmp.next;
            }
        }
        return head;
    }
}

链表的奇偶重排

题目链接
20210420205915

代码如下：

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
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        if(head == null){
            return head;
        }
        ListNode evenHead = head.next;
        ListNode odd = head;
        ListNode even = evenHead;
        while(even != null && even.next != null){
            // 获得奇数结点
            odd.next = even.next;
            odd = odd.next;
            // 获得偶数结点
            even.next = odd.next;
            even = even.next;
        }
        // 将奇数结点和偶数结点链接起来
        odd.next = evenHead;
        return head;
    }
}

重排链表

题目链接

20210421215012

代码如下：

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
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null)
            return;
        // 将链表分成两个部分
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode newList = slow.next;
        slow.next = null;
        // 将第二部分链表反转
        ListNode newHead = reverse(newList);
        // 合并两个链表
        while(newHead != null){
            ListNode temp = newHead.next;
            newHead.next = head.next;
            head.next = newHead;
            head = newHead.next;
            newHead = temp;
        }
    }
    
    // 反转链表
    public ListNode reverse(ListNode head){
        ListNode pre = null;
        while(head != null){
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

K 个一组翻转链表

题目链接

20210507223335

代码如下：
解法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
public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode tail = head;
    for (int i = 0; i < k; i++) {
        //剩余数量小于k的话，则不需要反转。
        if (tail == null) {
            return head;
        }
        tail = tail.next;
    }
    // 反转前 k 个元素
    ListNode newHead = reverse(head, tail);
    //下一轮的开始的地方就是tail
    head.next = reverseKGroup(tail, k);

    return newHead;
}

/*
左闭又开区间
    */
private ListNode reverse(ListNode head, ListNode tail) {
    ListNode pre = null;
    ListNode next = null;
    while (head != tail) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;

}

解法2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode end = dummy;

        // 找到待翻转链表的尾部
        while(end.next != null){
            for(int i = 0; i < k && end != null; i++){
                end = end.next;
            }
            // 如果末尾的链表长度不足k，保持原样
            if(end == null){
                break;
            }
            ListNode start = pre.next;
            // 找到待翻转部分的下一节点，并断开连接
            ListNode next = end.next;
            end.next = null;
            // 翻转链表
            pre.next = reverse(start);
            // 连接链表
            start.next = next;
            // 更新pre指针和end指针
            pre = start;
            end = start;
        }
        return dummy.next;

    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode curr = head;
        while(curr != null){
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
}

环形链表Ⅱ

题目链接

20210817214718

代码如下：

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        /**
        fast指针是slow的两倍，假设链表环以前部分长度为a，环的长度为b
        则 （1）f = 2s,且 fast 比 slow 多走n圈，则为nb，所以（2）f = s + nb
        (1) - (2) --> s = nb; 所有节点从链表头部走到环开始都需要走k步，k = a + nb;
        因为 由上式：s = nb,得出slow指针已经走了nb，还需要走a步，则可以将fast指针放在head
        处，每次走一步，并且slow指针每次也走一步，两个指针同时走a步会进行第二次相遇。
         */
        while(true){
            if(fast == null || fast.next == null){
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                break;
            }
        }
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;        
    }
}

两两交换链表中的节点

题目链接

20210817215421

代码如下：

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 边界判断
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        // 定义哑节点保存头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 定义头节点的前置节点
        ListNode pre = dummy;
        // 当前节点为pre节点的后置节点
        ListNode curr = pre.next;
        while(curr != null && curr.next != null){
            // 记录当前节点的后一节点
            ListNode next = curr.next;
            // 分以下三步交换curr和next节点
            curr.next = next.next;
            next.next = curr;
            pre.next = next;
            // 更新前置节点
            pre = curr;
            // 更新当前节点
            curr = pre.next;
        }
        return dummy.next;
    }
}

两数相加

题目链接

20210817215816

代码如下：

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(-1);
        ListNode curr = res;
        int carry = 0;
        while(l1 != null || l2 != null){
            // 获取两个节点的值
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int num = n1 + n2 + carry;
            // 计算进位以及取余
            carry = num / 10;
            num = num % 10;
            // 创建并连接新节点
            curr.next = new ListNode(num);
            curr = curr.next;
            // 如果两个链表当前节点不为空，向后移动
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
        }
        if(carry == 1){
            curr.next = new ListNode(1);
        }
        return res.next;
    }
}

大数加法

20210401192250

代码如下：

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
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // write code here
        int i = s.length() - 1;
        int j = t.length() - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        while(i >= 0 || j >= 0 || carry != 0){
            int x = i < 0 ? 0 : s.charAt(i--) - '0';
            int y = j < 0 ? 0 : t.charAt(j--) - '0';
            int sum = x + y + carry;
            sb.append(sum % 10);
            carry = sum / 10;
        }
        return sb.reverse().toString();
    }
}

二叉树

重建二叉树

20210401190107

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        Map<Integer,Integer> map = new HashMap();
        for(int i = 0; i < in.length; i++){
            map.put(in[i],i);
        }
        return dfs(0,pre.length - 1,0,in.length - 1,pre,in,map);
    }
    
    public TreeNode dfs(int pl,int pr,int il,int ir,int[] pre,int[] in,Map<Integer,Integer> map){
        if(pl > pr){
            return null;
        }
        // 根据先序遍历获得根节点
        int k = map.get(pre[pl]);
        TreeNode root = new TreeNode(pre[pl]);
        // 递归构造左子树
        root.left = dfs(pl + 1,pl  + k -il,il,k-1,pre,in,map);
        // 递归构造右子树
        root.right = dfs(pl + k- il + 1,pr,k+1,ir,pre,in,map);
        return root;
    }
}

在二叉树中找到两个节点的最近公共祖先

20210401190918

以下图片来自于牛客￥ABCDEF题解
图解
代码如下：

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
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        return dfs(root,o1,o2).val;
    }
    
    public TreeNode dfs(TreeNode root ,int o1,int o2){
        // 如果当前节点为空，或者当前节点等于o1或者等于o2就返回值给父亲节点
        if(root == null || root.val == o1 || root.val == o2){
            return root;
        }
        // 递归遍历左子树
        TreeNode left = dfs(root.left,o1,o2);
        // 递归遍历右子树
        TreeNode right = dfs(root.right,o1,o2);
        // 如果left、right都不为空，那么代表o1、o2在root的两侧，所以root为他们的公共祖先
        if(left != null && right != null){
            return root;
        }
        // 如果left、right有一个为空，那么就返回不为空的那一个
        return left == null? right : left;
    }
}

对称的二叉树

题目链接
20210401223309

代码如下：

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null ? true : recur(root.left,root.right);
    }

    public boolean recur(TreeNode A,TreeNode B){
        // 左右子树都为空，则树是对称的
        if(A == null && B == null){
            return true;
        }
        // 只有一边为空，且值不相等，则不对称
        if(A == null || B == null || A.val != B.val){
            return false;
        }
        // 递归判断左右子树，如果都对称，则树对称
        return recur(A.left,B.right) && recur(A.right,B.left);
    }
}

叶子相似的树

叶子相似的树
20210510095813

代码如下：

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 {

    List<Integer> res1 = new ArrayList();
    List<Integer> res2 = new ArrayList();

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        // 分别得到两棵树的叶值序列 
        dfs(root1,res1);
        dfs(root2,res2);
        // 比较两个数是否相同
        return res1.equals(res2);
    }


    public  void dfs(TreeNode root,List<Integer> res){
        // 根据题意，将叶子结点加入结果集
        if(root.left == null && root.right == null){
            res.add(root.val);
        }else{
            if(root.left != null){
                dfs(root.left,res);
            }
            if(root.right != null){
                dfs(root.right,res);
            }
        }
    }
}

二叉树的右视图

题目链接
20210406200218

代码如下：

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 List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList();
        if(root == null){
            return res;
        }
        Queue<TreeNode> q = new LinkedList();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode node = q.poll();
                if(node.left != null){
                    q.offer(node.left);
                }
                if(node.right != null){
                    q.offer(node.right);
                }
                // 将每一层的最后一个加入结果集,即为右视图
                if(i == size - 1){
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}

二叉树根节点到叶子节点和为指定值的路径

题目链接

20210412140517

代码如下：

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
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    
    ArrayList<ArrayList<Integer>> res = new ArrayList();
    ArrayList<Integer> tmp = new ArrayList();
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        dfs(root,sum,0);
        return res;
    }
    
    public void dfs(TreeNode root, int sum,int cnt){
        if(root == null){
            return;
        }
        // 如果节点为空结束当前递归
        tmp.add(root.val);
        // 把当前节点加入到路径和中
        cnt += root.val;
        // 如果找到叶子节点
        if(root.left == null && root.right == null){
            // 如果找到结果，将tmp加入结果集res
            if(sum == cnt){
                res.add(new ArrayList(tmp));
            }
        }else{
            // 递归左子树
            dfs(root.left,sum,cnt);
            // 递归右子树
            dfs(root.right,sum,cnt);
        }
        // 移除最后一个元素
        tmp.remove(tmp.size() - 1);
    }
}

二叉树根节点到叶子结点的所有路径和

题目链接

20210420171028

代码如下：

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
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int sumNumbers (TreeNode root) {
        if(root == null){
            return 0;
        }
        return dfs(root,0);
    }
    
    
    public int dfs(TreeNode root, int sum){
        if(root == null){
            return 0;
        }else{
            sum = sum * 10 + root.val;
            if(root.left == null && root.right == null){
                return sum;
            }else{
                // 直接将同级的叶子结点加起来
                return dfs(root.left,sum) + dfs(root.right,sum);
            }
        }
    }
}

二叉树从根节点到叶子结点路径问题

使用回溯求出所有路径，再根据具体题目要求筛选结果
代码如下：

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 {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root) {
        dfs(root);
        return ret;
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        // 将当前结点加入路径中
        path.offerLast(root.val);
        // 如果到达最底部，说明该路径
        if (root.left == null && root.right == null) {
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left);
        dfs(root.right);
        // 回到上一状态
        path.pollLast();
    }
}

二叉树中是否存在节点和为指定值的路径

题目链接

20210527153056

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root == null){
            return false;
        }
        sum -= root.val;
        if(sum == 0 && root.left == null && root.right == null){
            return true;
        }
        return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
    }
}

二叉树的最大路径和

题目链接

20210429113615

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    
    private int Max = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        dfs(root);
        return Max;
    }
    
    public int dfs(TreeNode root){
        if(root == null){
            return 0;
        } 
        int left = dfs(root.left);
        int right = dfs(root.right);
        int curr = root.val;
        // 如果左右子树大于0，则更新当前最大值
        if(left > 0){
            curr += left;
        }
        if(right > 0){
            curr += right;
        }
        // 更新当前最大值
        Max = Math.max(Max,curr);
        // 返回最大值
        return Math.max(root.val,Math.max(left,right) + root.val);
    }
}

左叶子之和

题目链接

20210817220252

代码如下：

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }

        int sum = 0;
        Queue<TreeNode> q = new LinkedList();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode node = q.poll();
                // 如果左孩子不为空
                if(node.left != null){
                    // 如果当前节点为左叶子节点
                    if(node.left.left == null && node.left.right == null){
                        sum += node.left.val;
                    }else{
                        q.offer(node.left);
                    }
                }
                if(node.right != null){
                    q.offer(node.right);
                }
            }
        }
        return sum;
    }
}

二叉树的所有路径

题目链接

20210817220856

代码如下:

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList();
        if(root == null){
            return paths;
        }
        constructPath(root,"",paths);
        return paths;
    }

    public void constructPath(TreeNode root,String s,List<String> paths){
        if(root != null){
            StringBuilder sb = new StringBuilder(s);
            sb.append(root.val);
            // 判断是不是叶子节点，如果是，加入结果集
            if(root.left == null && root.right == null){
                paths.add(sb.toString());
            }else{
                // 递归构建结果
                sb.append("->");
                constructPath(root.left,sb.toString(),paths);
                constructPath(root.right,sb.toString(),paths);
            }
        }
    } 
}

动态规划

子数组的最大累加和问题

20210401191428

以下图片来自于牛客￥ABCDEF题解
图解

代码如下：
解法1：循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int helper(int[] array) {
        int len = array.length;
        if (len == 0) {
            return 0;
        }
        // 累加子数组和
        int currSum = array[0];
        // 最大子数组和
        int maxSum = array[0];

        for (int i = 1; i < len; i++) {
            // 如果当前”累加子数组和“ 大于0，与当前数累加
            if (currSum > 0) {
                currSum += array[i];
            } else {
                // 如果当前”累加子数组和“ 小于0，抛弃前面累加和，从当前数开始累加
                currSum = array[i];
            }
            // 更新最大子数组和
            maxSum = Math.max(maxSum, currSum);
        }
        return maxSum;
    }

解法2：DP

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
import java.util.*;


public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxsumofSubarray (int[] arr) {
        // write code here
        //dp[i]代表到第i位的时侯,以arr[i]结尾的连续子数组最大累加和
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        int res = arr[0];
        for(int i = 1; i< arr.length; i++){
            // 如果前面的子数组和大于0，则更新当前位置
            if(dp[i-1] > 0){
                dp[i] = dp[i-1] + arr[i];
            }else{ // 否则，更新当前dp值为当前数组值
                dp[i] = arr[i];
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

最长递增子序列

1. 题目链接

20210401204605

代码如下:
解法一：DP（超时）

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
import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        int[] dp = new int[arr.length];
        int max = 1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < arr.length; i ++) {
            for (int j = 0; j < i; j ++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(max, dp[i]);
                }
            }
        }
        int[] res = new int[max];
        int index = dp.length - 1;
        while (index >= 0) {
            if (dp[index] == max) {
                res[max - 1] = arr[index];
                max --;
            }
            index --;
        }
        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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        int[] d = new int[arr.length];
        int[] index = new int[arr.length];
        int len = 0;
        
        d[len] = arr[len];
        index[0] = 0;
        for (int i = 1; i < arr.length; i ++) {
            if (arr[i] > d[len]) {
                len ++;
                d[len] = arr[i];
                index[i] = len;
            }
            else {
                int l = 0, r = len;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (d[mid] < arr[i]) {
                        l = mid + 1;
                    }
                    else {
                        r = mid - 1;
                    }
                }
                d[l] = arr[i];
                index[i] = l;
            }
        }
        int[] res = new int[len + 1];
        int cur = arr.length - 1;
        while (cur >= 0) {
            if (index[cur] == len) {
                res[len] = arr[cur];
                len --;
            }
            cur --;
        }
        return res;
    }
}

2.题目链接
20210401214846

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // dp数组表示以nums[1]结尾的“最长上升子序列”的长度
        int[] dp = new int[n];
        // 初始化dp数组为1
        Arrays.fill(dp,1);
        for(int i = 1; i < n; i++){
            // 下标为i以前上升子序列
            for(int j= 0; j < i; j++){
                if(nums[j] < nums[i]){
                    // 根据状态转换图更新最长上升子序列的长度
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
        }
        // 找到最大值
        int max = 0;
        for(int i = 0; i < n; i++){
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

最长公共子序列（返回值为子序列的长度）

题目链接
20210403133829

代码如下：

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

最长公共子序列（返回值为子序列）

题目链接

20210412161531

代码如下:

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
import java.util.*;


public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        
        // 从末尾开始向前找
        StringBuilder sb = new StringBuilder();
        int a = len1;
        int b = len2;
        while(a != 0 && b != 0){
            // 如果是公共子串
            if(s1.charAt(a-1) == s2.charAt(b-1)){
                // 加入结果集
                sb.append(s1.charAt(a-1));
                a--;
                b--;
            }else{
                // 从上面来
                if(dp[a-1][b] > dp[a][b-1]){
                    a--;
                }else{
                    // 从下面来
                    b--;
                }
            }
        }
        if(sb.length() == 0){
            return "-1";
        }else{
            return sb.reverse().toString();
        }
    }
}

不相交的线

题目链接

20210521210502

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m+1][n+1];

        for(int i = 1; i <= m; i++){
            int num1 = nums1[i-1];
            for(int j = 1; j <= n; j++){
                int num2 = nums2[j-1];
                if(num1 == num2){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[m][n];
    }
}

买卖股票的最佳时机

题目链接
20210404205827

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int min = Integer.MAX_VALUE;
        int maxProfit = 0;
        for(int i = 0; i < prices.length; i++){
            // 记录历史最低价
            if(prices[i] < min){
                min = prices[i];
            }else if(prices[i] - min > maxProfit){
                // 更新最大收益
                maxProfit = prices[i] - min;
            }
        }
        return maxProfit;
    }
}

买卖股票的最佳时机 II

题目链接

20210404210444

代码如下：

1

编辑距离

题目链接

20210409220146

代码如下：

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
import java.util.*;


public class Solution {
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m+1][n+1];
        // 初始化第一行
        for(int j = 1; j <= n; j++){
            dp[0][j] = j * ic;
        }
        // 初始化第一列
        for(int i = 1; i <= m; i++){
            dp[i][0] = i * dc;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(str1.charAt(i-1) == str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    // 将i个字符串转变为前j-1个字符串在插入第j个字符
                    int insert = dp[i][j-1] + ic;
                    // 将i-1个字符串转换为前j个字符串删除第i个字符
                    int delete = dp[i-1][j] + dc;
                    int replace = dp[i-1][j-1] + rc;
                    dp[i][j] = Math.min(Math.min(insert,delete),replace);
                }
            }
        }
        return dp[m][n];
    }
}

零钱兑换

题目链接

20210419140623

奇怪的打印机

题目链接

20210524223727

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int strangePrinter(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i][j - 1];
                } else {
                    int minn = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
                        minn = Math.min(minn, f[i][k] + f[k + 1][j]);
                    }
                    f[i][j] = minn;
                }
            }
        }
        return f[0][n - 1];
    }
}

最大正方形

题目链接

20210819232715

代码如下:

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 maximalSquare(char[][] matrix) {
        int max = 0;
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return max;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == '1'){
                    // 如果是第一行或者第一列，初始化值为1
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        // 更新当前位置能够组成的最大边长
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                }
                // 更新最大边长
                max = Math.max(max,dp[i][j]);
            }
        }
        return max * max;
    }
}

中心扩散法

最长回文子串

20210401190434

代码如下：

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
import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        int len = A.length();
        if(len < 2){
            return A.length();
        }
        int max = 0;
        for(int i = 0; i < len - 1; i++){
            // 回文类型为奇数型
            String s1 = helper(A,i,i);
            // 回文类型为偶数型
            String s2 = helper(A,i,i+1);
            // 求出最长的回文串
            String s3 = s1.length() > s2.length()? s1: s2;
            if(max < s3.length()){
                max = s3.length();
            }
        }
        return max;
    }
    
    public String helper(String s, int left, int right){
        int len = s.length();
        int i = left;
        int j = right;
        // 从中间向两边扩散
        while(i >= 0 && j < len){
            if(s.charAt(i) == s.charAt(j)){
                i--;
                j++;
            }else{
                break;
            }
        }
        // 截取回文串
        return s.substring(i+1,j);
    } 
}

单调栈

直方图的水量(接雨水)

题目链接
20210402140411

代码如下(双指针)：

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 trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int ans = 0;
        int leftMax = 0;
        int rightMax = 0;
        while(left < right){
            // 更新左边的最大值
            leftMax = Math.max(leftMax,height[left]);
            // 更新右边的最大值
            rightMax = Math.max(rightMax,height[right]);
            if(height[left] < height[right]){
                // 用左边的最大值减去当前高度
                ans += leftMax - height[left];
                left++;
            }else{
                // 用右边的最大值减去当前高度
                ans += rightMax - height[right];
                right--;
            }
        }
        return ans;
    }
}

代码如下(单调栈):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int trap(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList();
        for(int i = 0; i < height.length; i++){
            while(!stack.isEmpty() && height[i] > height[stack.peek()] ){
                int top = stack.pop();
                if(stack.isEmpty()){
                    break;
                }
                int left = stack.peek();
                int width = i - left - 1;
                int currHeight = Math.min(height[i],height[left]) - height[top];
                ans += currHeight * width;
            }
            stack.push(i);
        }
        return ans;
    }
}

柱状图中最大的矩形

题目链接
20210402144908

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
public int largestRectangleArea(int[] heights) {
        // 初始化最终结果为0
        int res = 0;
        Stack<Integer> stack = new Stack<>();

        // 将给定的原数组左右各添加一个元素0
        int[] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length-1] = 0;
        for (int i = 1; i < heights.length + 1; i++) {
            newHeights[i] = heights[i - 1];
        }

        // 开始遍历
        for (int i = 0; i < newHeights.length; i++) {
            // 如果栈不为空且当前考察的元素值小于栈顶元素值，
            // 则表示以栈顶元素值为高的矩形面积可以确定
            while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
                // 弹出栈顶元素
                int cur = stack.pop();
                // 获取栈顶元素对应的高
                int curHeight = newHeights[cur];
                // 栈顶元素弹出后，新的栈顶元素就是其左侧边界
                int leftIndex = stack.peek();
                // 右侧边界是当前考察的索引
                int rightIndex = i;
                // 计算矩形宽度
                int curWidth = rightIndex - leftIndex - 1;
                // 计算面积
                res = Math.max(res, curWidth * curHeight);
            }   
            // 当前考察索引入栈
            stack.push(i);
        }
        return res;
    }

去除重复字母

题目链接

20210505224655

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public String removeDuplicateLetters(String s) {
        int len = s.length();
        char[] ss = s.toCharArray();
        // 记录当前字符是否在栈中出现
        boolean[] visited = new boolean[26];
        // 记录每个元素最后出现的位置，用来判断当前元素是否可能在后面的元素中出现，如果出现则丢弃当前元素
        int[] lastIndex = new int[26];

        for(int i = 0; i < len; i++){
            lastIndex[ss[i] - 'a'] = i;
        }

        Deque<Character> stack = new ArrayDeque();

        for(int i = 0; i < len; i++){
            // 判断当前元素是否在栈中出现，如果出现则跳过
            if(visited[ss[i] - 'a']){
                continue;
            }
            // 如果栈不为空且不满足递增且栈顶元素会在后面出现
            while(!stack.isEmpty() && stack.peekLast() > ss[i] && lastIndex[stack.peekLast() - 'a'] > i){
                char ch = stack.pollLast();
                // 栈中不存在该元素
                visited[ch - 'a'] = false;
            }

            stack.offerLast(ss[i]);
            // 栈中存在该元素
            visited[ss[i] - 'a'] = true;
        }

        StringBuilder sb = new StringBuilder();
        for(char c : stack){
            sb.append(c);
        }
        return sb.toString();
    }
}

拼接最大数

拼接最大数

20210506132308

代码如下：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] preMax = new int[k];
        for(int i = 0; i <= k; i++){
            if(i > len1 || k - i > len2){
                continue;
            }
            // 用单调栈求出最优子序列
            int[] max1 = minStack(nums1,i);
            // 用单调栈求出最优子序列
            int[] max2 = minStack(nums2,k-i);
            // 合并两个数组
            int[] tmp = mergeArray(max1,max2);
            // 更新最优解
            if(compare(tmp,0,preMax,0) > 0){
                System.arraycopy(tmp, 0, preMax, 0, k);
            }
        }
        return preMax;
    }
    // 用单调栈求出最优子序列（核心部分）
    public static int[] minStack(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[k];

        Deque<Integer> stack = new ArrayDeque();
        int index = 0;
        while (index < n) {
            // 如果栈为空或者栈顶元素大于当前元素
            while (index < n && (stack.isEmpty() || stack.peekLast() >= nums[index])) {
                // 将当前元素入栈
                stack.offerLast(nums[index++]);
            }
            // 如果元素已经使用完，跳出循环
            if (index == n) {
                break;
            }
            // 当栈不为空且栈顶元素小于当前元素并且栈内元素加上未使用的元素大于等于k
            while (!stack.isEmpty() && stack.peekLast() < nums[index] && stack.size() + n - index - 1 >= k) {
                // 弹出栈顶元素
                stack.pollLast();
            }
            // 将当前元素加入栈
            stack.offerLast(nums[index++]);
        }
        // 获得结果集
        for (int i = 0; i < k; i++) {
            res[i] = stack.pollFirst();
        }
        return res;
    }

    // 合并两个数组
    public int[] mergeArray(int[] subsequence1, int[] subsequence2) {
        int x = subsequence1.length, y = subsequence2.length;
        if (x == 0) {
            return subsequence2;
        }
        if (y == 0) {
            return subsequence1;
        }
        int mergeLength = x + y;
        int[] merged = new int[mergeLength];
        int index1 = 0, index2 = 0;
        for (int i = 0; i < mergeLength; i++) {
            if (compare(subsequence1, index1, subsequence2, index2) > 0) {
                merged[i] = subsequence1[index1++];
            } else {
                merged[i] = subsequence2[index2++];
            }
        }
        return merged;
    }

    // 比较方法
    public int compare(int[] subsequence1, int index1, int[] subsequence2, int index2) {
        int x = subsequence1.length, y = subsequence2.length;
        while (index1 < x && index2 < y) {
            int difference = subsequence1[index1] - subsequence2[index2];
            if (difference != 0) {
                return difference;
            }
            index1++;
            index2++;
        }
        return (x - index1) - (y - index2);
    }
}

滑动窗口最大值(单调队列)

题目链接

20210525155614

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> queue = new ArrayDeque();
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        for(int i = 0; i < nums.length; i++){
            // 保证队列单调递减
            while(!queue.isEmpty() && queue.peekLast() < nums[i]){
                queue.pollLast();
            }
            // 满足单调递减，加入元素
            queue.addLast(nums[i]);
            if(i >= k - 1){
                // 获得最大值，即队首元素
                res[index++] = queue.peekFirst();
                if(i >= k-1 && nums[i - k + 1] == queue.peekFirst()){
                    // 移除窗口最左边的值
                    queue.removeFirst();
                }
            }
        }
        return res;
    }
}

栈

设计getMin功能的栈

题目链接

20210404203630

代码如下：

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
import java.util.*;


public class Solution {
    public Deque<Integer> s = new LinkedList();
    public Deque<Integer> min_s = new LinkedList();
    
    /**
     * return a array which include all ans for op3
     * @param op int整型二维数组 operator
     * @return int整型一维数组
     */
    public int[] getMinStack (int[][] op) {
        List<Integer> res = new ArrayList();
        for(int i = 0; i < op.length; i++){
            if(op[i][0] == 1){
                Push(op[i][1]);
            }else if(op[i][0] == 2){
                Pop();
            }else{
                res.add(getMin());
            }
        }
        int[] ans = new int[res.size()];
        for(int  i = 0; i < ans.length; i++){
            ans[i] = res.get(i);
        }
        return ans;
    }
    
    
    // 如果最小栈为空，或者栈顶元素大于x，则加入最小栈
    public void Push(int x){
        s.push(x);
        if(min_s.isEmpty() || min_s.peek() > x){
            min_s.push(x);
        }
        
    }
    // 如果最小栈栈顶元素和栈s中要出栈的元素相等，那么也需要出栈
    public void Pop(){
        if(!s.isEmpty()){
            if(s.peek().equals(min_s.peek())){
                min_s.pop();
            }
            s.pop();
        }
    }
    // 获得最小栈栈顶元素
    public int getMin(){
        return min_s.peek();
    }
}

用两个栈实现队列

题目链接

20210415224503

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 CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    
    public CQueue() {
        stack1 = new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        // 如果第二个栈为空
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        } 
        if (stack2.isEmpty()) {
            return -1;
        } else {
            int deleteItem = stack2.pop();
            return deleteItem;
        }
    }
}

队列

用队列实现栈

225. 用队列实现栈

20210901172441

代码如下：

只使用一个队列：

一个队列

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 MyStack {
    Queue<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        int n = queue.size();
        queue.offer(x);
        for (int i = 0; i < n; i++) {
            queue.offer(queue.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

使用两个队列：

两个队列

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 MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

回溯

字符串的排列

题目链接

20210406192459

代码入下：

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
import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        int len = str.length();
        char[] strs = str.toCharArray();
        // 对字符数组排序
        Arrays.sort(strs);
        ArrayList<String> res = new ArrayList();
        // 存放路径
        Deque<Character> path = new ArrayDeque();
        // 保存该字符是否用过
        boolean[] used = new boolean[len];
        // 深度有限遍历求得所有结果集
        dfs(strs,len,0,used,res,path);
        return res;
    }
    
    public void dfs(char[] strs,int len,int depth,boolean[] used,ArrayList<String> res,Deque<Character> path){
        // 如果到达最深的一层
        if(len == depth){
            // 封装结果
            StringBuilder sb = new StringBuilder();
            for(char ch : path){
                sb.append(ch);
            }
            res.add(new String(sb));
            return;
        }
        for(int i = 0; i < len; i++){
            // 判断当前字符是否用过
            if(used[i]){
                continue;
            }
            // 因为有重复元素，所以在下一层碰到相同元素将会使结果重复，相对于全排列，进一步剪枝
            if(i > 0 && strs[i] == strs[i-1] && !used[i-1]){
                continue;
            }
            // 回溯算法经典步骤
            // 先将当前字符加入栈，并将使用过的元素标记为true
            path.addLast(strs[i]);
            used[i] = true;
            dfs(strs,len,depth + 1,used,res,path);
            // 回到之前的状态
            path.removeLast();
            used[i] = false;
        }
    }
}

全排列 II

题目链接

20210406192852

代码如下：

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
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 数组长度
        int len = nums.length;
        Arrays.sort(nums);
        // 结果集
        List<List<Integer>> res = new ArrayList();
        // 双端队列，保存临时路径
        Deque<Integer> path = new ArrayDeque();
        // 布尔数组，保存改数字是否使用过
        boolean[] used = new boolean[len];
        // 深度优先遍历求所有结果集
        dfs(nums,len,0,used,path,res);
        return res;
    }

    public void dfs(int[] nums,int len,int depth,boolean[] used,Deque<Integer> path,List<List<Integer>> res){
        // 如果到达最深的一层
        if(depth == len){
            // 将当前路径加入结果集
            res.add(new ArrayList(path));
            return;
        }

        for(int i = 0 ; i < len; i++){
            // 判断当前数字是否用过
            if(used[i]){
                continue;
            }
            // 因为有重复元素，所以在下一层碰到相同元素将会使结果重复，相对于全排列，进一步剪枝
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            // 回溯算法经典步骤
            // 先将当前数字加入栈，并将使用过的元素标记为true
            path.addLast(nums[i]);
            used[i] = true;
            dfs(nums,len,depth + 1,used,path,res);
            // 回到之前的状态
            path.removeLast();
            used[i] = false;
        }
    }
}

括号生成

题目链接

20210421210802

代码如下：

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
public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> res = new ArrayList();
        backtrack("",0,0,n,res);
        return res;
    }
    
    public void backtrack(String s,int open,int close,int n, List<String> res){
        // 如果长度够了，加入结果集
        if(s.length() == n << 1){
            res.add(s);
            return;
        }
        if(open < n){
            backtrack(s + "(",open + 1,close,n,res);
        }
        if(close < open){
            backtrack(s + ")",open,close + 1, n ,res);
        }
    }
}

DFS

剑指 Offer 12. 矩阵中的路径

题目链接
20210419135630

代码如下：

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 Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if(dfs(board,words,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board,char[] words,int i, int j, int k){
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[k]){
            return false;
        }
        if( k == words.length - 1){
            return true;
        }
        board[i][j] = '\0';
        boolean res = dfs(board,words,i+1,j,k+1) || dfs(board,words,i-1,j,k+1) || dfs(board,words,i,j+1,k+1) ||dfs(board,words,i,j-1,k+1);
        board[i][j] = words[k];
        return res;
    }
}

合并区间

题目链接

20210412142702

代码入下：

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
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
import java.util.*;
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList();
        // 根据节点左边从小到大排序
        Collections.sort(intervals,(a,b)->{
            return a.start - b.start;
        });
        int i = 0;
        int n = intervals.size();
        while(i < n){
            // 获得当前节点的左右端点
            int left = intervals.get(i).start;
            int right = intervals.get(i).end;
            // 如果下一节点的左端点小于等于当前节点右端
            while(i < n - 1 && intervals.get(i+1).start <= right){
                // 更新右端点的值
                right = Math.max(right,intervals.get(i+1).end);
                i++;
            }
            // 将当前区间加入结果集
            res.add(new Interval(left,right));
            i++;
        }
        return res;
    }
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://xmmarlowe.github.io/2021/04/01/%E9%A2%98%E8%A7%A3/%E7%A0%94%E5%8F%91%E9%AB%98%E9%A2%91%E7%AE%97%E6%B3%95%E9%A2%98/

Marlowe

更新于：Sep 5, 2021

评论