LeetCode Problems

刷题资源

LeetCode题目链接：https://leetcode.com/problems/two-sum/
参考的刷题博客：https://leetcode.wang/

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

Approach 1: Brute Force
The brute force approach is simple. Loop through each element x and find if there is another value that equals to [target - x]

class Solution {
    // 方法1：暴力搜索
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }
}

Approach 2: Two-pass Hash Table
To improve our runtime complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to get its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.
We can reduce the lookup time from O(n)O(n) to O(1)O(1) by trading space for speed. A hash table is well suited for this purpose because it supports fast lookup in near constant time. I say “near” because if a collision occurred, a lookup could degenerate to O(n)O(n) time. However, lookup in a hash table should be amortized O(1)O(1) time as long as the hash function was chosen carefully.
A simple implementation uses two iterations. In the first iteration, we add each element’s value as a key and its index as a value to the hash table. Then, in the second iteration, we check if each element’s complement (target - nums[i]target−nums[i]) exists in the hash table. If it does exist, we return current element’s index and its complement’s index. Beware that the complement must not be nums[i]nums[i] itself!

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            // 要注意这种特殊情况，当遍历到i 位置，i索引元素的两倍，刚好等于target
            // 那么就会返回两个相同的索引，导致不符合题意
            if (map.containsKey(complement) && map.get(complement) != i){
                return new int[]{i, map.get(complement)};
            }
        }
        return null;
    }
}

Approach 3: One-pass Hash Table
It turns out we can do it in one-pass. While we are iterating and inserting elements into the hash table, we also look back to check if current element’s complement already exists in the hash table. If it exists, we have found a solution and return the indices immediately.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            // 1. 因为访问到这里，i索引还没添加到哈希表中，所以不用判断target等于两倍nums[i]的特殊情况了
            if (map.containsKey(complement) ){
                int index = map.get(complement);
                return new int[]{i, index};
            }
            // 2. 不管是否匹配到，都要把当前加入到哈希表中
            map.put(nums[i], i);
        }
        return null;
    }
}

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

方法1：虚拟头结点顺序添加。

class Solution {
    // Solution 中的参考代码
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 1. 虚拟头结点，最后返回 dummyHead.next
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1;
        ListNode q = l2;
        ListNode cur = dummyHead;
        int carry = 0;
        // 2. 有一个不为空就可以遍历
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (p != null) {
                p = p.next;
            }
            if (q != null) {
                q = q.next;
            }
        }
        // 3. 最后还有进位，创建一个结点存放进位，并和链表连接
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

方法2：求两个链表长度了，复杂度较高。

class Solution {
    // 两个链表相加
    public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
        int len1 = listLength(head1);
        int len2 = listLength(head2);
        // 1. 遍历得到链表长度，分辨出长短
        ListNode l = len1 >= len2 ? head1 : head2;
        ListNode s = l == head1 ? head2 : head1;
        ListNode curL = l;
        ListNode curS = s;
        ListNode last = curL;
        int carry = 0;
        int curNum = 0;
        // 2. 一起走过短链表的长度
        while (curS != null) {
            // 2.1 带进位相加，结果存储到长链表上，并计算进位项
            curNum = curL.val + curS.val + carry;
            curL.val = (curNum % 10);
            carry = curNum / 10;
            // last 唯一的作用是记录最后的结点
            last = curL;
            curL = curL.next;
            curS = curS.next;
        }
        // 3. 短链表走完了，开始走长链表
        while (curL != null) {
            curNum = curL.val + carry;
            curL.val = (curNum % 10);
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
        }
        // 4. 当长链表走到null，但还是有进位的时候，
        if (carry != 0) {
            // 4.1 创建一个结点对象，把进位的1赋值给它，并把last 指向它
            last.next = new ListNode(1);
        }
        // 5. 链表相加的结果赋值给长链表了，返回长链表的头结点
        return l;
    }
    // 求链表长度
    public static int listLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
}

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Approach 1: Brute Force

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (checkRepetition(s, i, j)) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }
    private boolean checkRepetition(String s, int start, int end) {
        int[] chars = new int[128];
        for (int i = start; i <= end; i++) {
            char c = s.charAt(i);
            chars[c]++;
            if (chars[c] > 1) {
                return false;
            }
        }
        return true;
    }
}

Approach 2: Sliding Window
这个方法真的很妙啊，用两个变量就能抽象出一个滑动窗口对象，这个滑动窗口向右滑动，左侧边界控制窗口大小，每次把最长不重复字符串大小保存到变量中，最后返回最大值。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 1. 
        int[] chars = new int[128];
        int left = 0;
        int right = 0;
        int res = 0;
        while(right < s.length() ) {
            char r = s.charAt(right);
            chars[r]++;     // 从0增加，记录该索引字符出现次数
            // 如果元素出现次数大于1，意味着滑动窗口中有这个元素
            // 就一直增加左边界索引，缩小滑动窗口
            while(chars[r] > 1) {
                char lf = s.charAt(left);   // 滑动窗口最左侧元素
                chars[lf]--;                // 滑动窗口缩小，最左侧元素所出现的次数减1
                left++;                     // 滑动窗口左侧边界往右扩展
            }
            res = Math.max(res, right - left + 1); 
            right++;    // 滑动窗口右移
        }
        return res;
    }
}

Approach 3: Sliding Window Optimized
The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.
The reason is that if s[j]s[j] have a duplicate in the range [i, j)[i,j) with index j’j′, we don’t need to increase ii little by little. We can skip all the elements in the range [i, j’][i,j′] and let ii to be j’ + 1j′+1 directly.

使用哈希表做缓存：

public class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // abcabcb
        // try to extend the range [i, j]
        for (int i = 0, k = 0; i < n; i++) {
            if (map.containsKey(s.charAt(i))) {
                int index = map.get(s.charAt(i));
                // k 代表的意思始终没有弄明白
                k = Math.max(index, k);
            }
            ans = Math.max(ans, i - k + 1);
            map.put(s.charAt(i), i + 1);
        }
        return ans;
    }
}

4. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).

这道题看着没意思，暂时没关注。。。

5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

参考：https://leetcode.wang/leetCode-5-Longest-Palindromic-Substring.html
这道题很难啊，暂时先放下。

6. Zigzag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

方法1：顺序遍历。
按照 Z的轨迹，遍历每个字符的同时，将字符存到对应的行，用一个变量控制遍历的方向，到达边界时就改变方向。

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        // 1. list容器，存储每层的字符串
        List<StringBuilder> level = new ArrayList<>();
        for (int i = 0; i < Math.min(s.length(), numRows); i++) {
            level.add(new StringBuilder());
        }
        int curRow = 0;
        boolean goingDown = false;
        char[] chars = s.toCharArray();
        // 2. 顺序遍历
        for (int i = 0; i < chars.length; i++) {
            // 3. 把字符添加到它所在的这层容器
            StringBuilder sb = level.get(curRow);
            sb.append(chars[i]);
            // 4. 到达边界就反转方向
            if (curRow == 0 || curRow == numRows - 1) {
                goingDown = !goingDown;
            }
            // 5. 根据方向标志，控制遍历脚步的正负
            curRow += goingDown ? 1 : -1;
        }
        // 6. 把各层结果汇总，最后返回
        StringBuilder ret = new StringBuilder();
        for (StringBuilder row :
                level) {
            ret.append(row);
        }
        return ret.toString();
    }
}

7. Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

这道题考虑的细节有好几处呢：在Java中，int基本数据类型范围是 -2147483648~2147483647
对于大于 intMax 的讨论，此时 x 一定是正数，pop 也是正数。

• 如果 rev > intMax / 10 ，那么没的说，此时肯定溢出了。
• 如果 rev == intMax / 10 = 2147483647 / 10 = 214748364 ，此时 rev * 10 就是 2147483640 如果 pop 大于 7 ，那么就一定溢出了。但是！如果假设 pop 等于 8，那么意味着原数 x 是 8463847412 了，输入的是 int ，而此时是溢出的状态，所以不可能输入，所以意味着 pop 不可能大于 7 ，也就意味着 rev == intMax / 10 时不会造成溢出。
• 如果 rev < intMax / 10 ，意味着 rev 最大是 214748363 ， rev * 10 就是 2147483630 , 此时再加上 pop ，一定不会溢出。

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;    // x 的末尾数字
            x /= 10;            // 更新x
            if (rev > Integer.MAX_VALUE/10 ) {
                return 0;
            }
            if (rev < Integer.MIN_VALUE/10 ) {
                return 0;
            }
            rev = rev * 10 + pop;   // 依次把x每位数字反转
        }
        return rev;
    } 
}

8. String to Integer

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

这种题有点难啊。

方法1：

class Solution {
    public int myAtoi(String input) {
        int sign = 1; 
        int result = 0; 
        int index = 0;
        int n = input.length();
        // Discard all spaces from the beginning of the input string.
        while (index < n && input.charAt(index) == ' ') { 
            index++; 
        }
        // sign = +1, if it's positive number, otherwise sign = -1. 
        if (index < n && input.charAt(index) == '+') {
            sign = 1;
            index++;
        } else if (index < n && input.charAt(index) == '-') {
            sign = -1;
            index++;
        }
        // Traverse next digits of input and stop if it is not a digit
        while (index < n && Character.isDigit(input.charAt(index))) {
            int digit = input.charAt(index) - '0';
            // Check overflow and underflow conditions. 
            if ((result > Integer.MAX_VALUE / 10) || 
                (result == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) {     
                // If integer overflowed return 2^31-1, otherwise if underflowed return -2^31.    
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            // Append current digit to the result.
            result = 10 * result + digit;
            index++;
        }
        // We have formed a valid number without any overflow/underflow.
        // Return it after multiplying it with its sign.
        return sign * result;
    }
}

9. Palindrome Number

Given an integer x, return true if x is palindrome integer.
An integer is a palindrome when it reads the same backward as forward.

• For example, 121 is a palindrome while 123 is not.

Approach 1: Revert half of the number

class Solution {
    public boolean isPalindrome(int x) {
        // Special cases:
        // As discussed above, when x < 0, x is not a palindrome.
        // Also if the last digit of the number is 0, in order to be a palindrome,
        // the first digit of the number also needs to be 0.
        // Only 0 satisfy this property.
        if (x < 0) {
            return false;
        }
        if (x % 10 == 0 && x != 0) {
            return false;
        }
        int rev = 0;
        while (x > rev) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        // When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
        // For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,
        // since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
        return x == rev || x == rev / 10;
    }
}

方法2：也是同样的方法，但细节不一样。

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        // 1. 得到原数字有多少位
        int digit = (int) (Math.log(x) / Math.log(10) + 1); //总位数
        int revert = 0;
        int pop = 0;
        // 2. 反转一半
        for (int i = 0; i < digit / 2; i++) { 
            pop = x % 10;
            revert = revert * 10 + pop;
            x /= 10;
        }
        // 3. 如果是偶数位
        if (digit % 2 == 0 && x == revert) {
            return true;
        }
        // 4. 奇数情况 x 除以 10 去除 1 位
        if (digit % 2 != 0 && x / 10 == revert) { 
            return true;
        }
        return false;
    }
}

11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Approach 1: Brute Force

public int maxArea(int[] height) {
    int maxarea = 0;
    for (int left = 0; left < height.length; left++) {
        for (int right = left + 1; right < height.length; right++) {
            int width = right - left;
            int high= Math.min(height[left], height[right]);
            int curArea = width * high;
            maxarea = Math.max(maxarea, curArea);
        }
    }
    return maxarea;
}

Approach 2: Two Pointer Approach

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0;
        int left = 0;
        int right = height.length - 1;
        while(left < right) {
            int high = Math.min(height[left], height[right]);
            int area = (right - left) * high;
            maxarea = Math.max(maxarea, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxarea;
    }
}

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.

Approach 1: Horizontal scanning

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
        return "";   
    }
    // 把第一个字符串作为LCP
    String prefix = strs[0];    
    // 2. 依次与其他字符串比较
    for (int i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) != 0) {
            // LCP 缩小一个字符
            prefix = prefix.substring(0, prefix.length() - 1);
            // 直到为空都没有LCP，那就返回空串
            if (prefix.isEmpty() ) {
                return "";   
            }
        }        
    }
    return prefix;
}

19. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

方法1：用容器存放结点，空间换时间。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 1. 空间换时间，创建一个list容器
        List<ListNode> list = new ArrayList<>();    
        ListNode original = head;       
        int len = 0;
        // 2. 遍历链表，得到结点、长度等信息
        while (head != null) {      
            list.add(head);
            len++;
            head = head.next;
        }
        if (len == 1) {            
            return null;
        }
        // 题意是删除倒数第n个结点，只删除这一个节点
        if (len == n) {
            return original.next;
        }
        // 4. 从list中取出要删除结点的前一个结点
        int remove = len - n;
        ListNode pre = list.get(remove - 1);    
        pre.next = pre.next.next;    // 修改链接
        return original;
    }
}

方法2：快慢双指针。

1. 注意while循环条件，如果有空指针异常，会导致程序出错的。

2. 要面对好几种特殊输入情况，代码细节挺难写的。

   class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 1. 虚拟头结点，指向原头结点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 2. 双指针
        // slow is at dummy not at head because we need to reach 1 node before the node we want to delete
        ListNode fast = head;   
        ListNode slow = dummy;
        // 3. 快指针走 n 步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 4. 快慢指针同步遍历，走到
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 5. 修改链接
        slow.next = slow.next.next;
        return dummy.next;
    }
   }

21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

方法1：递归。

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode mergeHead;
        if(list1.val < list2.val){
            mergeHead = list1;
            mergeHead.next = mergeTwoLists(list1.next, list2);
        } else{
            mergeHead = list2;
            mergeHead.next = mergeTwoLists(list1, list2.next);
        }
        return mergeHead;
    }
}

方法2：迭代

class Solution {
    public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        // 1. 链表是升序，找到较小的作为新链表的头结点
        ListNode head = head1.val <= head2.val ? head1 : head2;
        // 2. 找到两个链表的起始位置
        ListNode cur1 = head.next;
        ListNode cur2 = head == head1 ? head2 : head1;
        ListNode pre = head;
        // 3. 两个链表都不为空，进行合并操作
        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;
        }
        // 4. 遍历完一个链表，对另一个直接合并
        pre.next = cur1 != null ? cur1 : cur2;
        // 5. 返回新链表的头结点
        return head;
    }
}

23. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.

class Solution {
    // 比较器类
    // 自己创建的类，要排序就需要实现比较器接口或使用其他方法
    public static class ListNodeComparator implements Comparator<ListNode> {
        // 重写compare方法，定义排序规则
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }
    // 合并k 个有序链表
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        // 1. 用Java内置数据结构创建一个优先级队列，默认是小根堆，需要传入一个比较器对象作为参数
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
        // 2. 把列表中每个链表的头结点添加到堆
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                heap.add(lists[i]);
            }
        }
        // if (heap.isEmpty()){
        //     return null;
        // }
        // 3. 小根堆，推出堆顶元素，作为头结点
        // 发现链表问题不用递归的话都是这个步骤：
        // 第一步：单独处理头结点；
        // 第二步：在循环体中进行与第一步相似的步骤
        ListNode head = heap.poll();
        // 4. pre结点，并把下一个结点添加到堆，让小根堆保持固定的大小
        ListNode pre = head;
        if (pre.next != null) {
            heap.add(pre.next);
        }
        // 5. 小根堆的顶部是最小的元素，每次推出堆顶元素，并把pre的next指向它，链表就连接起来了，
        // 然后把它的next再添加到堆，元素在堆里面会再调整，把新的最小的元素移动到顶部，如此循环往复
        while (!heap.isEmpty()) {
            // 5.1 推出小根堆的堆顶元素
            ListNode cur = heap.poll();
            // 5.2 把它和前面排好序的链表建立链接关系，并移动pre
            pre.next = cur;
            pre = cur;
            // 5.3 next不为空就添加到堆，堆会再动态调整的
            if (cur.next != null) {
                heap.add(cur.next);
            }
        }
        // 6. 最后一步当然是返回头结点了
        return head;
    }
}

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

方法1：迭代。

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 1. 避免单独讨论头结点的情况，申请虚拟头结点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode point = dummy;
        // 2. 遍历
        while (point.next != null && point.next.next != null) { 
            ListNode swap1 = point.next;
            ListNode swap2 = point.next.next;
            // 3. 修改三个结点之间的链接
            point.next = swap2;
            swap1.next = swap2.next;
            swap2.next = swap1;
            // 4. 移动位置
            point = swap1;      
        }
        return dummy.next;
    }
}

方法2：递归。
一定要多看看，掌握这个方法。

public ListNode swapPairs(ListNode head) {
    // 1. 递归的basecase
    if ((head == null)||(head.next == null)) {
        return head;
    }
    // 递归到最后，head是一对结点的第一个，
    // 先保存它的next结点，再改变它的指向，接着让它原来的next结点指向它，这时候就反转好了，最后返回保存的那个next结点
    // 2. 保存下一个结点
    ListNode n = head.next;
    // 3. 修改链接
    head.next = swapPairs(head.next.next);
    // 4. 反转原next的链接，让它指向head
    n.next = head;
    // 5. 返回反转后的头结点
    return n;
}

25. Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
You may not alter the values in the list’s nodes, only nodes themselves may be changed.

方法1：递归。
很巧妙，运行流程大概懂了，但写不出来。以k 个结点为一组进行反转，上面那道题是k 等于2的时候的特例。

class Solution {
    // https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11423/Short-but-recursive-Java-code-with-comments
    // 代码很短，但是比较难理解，要创建几个结点并结合画图走一遍代码
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int count = 0;
        // 1. 先走k 步
        while(cur != null && count != k) {
            cur = cur.next;
            count++;
        }
        // 2. 等于k说明成功走过k 个结点，到下一段的头结点了
        if(count == k) {
            // 2.1 一直递归到尾部，
            // 最后一段小于k 步，那就不会走第2步，到第3步，传入的参数head 原样返回
            cur = reverseKGroup(cur, k);
            // 2.2 反转链表
            while(count-- > 0) {
                ListNode tmp = head.next;
                head.next = cur;
                cur = head;
                head = tmp;
            }
            // 2.3 把head 复位
            head = cur;
        }
        // 3. 两种情况，小于k 步，最后一段不用反转，直接返回传入的参数head；或者是执行完第二步了
        return head;
    }
}

方法2：迭代。

class Solution {
    public static ListNode reverseKGroup(ListNode head, int k) {
        // 1. 找到第一段要反转的两端结点
        ListNode start = head;
        ListNode end = getKGroupEnd(start, k);
        // 2. 判断是否能做反转，如果end为空，说明链表长度小于k，不用反转了
        if (end == null) {
            return head;
        }
        // 3. 保存反转后的头结点，就是第一段的end
        head = end;
        // 4. 开始对第一段进行反转
        reverse(start, end);
        // 第一组的start，反转后变成最后一个结点
        ListNode lastEnd = start;
        // 5. 当第一组的尾部结点的next 不为空时
        while (lastEnd.next != null) {
            // 6. 找到这组的start 和end
            start = lastEnd.next;
            end = getKGroupEnd(start, k);
            // 7. 和第2步一样，判断这组长度是否足够来反转
            if (end == null) {
                return head;
            }
            // 8. 对当前这段进行反转
            reverse(start, end);
            // 9. 反转后start 是尾，end 是头，使上一段的尾部指向end，start成为新的lastEnd
            lastEnd.next = end;
            lastEnd = start;
        }
        // 10. 返回第3步保存好的头结点head
        return head;
    }
    // 找到链表从start开始的第k 个结点
    public static ListNode getKGroupEnd(ListNode start, int k) {
        while (start != null && --k != 0  ) {
            start = start.next;
        }
        return start;
    }
    // 反转链表，范围包含start 和end
    public static void reverse(ListNode start, ListNode end) {
        // 1. end 跳到下一段的开头结点位置
        end = end.next;
        ListNode pre = null;
        ListNode cur = start;
        ListNode next = null;
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 5. 此时start是反转后的尾部结点，修改它的next就是把这段链表和下一段连接起来
        start.next = end;
    }
}

26. Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first _k slots of _nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

方法1：双指针。

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;   
        }
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    } 
}

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of _candidates where the chosen numbers sum to target._ You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.

方法1：回溯法

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), candidates, target, 0);
        return list;
    }
    private void backtrack(List<List<Integer>> list, List<Integer> res, int[] arr, int remain, int start) {
        // 1. 递归的basecase：小于0，无解
        if (remain < 0) {
            return;
        }
        // 2. 递归的basecase：等于0，刚好有一组解
        if (remain == 0) {
            list.add(new ArrayList<>(res ));
        } else {
            // 3. 没有凑够目标sum，才会继续试探
            // 试探所有情况，得到解或者走不通的时候就会回头
            for (int i = start; i < arr.length; i++) {
                // 添加，递归，移除，三句代码。递归的remain - arr[i]不能提出到外面
                res.add(arr[i]);
                backtrack(list, res, arr, remain - arr[i], i);
                // 关键步骤：找到解或者无解，回头移除末尾元素，继续尝试
                res.remove(res.size() - 1);
            }
        }
    }
}

41. First Missing Positive

Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.

参考：https://leetcode.com/problems/first-missing-positive/discuss/17071/My-short-c++-solution-O(1
核心思想是：Put each number in its right place. For example: When we find 5, then swap it with A[4].At last, the first place where its number is not right, return the place + 1.

方法1：有点像桶排序哦。就是第一步判断那里，有一点绕。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 1. 遍历每个数字，放到合适的位置
        for (int i = 0; i < n; i++) {
            //判断交换回来的数字
            // 这里的判断好绕啊，分不清哪儿是哪儿了
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                //第 nums[i] 个位置的下标是 nums[i] - 1
                swap(nums, i, nums[i] - 1);
            }
        }
        // 2. 找出第一个 nums[i] != i + 1 的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 3. 如果之前的数都满足就返回 n + 1
        return n + 1;
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

方法1：暴力破解。

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        //最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
        for (int i = 1; i < height.length - 1; i++) {
            int max_left = 0;
            // 1. 找出左边最高
            for (int j = i - 1; j >= 0; j--) {
                if (height[j] > max_left) {
                    max_left = height[j];
                }
            }
            int max_right = 0;
            // 2. 找出右边最高
            for (int j = i + 1; j < height.length; j++) {
                if (height[j] > max_right) {
                    max_right = height[j];
                }
            }
            // 3. 找出两端较小的
            int min = Math.min(max_left, max_right);
            // 4. 只有较小的一段大于当前列的高度才会有水，其他情况不会有水
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }
}

方法2：动态规划。
In brute force, we iterate over the left and right parts again and again just to find the highest bar size upto that index. But, this could be stored. Voila, dynamic programming.

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        // 1. 建立两个缓存数组，其中的元素代表 i 索引之前最高高度
        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];
        // 2. 遍历数组，得到关键信息。
        // height 中 i-1 和 i+1，是要包含端点的高度数据
        for (int i = 1; i < height.length - 1; i++) {
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        // 3. 根据木桶效应，求出当前 i 索引上能存储多少容量的水 
        for (int i = 1; i < height.length - 1; i++) {
            int min = Math.min(max_left[i], max_right[i]);
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }
}

方法3：双指针。

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        int max_left = 0;
        int max_right = 0;
        int left = 1;
        int right = height.length - 2; // 加右指针进去
        while (left -1 < right + 1) {
            //从左到右更
            if (height[left - 1] < height[right + 1]) {
                max_left = Math.max(max_left, height[left - 1]);
                int min = max_left;
                if (min > height[left]) {
                    sum = sum + (min - height[left]);
                }
                left++;
            } else {
                max_right = Math.max(max_right, height[right + 1]);
                int min = max_right;
                if (min > height[right]) {
                    sum = sum + (min - height[right]);
                }
                right--;
            }
        }
        return sum;
    }
}