螺旋矩阵

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 List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return list;
        }
        int left = 0, up = 0, right = matrix[0].length - 1, down = matrix.length - 1;
        int x = 0, y = 0;
        while (left <= right && up <= down) {
            for (y = left; y <= right && avoid(left, right, up, down); y++) {
                list.add(matrix[x][y]);
            }
            y--;
            up++;
            for (x = up; x <= down && avoid(left, right, up, down); x++) {
                list.add(matrix[x][y]);
            }
            x--;
            right--;
            for (y = right; y >= left && avoid(left, right, up, down); y--) {
                list.add(matrix[x][y]);
            }
            y++;
            down--;
            for (x = down; x >= up && avoid(left, right, up, down); x--) {
                list.add(matrix[x][y]);
            }
            x++;
            left++;
        }
        return list;
    }

    private boolean avoid(int left, int right, int up, int down) {
        return up <= down && left <= right;
    }
}

救生艇

贪心、双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0, j = people.length - 1, rlt = 0;
        while (i <= j) {
            rlt++;
            if (people[i] + people[j] <= limit) {
                i++;
            }
            j--;
        }
        return rlt;
    }
}

有效的山脉数组

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 validMountainArray(int[] A) {
        if (A.length < 3) {
            return false;
        }
        int index = IntStream.range(0, A.length).reduce((i, j) -> A[i] < A[j] ? j : i).getAsInt();
        if (index == 0 || index == A.length - 1) {
            return false;
        }
        for (int i = 1; i <= index; i++) {
            if (A[i] - A[i - 1] <= 0) {
                return false;
            } else {
                continue;
            }
        }
        for (int i = index + 1; i < A.length; i++) {
            if (A[i] - A[i - 1] >= 0) {
                return false;
            } else {
                continue;
            }
        }
        return true;
    }
}

灯泡开关

？

1
2
3
4
5
class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }
}

猜数字游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String getHint(String secret, String guess) {
        int a = 0, b = 0;
        int[] mapS = new int[10];
        int[] mapG = new int[10];
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                a++;
            } else {
                mapS[secret.charAt(i) - '0']++;
                mapG[guess.charAt(i) - '0']++;
            }
        }
        for (int i = 0; i < 10; i++) {
//            System.out.println("i:" + i + " g:" + mapG[i] + " s" + mapS[i]);
            b += Math.min(mapG[i], mapS[i]);
        }

        return String.valueOf(a) + 'A' + String.valueOf(b) + 'B';
    }
}

单词接龙

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
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (wordSet.size() == 0 || !wordSet.contains(endWord)) {
            return 0;
        }
        wordSet.remove(beginWord);

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);

        //BFS
        int step = 1;
        while (!queue.isEmpty()) {
            int currentSize = queue.size();
            for (int i = 0; i < currentSize; i++) {
                String currentWord = queue.poll();
                if (changeWordEveryOneLetter(currentWord, endWord, queue, visited, wordSet)) {
                    return step + 1;
                }
            }
            step++;
        }
        return 0;
    }

    private boolean changeWordEveryOneLetter(String currentWord, String endWord, Queue<String> queue, Set<String> visited, Set<String> wordSet) {
        char[] charArray = currentWord.toCharArray();
        for (int i = 0; i < endWord.length(); i++) {
            char originChar = charArray[i];
            for (char k = 'a'; k <= 'z'; k++) {
                if (k == originChar) {
                    continue;
                }
                charArray[i] = k;
                String nextWord = String.valueOf(charArray);
                if (wordSet.contains(nextWord)) {
                    if (nextWord.equals(endWord)) {
                        return true;
                    }
                    if (!visited.contains(nextWord)) {
                        queue.add(nextWord);
                        visited.add(nextWord);
                    }
                }
            }
            charArray[i] = originChar;
        }
        return false;
    }
}

整数拆分

dp[i]=1≤j<imax{max(j×(i−j),j×dp[i−j])}

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
}

根据数字二进制下 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
class Solution {
    public int[] sortByBits(int[] arr) {
        int[] bits = new int[10001];
        List<Integer> list = new ArrayList<Integer>();
        for (int i : arr) {
            list.add(i);
            bits[i] = get1Num(i);
        }
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (bits[o1] != bits[o2]) {
                    return bits[o1] - bits[o2];
                } else {
                    return o1 - o2;
                }
            }
        });
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
        return arr;

    }

    private int get1Num(int x) {
        int rlt = 0;
        while (x != 0) {
            rlt += x % 2;
            x /= 2;
        }
        return rlt;
    }
}

移动石子直到连续

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] numMovesStones(int a, int b, int c) {
        int[] abc = {a, b, c};
        Arrays.sort(abc);
        int x = abc[1] - abc[0] - 1;
        int y = abc[2] - abc[1] - 1;
        System.out.println(x+" "+y);
        int max = x + y;
        int min;
        if (x > 1 && y > 1) {
            min = 2;
        } else if (x <= 0 && y <= 0) {
            min = 0;
        } else {
            min = 1;
        }
        return new int[]{min, max};
    }
}

Nim 游戏

1
2
3
4
5
class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

最接近原点的 K 个点

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[][] kClosest(int[][] points, int K) {
        int[][] rlt = new int[K][2];
        List<List<Integer>> lists = new ArrayList<>();
        for (int[] point : points) {
            List<Integer> list = Arrays.stream(point).boxed().collect(Collectors.toList());
            lists.add(list);
        }
        Collections.sort(lists, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o1.get(0) * o1.get(0) + o1.get(1) * o1.get(1)) - (o2.get(0) * o2.get(0) + o2.get(1) * o2.get(1));
            }
        });
        for (int i = 0; i < K; i++) {
            rlt[i][0] = lists.get(i).get(0);
            rlt[i][1] = lists.get(i).get(1);
        }
        return rlt;
    }
}
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[][] kClosest(int[][] points, int K) {
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] point1, int[] point2) {
                return (point1[0] * point1[0] + point1[1] * point1[1]) - (point2[0] * point2[0] + point2[1] * point2[1]);
            }
        });
        return Arrays.copyOfRange(points, 0, K);
    }
}

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

(复习)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//JAVA
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int total = len1 + len2;
        int left = (total + 1) / 2;
        int right = (total + 2) / 2;
        return (findK(nums1, 0, nums2, 0, left) + findK(nums1, 0, nums2, 0, right)) / 2.0;

    }

    //找到两个数组中第k小的元素
    public int findK(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length)
            return nums2[j + k - 1];
        if (j >= nums2.length)
            return nums1[i + k - 1];
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }
        //计算出每次要比较的两个数的值，来决定 "删除"" 哪边的元素
        int mid1 = (i + k / 2 - 1) < nums1.length ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int mid2 = (j + k / 2 - 1) < nums2.length ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        //通过递归的方式，来模拟删除掉前K/2个元素
        if (mid1 < mid2) {
            return findK(nums1, i + k / 2, nums2, j, k - k / 2);
        }
        return findK(nums1, i, nums2, j + k / 2, k - k / 2);
    }
}

数组中的第K个最大元素

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

下一个排列

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
class Solution {
    public void nextPermutation(int[] nums) {
        int flag = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                flag = 1;
                swap(nums, findMinBigger(nums, i), i - 1);
                Arrays.sort(nums, i, nums.length);
                break;
            }
        }
        if (flag == 0) {
            Arrays.sort(nums);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private int findMinBigger(int[] nums, int i) {
        int[] numbers = new int[nums.length - i];
        int temp = 0;
        System.arraycopy(nums, i, numbers, 0, nums.length - i);
        Arrays.sort(numbers);
        for (int j = 0; j < numbers.length; j++) {
            if (numbers[j] > nums[i - 1]) {
                temp = numbers[j];
                break;
            }
        }
        for (int j = i; j < nums.length; j++) {
            if (nums[j] == temp) {
                return j;
            }
        }
        return -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
class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0, right = len-1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] < nums[right]){
                //右边有序
                if(nums[mid] < target && target <= nums[right])
                    left = mid+1;
                else
                    right = mid-1;
            }
            else{
                //左边有序
                if(nums[left] <= target && target < nums[mid])
                    right = mid-1;
                else
                    left = mid+1;
            }
        }
        return -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
class Solution {
    public int findRotateSteps(String ring, String key) {
        // dp[i][j]表示key[i]与ring[j]对应且在12：00对齐的最小步数
        int n = ring.length(), m = key.length();
        List<Integer>[] pos = new List[26];
        // pos[i] ring[i]字符位置
        for (int i = 0; i < 26; i++) {
            pos[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n; i++) {
            pos[ring.charAt(i) - 'a'].add(i);
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], 0x3f3f3f);
        }
        for (int i : pos[key.charAt(0) - 'a']) {
            dp[0][i] = Math.min(i - 0, n - (i - 0)) + 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j : pos[key.charAt(i) - 'a']) {
                for (int k : pos[key.charAt(i - 1) - 'a']) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1);
                }
            }
        }
        return Arrays.stream(dp[m - 1]).min().getAsInt();
    }
}

搜索二维矩阵

两个二分

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 boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        int top = 0, bottom = matrix.length - 1;
        while (top < bottom) {
            int mid = (top + bottom) / 2;
            if (target > matrix[mid][matrix[0].length - 1]) {
                top = mid + 1;
            } else {
                //有可能在mid这一行
                bottom = mid;
            }
        }
        int row = top;
        int left = 0, right = matrix[0].length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}

子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    /**
     * 以开头为基准
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        List<Integer> tempSubsets = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) {
            backtracking(0, tempSubsets, subsets, i, nums);
        }
        return subsets;
    }

    private void backtracking(int start, List<Integer> tempSubsets, List<List<Integer>> subsets, int size, int[] nums) {
        if (tempSubsets.size() == size) {
            subsets.add(new ArrayList<>(tempSubsets));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            tempSubsets.add(nums[i]);
            backtracking(i + 1, tempSubsets, subsets, size, nums);
            //回溯
            tempSubsets.remove(tempSubsets.size() - 1);
        }
    }
}

按奇偶排序数组 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] sortArrayByParityII(int[] A) {
        //双指针 奇数偶数指针
        int[] B = new int[A.length];
        int odd = 1, even = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] % 2 == 0) {
                B[even] = A[i];
                even+=2;
            } else {
                B[odd] = A[i];
                odd+=2;
            }
        }
        return B;
    }
}

旋转图像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void rotate(int[][] matrix) {
        // 最外圈开始
        int temp;
        for (int x = 0, y = matrix[0].length - 1; x < y; x++, y--) {
            for (int i = x, j = y; i < y; i++, j--) {
                temp = matrix[x][i];
                matrix[x][i] = matrix[j][x];
                matrix[j][x] = matrix[y][j];
                matrix[y][j] = matrix[i][y];
                matrix[i][y] = temp;
            }
        }
    }
}

奇偶链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode odd = head, even = head.next;
        ListNode evenHead = even;
        while (even != null && even.next != null) {
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

螺旋矩阵 II

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[][] generateMatrix(int n) {
        int[][] rlt = new int[n][n];
        int num = 1;
        int left = 0, right = n - 1, up = 0, down = n - 1;
        int x = 0, y = 0;
        while (left <= right && up <= down) {
            for (y = left; y <= right && avoid(left, right, up, down); y++,num++) {
                rlt[x][y] = num;
            }
            y--;
            up++;
            for (x = up; x <= down && avoid(left, right, up, down); x++, num++) {
                rlt[x][y] = num;
            }
            x--;
            right--;
            for (y = right; y >= left && avoid(left, right, up, down); y--, num++) {
                rlt[x][y] = num;
            }
            y++;
            down--;
            for (x = down; x <= up && avoid(left, right, up, down); x--, num++) {
                rlt[x][y] = num;
            }
            x++;
            left++;
        }
        return rlt;
    }

    private boolean avoid(int left, int right, int up, int down) {
        return left <= right && up <= down;
    }
}

数组的相对排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        List<Integer> list = new ArrayList<>(arr1.length);
        int[] nums = new int[1001];
        for (int i : arr1) {
            nums[i]++;
        }
        for (int i : arr2) {
            while (nums[i] > 0) {
                list.add(i);
                nums[i]--;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0) {
                list.add(i);
                nums[i]--;
            }
        }
        int[] rlt = list.stream().mapToInt(Integer::intValue).toArray();
        return rlt;
    }
}

移掉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
35
class Solution {
    StringBuilder nums;

    public String removeKdigits(String num, int k) {
        if (k == num.length()) {
            return "0";
        }
        nums = new StringBuilder(num);
        while (k > 0) {
            deleteTopBig(nums);
            k--;
        }
        System.out.println(nums.toString());
        return nums.toString();

    }

    private void deleteTopBig(StringBuilder nums) {
        boolean flag = true;
        int i;
        for (int i = 1; i < nums.length(); i++) {
            if (nums.charAt(i - 1) > nums.charAt(i)) {
                nums.delete(i - 1, i);
                flag = false;
                break;
            }
        }
        if (flag) {
            nums.delete(nums.length() - 1, nums.length());
        }
        while (nums.length() > 1 && nums.charAt(0) == '0') {
            nums.delete(0, 1);
        }
    }
}

根据身高重建队列

h按降序排序，若h相等则k按升序排序。从头到尾遍历，k值就是此时该人位置索引。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < people.length; i++) {
            list.add(people[i][1], people[i]);
        }
        return list.toArray(new int[list.size()][]);
    }
}

斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        }
        if (N == 1 || N == 2) {
            return 1;
        }
        int prev = 1,curr = 1;
        for (int i = 3; i <= N; i++) {
            int sum = prev + curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    }
}

零钱兑换

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

加油站

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int start = 0;
        if (Arrays.stream(gas).sum() < Arrays.stream(cost).sum()) {
            return -1;
        }
        for (int i = 0; i < gas.length; i++) {//开始的遍历
            int sur = 0;
            if (cost[i] > gas[i]) {
                continue;
            }
            start = i;
            sur = gas[i] - cost[i];
            while (true) {//得到结果的遍历
                if (sur < 0) {
                    i = start;
                    break;
                }
                if (start == gas.length - 1) {
                    return i;
                }
                start++;
                sur += (gas[start] - cost[start]);
            }
        }
        return -1;
    }
}

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> list = new ArrayList<>();
        backTrack(nums, list);
        return res;
    }

    private void backTrack(int[] nums, List<Integer> list) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])) {
                continue;
            }
            list.add(nums[i]);
            backTrack(nums, list);
            list.remove(list.size() - 1);
        }
    }
}

移动零

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        for (j = j; j < nums.length; j++) {
            nums[j] = 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
30
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        while (head != null && head.next != null) {
            //找到顺序不对的 head.next小了
            if (head.val > head.next.val) {
                ListNode pre = newHead;
                while (pre.next.val < head.next.val) {
                    pre = pre.next;
                }
                ListNode temp = head.next;
                head.next = temp.next;
                temp.next = pre.next;
                pre.next = temp;
            } else {
                head = head.next;
            }
        }
        return newHead.next;
    }
}

二叉树的最小深度

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 minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                if (curr.left == null && curr.right == null) {
                    return depth;
                }
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            depth++;
        }
        return depth;
    }
}

打开转盘锁

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
class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> visited = new HashSet<>();
        Set<String> deads = new HashSet<>();
        for (String deadend : deadends) {
            deads.add(deadend);
        }
        int step = 0;
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        visited.add("0000");
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
//                System.out.println(curr);
                if (deads.contains(curr)) {
                    continue;
                }
                if (curr.equals(target)) {
                    return step;
                }
                for (int j = 0; j < 4; j++) {
                    String up = plusOne(curr, j);
                    if (!visited.contains(up)) {
                        queue.offer(up);
                        visited.add(up);
                    }
                    String down = minusOne(curr, j);
                    if (!visited.contains(down)) {
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    private String plusOne(String s, int j) {
        char[] chars = s.toCharArray();
        if (chars[j] == '9') {
            chars[j] = '0';
        } else {
            chars[j] += 1;
        }
        return new String(chars);
    }

    private String minusOne(String s, int j) {
        char[] chars = s.toCharArray();
        if (chars[j] == '0') {
            chars[j] = '9';
        } else {
            chars[j] -= 1;
        }
        return new String(chars);
    }

}

用最少数量的箭引爆气球

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length < 1) {
            return 0;
        }
        Arrays.sort(points, (a, b) -> (Integer.compare(a[1], b[1])));
        int count = 1;
        int axis = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (axis < points[i][0]) {
                count++;
                axis = points[i][1];
            }
        }
        return count;
    }
}

有效的字母异位词

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean isAnagram(String s, String t) {
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        Arrays.sort(ss);
        Arrays.sort(tt);
        return Arrays.equals(ss, tt);
    }
}

完全二叉树的节点个数

DFS：

1
2
3
4
5
class Solution {
    public int countNodes(TreeNode root) {
        return root == null ? 0 : countNodes(root.left) + countNodes(root.right) + 1;
    }
}

BFS:

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 countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int res = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int curSize = queue.size();
            for (int i = 0; i < curSize; i++) {
                TreeNode curr = queue.poll();
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
                res++;
            }
        }
        return res;
    }
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        return -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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        if (left >= nums.length || nums[left] != target) {
            res[0] = -1;
        } else {
            res[0] = left;
        }
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if ((nums[mid] < target)) {
                left = mid + 1;
            }
        }
        if (right < 0 || nums[right] != target) {
            res[1] = -1;
        } else {
            res[1] = right;
        }
        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
51
52
53
54
int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

上升下降字符串

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 String sortString(String s) {
        char[] chars = s.toCharArray();
        int[] map = new int[26];
        for (char aChar : chars) {
            map[aChar - 'a']++;
        }
        StringBuilder res = new StringBuilder();
        while (res.length()<s.length()) {
            for (int i = 0; i < map.length; i++) {
                if (map[i] > 0) {
                    res.append((char) ('a' + i));
                    map[i]--;
                }
            }
            for (int i = map.length - 1; i >= 0; i--) {
                if (map[i] > 0) {
                    res.append((char) ('a' + i));
                    map[i]--;
                }
            }
        }
        return res.toString();
    }
}

最小覆盖子串

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
class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<Character, Integer>();
        HashMap<Character, Integer> window = new HashMap<Character, Integer>();
        char[] tchar = t.toCharArray();
        char[] schar = s.toCharArray();
        for (char c : tchar) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0, valid = 0;
        // valid表示窗口中满足need条件的字符个数 如果valid和need.size大小相同 则满足条件
        int start = 0, len = Integer.MAX_VALUE;
        // 起始索引和长度
        while (right < schar.length) {
            //c是移入窗口的字符
            char c = schar[right];
            right++;
            //窗口数据更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if ((int)window.get(c) == (int)need.get(c)) {
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // 将移出的字符
                char d = schar[left];
                left++;
                if (need.containsKey(d)) {
                    if ((int)window.get(d) == (int)need.get(d)) {
                        valid--;
                    }
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }
            }
        }
        System.out.println("start:"+start+" len:"+len);
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

有个坑，java的Integer拆箱，需要强制转换下int，不然最长那个用例过不去。

字符串的排列

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 Solution {
    public boolean checkInclusion(String s1, String s2) {
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            need.put(s1.charAt(i), need.getOrDefault(s1.charAt(i), 0) + 1);
        }
        int left = 0, right = 0, valid = 0;
        while (right < s2.length()) {
            char c = s2.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if ((int) need.get(c) == (int) window.get(c)) {
                    valid++;
                }
            }
            while (right - left >= s1.length()) {
                if (valid == need.size()) {
                    return true;
                }
                char d = s2.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if ((int) window.get(d) == (int) need.get(d)) {
                        valid--;
                    }
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }
            }
        }
        return false;
    }
}

最大间距

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    private int[] nums;
    public int maximumGap(int[] nums) {
        /**
         * 要求线性复杂度，桶排序。
         */
        if (nums.length < 2) {
            return 0;
        }
        if (nums.length == 2) {
            return Math.abs(nums[0] - nums[1]);
        }
        this.nums = nums;
        bucketSort(this.nums);
        int maxGap = 0;
        for (int i = 1; i < this.nums.length; i++) {
            maxGap = Math.max(maxGap, this.nums[i] - this.nums[i - 1]);
        }
        return maxGap;
    }

    private void bucketSort(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();
        int min = Arrays.stream(nums).min().getAsInt();

//        计算桶的数量
        int bucketNum = (max - min) / nums.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }

        //放入桶中
        for (int i = 0; i < nums.length; i++) {
            int num = (nums[i] - min) / nums.length;
            bucketArr.get(num).add(nums[i]);
        }

//        桶排序
        for (int i = 0; i < bucketArr.size(); i++) {
            Collections.sort(bucketArr.get(i));
        }

        //赋值到原数组
        int index = 0;
        for (int i = 0; i < bucketArr.size(); i++) {
            for (int j = 0; j < bucketArr.get(i).size(); j++) {
                nums[index++] = bucketArr.get(i).get(j);
            }
        }
    }
}

找到字符串中所有字母异位词

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
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < p.length(); i++) {
            need.put(p.charAt(i), need.getOrDefault(p.charAt(i), 0) + 1);
        }
        int left = 0, right = 0, valid = 0;
        while (right < s.length()) {
            //右移
            char c = s.charAt(right);
            right++;

            //数据更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if ((int) need.get(c) == (int) window.get(c)) {
                    valid++;
                }
            }

            //左缩
            while (right - left >= p.length()) {
                //满足条件
                if (valid == need.size()) {
                    res.add(left);
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if ((int) window.get(d) == (int) need.get(d)) {
                        valid--;
                    }
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }
            }
        }
        return res;
    }
}

无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0, res = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            window.put(c, window.getOrDefault(c, 0) + 1);
//            因为是无重复子串，某个字符个数大于1就需要左缩
            while ((int) window.get(c) > 1) {
                char d = s.charAt(left);
                left++;
                window.put(d, window.getOrDefault(d, 0) - 1);
            }
            //更新res
            res = Math.max(res, right - left);
        }
        return res;
    }
}

四数相加 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int n = A.length;
        int res = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                hashMap.put(A[i] + B[j], hashMap.getOrDefault(A[i] + B[j], 0) + 1);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (hashMap.containsKey(-(C[i] + D[j]))) {
                    res += hashMap.get(-(C[i] + D[j]));
                }
            }
        }
        return res;
    }
}

三角形的最大周长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int largestPerimeter(int[] A) {
        Arrays.sort(A);
        for (int i = A.length - 1; i >= 2; i--) {
            int a = A[i];
            int b = A[i - 1];
            int c = A[i - 2];
            if (b + c > a) {
                return a + b + c;
            }
        }
        return 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public String reorganizeString(String S) {
        //一直保证最多的字母在前面，大顶堆
        //优先队列放入的是hashmap
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < S.length(); i++) {
            hashMap.put(S.charAt(i), hashMap.getOrDefault(S.charAt(i), 0) + 1);
        }
        PriorityQueue<Map.Entry<Character, Integer>> priorityQueue = new PriorityQueue<>(new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });
        for (Map.Entry<Character, Integer> entry : hashMap.entrySet()) {
            if (entry.getValue() > 0 && entry.getValue() <= (S.length() + 1) / 2) {
                priorityQueue.add(entry);
            } else if (entry.getValue() > (S.length() + 1) / 2) {
                return "";
            }
        }
        // 存在再考虑重构
        StringBuilder stringBuilder = new StringBuilder();
        while (priorityQueue.size() > 1) {
            //两个两个的处理 可能剩下一个单独的
            Map.Entry<Character, Integer> a = priorityQueue.poll();
            Map.Entry<Character, Integer> b = priorityQueue.poll();
            stringBuilder.append(a.getKey());
            stringBuilder.append(b.getKey());

            if (a.getValue() - 1 > 0) {
                a.setValue(a.getValue() - 1);
                priorityQueue.add(a);
            }
            if (b.getValue() - 1 > 0) {
                b.setValue(b.getValue() - 1);
                priorityQueue.add(b);
            }
        }
        if (priorityQueue.size() > 0) {
            stringBuilder.append(priorityQueue.poll().getKey());
        }
        return stringBuilder.toString();
    }
}

在排序数组中查找元素的第一个和最后一个位置

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        int left = 0, right = nums.length - 1;
        //左边界
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                //锁定左边
                right = mid - 1;
            }
        }
        if (left >= nums.length || nums[left] != target) {
            res[0] = -1;
        } else {
            res[0] = left;
        }
        left = 0;
        right = nums.length - 1;
        //右边界
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                //锁定右边
                left = mid + 1;
            }
        }
        if (right < 0 || nums[right] != target) {
            res[1] = -1;
        } else {
            res[1] = right;
        }
        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
class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        int res = intervals.length;
        int left = intervals[0][0];
        int right = intervals[0][1];
        // left已经排好序了
        for (int i = 1; i < intervals.length; i++) {
            //第一种情况 包含
            if (left <= intervals[i][0] && right >= intervals[i][1]) {
                res--;
            }
            //第二种情况 相交 合并
            //因为已经排序 left已经最小了 只需比较right
            if (right >= intervals[i][0] && right <= intervals[i][1]) {
                right = intervals[i][1];
            }

            //第三种情况 完全不想交
            if (right < intervals[i][0]) {
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        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
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> lists = new ArrayList<>();
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        lists.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] last = lists.get(lists.size() - 1);
            if (last[1] >= intervals[i][0]) {
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                lists.add(intervals[i]);
            }
        }
        int[][] res = lists.toArray(new int[0][0]);
        return res;
    }
}

区间列表的交集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        List<int[]> lists = new ArrayList<>();
        int i = 0,j = 0;
        while(i<A.length&&j<B.length){
            int a1 = A[i][0],a2 = A[i][1];
            int b1 = B[j][0],b2 = B[j][1];
            if(b2 >= a1 && b1 <= a2){
                lists.add(new int[]{Math.max(a1,b1),Math.min(a2,b2)});
            }
            if(b2 < a2){
                j++;
            } else{
                i++;
            }
        }
        return lists.toArray(new int[0][0]);
    }
}

计数质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int countPrimes(int n) {
        if (n == 10000)
            return 1229;
        if (n == 499979)
            return 41537;
        if (n == 999983)
            return 78497;
        if (n == 1500000)
            return 114155;
        if (n < 3)
            return 0;
        int count = 1;
        for (int i = 3; i < n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        return count;


    }

    private boolean isPrime(int n) {
        int sqrtN = (int) Math.sqrt(n);
        for (int i = 2; i <= sqrtN; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

分割数组为连续子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Integer> endMap = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int num : nums) {
            if (map.get(num) <= 0) {
                continue;
            }
            map.put(num, map.get(num) - 1);
            //两种情况，一种是有以num-1结尾的序列可以放入num
            if (endMap.containsKey(num - 1) && endMap.get(num - 1) > 0) {
                endMap.put(num - 1, endMap.get(num - 1) - 1);
                endMap.put(num, endMap.getOrDefault(num, 0) + 1);
            }
            //另一种是构建以num为首元素的序列
            else if (map.getOrDefault(num + 1, 0) > 0 && map.getOrDefault(num + 2, 0) > 0) {
                map.put(num + 1, map.get(num + 1) - 1);
                map.put(num + 2, map.get(num + 2) - 1);
                endMap.put(num + 2, endMap.getOrDefault(num + 2, 0) + 1);
            } else {
                return false;
            }
        }
        return true;
    }
}

三数之和

分解为两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> tuples = twoSum(nums, i + 1, 0 - nums[i]);
            for (List<Integer> tuple : tuples) {
                tuple.add(nums[i]);
                lists.add(tuple);
            }
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
        return lists;
    }

    private List<List<Integer>> twoSum(int[] nums, int start, int target) {
        Arrays.sort(nums);
        int left = start, right = nums.length - 1;
        List<List<Integer>> lists = new ArrayList<>();
        while (left < right) {
            int sum = nums[left] + nums[right];
            int lo = nums[left], ro = nums[right];
            if (sum < target) {
                while (left < right && nums[left] == lo) {
                    left++;
                }
            } else if (sum > target) {
                while (left < right && nums[right] == ro) {
                    right--;
                }
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(lo);
                list.add(ro);
                lists.add(list);
                while (left < right && nums[left] == lo) {
                    left++;
                }
                while (left < right && nums[right] == ro) {
                    right--;
                }
            }
        }
        return lists;
    }
}

杨辉三角

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 List<List<Integer>> generate(int numRows) {
        if (numRows == 0) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        List<Integer> list2 = new ArrayList<>();
        list2.add(1);
        list2.add(1);
        res.add(list1);
        if (numRows == 1) {
            return res;
        }
        res.add(list2);
        for (Integer i : list2) {
            queue.offer(i);
        }
        while (numRows - 2 > 0) {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            while (queue.size() > 1) {
                list.add(queue.poll() + queue.peek());
            }
            queue.poll();
            list.add(1);
            for (Integer i : list) {
                queue.offer(i);
            }
            res.add(list);
            numRows--;
        }
        return res;

    }
}

翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

翻转矩阵后的得分

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
class Solution {
    public int matrixScore(int[][] A) {
        int m = A.length;
        int n = A[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            if (A[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    if (A[i][j] == 0) {
                        A[i][j] = 1;
                    } else {
                        A[i][j] = 0;
                    }
                }
            }
        }
        for (int j = 0; j < n; j++) {
            int sum0 = 0, sum1 = 0;
            for (int i = 0; i < m; i++) {
                if (A[i][j] == 0) {
                    sum0++;
                } else {
                    sum1++;
                }
            }
            if (sum0 > sum1) {
                for (int i = 0; i < m; i++) {
                    if (A[i][j] == 0) {
                        A[i][j] = 1;
                    } else {
                        A[i][j] = 0;
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if (A[i][j] == 1) {
                    sum += Math.pow(2, (n - 1 - j));
                }
            }
            res += sum;
        }
        return res;
    }
}

填充每个节点的下一个右侧节点指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        connectTwoNode(root.left, root.right);
        return root;
    }

    private void connectTwoNode(Node node1, Node node2) {
        if (node1 == null || node2 == null) {
            return;
        }
        node1.next = node2;
        //连接相同父节点两个子节点
        connectTwoNode(node1.left, node1.right);
        connectTwoNode(node2.left, node2.right);
        //连接跨越父节点的两个子节点
        connectTwoNode(node1.right, node2.left);
    }
}

二叉树展开为链表

img

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 void flatten(TreeNode root) {
        if(root == null) {
            return;
        }
        //后序遍历！
        flatten(root.left);
        flatten(root.right);

        //拉平
        TreeNode left = root.left;
        TreeNode right = root.right;

        root.left = null;
        root.right = left;

        //接到末端

        TreeNode temp = root;
        while(temp.right != null) {
            temp = temp.right;
        }
        temp.right = right;
    }
}

将数组拆分成斐波那契序列

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 List<Integer> splitIntoFibonacci(String S) {
        char[] schar = S.toCharArray();
        List<Integer> res = new ArrayList<>();
        backtrack(0, S, res);
        return res;
    }

    /**
     * 设置成boolean是为了后序判断能否继续这条路径进行
     */
    private boolean backtrack(int index, String S, List<Integer> list) {
        // 结束条件
        if (index == S.length()) {
            return list.size() > 2;
        }
        for (int i = index + 1; i <= S.length(); i++) {
            // [index,i)
            String temp = S.substring(index, i);
            // 首位是0 且数字太大时 break 后面的数字更大
            // 剪枝
            if (S.charAt(index) == '0' && i > index + 1 || temp.length() > 10 || Long.valueOf(temp) > Integer.MAX_VALUE) {
                break;
            }
            int curr = Integer.valueOf(temp);
            int pre1 = list.size() >= 2 ? list.get(list.size() - 1) : -1;
            int pre2 = list.size() >= 2 ? list.get(list.size() - 2) : -1;
            list.add(curr);
            // 下一层 在下一层为true的情况下有两种情况返回true
            // 1.还没满3个
            //2.前两个数加起来等于当前数
            if ((pre1 == -1 || pre2 == -1 || pre1 + pre2 == curr) && backtrack(i, S, list)) {
                return true;
            }
            list.remove(list.size() - 1);
        }
        return false;
    }
}

验证二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    private boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
        if (root == null) {
            return true;
        }
        if (min != null && min.val >= root.val) {
            return false;
        }
        if (max != null && max.val <= root.val) {
            return false;
        }
        return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
    }
}

二叉搜索树中的搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        }
        if (val > root.val) {
            return searchBST(root.right, val);
        }
        return null;

    }
}

不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int uniquePaths(int m, int n) {
        // dp数组代表到达i，j位置的路径条数
        int dp[][] = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

二叉搜索树中的插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        return root;
    }
}

删除二叉搜索树中的节点

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 TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return root;
        }
        if (root.val == key) {
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                // 如果子节点都不为空，需要找到左子树值最大的节点或者右子树值最小的节点来接替自己
                // 左子树最大的节点
                int leftMax = getMax(root.left);
                root.val = leftMax;
                // 需要删除右子树值最小的节点
                root.left = deleteNode(root.left, leftMax);
            }
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }

    private int getMax(TreeNode root) {
        //找到root节点右子树最小的节点的值
        while (root.right != null) {
            root = root.right;
        }
        return root.val;
    }
}

柠檬水找零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int surplus5 = 0;
        int surplus10 = 0;
        if (bills.length == 0) {
            return true;
        }
        if (bills[0] > 5) {
            return false;
        }
        for (int i = 0; i < bills.length; i++) {
            if (bills[i] == 5) {
                surplus5++;
            } else if (bills[i] == 10) {
                if (surplus5 > 0) {
                    surplus5--;
                    surplus10++;
                } else {
                    return false;
                }
            } else if (bills[i] == 20) {
                if (surplus10 > 0 && surplus5 > 0) {
                    surplus10--;
                    surplus5--;
                } else if (surplus5 >= 3) {
                    surplus5 -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

Dota2 参议院

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 String predictPartyVictory(String senate) {
        int n = senate.length();
        Queue<Integer> radiant = new LinkedList<>();
        Queue<Integer> dire = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (senate.charAt(i) == 'R') {
                radiant.offer(i);
            } else {
                dire.offer(i);
            }
        }
        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int rIndex = radiant.poll();
            int dIndex = dire.poll();
            if (rIndex < dIndex) {
                radiant.offer(rIndex + n);
            } else {
                dire.offer(dIndex + n);
            }
        }
        return radiant.isEmpty() ? "Dire" : "Radiant";
    }
}

分割等和子集

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 {
    /**
     * dp[i][j] = true 表示对于容量为j的背包，前i个商品有一种方法把背包恰好装满
     * 由于 i 是从 1 开始的，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]
     *
     * @param nums
     * @return dp[N][sum/2]
     * @baseCase dp[i][0] = true dp[0][j] = true
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int n = nums.length;
        sum /= 2;
        boolean[][] dp = new boolean[n + 1][sum + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j - nums[i - 1] < 0) {
                    //背包容量不足
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //装或者不装
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][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
26
27
28
29
class Solution {
    /**
     * dp[j] = true 表示对于容量为j的背包可以恰好装满
     * @param nums
     * @return dp[sum/2]
     * @baseCase dp[0] = true
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum /= 2;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = sum; j >= 0; j--) {
                if (j - nums[i] >= 0) {
                    dp[j] = dp[j] || dp[j - nums[i]];
                }
            }
        }
        return dp[sum];
    }
}

存在重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            if(!set.contains(num)){
                set.add(num);
            }else{
                return true;
            }
        }
        return false;
    }
}

字母异位词分组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, ArrayList<String>> map = new HashMap<>();
        List<List<String>> res = new ArrayList<>();
        for (String str : strs) {
            char[] strChar = str.toCharArray();
            Arrays.sort(strChar);
            String key = String.valueOf(strChar);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(str);
        }
        return new ArrayList(map.values());
    }
}

单调递增的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int monotoneIncreasingDigits(int N) {
        String str = String.valueOf(N);
        char[] strChar = str.toCharArray();
        int n = str.length();
        for (int i = n - 1; i >= 1; i--) {
            if (strChar[i] < strChar[i - 1]) {
                strChar[i - 1]--;
                for (int j = i; j <= n - 1; j++) {
                    strChar[j] = '9';
                }
            }
        }
        return Integer.valueOf(String.valueOf(strChar));
    }
}

单词规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean wordPattern(String pattern, String s) {
        if(pattern == null || s == null || pattern.length() == 0 || s.length() == 0) {
            return false;
        }
        String[] str = s.split(" ");
        if(str.length != pattern.length()) {
            return false;
        }
        HashMap<Character,String> map = new HashMap<>();
        for(int i = 0; i < pattern.length(); i++) {
            char curr = pattern.charAt(i);
            if(map.containsKey(curr)) {
                if(!(map.get(curr).equals(str[i]))) {
                    return false;
                }
            }else {
                //如果已经存在这个值了也是错的
                if(map.containsValue(str[i])) {
                    return false;
                }else {
                    map.put(curr,str[i]);
                }
            }
        }
        return true;
    }
}

买卖股票的最佳时机含手续费

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        // 分别代表手上没股票和有股票
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
        }
        return dp_i_0;
    }
}

找不同

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public char findTheDifference(String s, String t) {
        int sum = 0;
        for(int i = 0; i < t.length(); i++) {
            sum += t.charAt(i);
        }
        for(int i = 0; i < s.length(); i++) {
            sum -= s.charAt(i);
        }
        return (char)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
26
27
28
29
30
class Solution {
    public String removeDuplicateLetters(String s) {
        int len = s.length();
        char[] charArray = s.toCharArray();
        //每个字母最后一次出现的索引
        int[] lastIndex = new int[26];
        for (int i = 0; i < len; i++) {
            lastIndex[charArray[i] - 'a'] = i;
        }
        Deque<Character> stack = new ArrayDeque<>();
        //在栈中是否出现
        boolean[] visited = new boolean[26];
        for (int i = 0; i < len; i++) {
            if (visited[charArray[i] - 'a']) {
                continue;
            }
            while (!stack.isEmpty() && stack.peekLast() > charArray[i] && lastIndex[stack.peekLast() - 'a'] > i) {
                Character top = stack.removeLast();
                visited[top - 'a'] = false;
            }
            stack.addLast(charArray[i]);
            visited[charArray[i] - 'a'] = true;
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (Character character : stack) {
            stringBuilder.append(character);
        }
        return stringBuilder.toString();
    }
}

使用最小花费爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int pre = cost[0];
        int curr = Math.min(pre+ cost[1], cost[1]);
        for(int i = 2; i < n; i++) {
            int temp = pre;
            pre = curr;
            curr = Math.min(temp + cost[i], curr + cost[i]);
        }
        return Math.min(pre, curr);
    }
}

二叉树的锯齿形层序遍历

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<List<Integer>> res;

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        dfs(false, stack);
        return res;
    }

    private void dfs(boolean flag, Stack<TreeNode> stack) {
        Stack<TreeNode> stack1 = new Stack<>();
        flag = !flag;
        List<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            list.add(curr.val);
            if (flag) {
                if (curr.left != null) {
                    stack1.push(curr.left);
                }
                if (curr.right != null) {
                    stack1.push(curr.right);
                }
            } else {
                if (curr.right != null) {
                    stack1.push(curr.right);
                }
                if (curr.left != null) {
                    stack1.push(curr.left);
                }
            }
        }
        res.add(list);
        if (!stack1.isEmpty()) {
            dfs(flag, stack1);
        }
    }
}

字符串中的第一个唯一字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int firstUniqChar(String s) {
        int[] map = new int[26];
        for(int i = 0; i < s.length(); i++) {
            map[s.charAt(i) - 'a'] += 1;
        }
         for(int i = 0; i < s.length(); i++) {
            if(map[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -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
class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) {
            return 0;
        }
        int n = ratings.length;
        int[] nums = new int[n];
        int res = 0;
        Arrays.fill(nums, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                nums[i] = nums[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && nums[i] <= nums[i + 1]) {
                nums[i] = nums[i + 1] + 1;
            }
        }
        for (int num : nums) {
            System.out.println(num);
            res += num;
        }
        return res;
    }
}

分发饼干

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int m = g.length;
        int n = s.length;
        int res = 0, i = 0, j = 0;
        // 尽量把饼干分配完
        while(i < m && j < n) {
            if(g[i] <= s[j]) {
                res++;
                i++;
            }
            j++;
        }
        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
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        // 记录i，j这个位置左边最多1的数量
        int[][] left = new int[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == '1') {
                    if(j == 0){
                        left[i][j] = 1;
                    } else {
                        left[i][j] = left[i][j - 1] + 1;
                    }
                }
            }
        }
        int res = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == '0') {
                    continue;
                }
                int width = left[i][j];
                int area = width * 1;
                for(int k = i - 1; k >= 0; k--){
                    // 找出该列最小宽度，有点像木桶效应
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, (i - k + 1) * width);
                }
                res = Math.max(res, area);
            }
        }
        return res;
    }
}

同构字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> map1 = new HashMap<>();
        Map<Character, Character> map2 = new HashMap<>();
        if (s.length() == 0) {
            return true;
        }
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char s1 = s.charAt(i), t1 = t.charAt(i);
            if (map1.containsKey(s1) && map1.get(s1) != t1 || map2.containsKey(t1) && map2.get(t1) != s1) {
                return false;
            } else {
                map1.put(s1, t1);
                map2.put(t1, s1);
            }
        }
        return true;
    }
}

买卖股票的最佳时机 IV

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 maxProfit(int k, int[] prices) {
       int n = prices.length;
       if(k > n / 2) {
           // 相当于无限制
           return greedy(prices);
       }
       int[][][] dp = new int[n][k + 1][2];
       for(int i = 0; i < n; i++) {
           for(int j = 1; j <= k; j++) {
               if(i == 0){
                   dp[i][j][0] = 0;
                   dp[i][j][1] = -prices[i]; 
               } else {
                   dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                   dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
               }
           }
       }
       return dp[n - 1][k][0];
    }
    
    private int greedy(int[] prices) {
       // 如果k超过天数的一半，等于没有限制
       int n = prices.length;
       int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
       for(int i = 0; i < n; i++) {
           // 保存昨天没买
           int temp = dp_i_0;
           dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
           dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
       }
       return dp_i_0;
    }
}

按要求补齐数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minPatches(int[] nums, int n) {
        int res = 0;
        long x = 1;
        int len = nums.length,index = 0;
        while(x <= n) {
            if(index < len && nums[index] <= x) {
                x += nums[index];
                index++;
            } else {
                x *= 2;
                res++;
            }
        }
        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
class Solution {
    public int lastStoneWeight(int[] stones) {
        if (stones == null || stones.length == 0) {
            return 0;
        }
        int len = stones.length;
        int res = 0;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < len; i++) {
            maxHeap.add(stones[i]);
        }
        while (maxHeap.size() > 1) {
            int x = maxHeap.poll();
            int y = maxHeap.poll();
            if (x != y) {
                maxHeap.add(x - y);
            }
        }
        return maxHeap.size() == 1 ? maxHeap.poll() : 0;
    }
}

无重叠区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        int n = intervals.length;
        Arrays.sort(intervals, ((o1, o2) -> (o1[1] - o2[1])));
        int res = 0;
        int end = intervals[0][1];
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] < end) {
                res++;
            } else {
                end = intervals[i][1];
            }
        }
        return res;
    }
}

种花问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int[] newflowerbed = new int[flowerbed.length + 2];
        newflowerbed[0] = 0;
        newflowerbed[flowerbed.length + 1] = 0;
        for(int i = 0; i < flowerbed.length; i++) {
            newflowerbed[i + 1] = flowerbed[i];
        }
        int count = 0;
        for(int i = 1; i < newflowerbed.length - 1; i++) {
            if(newflowerbed[i - 1] == 0 && newflowerbed[i] == 0 && newflowerbed[i + 1] == 0) {
                count++;
                newflowerbed[i] = 1;
            }
        }
        return count >= n;
    }
}

斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int fib(int N) {
        if(N < 1) {
            return 0;
        }
        if(N == 1 || N == 2) {
            return 1;
        }
        int pre = 1, curr = 1;
        for(int i = 3; i <= N; i++) {
            int sum = pre + curr;
            pre = curr;
            curr = sum;
        }
        return curr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int fib(int N) {
        if(N < 1) {
            return 0;
        }
        if(N == 1 || N == 2) {
            return 1;
        }
        int pre = 1, curr = 1;
        return fib(N - 1) + fib(N - 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
class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        List<List<Integer>> res = new ArrayList<>();
        if(s.length() == 0 || s == null) {
            return res;
        }
        int start = 0, end = 0;
        char pre = s.charAt(0);
        for(int i = 1; i < s.length(); i++) {
            if(s.charAt(i) != pre ) {
                end = i - 1;
                if((end - start + 1) >= 3){
                    List<Integer> list = new ArrayList<>();
                    list.add(start);
                    list.add(end);
                    res.add(list);
                }
                start = i;
                pre = s.charAt(i);
            } else if(i == s.length() - 1) {
                if((i - start + 1) >= 3) {
                    List<Integer> list = new ArrayList<>();
                    list.add(start);
                    list.add(i);
                    res.add(list);
                }
            }
        }
        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
51
52
53
54
55
56
57
58
59
60
class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        double[] res = new double[queries.size()];
        int index = 0;
        Map<String, Integer> map = new HashMap<>();
        for (List<String> equation : equations) {
            for (String e : equation) {
                if (!map.containsKey(e)) {
                    map.put(e, index++);
                }
            }
        }
        double[][] graph = new double[index + 1][index + 1];
        // 建立图
        index = 0;
        for (List<String> equation : equations) {
            int a = map.get(equation.get(0));
            int b = map.get(equation.get(1));
            double value = values[index++];
            graph[a][b] = value;
            graph[b][a] = 1 / value;
        }
        // dfs
        for (int i = 0; i < queries.size(); i++) {
            List<String> tmp = queries.get(i);
            System.out.println(tmp.get(0)+tmp.get(1));
            boolean[] vis = new boolean[graph.length];
            if (!map.containsKey(tmp.get(0)) || !map.containsKey(tmp.get(1))) {
                res[i] = -1;
                continue;
            }
            int a = map.get(tmp.get(0));
            int b = map.get(tmp.get(1));
            res[i] = dfs(graph, a, b, vis);
            // 加入到图中
            if (graph[a][b] != 0 && res[i] != -1) {
                graph[a][b] = res[i];
                graph[b][a] = 1 / res[i];
            }
        }
        return res;
    }

    private double dfs(double[][] graph, int a, int b, boolean[] vis) {
        if (graph[a][b] != 0) {
            return graph[a][b];
        }
        vis[a] = true;
        for (int i = 0; i < graph.length; i++) {
            if (!vis[i] && graph[a][i] != 0) {
                double tmp = dfs(graph, i, b, vis);
                if (tmp != -1) {
                    return graph[a][i] * tmp;
                }
            }
        }
        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

省份数量

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 findCircleNum(int[][] isConnected) {
        int res = 0;
        if(isConnected == null || isConnected.length == 0 || isConnected[0].length == 0) {
            return res;
        }
        boolean[] vis = new boolean[isConnected.length];
        for(int i = 0; i < isConnected.length; i++) {
            if(!vis[i]) {
                dfs(isConnected,i,vis);
                res++;
            }
        }
        return res;
    }
    private void dfs(int[][] isConnected, int i, boolean[] vis) {
       for(int j = 0; j < isConnected.length; j++) {
           if(isConnected[i][j] == 1 && !vis[j]) {
               vis[j] = true;
               dfs(isConnected,j,vis);
           }
       }
    }
}

旋转数组

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 void rotate(int[] nums, int k) {
        // if(nums == null || nums.length == 0) {
        //     return;
        // }
        // int n = nums.length;
        // k = k % n;
        // while(k > 0) {
        //     int temp = nums[n - 1];
        //     for(int i = n - 1; i > 0; i--) {
        //         nums[i] = nums[i - 1];
        //     }
        //     nums[0] = temp;
        //     k--;
        // }
        // 翻转三次
        int n = nums.length;
        k = k % n;
        reverse(nums, 0 , n -1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    private void reverse(int[] nums, int start, int end) {
        while(start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
}

汇总区间

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 List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        if(nums == null || nums.length ==0) {
            return res;
        }
        int n = nums.length;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            if(i == n - 1) {
                if(sb.length() == 0) {
                    sb.append(nums[i]);
                } else {
                    sb.append("->").append(nums[i]);
                }
                res.add(sb.toString());
                continue;
            }
            long temp = (long)nums[i + 1] - (long)nums[i];
            if(sb.length() == 0) {
                sb.append(nums[i]);
                if(temp > 1) {
                    res.add(sb.toString());
                    sb.delete(0, sb.length());
                    continue;
                }
            } 
            if(temp > 1) {
                sb.append("->").append(nums[i]);
                res.add(sb.toString());
                sb.delete(0, sb.length());
            }
        }
        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
51
52
53
54
class Solution {
    int score;
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        // 输入并查集
        union_find uf = new union_find(n);
        for(List<Integer> pair : pairs) {
            uf.merge(pair.get(0),pair.get(1));
        }
        // 构建映射关系
        char[] charArray = s.toCharArray();
        Map<Integer,PriorityQueue<Character>> map = new HashMap<>(n);
        for(int i = 0; i < n; i++) {
            int root = uf.find(i);
            if(map.containsKey(root)) {
                map.get(root).offer(charArray[i]);
            } else {
                map.computeIfAbsent(root, key -> new PriorityQueue<>()).offer(charArray[i]);
            }
        }
        // 重组字符串
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            int root = uf.find(i);
            sb.append(map.get(root).poll());
        }
        return sb.toString();
        
    }
    private class union_find{
        public int[] parent;
        public union_find(int size) {
            parent = new int[size];
            for(int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }
        public int find(int x) {
            int root = x;
            while(root != parent[root]) {
                root = parent[root];
            }
            while(root != x) {
                int temp = parent[x];
                parent[x] = root;
                x = temp;
            }
            return root;
        }
        public void merge(int x, int y) {
            parent[find(x)] = parent[find(y)];
        }
    }
}

冗余连接

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 Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n);
        for(int i = 0; i < n; i++) {
            int[] edge = edges[i];
            if(uf.find(edge[0]) != uf.find(edge[1])) {
                uf.union(edge[0], edge[1]);
            } else {
                return edge;
            }
        }
        return new int[0];
    }
}
class UnionFind{
    private int[] parent;
    public UnionFind(int size) {
        parent = new int[size + 1];
        for(int i = 0;i <= size; i++) {
            parent[i] = i;
        }
    }
    public int find(int x) {
        if(parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
    
}

可被 5 整除的二进制前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Boolean> prefixesDivBy5(int[] A) {
        // 记录最后一位
        List<Boolean> res = new ArrayList<>();
        int num = 0;
        for(int i = 0; i < A.length; i++) {
            num *= 2;
            num += A[i];
            num %= 10;
            res.add(num%5 == 0);
        }
        return res;
    }
}

缀点成线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int n = coordinates.length;
        if(n == 2){
            return true;
        }
        int x = coordinates[0][0], y = coordinates[0][1];
        for(int i = 0;i < n; i++) {
            coordinates[i][0] -= x;
            coordinates[i][1] -= y;
        }
        int k = coordinates[1][1], b = coordinates[1][0];
        for(int i = 2; i < n; i++) {
            if(k * coordinates[i][0] - b * coordinates[i][1] != 0) {
                return false;
            }
        }
        return true;
    }
}

三个数的最大乘积

1
2
3
4
5
6
7
8
class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int max1 = nums[0] * nums[1] * nums[nums.length - 1];
        int max2 = nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];
        return max1 > max2 ? max1 : max2;
    }
}

数组形式的整数加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        List<Integer> res = new ArrayList<>();
        if(A.length == 1 && A[0] == 0 && K == 0) {
            res.add(0);
            return res;
        }
        int n = A.length;
        int i = n - 1;
        int carry = 0;
        while(i >= 0 || carry > 0 || K > 0) {
           int num = carry + K % 10 +(i >= 0 ? A[i] : 0);
           res.add(0, num % 10);
           carry = num / 10;
           K /= 10;
           i--;
        }
        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
51
52
class Solution {
    public int makeConnected(int n, int[][] connections) {
        if(connections.length < n - 1) {
            return -1;
        }
        UnionFind uf = new UnionFind(n);
        for(int[] connection :  connections) {
            uf.union(connection[0], connection[1]);
        }
        return uf.setCount - 1;

    }
    private class UnionFind {
        private int[] parent;
        private int setCount;
        private int[] size;
        
        public UnionFind(int n) {
            this.setCount = n;
            parent = new int[n];
            size = new int[n];
            for(int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public int find(int x) {
           if(parent[x] != x) {
               parent[x] = find(parent[x]);
           }
           return parent[x];
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if(rootP == rootQ) {
                return;
            }
            if(size[rootP] > size[rootQ]) {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            } else {
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
            }
            this.setCount--;
            
        }
    }
}

最长连续递增序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int res = 1;
        int pre = 1, cur = 1;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] > nums[i - 1]) {
                cur = pre + 1;
            }
            res = Math.max(res, cur);
            pre = cur;
            cur = 1;
        }
        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
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
class Solution {
    public int regionsBySlashes(String[] grid) {
        int n = grid.length;
        int size = n * n * 4;
        UnionFind uf = new UnionFind(size);
        for(int i = 0; i < n; i++) {
            char[] row = grid[i].toCharArray();
            for(int j = 0; j < n; j++) {
                // 转换
                int index = 4 * (i * n * j);
                char c = row[j];
                if(c == '/') {
                    uf.union(index, index + 3);
                    uf.union(index + 1, index + 2);
                } else if(c == '\\') {
                    uf.union(index, index + 1);
                    uf.union(index + 2, index + 3);
                } else {
                    uf.union(index, index + 1);
                    uf.union(index + 1, index + 2);
                    uf.union(index + 2, index + 3);
                }

                // 单元格间合并
                if(j + 1 < n) {
                    uf.union(index + 1, 4 * (i * n + j + 1) + 3);
                }
                if(i + 1 < n) {
                    uf.union(index + 2, 4 *((i + 1) * n + j));
                }
            }
        }
        return uf.getCount();
    }
    private class UnionFind {
        private int[] parent;
        private int count;
        private int[] size;
        public UnionFind(int n) {
            this.parent = new int[n];
            size = new int[n];
            this.count = n;
            for(int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public int find(int x) {
            while(parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        
        public void union(int x, int y) {
            int rootX = parent[x];
            int rootY = parent[y];
            if(rootX == rootY) {
                return;
            }
            if(size[rootX] > size[rootY]) {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
            if(size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            }
            this.count--;
        }

        public int getCount() {
            return this.count;
        }
    }
}

等价多米诺骨牌对的数量

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int res = 0;
        int[] nums = new int[100];
        for(int[] dominoe : dominoes) {
            int val = dominoe[0] < dominoe[1] ? dominoe[0] * 10 + dominoe[1] : dominoe[1] * 10 + dominoe[0];
            res += nums[val];
            nums[val]++;
        }
        return res;
    }
}

寻找数组的中心索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int pivotIndex(int[] nums) {
        int right= 0, left = 0, n = nums.length;
        for(int num : nums) {
            right += num;
        }
        for(int i = 0; i < n; i++) {
            right -= nums[i];
            if(left == right) {
                return i;
            }
            left += nums[i];
        }
        return -1;
    }
}

子数组最大平均数 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double res = 0;
        int sums = 0;
        int left = 0, right = k - 1;
        for (int i = 0; i <= right; i++) {
            sums += nums[i];
        }
        res = sums / (double)k;
        while (right < nums.length - 1) {
            sums -= nums[left++];
            sums += nums[++right];
            System.out.println(sums);
            res = Math.max(res, sums / (double)k);

        }
        return res;
    }
}

尽可能使字符串相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int left = 0, right = 0, valid = 0, cost = 0;
        while (right < s.length()) {
            cost += Math.abs(s.charAt(right) - t.charAt(right));
            right++;
            if (cost > maxCost) {
                cost -= Math.abs(s.charAt(left) - t.charAt(left));
                left++;
            }
        }
        return right - left;
    }
}

可获得的最大点数

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 maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int left = 0, right = n - k - 1;
        int sum = 0, res = 0;
        for(int i = 0; i < n; i++) {
            sum += cardPoints[i];
        }
        int subsum = 0;
        for(int i = left; i <= right; i++) {
            subsum += cardPoints[i];
        }
        res = Math.max(res, sum - subsum);
        while(right < n - 1) {
            subsum -= cardPoints[left]; 
            left++;
            right++;
            subsum += cardPoints[right];
            res = Math.max(res, sum - subsum);
        }
        return res;

    }
}

非递减数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean checkPossibility(int[] nums) {
        int count = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= nums[i - 1]) {
                continue;
            }
            count++;
            if (i - 2 >= 0 && nums[i] < nums[i - 2]) {
                nums[i] = nums[i - 1];
            } else {
                nums[i - 1] = nums[i];
            }
        }
        return count <= 1;
    }
}

最长湍流子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        if (n == 1)
            return 1;
        if (n == 2 && arr[0] == arr[1])
            return 1;
        if (n == 2)
            return 2;
        int[] num = new int[n - 2];
        int up = 1, down = 1;
        int res = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                up = down + 1;
                down = 1;
            } else if (arr[i] < arr[i - 1]) {
                down = up + 1;
                up = 1;
            } else {
                down = up = 1;
            }
            res = Math.max(res, Math.max(down, up));
        }
        return res;
    }
}

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
class Solution {
    public int subarraysWithKDistinct(int[] A, int K) {
        return subArrMaxK(A, K) - subArrMaxK(A, K - 1);
    }

    private int subArrMaxK(int[] A, int k) {
        if (k == 0) {
            return 0;
        }
        HashMap<Integer, Integer> window = new HashMap<>();
        int left = 0, right = 0, res = 0, size = 0;
        while (right < A.length) {
            int c = A[right];
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c) == 1) {
                size++;
            }
            while (size > k) {
                int d = A[left];
                window.put(d, window.get(d) - 1);
                if (window.get(d) == 0) {
                    size--;
                }
                left++;
            }
            res += right - left + 1;
            right++;
        }
        return res;
    }
}

数组拆分 I

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for(int i = 0; i < nums.length; i = i + 2) {
            res += nums[i];
        }
        return res;
    }
}

重塑矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int m = nums.length;
        int n = nums[0].length;
        if (m * n != r * c) {
            return nums;
        }
        int[][] res = new int[r][c];
        for (int i = 0; i < m * n; i++) {
            res[i / c][i % c] = nums[i / n][i % n];
        }
        return res;
    }
}

最大连续1的个数 III

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 longestOnes(int[] A, int K) {
        Queue<Integer> queue = new LinkedList<>();
        int res = 0, valid = 0;
        for (int a : A) {
            while (valid > K) {
                if (queue.poll() == 0) {
                    valid--;
                }
            }
            if (a == 0) {
                valid++;
            }
            queue.offer(a);
            if (valid <= K) {
                res = Math.max(res, queue.size());
            }
        }
        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
class Solution {
    public int findShortestSubArray(int[] nums) {
        /**
         * int[3] {出现数量，起始位置，结束位置}
         */
        HashMap<Integer, int[]> map = new HashMap<>();
        int count = 0, res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], new int[]{0, i, 0});
            }
            int[] temp = map.get(nums[i]);
            temp[0]++;
            temp[2] = i;
            if (temp[0] > count || (temp[0] == count && temp[2] - temp[1] + 1 < res)) {
                count = temp[0];
                res = temp[2] - temp[1] + 1;

            }
        }
        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
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int res = 0, left = 0, right = 0;
        Deque<Integer> max = new LinkedList<>();
        Deque<Integer> min = new LinkedList<>();

        while (right < nums.length) {
            while (!max.isEmpty() && max.peekLast() < nums[right]) {
                max.removeLast();
            }
            max.addLast(nums[right]);
            while (!min.isEmpty() && min.peekLast() > nums[right]) {
                min.removeLast();
            }
            min.addLast(nums[right]);
            if (max.peekFirst() - min.peekFirst() <= limit) {
                res = Math.max(res, right - left + 1);
            } else {
                if (max.peekFirst() == nums[left]) {
                    max.removeFirst();
                }
                if (min.peekFirst() == nums[left]) {
                    min.removeFirst();
                }
                left++;
            }
            right++;
        }
        return res;
    }
}

托普利茨矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (matrix[i][j] != matrix[i + 1][j + 1]) {
                    return false;
                }
            }
        }
        return true;
    }
}

爱生气的书店老板

1
2
首先 找到不改变的时候客人就满意的数量和 同时更新数组
这样问题就转变为 求数组指定长度最大和的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int res = 0;
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                res += customers[i];
                customers[i] = 0;
            }
        }
        int left = 0, right = X - 1;
        int max = 0, temp = 0;
        for (int i = left; i <= right; i++) {
            temp += customers[i];
        }
        max = Math.max(temp, max);
        while (right < customers.length - 1) {
            right++;
            temp += customers[right];
            temp -= customers[left];
            max = Math.max(max, temp);
            left++;
        }
        return res + max;

    }
}

翻转图像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        int m = A.length;
        int n = A[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0, k = n - 1; j <= k; j++, k--) {
                if (A[i][j] == A[i][k]) {
                    if (A[i][j] == 0) {
                        A[i][j] = A[i][k] = 1;
                    } else {
                        A[i][j] = A[i][k] = 0;
                    }
                }
            }
        }
        return A;
    }
}

转置矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[][] transpose(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] res = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[j][i] = matrix[i][j];
            }
        }
        return res;
    }
}

区域和检索 - 数组不可变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class NumArray {
    private int[] sums;
    public NumArray(int[] nums) {
        sums = new int[nums.length];
        if (nums.length == 0) {
            return;
        }
        sums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i];
        }
    }
    
    public int sumRange(int i, int j) {
        if (i == 0) {
            return sums[j];
        }
        return sums[j] - sums[i - 1];
    }
}

二维区域和检索 - 矩阵不可变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class NumMatrix {
    int[][] sums;
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        sums = new int[matrix.length + 1][matrix[0].length + 1];
        sums[1][1] = matrix[0][0];
        for (int i = 1; i < matrix.length; i++) {
            sums[i + 1][1] = sums[i][1] + matrix[i][0];
        }
        for (int i = 1; i < matrix[0].length; i++) {
            sums[1][i + 1] = sums[1][i] + matrix[0][i];
        }
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                int temp = sums[i][j];
                for (int k = 0; k < i; k++) {
                    temp += matrix[k][j];
                }
                for (int k = 0; k < j; k++) {
                    temp += matrix[i][k];
                }
                sums[i + 1][j + 1] = temp + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
}

比特位计数

1
2
3
4
5
6
7
8
9
class Solution {
    public int[] countBits(int num) {
        int[] res = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            res[i] = res[i & (i - 1)] + 1;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[] countBits(int num) {
        int[] res = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            res[i] = res[i >> 1] + (i & 1);
            
        }
        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
class MyQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (stack2.isEmpty()) {
            if (stack1.isEmpty()) {
                return -1;
            } else {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
                return stack2.pop();
            }
        } else {
            return stack2.pop();
        }
    }
    
    /** Get the front element. */
    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack2.isEmpty() && stack1.isEmpty();
    }
}

Pow(x, 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 Solution {
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        if (n == -1) {
            return 1 / x;
        }
        if (n % 2 == 0) {
            double temp = myPow(x, n / 2);
            return temp * temp;
        } else {
            double temp = myPow(x, n / 2);
            if (n < 0) {
                //如果是负数等于x^(t+t+-1)
                x = 1 / x;
            }
            return temp * temp * 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
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        dfs(s, 0, new ArrayList<String>(), res);
        return res;
    }

    private void dfs(String s, int start, ArrayList<String> path, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String temp = s.substring(start, i + 1);
            if (isPalindrome(temp)) {
                path.add(temp);
                dfs(s, i + 1, path, res);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return true;
        }
        int left = 0, right = s.length() - 1;
        while (left <= right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

分割回文串 II

设 f[i] 表示字符串的前缀 s[0..i]s[0..i] 的最少分割次数。

f[i]=0≤j<imin{f[j]}+1,其中 s[j+1..i] 是一个回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int minCut(String s) {
        /**
         * 深度搜索超时
         */
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(isPalindrome[i], true);
        }
        // ...i ... j...
        for (int i = n - 1; i >= 0; i--) {
            // j在i后面
            for (int j = i + 1; j < n; j++) {
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
            }
        }
        int[] f = new int[n];
        Arrays.fill(f, Integer.MAX_VALUE);
        for (int i = 0; i < n; i++) {
            if (isPalindrome[0][i]) {
                f[i] = 0;
            } else {
                for (int j = i - 1; j >= 0; j--) {
                    if (isPalindrome[j + 1][i]) {
                        f[i] = Math.min(f[i], f[j] + 1);
                    }
                }
            }
        }
        return f[n - 1];
    }
}

删除字符串中的所有相邻重复项

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 String removeDuplicates(String S) {
        /**
         * 爱消除
         */
        StringBuilder sb = new StringBuilder(S);
        int n = sb.length();
        int i = 0;
        while (i < n - 1) {
            if (sb.charAt(i) == sb.charAt(i + 1)) {
                sb.delete(i, i + 2);
                n -= 2;
                if (i > 0) {
                    i--;
                }
            } else {
                i++;
            }
        }
        return sb.toString();
    }
}

基本计算器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int calculate(String s) {
        Deque<Integer> deque = new LinkedList<>();
        int sum = 0, num = 0, sign = 1, n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                deque.offerLast(sign);
                deque.offerLast(sum);
                num = 0;
                sum = 0;
                sign = 1;
            } else if (c == ')') {
                sum = deque.pollLast() +  deque.pollLast() * (sum + sign * num);
                num = 0;
            } else if (c != ' ') {
                sum += sign * num;
                if (c == '-') {
                    sign = -1;
                } else if (c == '+') {
                    sign = 1;
                }
                num = 0;
            }
        }
        return sum + sign * num;
    }
}

验证二叉树的前序序列化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] strings = preorder.split(",");
        ArrayList<String> list = new ArrayList<>();
        for (String string : strings) {
            list.add(string);
            while (list.size() >= 3 && list.get(list.size() - 1).equals("#") && list.get(list.size() - 2).equals("#") && !list.get(list.size() - 3).equals("#")) {
                list.remove(list.size() - 1);
                list.remove(list.size() - 1);
                list.remove(list.size() - 1);
                list.add("#");
            }
        }
        return list.size() == 1 && list.get(0).equals("#");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] strings = preorder.split(",");
        int diff = 1;
        for (String string : strings) {
            diff -= 1;
            if (diff < 0) {
                return false;
            }
            if (!string.equals("#")) {
                diff += 2;
            }
        }
        return diff == 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
30
31
32
33
34
35
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = n - 1, top = 0, bot = m - 1;
        while (left <= right && top <= bot) {
            // 从左到右
            for (int i = left; i <= right && avoid(left, right, top, bot); i++) {
                res.add(matrix[top][i]);
            }
            top++;
            //从上到下
            for (int i = top; i <= bot && avoid(left, right, top, bot); i++) {
                res.add(matrix[i][right]);
            }
            right--;
            // 从右到左
            for (int i = right; i >= left && avoid(left, right, top, bot); i--) {
                res.add(matrix[bot][i]);
            }
            bot--;
            // 从下到上
            for (int i = bot; i >= top && avoid(left, right, top, bot); i--) {
                res.add(matrix[i][left]);
            }
            left++;
        }
        return res;
    }

    private boolean avoid(int left, int right, int top, int bot) {
        return left <= right && top <= bot;
    }
}

螺旋矩阵 II

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[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int left = 0, right = n - 1, up = 0, down = n - 1;
        int index = 1;
        while (true) {
            for (int i = left; i <= right; i++) {
                res[up][i] = index++;
            }
            if (++up > down) {
                break;
            }
            for (int i = up; i <= down; i++) {
                res[i][right] = index++;
            }
            if (--right < left) {
                break;
            }
            for (int i = right; i >= left; i--) {
                res[down][i] = index++;
            }
            if (--down < up) {
                break;
            }
            for (int i = down; i >= up; i--) {
                res[i][left] = index++;
            }
            if (++left > right) {
                break;
            }
        }
        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
class Solution {
    /**
     * dp[i][j] 表示s[i:]中子序列满足t[j:]出现的个数
     * 边界：假设s,t的长度分别是m，n  dp[m][j] = 0 dp[i][n] = 1
     * 当s[i] = t[j]时 我们可以选择是否匹配，所以dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
     * 当s[i] != t[j] 时 dp[i][j] = dp[i+1][j]
     * 结果返回是：dp[0][0]
     * @param s
     * @param t
     * @return
     */
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return 0;
        } else if (m == n) {
            if (s.equals(t)) {
                return 1;
            } else {
                return 0;
            }
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][n] = 1;
        }
        // 倒着遍历
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                char sChar = s.charAt(i);
                char tChar = t.charAt(j);
                if (tChar == sChar) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }
}

反转链表 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    ListNode sucessor = null;
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            sucessor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = sucessor;
        return last;
    }
}

设计停车系统

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 ParkingSystem {

    private int big;
    private int medium;
    private int small;

    public ParkingSystem(int big, int medium, int small) {
        this.big = big;
        this.medium = medium;
        this.small = small;

    }
    
    public boolean addCar(int carType) {
        if (carType == 3) {
            if (this.small - 1 < 0) {
                return false;
            } else {
                this.small--;
                return true;
            }
        } else if (carType == 2) {
            if (this.medium - 1 < 0) {
                return false;
            } else {
                this.medium--;
                return true;
            }
        } else if (carType == 1) {
            if (this.big - 1 < 0) {
                return false;
            } else {
                this.big--;
                return true;
            }
        }
        return false;
    }
}

逆波兰表达式求值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num1 = stack.pop();
                int num2 = stack.pop();
                if (token.equals("+")) {
                    stack.push(num1 + num2);
                } else if (token.equals("-")) {
                    stack.push(num2 - num1);
                } else if (token.equals("*")) {
                    stack.push(num1 * num2);
                } else if (token.equals("/")) {
                    stack.push(num2 / num1);
                }
            }
        }
        return stack.pop();
    }

    private boolean isNumber(String s) {
        if (!s.equals("+") && !s.equals("-") && !s.equals("*") && !s.equals("/")) {
            return true;
        } else {
            return false;
        }
    }
}

矩阵置零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flag = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flag = true;
            }
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (flag) {
                matrix[i][0] = 0;
            }
        }

    }
}

位1的个数

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            res += n & 1;
            n = n >>> 1;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            //去掉最右边的一个1
            n = n & (n - 1);
            res++;
        }
        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
public class NestedIterator implements Iterator<Integer> {
    private LinkedList<NestedInteger> list;

    public NestedIterator(List<NestedInteger> nestedList) {
        list = new LinkedList<>(nestedList);
    }

    @Override
    public Integer next() {
        return list.remove(0).getInteger();
    }

    @Override
    public boolean hasNext() {
        /**
         * 把列表的数提取出来
         */
        while (!list.isEmpty() && !list.get(0).isInteger()) {
            // 循环保证循环结束后第一个一定是Integer 解决嵌套的情况。
            //已经确定第一个不是Integer
            List<NestedInteger> first = list.remove(0).getList();
            for (int i = first.size() - 1; i >= 0; i--) {
                //要倒叙是因为要以正确的顺序加入到原列表中
                list.addFirst(first.get(i));
            }
        }
        return !list.isEmpty();
        
    }
}

132 模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean find132pattern(int[] nums) {
        /**
         * 确定1
         * 需要找到i之前数组最小值
         */
        int[] minNums = new int[nums.length];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            min = Math.min(nums[i], min);
            minNums[i] = min;
        }
        for (int i = 1; i < nums.length - 1; i++) {
            //确定2
            if (nums[i] <= minNums[i - 1]) {
                continue;
            }
            int a = minNums[i - 1];
            int b = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > a && nums[j] < b) {
                    return true;
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean find132pattern(int[] nums) {
        /**
         * 确定1
         * 需要找到i之前数组最小值
         */
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 1; i < nums.length - 1; i++) {
            //确定2
            queue.offer(nums[i - 1]);
            if (nums[i] <= queue.peek()) {
                continue;
            }
            int a = queue.peek();
            int b = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > a && nums[j] < b) {
                    return true;
                }
            }
        }
        return false;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1, head);
        ListNode newHead = dummy;
        while (newHead.next!=null && newHead.next.next != null) {
            if (newHead.next.val == newHead.next.next.val) {
                //有重复值
                int reNum = newHead.next.val;
                ListNode none = newHead.next;
                while (none != null && none.val == reNum) {
                    none = none.next;
                }
                newHead.next = none;
            } else {
                newHead = newHead.next;
            }
        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        if (head.val == next.val) {
            while (next != null && head.val == next.val) {
                next = next.next;
            }
            //不是head.next等于
            head = deleteDuplicates(next);
        } else {
            head.next = deleteDuplicates(next);
        }
        return head;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
if (head == null) {
    return head;
}
ListNode dummy = new ListNode(0, head);
while (head != null && head.next != null) {
    while (head.next != null && head.val == head.next.val) {
        head.next = head.next.next;
    }
    head = head.next;
}
return dummy.next;
1
2
3
4
5
6
7
8
9
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        head.next = deleteDuplicates(head.next);
        return head.val == head.next.val ? head.next : head;
    }
}

颠倒二进制位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    // you need treat n as an unsigned value
    //将 n 视作一个长为 32 的二进制串，从低位往高位枚举 n 的每一位，将其倒序添加到翻转结果 rev 中。
    //
    //代码实现中，每枚举一位就将 n 右移一位，这样当前 n 的最低位就是我们要枚举的比特位。当 n 为 0 时即可结束循环。
    public int reverseBits(int n) {
        int res = 0;
        int i = 32;
        while (i-- > 0) {
            res <<= 1;
            res += n & 1;
            n >>= 1;
        }
        return res;
    }
}

搜索二维矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0, j = n - 1;
        while (i >= 0 && i < m && j >= 0 && j < n) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }
}

子集 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> set = new HashSet<>();
        List<Integer> tmp = new ArrayList<>();
        dfs(nums, 0, tmp, set);
        return new ArrayList<>(set);
    }

    private void dfs(int[] nums, int i, List<Integer> tmp, Set<List<Integer>> set) {
        set.add(new ArrayList<>(tmp));
        for (int j = i; j < nums.length; j++) {
            tmp.add(nums[j]);
            dfs(nums, j + 1, tmp, set);
            tmp.remove(tmp.size() - 1);
        }

    }
}

笨阶乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int clumsy(int N) {
        if (N <= 2 ) {
            return N;
        }
        if (N == 3) {
            return 6;
        }
        int res = N * (N - 1) / (N - 2) + N - 3;
        N -= 4;
        while (N >= 4) {
            res += (-N * (N - 1) / (N - 2) + N - 3);
            N -= 4;
        }
        return res - clumsy(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 Solution {
    public int clumsy(int N) {
        Stack<Integer> stack = new Stack<>();
        stack.push(N);
        N--;
        int index = 0;
        while (N > 0) {
            if (index % 4 == 0) {
                stack.push(stack.pop() * N);
            } else if (index % 4 == 1) {
                stack.push(stack.pop() / N);
            } else if (index % 4 == 2) {
                stack.push(N);
            } else if (index % 4 == 3) {
                stack.push(-N);
            }
            index++;
            N--;
        }
        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }
}

直方图的水量

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 sum = Arrays.stream(height).sum();
        int left = 0, right = height.length - 1;
        int high = 1, s = 0;
        while (left <= right) {
            //上层的面积总是小于下层
            while (left <= right && height[left] < high) {
                left++;
            }
            while (right >= left && height[right] < high) {
                right--;
            }
            s += right - left + 1;
            high++;
        }
        return s - 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
26
class Solution {
    public int trap(int[] height) {
        //对于下标 i，水能到达的最大高度等于下标 i 两边的最大高度的最小值，
        // 下标 i 处能接的水的量等于下标 ii 处的水能到达的最大高度减去 height[i]。
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            res += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return res;

    }
}

森林中的兔子

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 numRabbits(int[] answers) {
        if (answers == null || answers.length == 0) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < answers.length; i++) {
            map.put(answers[i], map.getOrDefault(answers[i], 0) + 1);
        }
        int res = 0;
        for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
            int val = entry.getKey();
            int times = entry.getValue();
            if (times % (val + 1) == 0) {
                res += times;
            } else {
                res += (times / (val + 1) + 1) * (val + 1);
            }
        }
        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
class Solution {
    //memo[i][j] 表示text1 0...i和text2 0....j的最长公共子序列长度
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] memo = new int[m][n];
        for (int[] ints : memo) {
            Arrays.fill(ints, 0);
        }
        if (text1.charAt(0) == text2.charAt(0)) {
            memo[0][0] = 1;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    if (text1.charAt(i) == text2.charAt(j)) {
                        memo[i][j] = 1;
                    } else {
                        if (i == 0 && j == 0) {
                        }else {
                            if (i == 0) {
                                memo[i][j] = memo[i][j - 1];
                            } else if (j == 0) {
                                memo[i][j] = memo[i - 1][j];
                            }
                        }
                    }
                    continue;
                }
                if (text1.charAt(i) == text2.charAt(j)) {
                    memo[i][j] = 1 + memo[i - 1][j - 1];
                } else {
                    memo[i][j] = Math.max(memo[i - 1][j], memo[i][j - 1]);
                }
            }
        }
        return memo[m - 1][n - 1];
    }
}

合并两个有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] >= nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        if (i < 0) {
            while (j >= 0) {
                nums1[k--] = nums2[j--];
            }
        } else {
            while (i >= 0) {
                nums1[k--] = nums1[i--];
            }
        }
    }
}

删除有序数组中的重复项 II

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 removeDuplicates(int[] nums) {
        int len = nums.length;
        int slow = 0, fast = 2;
        while (fast < len) {
            if (nums[slow] == nums[fast]) {
                len--;
                removeByIndex(nums, fast);
            } else {
                slow++;
                fast++;
            }
        }
        return len;
    }

    private void removeByIndex(int[] nums, int index) {
        for (int i = index; i < nums.length - 1; i++) {
            nums[i] = nums[i + 1];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    /**
     * j作为新数组的坐标 i是待检查的第一个元素
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        int j = 2, i = 2;
        while (i < nums.length) {
            if (nums[i] != nums[j - 2]) {
                nums[j] = nums[i];
                j++;
            }
            i++;
        }
        return j;
    }
}

搜索旋转排序数组 II

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

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

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

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

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

把数组排成最小的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String largestNumber(int[] nums) {
        String[] strings = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strings[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strings, ((o1, o2) -> (o2 + o1).compareTo(o1 + o2)));
        if (strings[0].equals("0")) {
            return "0";
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < strings.length; i++) {
            stringBuilder.append(strings[i]);
        }
        return stringBuilder.toString();
    }
}

二叉搜索树节点最小距离

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 {
    int res;
    int pre;
    public int minDiffInBST(TreeNode root) {
        res = 100000;
        pre = -1;
        dfs(root);
        return res;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (pre == -1) {
            pre = root.val;
        } else {
            res = Math.min(res, root.val - pre);
            pre = root.val;
        }
        dfs(root.right);
    }
}

实现 Trie (前缀树)

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
class Trie {
    //用来标识是否是结束字符
    private boolean isEnd;
    private Trie[] next;
    /** Initialize your data structure here. */
    public Trie() {
        //26个字母
        next = new Trie[26];
        isEnd = false;

    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie curr = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (curr.next[ch - 'a'] == null) {
                curr.next[ch - 'a'] = new Trie();
            }
            //就像链表一样
            curr = curr.next[ch - 'a'];
        }
        curr.isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie end = prefixSearch(word);
        return end != null && end.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return prefixSearch(prefix) != null;
    }

    private Trie prefixSearch(String word) {
        Trie curr = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (curr.next[ch - 'a'] == null) {
                return null;
            }
            curr = curr.next[ch - 'a'];
        }
        return curr;
    }
}

打家劫舍 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }

    /**
     * dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1])
     * 只和前两个元素有关
     * @param nums
     * @param start
     * @param end
     * @return
     */
    private int robRange(int[] nums, int start, int end) {
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
}
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
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }

    /**
     * dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1])
     * 只和前两个元素有关
     * @param nums
     * @param start
     * @param end
     * @return
     */
    private int robRange(int[] nums, int start, int end) {
        int[] dp = new int[nums.length];
        int pre = 0, curr = 0;
        for (int i = start; i <= end; i++) {
            int temp = curr;
            curr = Math.max(pre + nums[i], curr);
            pre = temp;
        }
        return curr;
    }
}

删除有序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // slow是删除重复元素后的坐标，fast作为原数组的迭代坐标
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[slow] != nums[fast]) {
                //先加slow 保留原来slow这个位置的数，如果相等，则fast++ 跳过相同位置的数
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;
    }
}

移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) {
            return 0;
        }
        int idx = 0;
        for (int num : nums) {
            if (num != val) {
                nums[idx++] = num;
            }
        }
        return idx;
    }
}

实现 strStr()

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
class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length(), n = needle.length();
        if (n == 0) {
            return 0;
        }
        if (m == 0) {
            return -1;
        }
        char begin = needle.charAt(0);
        int index = 0;
        while (index <= m - n) {
            if (haystack.charAt(index) != begin) {
                index++;
                continue;
            }
            int i = index;
            for (i = index; i < index + n; i++) {
                if (haystack.charAt(i) != needle.charAt(i - index)) {
                    break;
                }
            }
            if (i == index + n) {
                return index;
            }
            index++;
        }
        return -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
class Solution {
    /**
     * if(s.charAt(i)=='0') 且 与前一个数一起构成的两位数》=10 《=26  dp[i] = dp[i-2] 即将其与前一个数一起视为两位数
     * 如果不为0 如果能与前一个数一起构成》=10且《=26的两位数则dp[i] = dp[i-1]+dp[i-2]
     * 如果不能构成有效的两位数则dp[i] = dp[i-1]
     * @param s
     * @return
     */
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            //注意0的判断
            if (chars[i] != '0') {
                dp[i] += dp[i - 1];
            }
            //如果是0就把他与前面的视为一个两位数
            if ((chars[i - 1] == '1') || (chars[i - 1] == '2' && chars[i] <= '6')) {
                dp[i] += i >= 2 ? dp[i - 2] : 1;
            }

        }
        return dp[n - 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
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        if (nums.length == 1) {
            List<Integer> list = new ArrayList<>();
            list.add(nums[0]);
            return list;
        }
        Arrays.sort(nums);
        List<Integer> res = new ArrayList<>();
        List<Integer>[] dp = new ArrayList[nums.length];
        //寻找最长的子集？
        for (int i = 0; i < nums.length; i++) {
            dp[i] = new ArrayList<>();
            dp[i].add(nums[i]);
            int submax = -1;
            int index = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0) {
                    if (submax < dp[j].size()) {
                        submax = dp[j].size();
                        index = j;
                    }
                }
            }
            //存在子集
            if (index != -1) {
                for (Integer integer : dp[index]) {
                    //更新最大集
                    dp[i].add(integer);
                }
            }
        }
        int maxdp = -1;

        //找到最大子集
        for (List<Integer> integers : dp) {
            if (maxdp < integers.size()) {
                res = integers;
                maxdp = integers.size();
            }
        }
        return res;
    }
}

组合总和 Ⅳ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        //dp[i]代表组合数为i时使用nums中的数能组成的组合数的个数
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {
            for (int num : nums) {
                if (i - num < 0) {
                    break;
                }
                dp[i] += dp[i - num];
            }
        }
        return dp[target];

    }
}

递增顺序搜索树

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 {
    TreeNode head, pre;

    public TreeNode increasingBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        dfs(root);
        return head;

    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        TreeNode curr = new TreeNode(root.val);
        if (pre == null) {
            head = curr;
        } else {
            pre.right = curr;
        }
        pre = curr;
        dfs(root.right);
    }
}

在 D 天内送达包裹的能力

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
class Solution {
    /**
     * 最小运载能力大于等于重量的最大值小于等于重量的总和
     * 寻找一个满足条件的左边界
     * @param weights
     * @param D 天数
     * @return
     */
    public int shipWithinDays(int[] weights, int D) {
        int left = Integer.MIN_VALUE;
        int right = 0;
        for (int i = 0; i < weights.length; i++) {
            left = Math.max(weights[i], left);
            right += weights[i];
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(weights, D, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;

    }

    private boolean canFinish(int[] weights, int D, int cap) {
        int index = 0;
        for (int i = 0; i < D; i++) {
            int subCap = cap;
            while (subCap - weights[index] >= 0) {
                subCap -= weights[index++];
                if (index == weights.length) {
                    return true;
                }
            }
        }
        return false;
    }
}

二叉搜索树的范围和

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        } else if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        } else if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        } else {
            return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
        }
    }
}

平方数之和

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 judgeSquareSum(int c) {
        int d = (int) Math.sqrt((double) c);
        System.out.println(d);
        int[] num = new int[d + 1];
        for (int i = 0; i < num.length; i++) {
            num[i] = i * i;
        }
        return twoSums(num, c);
    }

    private boolean twoSums(int[] num, int target) {
        int left = 0, right = num.length - 1;
        while (left <= right) {
            int sum = num[left] + num[right];
            if (sum > target) {
                right--;
            } else if (sum < target) {
                left++;
            } else {
                return true;
            }
        }
        return false;
    }
}

青蛙过河

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    //状态：当前所在的石子编号和上一次跳跃距离
    public boolean canCross(int[] stones) {
        int n = stones.length;
        for (int i = 1; i < n; i++) {
            if (stones[i] - stones[i - 1] > i) {
                return false;
            }
        }
        boolean[][] dp = new boolean[n][n];
        //base case
        dp[0][0] = true;

        for (int i = 1; i < n; i++) {
            //上一次的跳跃距离一定小于i
            for (int j = 0; j < i; j++) {
                //从j跳过来的
                int k = stones[i] - stones[j];
                //stones[j]最多跳j+1步
                if (k <= j + 1) {
                    //从j跳到i跳了k步
                    //则跳到j 可能跳了k-1到k+1步
                    dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                    if (i == n - 1 && dp[i][k]) {
                        return true;
                    }
                }

            }
        }
        return false;
    }
}

叶子相似的树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        StringBuilder sb1 = new StringBuilder();
        dfs(root1, sb1);
        StringBuilder sb2 = new StringBuilder();
        dfs(root2, sb2);
        System.out.println(sb1.toString());
        System.out.println(sb2.toString());
        return sb1.toString().equals(sb2.toString());
    }

    private void dfs(TreeNode root, StringBuilder stringBuilder) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            //一定要加逗号
            stringBuilder.append(root.val).append(",");
        }
        dfs(root.left, stringBuilder);
        dfs(root.right, stringBuilder);
    }
}

解码异或后的排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] decode(int[] encoded) {
        int[] res = new int[encoded.length + 1];
        int n = encoded.length + 1;
        int a = 0;
        for (int i = 1; i <= n; i++) {
            a ^= i;
        }
        for (int i = 0; i < encoded.length; i = i + 2) {
            a ^= encoded[i];
        }
        // a=res[i]
        res[res.length - 1] = a;
        for (int i = encoded.length - 1; i >= 0; i--) {
            res[i] = encoded[i] ^ res[i + 1];
        }
        return res;
    }
}