'数据结构与算法 精选TOP面试题'

LeetCode 精选TOP 面试题

链接直达

1.两数之加

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。

链接：https://leetcode-cn.com/problems/two-sum

public class Problem_0001_TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[] { map.get(target - nums[i]), i };
            }
            map.put(nums[i], i);
        }
        return new int[] { -1, -1 };
    }
}

2.两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

链接：https://leetcode-cn.com/problems/add-two-numbers

public class Problem_0002_AddTwoNumbers {

    // 不要提交这个类描述
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int value) {
            this.val = value;
        }
    }

    public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
        int ca = 0;
        int n1 = 0;
        int n2 = 0;
        int n = 0;
        ListNode c1 = head1;
        ListNode c2 = head2;
        ListNode node = null;
        ListNode pre = null;
        while (c1 != null || c2 != null) {
            n1 = c1 != null ? c1.val : 0;
            n2 = c2 != null ? c2.val : 0;
            n = n1 + n2 + ca;
            pre = node;
            node = new ListNode(n % 10);
            node.next = pre;
            ca = n / 10;
            c1 = c1 != null ? c1.next : null;
            c2 = c2 != null ? c2.next : null;
        }
        if (ca == 1) {
            pre = node;
            node = new ListNode(1);
            node.next = pre;
        }
        return reverseList(node);
    }

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

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

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

public class Problem_0003_LongestSubstringWithoutRepeatingCharacters {

    public static int lengthOfLongestSubstring(String str) {
        if (str == null || str.equals("")) {
            return 0;
        }
        char[] chas = str.toCharArray();
        int[] map = new int[256];
        for (int i = 0; i < 256; i++) {
            map[i] = -1;
        }
        int len = 0;
        int pre = -1;
        int cur = 0;
        for (int i = 0; i != chas.length; i++) {
            pre = Math.max(pre, map[chas[i]]);
            cur = i - pre;
            len = Math.max(len, cur);
            map[chas[i]] = i;
        }
        return len;
    }
}

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

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

public class Problem_0004_MedianOfTwoSortedArrays {

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int size = nums1.length + nums2.length;
        boolean even = (size & 1) == 0;
        if (nums1.length != 0 && nums2.length != 0) {
            if (even) {
                return (double) (findKthNum(nums1, nums2, size / 2) + findKthNum(nums1, nums2, size / 2 + 1)) / 2D;
            } else {
                return findKthNum(nums1, nums2, size / 2 + 1);
            }
        } else if (nums1.length != 0) {
            if (even) {
                return (double) (nums1[(size - 1) / 2] + nums1[size / 2]) / 2;
            } else {
                return nums1[size / 2];
            }
        } else if (nums2.length != 0) {
            if (even) {
                return (double) (nums2[(size - 1) / 2] + nums2[size / 2]) / 2;
            } else {
                return nums2[size / 2];
            }
        } else {
            return 0;
        }
    }

    public static int findKthNum(int[] arr1, int[] arr2, int kth) {
        int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
        int[] shorts = arr1.length < arr2.length ? arr1 : arr2;
        int l = longs.length;
        int s = shorts.length;
        if (kth <= s) {
            return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1);
        }
        if (kth > l) {
            if (shorts[kth - l - 1] >= longs[l - 1]) {
                return shorts[kth - l - 1];
            }
            if (longs[kth - s - 1] >= shorts[s - 1]) {
                return longs[kth - s - 1];
            }
            return getUpMedian(shorts, kth - l, s - 1, longs, kth - s, l - 1);
        }
        if (longs[kth - s - 1] >= shorts[s - 1]) {
            return longs[kth - s - 1];
        }
        return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
    }

    public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) {
        int mid1 = 0;
        int mid2 = 0;
        while (s1 < e1) {
            mid1 = (s1 + e1) / 2;
            mid2 = (s2 + e2) / 2;
            if (A[mid1] == B[mid2]) {
                return A[mid1];
            }
            if (((e1 - s1 + 1) & 1) == 1) { // 奇数长度
                if (A[mid1] > B[mid2]) {
                    if (B[mid2] >= A[mid1 - 1]) {
                        return B[mid2];
                    }
                    e1 = mid1 - 1;
                    s2 = mid2 + 1;
                } else { // A[mid1] < B[mid2]
                    if (A[mid1] >= B[mid2 - 1]) {
                        return A[mid1];
                    }
                    e2 = mid2 - 1;
                    s1 = mid1 + 1;
                }
            } else { // 偶数长度
                if (A[mid1] > B[mid2]) {
                    e1 = mid1;
                    s2 = mid2 + 1;
                } else {
                    e2 = mid2;
                    s1 = mid1 + 1;
                }
            }
        }
        return Math.min(A[s1], B[s2]);
    }
}

5.最长回文子串

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

链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
解题思路：https://midkuro.gitee.io/2020/10/30/algorithm-trainingcamp1/#Manacher%E7%AE%97%E6%B3%95

7.整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

注意：
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

链接：https://leetcode-cn.com/problems/reverse-integer

public class Problem_0007_ReverseInteger {

    public static int reverse(int x) {
        //把值转负数，增大范围
        boolean neg = ((x >>> 31) & 1) == 1;
        x = neg ? x : -x;
        //用以计算防止溢出
        int m = Integer.MIN_VALUE / 10;
        int o = Integer.MIN_VALUE % 10;
        int res = 0;
        while (x != 0) {
            if (res < m || (res == m && x % 10 < o)) {
                return 0;
            }
            res = res * 10 + x % 10;
            x /= 10;
        }
        return neg ? res : Math.abs(res);
    }
}

10.正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

链接：https://leetcode-cn.com/problems/regular-expression-matching

public static boolean isValid(char[] str, char[] pattern) {
    for (char cha : str) {
        if (cha == '.' || cha == '*') {
            return false;
        }
    }
    for (int i = 0; i < pattern.length; i++) {
        if (pattern[i] == '*' && (i == 0 || pattern[i - 1] == '*')) {
            return false;
        }
    }
    return true;
}

// 课堂现场写
public static boolean isMatch1(String s, String p) {
    if (s == null || p == null) {
        return false;
    }
    char[] str = s.toCharArray();
    char[] pattern = p.toCharArray();
    return isValid(str, pattern) && process1(str, pattern, 0, 0);
}

// 课堂现场写
// str[si.....] 能否被 pattern[pi...] 变出来
// 潜台词：pi位置，pattern[pi] != '*'
public static boolean process1(char[] str, char[] pattern, int si, int pi) {
    if (si == str.length) { // si越界了
        if (pi == pattern.length) {
            return true;
        }
        if (pi + 1 < pattern.length && pattern[pi + 1] == '*') {
            return process1(str, pattern, si, pi + 2);
        }
        return false;
    }
    // si 没越界
    if (pi == pattern.length) {
        return si == str.length;
    }
    // si 没越界 pi 没越界
    if (pi + 1 >= pattern.length || pattern[pi + 1] != '*') {
        return ((str[si] == pattern[pi]) || (pattern[pi] == '.')) && process1(str, pattern, si + 1, pi + 1);
    }
    // si 没越界 pi 没越界 pi+1 *
    if (pattern[pi] != '.' && str[si] != pattern[pi]) {
        return process1(str, pattern, si, pi + 2);
    }
    // si 没越界 pi 没越界 pi+1 * [pi]可配[si]
    if (process1(str, pattern, si, pi + 2)) {
        return true;
    }
    while (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')) {
        if (process1(str, pattern, si + 1, pi + 2)) {
            return true;
        }
        si++;
    }
    return false;
}

11.盛最多水的容器

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

链接：https://leetcode-cn.com/problems/container-with-most-water

public class Problem_0011_ContainerWithMostWater {

    public static int maxArea(int[] h) {
        int max = 0;
        int l = 0;
        int r = h.length - 1;
        while (l < r) {
            max = Math.max(max, Math.min(h[l], h[r]) * (r - l));
            if (h[l] > h[r]) {
                r--;
            } else {
                l++;
            }
        }
        return max;
    }
}

12.整数转罗马数字

链接：https://leetcode-cn.com/problems/integer-to-roman/

public class Problem_0012_IntegerToRoman {

    public static String intToRoman(int num) {
        String[][] c = { 
            { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" },
            { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" },
            { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" },
            { "", "M", "MM", "MMM" } };
        StringBuilder roman = new StringBuilder();
        roman
            .append(c[3][num / 1000 % 10])
            .append(c[2][num / 100 % 10])
            .append(c[1][num / 10 % 10])
            .append(c[0][num % 10]);
        return roman.toString();
    }

}

13.罗马数字转整数

链接：https://leetcode-cn.com/problems/roman-to-integer/

public class Problem_0013_RomanToInteger {

    public static int romanToInt(String s) {
        int nums[] = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case 'M':
                    nums[i] = 1000;
                    break;
                case 'D':
                    nums[i] = 500;
                    break;
                case 'C':
                    nums[i] = 100;
                    break;
                case 'L':
                    nums[i] = 50;
                    break;
                case 'X':
                    nums[i] = 10;
                    break;
                case 'V':
                    nums[i] = 5;
                    break;
                case 'I':
                    nums[i] = 1;
                    break;
            }
        }
        int sum = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] < nums[i + 1]) {
                sum -= nums[i];
            } else {
                sum += nums[i];
            }
        }
        return sum + nums[nums.length - 1];
    }
}

14最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

连接：https://leetcode-cn.com/problems/longest-common-prefix/

public class Problem_0014_LongestCommonPrefix {

    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        char[] chs = strs[0].toCharArray();
        int min = Integer.MAX_VALUE;
        for (String str : strs) {
            char[] tmp = str.toCharArray();
            int index = 0;
            while (index < tmp.length && index < chs.length) {
                if (chs[index] != tmp[index]) {
                    break;
                }
                index++;
            }
            min = Math.min(index, min);
            if (min == 0) {
                return "";
            }
        }
        return strs[0].substring(0, min);
    }
}

15.三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

链接：https://leetcode-cn.com/problems/3sum

public static List<List<Integer>> threeSum1(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList<>();
    // 第一个数选了i位置的数
    for (int i = 0; i < nums.length - 2; i++) {
        if (i == 0 || nums[i - 1] != nums[i]) {
            List<List<Integer>> nexts = twoSum1(nums, i + 1, -nums[i]);
            for (List<Integer> cur : nexts) {
                cur.add(0, nums[i]);
                ans.add(cur);
            }
        }
    }
    return ans;
}

// nums已经有序了
// nums[begin......]范围上，找到累加和为target的所有二元组
public static List<List<Integer>> twoSum1(int[] nums, int begin, int target) {
    int L = begin;
    int R = nums.length - 1;
    List<List<Integer>> ans = new ArrayList<>();
    while (L < R) {
        if (nums[L] + nums[R] > target) {
            R--;
        } else if (nums[L] + nums[R] < target) {
            L++;
        } else {
            if (L == begin || nums[L - 1] != nums[L]) {
                List<Integer> cur = new ArrayList<>();
                cur.add(nums[L]);
                cur.add(nums[R]);
                ans.add(cur);
            }
            L++;
        }
    }
    return ans;
}

17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

连接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

public class Problem_0017_LetterCombinationsOfAPhoneNumber {

    public static char[][] phone = { 
        { 'a', 'b', 'c' }, // 2    0
        { 'd', 'e', 'f' }, // 3    1
        { 'g', 'h', 'i' }, // 4    2
        { 'j', 'k', 'l' }, // 5    3
        { 'm', 'n', 'o' }, // 6    
        { 'p', 'q', 'r', 's' }, // 7 
        { 't', 'u', 'v' },   // 8
        { 'w', 'x', 'y', 'z' }, // 9
    };

    // "23"
    public static List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        char[] str = digits.toCharArray();
        char[] path = new char[str.length];
        process(str, 0, path, ans);
        return ans;
    }

    // str = ['2','3']  3   3
    // str[....index-1]，按出的结果是什么都在path里
    // str[index...]  按完之后，有哪些组合，放入到ans里
    public static void process(char[] str, int index, char[] path, List<String> ans) {
        if (index == str.length) {
            ans.add(String.valueOf(path));
        } else {
            char[] cands = phone[str[index] - '2'];
            for (char cur : cands) {
                path[index] = cur;
                process(str, index + 1, path, ans);
            }
        }
    }
}

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

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

链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

public class Problem_0019_RemoveNthNodeFromEndofList {

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            n--;
            if (n == -1) {
                pre = head;
            }
            if (n < -1) {
                pre = pre.next;
            }
            cur = cur.next;
        }
        if (n > 0) {
            return head;
        }
        if (pre == null) {
            return head.next;
        }
        pre.next = pre.next.next;
        return head;
    }
}

20.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

链接：https://leetcode-cn.com/problems/valid-parentheses

public class Problem_0020_ValidParentheses {

    public static boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        char[] str = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length; i++) {
            char cha = str[i];
            if (cha == '(' || cha == '[' || cha == '{') {
                stack.add(cha == '(' ? ')' : (cha == '[' ? ']' : '}'));
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char last = stack.pop();
                if (cha != last) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

21.合并两个有序链表

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

链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/

public class Problem_0021_MergeTwoSortedLists {

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        ListNode head = l1.val <= l2.val ? l1 : l2;
        ListNode cur1 = head.next;
        ListNode cur2 = head == l1 ? l2 : l1;
        ListNode pre = head;
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        pre.next = cur1 != null ? cur1 : cur2;
        return head;
    }
}

22.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合

链接：https://leetcode-cn.com/problems/generate-parentheses/

public static List<String> generateParenthesis(int n) {
    char[] path = new char[n << 1];
    List<String> ans = new ArrayList<>();
    process(path, 0, 0, n, ans);
    return ans;
}

// 依次在path上填写决定
// ( ( ) ) ( )....
// 0 1 2 3 4 5
// path[0...index-1]决定已经做完了
// index位置上，( )
public static void process(char[] path, int index, int leftMinusRight, int leftRest, List<String> ans) {
    if (index == path.length) {
        ans.add(String.valueOf(path));
    } else {
        if (leftRest > 0) {
            path[index] = '(';
            process(path, index + 1, leftMinusRight + 1, leftRest - 1, ans);
        }
        if (leftMinusRight > 0) {
            path[index] = ')';
            process(path, index + 1, leftMinusRight - 1, leftRest, ans);
        }
    }
}

23.合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/

public class Problem_0023_MergeKSortedLists {

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static class ListNodeComparator implements Comparator<ListNode> {

        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }

    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                heap.add(lists[i]);
            }
        }
        if (heap.isEmpty()) {
            return null;
        }
        ListNode head = heap.poll();
        ListNode pre = head;
        if (pre.next != null) {
            heap.add(pre.next);
        }
        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = cur;
            if (cur.next != null) {
                heap.add(cur.next);
            }
        }
        return head;
    }
}

26.删除排序数组中的重复项

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

public class Problem_0026_RemoveDuplicatesFromSortedArray {

    public static int removeDuplicates(int[] nums) {
        if (nums == null) {
            return 0;
        }
        if (nums.length < 2) {
            return nums.length;
        }
        int done = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[done]) {
                nums[++done] = nums[i];
            }
        }
        return done + 1;
    }
}

28.实现strStr函数

KMP算法:https://midkuro.gitee.io/2020/10/30/algorithm-trainingcamp1/#KMP%E7%AE%97%E6%B3%95

链接：https://leetcode-cn.com/problems/implement-strstr/

29.两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

链接：https://leetcode-cn.com/problems/divide-two-integers

public class Problem_0029_DivideTwoIntegers {

    public static int add(int a, int b) {
        int sum = a;
        while (b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }

    public static int negNum(int n) {
        return add(~n, 1);
    }

    public static int minus(int a, int b) {
        return add(a, negNum(b));
    }

    public static int multi(int a, int b) {
        int res = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                res = add(res, a);
            }
            a <<= 1;
            b >>>= 1;
        }
        return res;
    }

    public static boolean isNeg(int n) {
        return n < 0;
    }

    public static int div(int a, int b) {
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        int res = 0;
        for (int i = 31; i > negNum(1); i = minus(i, 1)) {
            if ((x >> i) >= y) {
                res |= (1 << i);
                x = minus(x, y << i);
            }
        }
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    }

    public static int divide(int dividend, int divisor) {
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        // 除数不是系统最小
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == negNum(1)) {
                return Integer.MAX_VALUE;
            }
            int res = div(add(dividend, 1), divisor);
            return add(res, div(minus(dividend, multi(res, divisor)), divisor));
        }
        // dividend不是系统最小，divisor也不是系统最小
        return div(dividend, divisor);
    }
    // div(a,b) a和b都不能是系统最小

    // 现场福利函数
    public static String printNumBinary(int num) {
        StringBuilder builder = new StringBuilder();
        for (int i = 31; i >= 0; i--) {
            builder.append(((num >> i) & 1) == 0 ? '0' : '1');
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        int num = -1;
        System.out.println(printNumBinary(num));
    }
}

33.搜索旋转排序数组

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 

链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array

public class Problem_0033_SearchInRotatedSortedArray {

    public static int search(int[] arr, int num) {
        int L = 0;
        int R = arr.length - 1;
        int M = 0;
        while (L <= R) {
            M = (L + R) / 2;
            if (arr[M] == num) {
                return M;
            }
            // arr[M] != num
            if (arr[L] == arr[M] && arr[M] == arr[R]) {
                while (L != M && arr[L] == arr[M]) {
                    L++;
                }
                // L和M没撞上，[L]!=[M] L,.....M
                if (L == M) {
                    L = M + 1;
                    continue;
                }
            }
            // arr[M] != num
            // [L] [M] [R] 不都一样的情况
            if (arr[L] != arr[M]) {
                if (arr[M] > arr[L]) {
                    if (num >= arr[L] && num < arr[M]) {
                        R = M - 1;
                    } else {
                        L = M + 1;
                    }
                } else { //  [L]  >  [M]
                    if (num > arr[M] && num <= arr[R]) {
                        L = M + 1;
                    } else {
                        R = M - 1;
                    }
                }
            } else { // [L] === [M] ->  [M]!=[R]
                if (arr[M] < arr[R]) {
                    if (num > arr[M] && num <= arr[R]) {
                        L = M + 1;
                    } else {
                        R = M - 1;
                    }
                } else {
                    if (num >= arr[L] && num < arr[M]) {
                        R = M - 1;
                    } else {
                        L = M + 1;
                    }
                }
            }
        }
        return -1;
    }
}

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

public class Problem_0034_FindFirstAndLastPositionOfElementInSortedArray {

    public static int[] searchRange(int[] nums, int target) {
        int[] ans = { -1, -1 };
        if (nums == null || nums.length == 0) {
            return ans;
        }
        ans[0] = findFirst(nums, target);
        ans[1] = findLast(nums, target);
        return ans;
    }

    public static int findFirst(int[] arr, int num) {
        int L = 0;
        int R = arr.length - 1;
        int ans = -1;
        int mid = 0;
        while (L <= R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] < num) {
                L = mid + 1;
            } else if (arr[mid] > num) {
                R = mid - 1;
            } else {
                ans = mid;
                R = mid - 1;
            }
        }
        return ans;
    }

    public static int findLast(int[] arr, int num) {
        int L = 0;
        int R = arr.length - 1;
        int ans = -1;
        int mid = 0;
        while (L <= R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] < num) {
                L = mid + 1;
            } else if (arr[mid] > num) {
                R = mid - 1;
            } else {
                ans = mid;
                L = mid + 1;
            }
        }
        return ans;
    }
}

36.有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

链接：https://leetcode-cn.com/problems/valid-sudoku

public class Problem_0036_ValidSudoku {
    public static boolean isValidSudoku(char[][] board) {
        boolean[][] row = new boolean[9][10];
        boolean[][] col = new boolean[9][10];
        boolean[][] bucket = new boolean[9][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int bid = 3 * (i / 3) + (j / 3);
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    if (row[i][num] || col[j][num] || bucket[bid][num]) {
                        return false;
                    }
                    row[i][num] = true;
                    col[j][num] = true;
                    bucket[bid][num] = true;
                }
            }
        }
        return true;
    }
}

37.解数独

编写一个程序，通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

链接：https://leetcode-cn.com/problems/sudoku-solver

public class Problem_0037_SudokuSolver {

    public static void solveSudoku(char[][] board) {
        boolean[][] row = new boolean[9][10];
        boolean[][] col = new boolean[9][10];
        boolean[][] bucket = new boolean[9][10];
        initMaps(board, row, col, bucket);
        process(board, 0, 0, row, col, bucket);
    }

    public static void initMaps(char[][] board, boolean[][] row, boolean[][] col, boolean[][] bucket) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int bid = 3 * (i / 3) + (j / 3);
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    row[i][num] = true;
                    col[j][num] = true;
                    bucket[bid][num] = true;
                }
            }
        }
    }

    public static boolean process(char[][] board, int i, int j, boolean[][] row, boolean[][] col, boolean[][] bucket) {
        if (i == 9) {
            return true;
        }
        int nexti = j != 8 ? i : i + 1;
        int nextj = j != 8 ? j + 1 : 0;
        if (board[i][j] != '.') {
            return process(board, nexti, nextj, row, col, bucket);
        } else {
            int bid = 3 * (i / 3) + (j / 3);
            for (int num = 1; num <= 9; num++) {
                if ((!row[i][num]) && (!col[j][num]) && (!bucket[bid][num])) {
                    row[i][num] = true;
                    col[j][num] = true;
                    bucket[bid][num] = true;
                    board[i][j] = (char) (num + '0');
                    if (process(board, nexti, nextj, row, col, bucket)) {
                        return true;
                    }
                    row[i][num] = false;
                    col[j][num] = false;
                    bucket[bid][num] = false;
                    board[i][j] = '.';
                }
            }
            return false;
        }
    }
}

41.缺失的第一个整数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

链接：https://leetcode-cn.com/problems/first-missing-positive

public class Problem_0041_FirstMissingPositive {
    public static int firstMissingPositive(int[] arr) {
        //双指针，卡位置
        int l = 0;
        int r = arr.length;
        while (l < r) {
            //如果当前的值 = index + 1，则认为是正确的
            if (arr[l] == l + 1) {
                l++;
            //若当前的值 < index、大于 r，或者他应该落在的位置上已存在相同的值，则无效
            } else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {
                swap(arr,l,--r);
            } else {
                //和它应该存在的位置做交换，接着卡L指针
                swap(arr, l, arr[l] - 1);
            }
        }
        return l + 1;
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

42.接雨水

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

public class Problem_0042_TrappingRainWater {

    public static int trap(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int N = arr.length;
        int L = 1;
        int leftMax = arr[0];
        int R = N - 2;
        int rightMax = arr[N - 1];
        int water = 0;
        while (L <= R) {
            if (leftMax <= rightMax) {
                water += Math.max(0, leftMax - arr[L]);
                leftMax = Math.max(leftMax, arr[L++]);
            } else {
                water += Math.max(0, rightMax - arr[R]);
                rightMax = Math.max(rightMax, arr[R--]);
            }
        }
        return water;
    }
}

44.通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

链接：https://leetcode-cn.com/problems/wildcard-matching

public static boolean isMatch1(String str, String pattern) {
    char[] s = str.toCharArray();
    char[] p = pattern.toCharArray();
    return process1(s, p, 0, 0);
}

// s[si....] 能否被 p[pi....] 匹配出来
public static boolean process1(char[] s, char[] p, int si, int pi) {
    if (si == s.length) { // s -> ""
        if (pi == p.length) { // p -> ""
            return true;
        } else {
            // p -> "..."
            // p[pi] == '*' && p[pi+1...] -> "
            return p[pi] == '*' && process1(s, p, si, pi + 1);
        }
    }
    if (pi == p.length) { // p -> "" s
        return si == s.length;
    }
    // s从si出发.... p从pi出发...
    // s[si] -> 小写字母
    // p[pi] -> 小写、?、*
    if (p[pi] != '?' && p[pi] != '*') {
        return s[si] == p[pi] && process1(s, p, si + 1, pi + 1);
    }
    // si.. pi.. pi ? *
    if (p[pi] == '?') {
        return process1(s, p, si + 1, pi + 1);
    }
    for (int len = 0; len <= s.length - si; len++) {
        if (process1(s, p, si + len, pi + 1)) {
            return true;
        }
    }
    return false;
}

// 最终做的化简
public static boolean isMatch3(String str, String pattern) {
    char[] s = str.toCharArray();
    char[] p = pattern.toCharArray();
    int N = s.length;
    int M = p.length;
    boolean[][] dp = new boolean[N + 1][M + 1];
    dp[N][M] = true;
    for (int pi = M - 1; pi >= 0; pi--) {
        dp[N][pi] = p[pi] == '*' && dp[N][pi + 1];
    }
    for (int si = N - 1; si >= 0; si--) {
        for (int pi = M - 1; pi >= 0; pi--) {
            if (p[pi] != '*') {
                dp[si][pi] = (p[pi] == '?' || s[si] == p[pi]) && dp[si + 1][pi + 1];
            } else {
                dp[si][pi] = dp[si][pi + 1] || dp[si + 1][pi];
            }
        }
    }
    return dp[0][0];
}

55.跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。

public class Problem_0055_JumpGame {
    public static boolean canJump(int[] nums) {
        if (nums == null || nums.length < 2) {
            return true;
        }
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (i > max) {
                return false;
            }
            max = Math.max(max, i + nums[i]);
        }
        return true;
    }
}

45.跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。

链接：https://leetcode-cn.com/problems/jump-game-ii

public class Problem_0045_JumpGameII {

  public static int jump(int[] arr) {
    if (arr == null || arr.length == 0) {
      return 0;
    }
    int step = 0;
    int cur = 0;
    int next = arr[0];
    for (int i = 1; i < arr.length; i++) {
      if (cur < i) {
        step++;
        cur = next;
      }
      next = Math.max(next, i + arr[i]);
    }
    return step;
  }
}

45.跳跃游戏 III

进阶：给定一个起始下标和结束下标，可以往左跳，也可以往右跳，固定位置跳，问最少跳几次从起始下标跳到结束下标

思路：当做二叉树的宽度优先遍历来做（队列），需要去重重复计算过的下标，层数就是跳的步数

46.全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

链接：https://leetcode-cn.com/problems/permutations/

public static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    process(nums, 0, ans);
    return ans;
}

public static void process(int[] nums, int index, List<List<Integer>> ans) {
    if (index == nums.length) {
        ArrayList<Integer> cur = new ArrayList<>();
        for (int num : nums) {
            cur.add(num);
        }
        ans.add(cur);
    } else {
        for (int j = index; j < nums.length; j++) {
            swap(nums, index, j);
            process(nums, index + 1, ans);
            swap(nums, index, j);
        }
    }
}

public static void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

48.旋转图像

给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

链接：https://leetcode-cn.com/problems/rotate-image

public class Problem_0048_RotateImage {
    public static void rotate(int[][] matrix) {
        // matrix.len == matrix[0].len
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix[0].length - 1;
        while (tR < dR) {
            rotateEdge(matrix, tR++, tC++, dR--, dC--);
        }
    }

    public static void rotateEdge(int[][] m, int tR, int tC, int dR, int dC) {
        int times = dC - tC;
        int tmp = 0;
        for (int i = 0; i != times; i++) { 
            tmp = m[tR][tC + i];
            m[tR][tC + i] = m[dR - i][tC];
            m[dR - i][tC] = m[dR][dC - i];
            m[dR][dC - i] = m[tR + i][dC];
            m[tR + i][dC] = tmp;
        }
    }
}

49.字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

链接：https://leetcode-cn.com/problems/group-anagrams/

public static List<List<String>> groupAnagrams2(String[] strs) {
    HashMap<String, List<String>> map = new HashMap<String, List<String>>();
    for (String str : strs) {
        char[] chs = str.toCharArray();
        Arrays.sort(chs);
        String key = String.valueOf(chs);
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<String>());
        }
        map.get(key).add(str);
    }
    List<List<String>> res = new ArrayList<List<String>>();
    for (List<String> list : map.values()) {
        res.add(list);
    }
    return res;
}

50.Pox(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数

链接：https://leetcode-cn.com/problems/powx-n/

public static double myPow2(double x, int n) {
    if (n == 0) {
        return 1D;
    }
    int pow = Math.abs(n == Integer.MIN_VALUE ? n + 1 : n);
    double t = x;
    double ans = 1D;
    while (pow != 0) {
        if ((pow & 1) != 0) {
            ans *= t;
        }
        pow >>= 1;
        t = t * t;
    }
    if (n == Integer.MIN_VALUE) {
        ans *= x;
    }
    return n < 0 ? (1D / ans) : ans;
}

53.最大子序和

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

链接：https://leetcode-cn.com/problems/maximum-subarray/

public int maxSubArray(int[] nums) {
    int pre = 0, maxAns = nums[0];
    for (int x : nums) {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    }
    return maxAns;
}

54.螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

链接：https://leetcode-cn.com/problems/spiral-matrix/

public class Problem_0054_SpiralMatrix {

    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return ans;
        }
        int a = 0;
        int b = 0;
        int c = matrix.length - 1;
        int d = matrix[0].length - 1;
        while (a <= c && b <= d) {
            addEdge(matrix, a++, b++, c--, d--, ans);
        }
        return ans;
    }

    public static void addEdge(int[][] m, int a, int b, int c, int d, List<Integer> ans) {
        if (a == c) {
            for (int i = b; i <= d; i++) {
                ans.add(m[a][i]);
            }
        } else if (b == d) {
            for (int i = a; i <= c; i++) {
                ans.add(m[i][b]);
            }
        } else {
            int curC = b;
            int curR = a;
            while (curC != d) {
                ans.add(m[a][curC]);
                curC++;
            }
            while (curR != c) {
                ans.add(m[curR][d]);
                curR++;
            }
            while (curC != b) {
                ans.add(m[c][curC]);
                curC--;
            }
            while (curR != a) {
                ans.add(m[curR][b]);
                curR--;
            }
        }
    }
}

56.合并区间

给出一个区间的集合，请合并所有重叠的区间。
链接：https://leetcode-cn.com/problems/merge-intervals/

public class Problem_0056_MergeIntervals {

    public static class Range {
        public int start;
        public int end;

        public Range(int s, int e) {
            start = s;
            end = e;
        }
    }

    public static class RangeComparator implements Comparator<Range> {

        @Override
        public int compare(Range o1, Range o2) {
            return o1.start - o2.start;
        }

    }

    // intervals  N * 2
    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][0];
        }
        Range[] arr = new Range[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            arr[i] = new Range(intervals[i][0], intervals[i][1]);
        }
        Arrays.sort(arr, new RangeComparator());
        ArrayList<Range> ans = new ArrayList<>();
        int s = arr[0].start;
        int e = arr[0].end;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i].start > e) {
                ans.add(new Range(s, e));
                s = arr[i].start;
                e = arr[i].end;
            } else {
                e = Math.max(e, arr[i].end);
            }
        }
        ans.add(new Range(s, e));
        return generateMatrix(ans);
    }

    public static int[][] generateMatrix(ArrayList<Range> list) {
        int[][] matrix = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            matrix[i] = new int[] { list.get(i).start, list.get(i).end };
        }
        return matrix;
    }
}

62.不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

链接：https://leetcode-cn.com/problems/unique-paths

public class Problem_0062_UniquePaths {
    //C(9,3) 数学排列
    public static int uniquePaths(int m, int n) {
        int part = n - 1;
        int all = m + n - 2;
        long o1 = 1;
        long o2 = 1;
        for (int i = part + 1, j = 1; i <= all || j <= all - part; i++, j++) {
            o1 *= i;
            o2 *= j;
            long gcd = gcd(o1,o2);
            o1 /= gcd;
            o2 /= gcd;
        }
        return (int)o1;
    }

    // 辗转相除法，调用的时候，请保证初次调用时，m和n都不为0
    public static long gcd(long m, long n) {
        return n == 0 ? m : gcd(n, m % n);
    }
}

66.加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

链接：https://leetcode-cn.com/problems/plus-one

public class Problem_0066_PlusOne {
    public static int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        int[] ans = new int[n + 1];
        ans[0] = 1;
        return ans;
    }
}

69.x的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
    
链接：https://leetcode-cn.com/problems/sqrtx/

public class Problem_0069_SqrtX {

    // x一定非负，输入可以保证
    public static int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        if (x < 3) {
            return 1;
        }
        long ans = 1;
        long L = 1;
        long R = x;
        long M = 0;
        while (L <= R) {
            M = (L + R) / 2;
            if (M * M <= x) {
                ans = M;
                L = M + 1;
            } else {
                R = M - 1;
            }
        }
        return (int) ans;
    }
}

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

链接：https://leetcode-cn.com/problems/climbing-stairs/

public class Problem_0070_ClimbingStairs {

    public static int climbStairs(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int[][] base = { { 1, 1 }, { 1, 0 } };
        int[][] res = matrixPower(base, n - 2);
        return 2 * res[0][0] + res[1][0];
    }

    public static int[][] matrixPower(int[][] m, int p) {
        int[][] res = new int[m.length][m[0].length];
        for (int i = 0; i < res.length; i++) {
            res[i][i] = 1;
        }

        // res = 矩阵中的1
        int[][] tmp = m;// 矩阵1次方
        for (; p != 0; p >>= 1) {
            if ((p & 1) != 0) {
                res = muliMatrix(res, tmp);
            }
            tmp = muliMatrix(tmp, tmp);
        }
        return res;
    }

    // 两个矩阵乘完之后的结果返回
    public static int[][] muliMatrix(int[][] m1, int[][] m2) {
        int[][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m2.length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }
}

73.矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

链接：https://leetcode-cn.com/problems/set-matrix-zeroes/

public static void setZeroes2(int[][] matrix) {
    boolean col0 = false;
    int i = 0;
    int j = 0;
    for (i = 0; i < matrix.length; i++) {
        for (j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                if (j == 0) {
                    col0 = true;
                } else {
                    matrix[0][j] = 0;
                }
            }
        }
    }
    for (i = matrix.length - 1; i >= 0; i--) {
        for (j = 1; j < matrix[0].length; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    if (col0) {
        for (i = 0; i < matrix.length; i++) {
            matrix[i][0] = 0;
        }
    }
}

75.颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

链接：https://leetcode-cn.com/problems/sort-colors

public class Problem_0075_SortColors {
    public static void sortColors(int[] nums) {
        int less = -1;
        int more = nums.length;
        int index = 0;
        while (index < more) {
            if (nums[index] == 1) {
                index++;
            } else if (nums[index] == 0) {
                swap(nums, index++, ++less);
            } else {
                swap(nums, index, --more);
            }
        }
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

76.最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

链接：https://leetcode-cn.com/problems/minimum-window-substring

public class Problem_0076_MinimumWindowSubstring {

    public static String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        char[] str = s.toCharArray();
        char[] target = t.toCharArray();
        int[] map = new int[256];
        for (char cha : target) {
            map[cha]++;
        }
        int all = target.length;
        int L = 0;
        int R = 0;
        // -1(从来没找到过合法的)
        int minLen = -1;
        int ansl = -1;
        int ansr = -1;
        // [L..R)   [0,0)  R
        while (R != str.length) {
            map[str[R]]--;
            if (map[str[R]] >= 0) {
                all--;
            }
            if (all == 0) {
                while (map[str[L]] < 0) {
                    map[str[L++]]++;
                }
                if (minLen == -1 || minLen > R - L + 1) {
                    minLen = R - L + 1;
                    ansl = L;
                    ansr = R;
                }
                all++;		
                map[str[L++]]++;
            }
            R++;
        }
        return minLen == -1 ? "" : s.substring(ansl, ansr + 1);
    }
}

78.子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

链接：https://leetcode-cn.com/problems/subsets/

public class Problem_0078_Subsets {

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        process(nums, 0, path, ans);
        return ans;
    }

    // 当前来到index位置，做决定，1）不要当前位置的数   2）要当前位置的数
    // 如果要当前位置的数，把该数字，放入到path中去
    // 如果不要当前位置的数，不把该数字，放入到path中去
    public static void process(int nums[], int index, LinkedList<Integer> path, List<List<Integer>> ans) {
        if (index == nums.length) {
            ans.add(copy(path));
        } else {
            process(nums, index + 1, path, ans);
            path.addLast(nums[index]);
            process(nums, index + 1, path, ans);
            path.removeLast();
        }
    }

    public static ArrayList<Integer> copy(LinkedList<Integer> path) {
        ArrayList<Integer> ans = new ArrayList<>();
        for (Integer num : path) {
            ans.add(num);
        }
        return ans;
    }
}

79.单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

链接：https://leetcode-cn.com/problems/word-search

public class Problem_0079_WordSearch {

    public static boolean exist(char[][] board, String word) {
        char[] w = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (process(board, i, j, w, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    // 目前到达了b[i][j]，word[k....]
    // 从b[i][j]出发，能不能搞定word[k....]  true  false
    public static boolean process(char[][] b, int i, int j, char[] w, int k) {
        if(k == w.length) {
            return true;
        }
        // k 有字符
        if (i < 0 || i == b.length || j < 0 || j == b[0].length) {
            return false;
        }
        if (b[i][j] != w[k]) {
            return false;
        }
        char tmp = b[i][j];
        b[i][j] = 0;
        boolean ans =  process(b, i - 1, j, w, k + 1) 
            || process(b, i + 1, j, w, k + 1) 
            || process(b, i, j - 1, w, k + 1)
            || process(b, i, j + 1, w, k + 1);
        b[i][j] = tmp;
        return ans;
    }
}

84.柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

public class Problem_0084_LargestRectangleInHistogram {

    public static int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int maxArea = 0;
        // 只放下标
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
                int j = stack.pop();
                int k = stack.isEmpty() ? -1 : stack.peek();
                int curArea = (i - k - 1) * height[j];
                maxArea = Math.max(maxArea, curArea);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int curArea = (height.length - k - 1) * height[j];
            maxArea = Math.max(maxArea, curArea);
        }
        return maxArea;
    }
}

88.合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

链接：https://leetcode-cn.com/problems/merge-sorted-array

public class Problem_0088_MergeSortedArray {

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = nums1.length;
        while (m > 0 && n > 0) {
            if (nums1[m - 1] >= nums2[n - 1]) {
                nums1[--index] = nums1[--m];
            } else {
                nums1[--index] = nums2[--n];
            }
        }
        while (m > 0) {
            nums1[--index] = nums1[--m];
        }
        while (n > 0) {
            nums1[--index] = nums2[--n];
        }
    }
}

91.解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。
例如，"111" 可以将 "1" 中的每个 "1" 映射为 "A" ，从而得到 "AAA" ，或者可以将 "11" 和 "1"（分别为 "K" 和 "A" ）映射为 "KA" 。
注意，"06" 不能映射为 "F" ，因为 "6" 和 "06" 不同。
给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。

链接：https://leetcode-cn.com/problems/decode-ways

public static int numDecodings2(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    char[] str = s.toCharArray();
    int N = str.length;
    // dp[i] -> process(str, index)返回值 index 0 ~ N
    int[] dp = new int[N + 1];
    dp[N] = 1;

    // dp依次填好 dp[i] dp[i+1] dp[i+2]
    for (int i = N - 1; i >= 0; i--) {
        if (str[i] != '0') {
            dp[i] = dp[i + 1];
            if (i + 1 == str.length) {
                continue;
            }
            int num = (str[i] - '0') * 10 + str[i + 1] - '0';
            if (num <= 26) {
                dp[i] += dp[i + 2];
            }
        }
    }
    return dp[0];
}

94.二叉树的中序遍历

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

链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

public class Problem_0094_BinaryTreeInorderTraversal {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            ans.add(cur.val);
            cur = cur.right;
        }
        return ans;
    }
}

98.验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

链接：https://leetcode-cn.com/problems/validate-binary-search-tree

public class Problem_0098_ValidateBinarySearchTree {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        TreeNode cur = root;
        TreeNode mostRight = null;
        Integer pre = null;
        boolean ans = true;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            if (pre != null && pre >= cur.val) {
                ans = false;
            }
            pre = cur.val;
            cur = cur.right;
        }
        return ans;
    }
}

101.对称二叉树

给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的

链接：https://leetcode-cn.com/problems/symmetric-tree/

public class Problem_0101_SymmetricTree {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    // 一棵树是原始树  head1
    // 另一棵是翻面树  head2
    public static boolean isMirror(TreeNode head1, TreeNode head2) {
        if (head1 == null && head2 == null) {
            return true;
        }
        if (head1 != null && head2 != null) {
            return head1.val == head2.val 
                && isMirror(head1.left, head2.right) 
                && isMirror(head1.right, head2.left);
        }
        // 一个为空，一个不为空  false
        return false;
    }
}

102.二叉树的层序遍历

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

链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

public class Problem_0102_BinaryTreeLevelOrderTraversal {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        int size = 0;
        while(!deque.isEmpty()) {
            size = deque.size();
            List<Integer> curLevel = new ArrayList<>();
            for(int i = 0 ; i< size;i++) {
                TreeNode cur = deque.pollLast();
                curLevel.add(cur.val);
                if(cur.left != null) {
                    deque.addFirst(cur.left);
                }
                if(cur.right != null) {
                    deque.addFirst(cur.right);
                }
            }
            ans.add(curLevel);
        }
        return ans;
    }
}

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

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

链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

public class Problem_0103_BinaryTreeZigzagLevelOrderTraversal {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        int size = 0;
        boolean isHead = true;
        while (!deque.isEmpty()) {
            size = deque.size();
            List<Integer> curLevel = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = isHead ? deque.pollFirst() : deque.pollLast();
                curLevel.add(cur.val);
                if(isHead) {
                    if (cur.left != null) {
                        deque.addLast(cur.left);
                    }
                    if (cur.right != null) {
                        deque.addLast(cur.right);
                    }
                }else {
                    if (cur.right != null) {
                        deque.addFirst(cur.right);
                    }
                    if (cur.left != null) {
                        deque.addFirst(cur.left);
                    }
                }
            }
            ans.add(curLevel);
            isHead = !isHead;
        }
        return ans;
    }
}

104.二叉树最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

public class Problem_0104_MaximumDepthOfBinaryTree {

    /*
	 * 注意最小高度比这个复杂，要额外小心判断空
	 * */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

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

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

public class Problem_0105_ConstructBinaryTreeFromPreorderAndInorderTraversal {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
    }

    public static TreeNode f(int[] pre, int L1, int R1, int[] in, int L2, int R2, HashMap<Integer, Integer> map) {
        if (L1 > R1) {
            return null;
        }
        TreeNode head = new TreeNode(pre[L1]);
        if (L1 == R1) {
            return head;
        }
        int findIndex = map.get(pre[L1]);
        head.left = f(pre, L1 + 1, L1 + findIndex - L2, in, L2, findIndex - 1, map);
        head.right = f(pre, L1 + findIndex - L2 + 1, R1, in, findIndex + 1, R2, map);
        return head;
    }

}

108.将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

public class Problem_0108_ConvertSortedArrayToBinarySearchTree {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return process(nums, 0, nums.length - 1);
    }

    public static TreeNode process(int[] nums, int L, int R) {
        if (L > R) {
            return null;
        }
        if (L == R) {
            return new TreeNode(nums[L]);
        }
        int M = (L + R) / 2;
        TreeNode head = new TreeNode(nums[M]);
        head.left = process(nums, L, M - 1);
        head.right = process(nums, M + 1, R);
        return head;
    }
}

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

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node

public class Problem_0116_PopulatingNextRightPointersInEachNode {

  public static class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
  }

  public static class MyQueue {
    public Node head;
    public Node tail;
    public int size;

    public MyQueue() {
      head = null;
      tail = null;
      size = 0;
    }

    public boolean isEmpty() {
      return size == 0;
    }

    public void offer(Node cur) {
      size++;
      if (head == null) {
        head = cur;
        tail = cur;
      } else {
        tail.next = cur;
        tail = cur;
      }
    }

    public Node poll() {
      size--;
      Node ans = head;
      head = head.next;
      ans.next = null;
      return ans;
    }

  }

  public static Node connect(Node root) {
    if (root == null) {
      return root;
    }
    MyQueue queue = new MyQueue();
    queue.offer(root);
    while (!queue.isEmpty()) {
      // 第一个弹出的节点
      Node pre = null;
      int size = queue.size;
      for (int i = 0; i < size; i++) {
        Node cur = queue.poll();
        if (cur.left != null) {
          queue.offer(cur.left);
        }
        if (cur.right != null) {
          queue.offer(cur.right);
        }
        if (pre != null) {
          pre.next = cur;
        }
        pre = cur;
      }
    }
    return root;
  }
}

118.杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

链接：https://leetcode-cn.com/problems/pascals-triangle/

public class Problem_0118_PascalTriangle {

    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            ans.add(new ArrayList<>());
            ans.get(i).add(1);
        }
        for (int i = 1; i < numRows; i++) {
            for (int j = 1; j < i; j++) {
                ans.get(i).add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
            }
            ans.get(i).add(1);
        }
        return ans;
    }
}

121.买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

public class Problem_0121_BestTimeToBuyAndSellStock {

    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        // 0...i 最小值
        int min = prices[0];
        int ans = 0;
        for (int i = 0; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            ans = Math.max(ans, prices[i] - min);
        }
        return ans;
    }
}

122.买卖股票的最佳时机II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii

public class Problem_0122_BestTimeToBuyAndSellStockII {

    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            ans += Math.max(prices[i] - prices[i-1], 0);
        }
        return ans;
    }
}

123.买卖股票的最佳时机III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii

public class Problem_0123_BestTimeToBuyAndSellStockIII {

    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int ans = 0;
        int doneOnceMinusBuyMax = -prices[0];
        int doneOnceMax = 0;// 0 : [0] - [0]
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            ans = Math.max(ans, doneOnceMinusBuyMax + prices[i]);
            min = Math.min(min, prices[i]);
            doneOnceMax = Math.max(doneOnceMax, prices[i] - min);
            doneOnceMinusBuyMax = Math.max(doneOnceMinusBuyMax, doneOnceMax - prices[i]);
        }
        return ans;
    }
}

188.买卖股票的最佳时机IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv

public class Problem_0188_BestTimeToBuyAndSellStockIV {

  public static int maxProfit1(int K, int[] arr) {
    if (arr == null || arr.length == 0) {
      return 0;
    }
    int N = arr.length;
    if (K >= N / 2) {
      return allTrans(arr);
    }
    int[][] dp = new int[N][K + 1];
    for (int i = 1; i < N; i++) {
      for (int j = 1; j <= K; j++) {
        dp[i][j] = dp[i - 1][j];
                //枚举行为
        for (int p = 0; p <= i; p++) {
          dp[i][j] = Math.max(dp[p][j - 1] + arr[i] - arr[p], dp[i][j]);
        }
      }
    }
    return dp[N - 1][K];
  }
  
    //斜率优化
  public static int maxProfit2(int K, int[] prices) {
    if (prices == null || prices.length == 0) {
      return 0;
    }
    int N = prices.length;
    if (K >= N / 2) {
      return allTrans(prices);
    }
    int[][] dp = new int[K + 1][N];
    int ans = 0;
    for (int j = 1; j <= K; j++) {
      int pre = dp[j][0];
      int best = pre - prices[0];
      for (int i = 1; i < N; i++) {
        pre = dp[j - 1][i];
        dp[j][i] = Math.max(dp[j][i - 1], prices[i] + best);
        best = Math.max(best, pre - prices[i]);
        ans = Math.max(dp[j][i], ans);
      }
    }
    return ans;
  }

  public static int allTrans(int[] prices) {
    int ans = 0;
    for (int i = 1; i < prices.length; i++) {
      ans += Math.max(prices[i] - prices[i - 1], 0);
    }
    return ans;
  }
}

309.买卖股票的最佳时机V

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

public class Problem_0309_BestTimeToBuyAndSellStockWithCooldown {

    // 该方法是对的，提交之后大量的测试用例通过，最后几个会超时
    // 如果把这个方法改成动态规划，是可以通过的，但这个尝试不是最优解
    public static int maxProfit1(int[] prices) {
        return process1(prices, false, 0, 0);
    }

    // buy == false 目前可以交易，而且当前没有购买行为
    // buy == true 已经买了，买入价buyPrices，待卖出
    public static int process1(int[] prices, boolean buy, int index, int buyPrices) {
        if (index >= prices.length) {
            return 0;
        }
        if (buy) {
            int noSell = process1(prices, true, index + 1, buyPrices);
            int yesSell = prices[index] - buyPrices + process1(prices, false, index + 2, 0);
            return Math.max(noSell, yesSell);
        } else {
            int noBuy = process1(prices, false, index + 1, 0);
            int yesBuy = process1(prices, true, index + 1, prices[index]);
            return Math.max(noBuy, yesBuy);
        }
    }

    // 最优尝试如下：
    // buy[i] : 在0...i范围上，最后一次操作是buy动作，
    // 这最后一次操作有可能发生在i位置，也可能发生在i之前
    // buy[i]值的含义是：max{ 所有可能性[之前交易获得的最大收益 - 最后buy动作的收购价格] }
    // 比如：arr[0...i]假设为[1,3,4,6,2,7,1...i之后的数字不用管]
    // 什么叫，所有可能性[之前交易获得的最大收益 - 最后buy动作的收购价格]？
    // 比如其中一种可能性：
    // 假设最后一次buy动作发生在2这个数的时候，那么之前的交易只能在[1,3,4]上结束，因为6要cooldown的，
    // 此时最大收益是多少呢？是4-1==3。那么，之前交易获得的最大收益 - 最后buy动作的收购价格 = 3 - 2 = 1
    // 另一种可能性：
    // 再比如最后一次buy动作发生在最后的1这个数的时候，那么之前的交易只能在[1,3,4,6,2]上发生，因为7要cooldown的，
    // 此时最大收益是多少呢？是6-1==5。那么，之前交易获得的最大收益 - 最后buy动作的收购价格 = 5 - 1 = 4
    // 除了上面两种可能性之外，还有很多可能性，你可以假设每个数字都是最后buy动作的时候，
    // 所有可能性中，(之前交易获得的最大收益 - 最后buy动作的收购价格)的最大值，就是buy[i]的含义
    // 为啥buy[i]要算之前的最大收益 - 最后一次收购价格？尤其是最后为什么要减这么一下？
    // 因为这样一来，当你之后以X价格做成一笔交易的时候，当前最好的总收益直接就是 X + buy[i]了
    //
    // sell[i] :0...i范围上，最后一次操作是sell动作，这最后一次操作有可能发生在i位置，也可能发生在之前
    // sell[i]值的含义：0...i范围上，最后一次动作是sell的情况下，最好的收益
    //
    // 于是通过分析，能得到以下的转移方程：
    // buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i])
    // 如果i位置没有发生buy行为，说明有没有i位置都一样，那么buy[i] = buy[i-1]，这显而易见
    // 如果i位置发生了buy行为, 那么buy[i] = sell[i - 2] - prices[i]，
    // 因为你想在i位置买的话，你必须保证之前交易行为发生在0...i-2上，
    // 因为如果i-1位置有可能参与交易的话，i位置就要cooldown了，
    // 而且之前交易行为必须以sell结束，你才能buy，而且要保证之前交易尽可能得到最好的利润，
    // 这正好是sell[i - 2]所代表的含义，并且根据buy[i]的定义，最后一定要 - prices[i]
    //
    // sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i])
    // 如果i位置没有发生sell行为，那么sell[i] = sell[i-1]，这显而易见
    // 如果i位置发生了sell行为，那么我们一定要找到 {之前获得尽可能好的收益 - 最后一次的收购价格尽可能低}，
    // 而这正好是buy[i - 1]的含义！之前所有的"尽可能"中，最好的一个！
    public static int maxProfit2(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int N = prices.length;
        int[] buy = new int[N];
        int[] sell = new int[N];
        buy[1] = Math.max(-prices[0], -prices[1]);
        sell[1] = Math.max(0, prices[1] - prices[0]);
        for (int i = 2; i < N; i++) {
            buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
        }
        return sell[N - 1];
    }

    // 最优解就是方法2的空间优化而已
    public static int maxProfit3(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int buy1 = Math.max(-prices[0], -prices[1]);
        int sell1 = Math.max(0, prices[1] - prices[0]);
        int sell2 = 0;
        for (int i = 2; i < prices.length; i++) {
            int tmp = sell1;
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy1 = Math.max(buy1, sell2 - prices[i]);
            sell2 = tmp;
        }
        return sell1;
    }
}

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

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

public class Problem_0124_BinaryTreeMaximumPathSum {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    public static int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return process(root).maxPathSum;
    }

    public static class Info {
        public int maxPathSum;
        public int maxPathSumFromHead;

        public Info(int path, int head) {
            maxPathSum = path;
            maxPathSumFromHead = head;
        }
    }

    public static Info process(TreeNode x) {
        if (x == null) {
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int p1 = Integer.MIN_VALUE;
        if (leftInfo != null) {
            p1 = leftInfo.maxPathSum;
        }
        int p2 = Integer.MIN_VALUE;
        if (rightInfo != null) {
            p2 = rightInfo.maxPathSum;
        }
        int p3 = x.val;
        int p4 = Integer.MIN_VALUE;
        if (leftInfo != null) {
            p4 = x.val + leftInfo.maxPathSumFromHead;
        }
        int p5 = Integer.MIN_VALUE;
        if (rightInfo != null) {
            p5 = x.val + rightInfo.maxPathSumFromHead;
        }
        int p6 = Integer.MIN_VALUE;
        if (leftInfo != null && rightInfo != null) {
            p6 = x.val + leftInfo.maxPathSumFromHead + rightInfo.maxPathSumFromHead;
        }
        int maxSum = Math.max(Math.max(Math.max(p1, p2), Math.max(p3, p4)), Math.max(p5, p6));
        int maxSumFromHead = Math.max(p3, Math.max(p4, p5));
        return new Info(maxSum, maxSumFromHead);
    }
}

125.验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

连接：https://leetcode-cn.com/problems/valid-palindrome/

public class Problem_0125_ValidPalindrome {
    public static boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        char[] str = s.toCharArray();
        int L = 0;
        int R = str.length - 1;
        while (L < R) {
            if (validChar(str[L]) && validChar(str[R])) {
                if (!equal(str[L], str[R])) {
                    return false;
                }
                L++;
                R--;
            } else {
                L += validChar(str[L]) ? 0 : 1;
                R -= validChar(str[R]) ? 0 : 1;
            }
        }
        return true;
    }

    public static boolean validChar(char c) {
        return isLetter(c) || isNumber(c);
    }

    public static boolean equal(char c1, char c2) {
        if (isNumber(c1) || isNumber(c2)) {
            return c1 == c2;
        }
        return (c1 == c2) || (Math.max(c1, c2) - Math.min(c1, c2) == 32);
    }

    public static boolean isLetter(char c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    }

    public static boolean isNumber(char c) {
        return (c >= '0' && c <= '9');
    }
}

127.单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

链接：https://leetcode-cn.com/problems/word-ladder

public class Problem_0127_WordLadder {

    public static int ladderLength1(String start, String to, List<String> list) {
        list.add(start);
        HashMap<String, ArrayList<String>> nexts = getNexts(list);
        HashMap<String, Integer> distanceMap = new HashMap<>();
        distanceMap.put(start, 1);
        HashSet<String> set = new HashSet<>();
        set.add(start);
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            Integer distance = distanceMap.get(cur);
            for (String next : nexts.get(cur)) {
                if (next.equals(to)) {
                    return distance + 1;
                }
                if (!set.contains(next)) {
                    set.add(next);
                    queue.add(next);
                    distanceMap.put(next, distance + 1);
                }
            }

        }
        return 0;
    }

    public static HashMap<String, ArrayList<String>> getNexts(List<String> words) {
        HashSet<String> dict = new HashSet<>(words);
        HashMap<String, ArrayList<String>> nexts = new HashMap<>();
        for (int i = 0; i < words.size(); i++) {
            nexts.put(words.get(i), getNext(words.get(i), dict));
        }
        return nexts;
    }

    // 应该根据具体数据状况决定用什么来找邻居
    // 1)如果字符串长度比较短，字符串数量比较多，以下方法适合
    // 2)如果字符串长度比较长，字符串数量比较少，以下方法不适合
    public static ArrayList<String> getNext(String word, HashSet<String> dict) {
        ArrayList<String> res = new ArrayList<String>();
        char[] chs = word.toCharArray();
        for (char cur = 'a'; cur <= 'z'; cur++) {
            for (int i = 0; i < chs.length; i++) {
                if (chs[i] != cur) {
                    char tmp = chs[i];
                    chs[i] = cur;
                    if (dict.contains(String.valueOf(chs))) {
                        res.add(String.valueOf(chs));
                    }
                    chs[i] = tmp;
                }
            }
        }
        return res;
    }

    public static int ladderLength2(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return 0;
        }
        HashSet<String> startSet = new HashSet<>();
        HashSet<String> endSet = new HashSet<>();
        HashSet<String> visit = new HashSet<>();
        startSet.add(beginWord);
        endSet.add(endWord);
        for (int len = 2; !startSet.isEmpty(); len++) {
            HashSet<String> nextSet = new HashSet<>();
            for (String w : startSet) {
                for (int j = 0; j < w.length(); j++) {
                    char[] ch = w.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c != w.charAt(j)) {
                            ch[j] = c;
                            String next = String.valueOf(ch);
                            if (endSet.contains(next)) {
                                return len;
                            }
                            if (dict.contains(next) && !visit.contains(next)) {
                                nextSet.add(next);
                                visit.add(next);
                            }
                        }
                    }
                }
            }
            startSet = (nextSet.size() < endSet.size()) ? nextSet : endSet;
            endSet = (startSet == nextSet) ? endSet : nextSet;
        }
        return 0;
    }
}

128.最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

链接：https://leetcode-cn.com/problems/longest-consecutive-sequence

public class Problem_0128_LongestConsecutiveSequence {

    public static int longestConsecutive(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = 0;
        for (int num : nums) {
            if (!map.containsKey(num)) {
                map.put(num, 1);
                int preLen = map.containsKey(num - 1) ? map.get(num - 1) : 0;
                int posLen = map.containsKey(num + 1) ? map.get(num + 1) : 0;
                int all = preLen + posLen + 1;
                map.put(num - preLen, all);
                map.put(num + posLen, all);
                len = Math.max(len, all);
            }
        }
        return len;
    }
}

130.被围绕的区域

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

链接：https://leetcode-cn.com/problems/surrounded-regions/

public class Problem_0130_SurroundedRegions {

    // 从边界开始感染的方法，比第一种方法更好
    public static void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return;
        }
        int N = board.length;
        int M = board[0].length;
        for (int j = 0; j < M; j++) {
            if (board[0][j] == 'O') {
                free(board, 0, j);
            }
            if (board[N - 1][j] == 'O') {
                free(board, N - 1, j);
            }
        }
        for (int i = 1; i < N - 1; i++) {
            if (board[i][0] == 'O') {
                free(board, i, 0);
            }
            if (board[i][M - 1] == 'O') {
                free(board, i, M - 1);
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == 'F') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public static void free(char[][] board, int i, int j) {
        if (i < 0 || i == board.length || j < 0 || j == board[0].length || board[i][j] != 'O') {
            return;
        }
        board[i][j] = 'F';
        free(board, i + 1, j);
        free(board, i - 1, j);
        free(board, i, j + 1);
        free(board, i, j - 1);
    }
}

131.分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。

链接：https://leetcode-cn.com/problems/palindrome-partitioning/

public class Problem_0131_PalindromePartitioning {

  public static List<List<String>> partition(String s) {
    // dp[L][R] -> 是不是回文
    boolean[][] dp = getdp(s.toCharArray());
    LinkedList<String> path = new LinkedList<>();
    List<List<String>> ans = new ArrayList<>();
    process(s, 0, path, dp, ans);
    return ans;
  }

  public static boolean[][] getdp(char[] str) {
    int N = str.length;
    boolean[][] dp = new boolean[N][N];
    for (int i = 0; i < N - 1; i++) {
      dp[i][i] = true;
      dp[i][i + 1] = str[i] == str[i + 1];
    }
    dp[N - 1][N - 1] = true;
    for (int j = 2; j < N; j++) {
      int row = 0;
      int col = j;
      while (row < N && col < N) {
        dp[row][col] = str[row] == str[col] && dp[row + 1][col - 1];
        row++;
        col++;
      }
    }
    return dp;
  }

  // s 字符串
  // s[0...index-1] 已经做过的决定，放入了path中
  // 在index开始做属于这个位置的决定，
  // index == s.len  path之前做的决定（一种分割方法），放进总答案ans里
  public static void process(String s, int index, LinkedList<String> path, 
			boolean[][] dp, List<List<String>> ans) {
    if (index == s.length()) {
      ans.add(copy(path));
    } else {
      for (int end = index; end < s.length(); end++) {
        // index..index   
        // index..index+1
        // index..index+2
        // index..end
        if (dp[index][end]) {
          path.addLast(s.substring(index, end + 1));
          process(s, end + 1, path, dp, ans);
          path.pollLast();
        }
      }
    }
  }

  public static List<String> copy(List<String> path) {
    List<String> ans = new ArrayList<>();
    for (String p : path) {
      ans.add(p);
    }
    return ans;
  }
}

134.加油站

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

链接：https://leetcode-cn.com/problems/gas-station/

/*
通俗做法：计算一个累加和数组，二倍长度，累加两遍，求每个位置的值，只需要在二倍长度里计算，减去累加和数组的[i-1]的值，即可。
*/
public class Problem_0134_GasStation {

    /*
	 * 这个方法的时间复杂度O(N)，额外空间复杂度O(N)
	 */
    public static int canCompleteCircuit1(int[] gas, int[] cost) {
        int N = gas.length;
        int init = -1;
        for (int i = 0; i < N; i++) {
            gas[i] -= cost[i];
            if (gas[i] >= 0) {
                init = init == -1 ? i : init;
            }
        }
        if (init == -1) {
            return -1;
        }
        int[] all = new int[N << 1];
        int index = 0;
        all[index++] = gas[init];
        int start = (init < N - 1) ? (init + 1) : 0;
        while (start != init) {
            all[index++] = gas[start];
            start = (start < N - 1) ? (start + 1) : 0;
        }
        for (int i = 0; i < N; i++) {
            all[i + N] = all[i];
        }
        for (int i = 1; i < all.length; i++) {
            all[i] = all[i] + all[i - 1];
        }
        LinkedList<Integer> minQ = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            while (!minQ.isEmpty() && all[minQ.peekLast()] >= all[i]) {
                minQ.pollLast();
            }
            minQ.add(i);
        }
        if (all[minQ.peekFirst()] >= 0) {
            return init;
        }
        for (int i = 0; i < N; i++) {
            while (!minQ.isEmpty() && all[minQ.peekLast()] >= all[i + N]) {
                minQ.pollLast();
            }
            minQ.add(i + N);
            if (minQ.peekFirst() == i) {
                minQ.peekFirst();
            }
            if (all[minQ.peekFirst()] - all[i] >= 0) {
                return i + init + 1;
            }
        }
        return -1;
    }

    /*
	 * 这个方法的时间复杂度O(N)，额外空间复杂度O(1)
	 * 训练营讲了
	 */
    public static int canCompleteCircuit2(int[] oil, int[] dis) {
        int init = changeDisArrayGetInit(oil, dis);
        if (init != -1) {
            int ans = enlargeArea(dis, init);
            if (ans != -1) {
                return ans;
            }
        }
        return -1;
    }

    public static int changeDisArrayGetInit(int[] oil, int[] dis) {
        int init = -1;
        for (int i = 0; i < dis.length; i++) {
            dis[i] = oil[i] - dis[i];
            if (dis[i] >= 0) {
                init = i;
            }
        }
        return init;
    }

    public static int enlargeArea(int[] dis, int init) {
        int ans = -1;
        int start = init;
        int end = nextIndex(init, dis.length);
        int need = 0;
        int rest = 0;
        do {
            // 当前来到的start已经在连通区域中，可以确定后续的开始点一定无法转完一圈
            if (start != init && start == lastIndex(end, dis.length)) {
                break;
            }
            // 当前来到的start不在连通区域中，就扩充连通区域
            if (dis[start] < need) { // 当前start无法接到连通区的头部
                need -= dis[start];
            } else { // 当前start可以接到连通区的头部，开始扩充连通区域的尾巴
                rest += dis[start] - need;
                need = 0;
                while (rest >= 0 && end != start) {
                    rest += dis[end];
                    end = nextIndex(end, dis.length);
                }
                // 如果连通区域已经覆盖整个环，当前的start是良好出发点，进入2阶段
                if (rest >= 0) {
                    ans = Math.min(start, connectGood(dis, lastIndex(start, dis.length), init));
                    break;
                }
            }
            start = lastIndex(start, dis.length);
        } while (start != init);
        return ans;
    }

    // 已知start的next方向上有一个良好出发点
    // start如果可以达到这个良好出发点，那么从start出发一定可以转一圈
    public static int connectGood(int[] dis, int start, int init) {
        int ans = dis.length;
        int need = 0;
        while (start != init) {
            if (dis[start] < need) {
                need -= dis[start];
            } else {
                ans = Math.min(ans, start);
                need = 0;
            }
            start = lastIndex(start, dis.length);
        }
        return ans;
    }

    public static int lastIndex(int index, int size) {
        return index == 0 ? (size - 1) : index - 1;
    }

    public static int nextIndex(int index, int size) {
        return index == size - 1 ? 0 : (index + 1);
    }
}

136.只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

链接：https://leetcode-cn.com/problems/single-number/

public class Problem_0136_SingleNumber {

  public static int singleNumber(int[] nums) {
    int eor = 0;
    for (int num : nums) {
      eor ^= num;
    }
    return eor;
  }
}

138.复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。 
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。

链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer

public class Problem_0138_CopyListWithRandomPointer {

    public static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next = null;
        // 1 -> 2 -> 3 -> null
        // 1 -> 1' -> 2 -> 2' -> 3 -> 3'
        while (cur != null) {
            next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        Node copy = null;
        // 1 1' 2 2' 3 3'
        // 依次设置 1' 2' 3' random指针
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            copy.random = cur.random != null ? cur.random.next : null;
            cur = next;
        }
        Node res = head.next;
        cur = head;
        // 老 新 混在一起，next方向上，random正确
        // next方向上，把新老链表分离
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            cur.next = next;
            copy.next = next != null ? next.next : null;
            cur = next;
        }
        return res;
    }
}

139.单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

链接：https://leetcode-cn.com/problems/word-break

public class Problem_0139_WordBreak {

    public static boolean wordBreak(String s, List<String> wordDict) {
        Node root = new Node();
        for (String str : wordDict) {
            char[] chs = str.toCharArray();
            Node node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new Node();
                }
                node = node.nexts[index];
            }
            node.end = true;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        boolean[] dp = new boolean[N + 1];
        dp[N] = true;
        for (int i = N - 1; i >= 0; i--) {
            Node cur = root;
            for (int end = i; end < N; end++) {
                int path = str[end] - 'a';
                if (cur.nexts[path] == null) {
                    break;
                }
                cur = cur.nexts[path];
                if (cur.end && dp[end + 1]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }

    public static boolean wordBreak2(String s, List<String> wordDict) {
        return process(s, 0, new HashSet<>(wordDict)) != 0;
    }

    // s[0......index-1]这一段，已经分解过了，不用在操心
    // s[index.....] 这一段字符串，能够被分解的方法数，返回
    public static int process(String s, int index, HashSet<String> wordDict) {
        if (index == s.length()) {
            return 1;
        }
        // index没到最后
        // index...index
        // index...index+1
        // index....index+2
        // index....end
        int ways = 0;
        for (int end = index; end < s.length(); end++) {
            // s[index....end]
            String pre = s.substring(index, end + 1);
            if (wordDict.contains(pre)) {
                ways += process(s, end + 1, wordDict);
            }
        }
        return ways;
    }

    public static boolean wordBreak3(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        int N = s.length();
        int[] dp = new int[N + 1];
        // dp[i] = process(s, i, set)的返回值
        dp[N] = 1;
        for (int index = N - 1; index >= 0; index--) {
            int ways = 0;
            for (int end = index; end < s.length(); end++) {
                // s[index....end]
                String pre = s.substring(index, end + 1);
                if (set.contains(pre)) {
                    ways += dp[end + 1];
                }
            }
            dp[index] = ways;
        }
        return dp[0] != 0;
    }

    public static class Node {
        public boolean end;
        public Node[] nexts;

        public Node() {
            end = false;
            nexts = new Node[26];
        }
    }

    public static boolean wordBreak4(String s, List<String> wordDict) {
        Node root = new Node();
        for (String str : wordDict) {
            char[] chs = str.toCharArray();
            Node node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new Node();
                }
                node = node.nexts[index];
            }
            node.end = true;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            Node cur = root;
            for (int end = i; end < N; end++) {
                cur = cur.nexts[str[end] - 'a'];
                if (cur == null) {
                    break;
                }
                if (cur.end) {
                    dp[i] += dp[end + 1];
                }
            }
        }
        return dp[0] != 0;
    }

}

140.单词拆分II

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

链接：https://leetcode-cn.com/problems/word-break-ii

public class Problem_0140_WordBreakII {

    public static class Node {
        public String path;
        public boolean end;
        public Node[] nexts;

        public Node() {
            path = null;
            end = false;
            nexts = new Node[26];
        }
    }

    public static List<String> wordBreak(String s, List<String> wordDict) {
        char[] str = s.toCharArray();
        Node root = gettrie(wordDict);
        boolean[] dp = getdp(s, root);
        ArrayList<String> path = new ArrayList<>();
        List<String> ans = new ArrayList<>();
        process(str, 0, root, dp, path, ans);
        return ans;
    }

    public static void process(char[] str, int index, Node root, boolean[] dp, ArrayList<String> path,
                               List<String> ans) {
        if (index == str.length) {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < path.size() - 1; i++) {
                builder.append(path.get(i) + " ");
            }
            builder.append(path.get(path.size() - 1));
            ans.add(builder.toString());
        } else {
            Node cur = root;
            for (int end = index; end < str.length; end++) {
                int road = str[end] - 'a';
                if (cur.nexts[road] == null) {
                    break;
                }
                cur = cur.nexts[road];
                if (cur.end && dp[end + 1]) {
                    path.add(cur.path);
                    process(str, end + 1, root, dp, path, ans);
                    path.remove(path.size() - 1);
                }
            }
        }
    }

    public static Node gettrie(List<String> wordDict) {
        Node root = new Node();
        for (String str : wordDict) {
            char[] chs = str.toCharArray();
            Node node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new Node();
                }
                node = node.nexts[index];
            }
            node.path = str;
            node.end = true;
        }
        return root;
    }

    public static boolean[] getdp(String s, Node root) {
        char[] str = s.toCharArray();
        int N = str.length;
        boolean[] dp = new boolean[N + 1];
        dp[N] = true;
        for (int i = N - 1; i >= 0; i--) {
            Node cur = root;
            for (int end = i; end < N; end++) {
                int path = str[end] - 'a';
                if (cur.nexts[path] == null) {
                    break;
                }
                cur = cur.nexts[path];
                if (cur.end && dp[end + 1]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp;
    }
}

141.环形链表

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗

链接：https://leetcode-cn.com/problems/linked-list-cycle/

public class Problem_0141_LinkedListCycle {

    public static class ListNode {
        int val;
        ListNode next;
    }

    public static boolean hasCycle(ListNode head) {
        return getFirstLoopNode(head) != null;
    }

    public static ListNode getFirstLoopNode(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while (slow != fast) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

146.LRU缓存机制

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

链接：https://leetcode-cn.com/problems/lru-cache

public class Problem_0146_LRUCache {

    private MyCache<Integer, Integer> cache;

    public Problem_0146_LRUCache(int capacity) {
        cache = new MyCache<>(capacity);
    }

    public int get(int key) {
        Integer ans = cache.get(key);
        return ans == null ? -1 : ans;
    }

    public void put(int key, int value) {
        cache.set(key, value);
    }

    public static class Node<K, V> {
        public K key;
        public V value;
        public Node<K, V> last;
        public Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public static class NodeDoubleLinkedList<K, V> {
        private Node<K, V> head;
        private Node<K, V> tail;

        public NodeDoubleLinkedList() {
            head = null;
            tail = null;
        }

        public void addNode(Node<K, V> newNode) {
            if (newNode == null) {
                return;
            }
            if (head == null) {
                head = newNode;
                tail = newNode;
            } else {
                tail.next = newNode;
                newNode.last = tail;
                tail = newNode;
            }
        }

        public void moveNodeToTail(Node<K, V> node) {
            if (tail == node) {
                return;
            }
            // node 不是尾巴
            if (head == node) {
                head = node.next;
                head.last = null;
            } else {
                node.last.next = node.next;
                node.next.last = node.last;
            }
            node.last = tail;
            node.next = null;
            tail.next = node;
            tail = node;
        }

        public Node<K, V> removeHead() {
            if (head == null) {
                return null;
            }
            Node<K, V> res = head;
            if (head == tail) { // 链表中只有一个节点的时候
                head = null;
                tail = null;
            } else {
                head = res.next;
                res.next = null;
                head.last = null;
            }
            return res;
        }

    }

    public static class MyCache<K, V> {
        private HashMap<K, Node<K, V>> keyNodeMap;
        private NodeDoubleLinkedList<K, V> nodeList;
        private final int capacity;

        public MyCache(int cap) {
            if (cap < 1) {
                throw new RuntimeException("should be more than 0.");
            }
            keyNodeMap = new HashMap<K, Node<K, V>>();
            nodeList = new NodeDoubleLinkedList<K, V>();
            capacity = cap;
        }

        public V get(K key) {
            if (keyNodeMap.containsKey(key)) {
                Node<K, V> res = keyNodeMap.get(key);
                nodeList.moveNodeToTail(res);
                return res.value;
            }
            return null;
        }

        public void set(K key, V value) {
            if (keyNodeMap.containsKey(key)) {
                Node<K, V> node = keyNodeMap.get(key);
                node.value = value;
                nodeList.moveNodeToTail(node);
            } else {
                if (keyNodeMap.size() == capacity) {
                    removeMostUnusedCache();
                }
                Node<K, V> newNode = new Node<K, V>(key, value);
                keyNodeMap.put(key, newNode);
                nodeList.addNode(newNode);
            }
        }

        private void removeMostUnusedCache() {
            Node<K, V> removeNode = nodeList.removeHead();
            keyNodeMap.remove(removeNode.key);
        }
    }
}

最后更新： 2021年02月01日 17:52

原始链接： https://midkuro.gitee.io/2020/11/01/algorithm-topinterview/

Kuro

赏

× 请我吃糖~