今天来看LeetCode21-40题详解

21. 合并两个有序链表

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

归并思想

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                curr.next = l1;                l1 = l1.next;            }else{
                curr.next = l2;                l2 = l2.next;            }            curr = curr.next;        }        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

递归

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);            return l1;
        }else{
            l2.next = mergeTwoLists(l1, l2.next);        	return l2; 
        }    }

22. 括号生成

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

示例：

输入：n = 3
输出：[       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

使用String，每次状态变更都会创建新的对象，不需要状态重置。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        String sb = "";
        dfs(n, n, res, sb);        return res;
    }    void dfs(int l,int r, List<String> res, String sb){
        if(l == 0 && r == 0){
            res.add(sb);
            return;
        }		//保证一旦右括号先出现就停止
        if(l > r) return;
        if(l > 0) dfs(l - 1, r, res, sb + "(");
        if(r > 0) dfs(l, r - 1, res, sb + ")");
    }
}

使用StringBuilder，需要状态重置。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(n, n, res, sb);        return res;
    }    void dfs(int l,int r, List<String> res, StringBuilder sb){
        if(l == 0 && r == 0){
            res.add(sb.toString());
            return;
        }        if(l > r) return;
        if(l > 0){
            sb.append("(");
            dfs(l - 1, r, res, sb);
            sb.deleteCharAt(sb.length() -1);
        }         if(r > 0) {
            sb.append(")");
            dfs(l, r - 1, res, sb);
            sb.deleteCharAt(sb.length() -1);
        }    }}

23. 合并K个升序链表

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

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

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：[  1->4->5,
  1->3->4,
  2->6
]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

分治+ 归并

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        return merge(lists, 0 , lists.length - 1);
    }    ListNode merge(ListNode[] lists, int l, int r){        if(l == r) return lists[l];
        int mid = l + r >>> 1;
        ListNode l1 = merge(lists, l , mid);        ListNode l2 = merge(lists, mid + 1, r);
        return mergeTwoLists(l1, l2);
    }    ListNode mergeTwoLists(ListNode l1, ListNode l2){        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);            return l2;
        }    }}

优先队列

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for (ListNode node: lists) {
            if (node != null) {
                pq.offer(node);            }        }        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;        while (!pq.isEmpty()) {
            ListNode minNode = pq.poll();            tail.next = minNode;            tail = minNode;            if (minNode.next != null) {
                pq.offer(minNode.next);            }        }        return dummyHead.next;
    }}

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        for(ListNode p = dummy; p.next != null && p.next.next != null; ){
            ListNode a = p.next,b = a.next;
            p.next = b;
            a.next = b.next;
            b.next = a;
            p = a;        }        return dummy.next;
    }

25. K 个一组翻转链表

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

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        // 区间 [a, b) 包含 k 个待反转元素        ListNode a, b;        a = b = head;        for (int i = 0; i < k; i++) {
            // 不足 k 个，不需要反转，base case            if (b == null) return head;
            b = b.next;
        }        // 反转前 k 个元素, 返回的值就是反转之后的head        ListNode newHead = reverse(a, b);
        // 递归反转后续链表并连接起来        a.next = reverseKGroup(b, k);
        return newHead;
            }	//反转 [head, tail)    ListNode reverse(ListNode head ,ListNode tail){
        ListNode p = head, pre = null, next = null;
        while(p != tail){
            next = p.next;
            p.next = pre;
            pre = p;            p = next;
        }        return pre;
    }

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

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

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

示例 1:

给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
   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]) nums[++i] = nums[j];
       }
       //返回长度
       return i + 1;
   }

27. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
    public int removeElement(int[] nums, int val) {
        int k = 0;
        for(int i = 0; i < nums.length; i ++){
            if(nums[i] != val){
                nums[k++] = nums[i];
            }
        }
        return k;
    }

28. 实现 strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length(), n = needle.length();
        if (n == 0) return 0;
        for(int i = 0;i <= m - n ; i ++){
            //if(haystack.substring(i , i + n).equals(needle))  return i;
            if(check(haystack.substring(i , i + n), needle))  return i;
        }        return -1;
    }	//相当于equals函数    boolean check(String s1, String s2){        int k = 0;
        while(k < s2.length()){
            if(s1.charAt(k) != s2.charAt(k)) return false;
            k ++;        }        return true;
    }}

29. 两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

将被除数和除数都转成正数或负数进行计算，由于在Java中，当t=Integer.MIN_VALUE时（t取相反数依旧是它本身）此时可能存在越界问题，因此都用负数进行计算

    //O(N) 时间复杂度 超时
    public int divide(int a, int b) {
        //特殊情况
        if(a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;
        //k标识a与b是否同号
        boolean k = (a > 0 && b > 0) || (a < 0 && b < 0);
        int res = 0;
        //转化为负数
        a = -Math.abs(a);
        b = -Math.abs(b);
        //循环减相当于除法操作
        while(a <= b){
            a -= b;
            res ++;
        }
        return k? res : -res;
    }

使用二分法改善，a每次减去2n2n个b，res每次加上2n2n

    //O(log(n)) 
    public int divide(int a, int b) {
        //特殊情况
        if(a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;
        //k标识a与b是否同号
        boolean k = (a > 0 && b > 0) || (a < 0 && b < 0);
        int res = 0;
        //转化为负数
        a = -Math.abs(a);
        b = -Math.abs(b);
        //循环减相当于除法操作
        while(a <= b){
            int temp = b;
            int c = 1;
            //每次减去2^n
            while(a - temp <= temp){
                temp = temp << 1;
                c = c << 1;
            }
            a -= temp;
            res += c;
        }
        return k? res : -res;
    }

30. 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出：[0,9]解释：从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出：[]public List<Integer> findSubstring(String s, String[] words) {    List<Integer> res = new ArrayList<>();    int wordNum = words.length;    if(wordNum == 0) return res;
    int wordLen = words[0].length();
    // allWords存储所有单词
    HashMap<String, Integer> allWords = new HashMap<>();    for(String w : words) allWords.put(w, allWords.getOrDefault(w, 0) + 1);
    // 遍历所有子串
    for(int i = 0; i < s.length() - wordNum * wordLen + 1; i ++){
        // hasWords存储当前扫描的字符串含有的单词
        HashMap<String, Integer> hasWords = new HashMap<>();        int num = 0;
        // 判断该子串是否符合
        while(num < wordNum){
            //每次取一段
            String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
            if(allWords.containsKey(word)){
                hasWords.put(word, hasWords.getOrDefault(word, 0) + 1);
                // 判断当前单词的value 和 allWords中该单词的value
                if(hasWords.get(word) > allWords.get(word)) break;
            }else{
                break;
            }            num ++;        }        // 判断是不是所有的单词都符合条件
        if(num == wordNum) res.add(i);
    }
    return res;
}

31. 下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,31,1,5 → 1,5,1

public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        //找到第一个不再递增的位置
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;        }        //如果到了最左边，就直接倒置输出        if (i < 0) {
            reverse(nums, 0);
            return;
        }        //找到刚好大于 nums[i]的位置        int j = nums.length - 1;
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;        }        //交换        swap(nums, i, j);        //利用倒置进行排序
        reverse(nums, i + 1);
    }    private void swap(int[] nums, int i, int j) {
        int temp = nums[j];
        nums[j] = nums[i];        nums[i] = temp;    }    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);            i++;            j--;        }    }

32. 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"//")()(" --> 1001
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();        int n = s.length();
        char[] chs = s.toCharArray();        int[] mark = new int[n];
        int left = 0, len = 0, ans = 0;
        for(int i = 0; i < n; i ++){
            if(chs[i] == '(') stack.push(i);
            else{
                //没有匹配的左括号的右括号，置1
                if(stack.isEmpty())mark[i] = 1;
                //如果有匹配的左括号，弹出
                else stack.pop();
            }        }        // System.out.println(Arrays.toString(mark));        //多余的左括号，置1
        while(!stack.isEmpty()){
            mark[stack.pop()] = 1;
        }        //找到最长连续0的长度
        for(int i = 0; i < n; i ++){
            if(mark[i] == 1){
                len = 0;
                continue;
            }            len ++;            ans = Math.max(ans , len);        }        return ans;
    }

33. 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1public int search(int[] nums, int target) {
        if(nums.length == 0) return -1;
        int l = 0, r = nums.length -1;
        //找到最小值的索引位置
        while(l < r){
            int mid = l + r >> 1;
            if( nums[mid] <= nums[nums.length -1 ]) 
                r = mid;            else 
                l = mid + 1;
        }//此时l == r  == k        if( target <= nums[nums.length -1]) 
            //[k,len-1]
            r = nums.length -1; 
        else {
            //左边那段中寻找[0,k-1]
            l = 0;
            r --; //因为上面二分完之后找到了第二段的第一个索引，因此r = r-1
        }        while(l < r){
            int mid = l + r >> 1;
            if( nums[mid] >= target) r = mid;
            else l = mid + 1;
        }        //二分得出的是第一个>=target的值，需要判断一下是否就是寻找的那个数        if( nums[l]  ==  target) return l;
        return -1;
    }

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]public int[] searchRange(int[] nums, int t) {
        if(nums.length == 0) return new int[]{-1, -1};
        int l = 0, r = nums.length -1;
        //找第一个数
        while(l < r){
            int mid = l + r >>> 1;
            //假设mid位置为8，前面可能还有，r = mid
            if(nums[mid] >= t){
                r = mid;            }else{
                l = mid + 1;
            }        }        //将会二分出大于等于t的第一个数如果不等于t 则不存在        if(nums[r] != t) return new int[]{-1, -1};
        int start = r;
        l = 0;
        r = nums.length -1;
        while(l < r){
            //这里条件 l = mid, 注意这里向上取整
            int mid = l + r + 1 >>> 1;
            //找到第一个 <= target的数
            if( nums[mid] <= t){
                l = mid;            }else{
                r = mid - 1;
            }        }        int end = r;
        return new int[]{start, end};
    }

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1public int searchInsert(int[] nums, int target) {
        if(nums.length == 0 || nums[nums.length-1] < target) return nums.length;
        int l = 0, r = nums.length -1;
        //找到 >= target的第一个坐标
        while( l < r){
            int mid = l + r >> 1;
            if( nums[mid] >= target){
                r = mid;            }else{
                l = mid + 1;
            }        }        return r;
    }

36. 有效的数独

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

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

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 2:

输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。

public boolean isValidSudoku(char[][] board) {
        // 记录某行，某位数字是否已经被摆放        boolean[][] row = new boolean[9][9];
        // 记录某列，某位数字是否已经被摆放        boolean[][] col = new boolean[9][9];
        // 记录某 3x3 宫格内，某位数字是否已经被摆放        boolean[][] block = new boolean[9][9];
        for(int i = 0; i < 9; i ++){
            for(int j = 0; j < 9; j ++){
                //.的情况不用考虑
                if(board[i][j] == '.') continue;
                //数字为1-9
                int num = board[i][j] - '1';
                //映射到子数独中
                int index = i / 3 * 3 + j / 3;
                if(row[i][num] || col[j][num] || block[index][num]) 
                    return false;
                else{
                    row[i][num] = true;
                    col[j][num] = true;
                    block[index][num] = true;
                }
            }
        }
        return true;
    }

37. 解数独

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

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

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

空白格用 '.' 表示。

一个数独。

答案被标成红色。

提示：

给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

public void solveSudoku(char[][] board) {
        boolean flag = dfs(board, 0 ,0);
        return;
    }
    boolean dfs(char[][] board, int i , int j){
        if(i == 9) return true;
        //到最后一列，换下一行
        if(j == 9) return dfs(board, i + 1, 0); 
        if(board[i][j] != '.') return dfs(board, i , j + 1);
        //选择列表1 - 9
        for(char c = '1'; c <= '9'; c ++){ 
            if (!isValid(board, i ,j ,c)) continue; 
            //选择
            board[i][j] = c; 
            //下一层
            if (dfs(board, i, j + 1)) return true;
            //撤销选择
            board[i][j] = '.';
        }
        return false;
    }
    boolean isValid(char[][] board , int x , int y ,char n){
        for (int i = 0;i < 9; i ++){
            //列重复
            if (board[i][y] == n) return false;
            //行重复
            if (board[x][i] == n) return false;
        }
        //找到九宫格左上元素，依次遍历
        for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i ++){ 
            for (int j = y / 3 * 3;j < y / 3 * 3 + 3; j ++){
                if (board[i][j] == n) return false;
            }
        }
        return true;
    }

38. 外观数列

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意：整数序列中的每一项将表示为一个字符串。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

第一项是数字 1

描述前一项，这个数是 1 即 “一个 1 ”，记作 11

描述前一项，这个数是 11 即 “两个 1 ” ，记作 21

描述前一项，这个数是 21 即 “一个 2 一个 1 ” ，记作 1211

描述前一项，这个数是 1211 即 “一个 1 一个 2 两个 1 ” ，记作 111221

示例 1:

输入: 1
输出: "1"
解释：这是一个基本样例。

示例 2:

输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。public String countAndSay(int n) {
        String s = "1";
        //循环n - 1次
        for(int i = 0; i < n - 1 ; i ++){
            StringBuilder sb = new StringBuilder();            //每一次记录相同一段的个数
            for(int j = 0; j < s.length(); j ++){
                int k = j;
                while(k < s.length() && s.charAt(k) == s.charAt(j)){
                    k++;                }                //个数                String count = k - j + "";
                //个数 + 字符
                sb.append(count + s.charAt(j));                j = k - 1;
            }            s= sb.toString();
        }        return s;
    }

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

https://www.cnblogs.com/summerday152/p/13615904.html

public List<List<Integer>> combinationSum(int[] arr, int t) {
        List<List<Integer>> res = new ArrayList<>();        List<Integer> path = new ArrayList<>();
        Arrays.sort(arr);//排序是剪枝的前提
        dfs(res,path,0,arr,t);
        return res;
    }        void dfs(List<List<Integer>> res,List<Integer> path,int s,int[] arr, int t){
        if(t <= 0){
            if(t == 0){
                res.add(new ArrayList<>(path));
            }            return;
        }        for(int i = s; i < arr.length; i++){
            if(arr[i] > t){ //由于数组已经有序，当前这个数应该小于等于剩余数t
                break;
            }            path.add(arr[i]);
            dfs(res,path,i,arr,t-arr[i]); //因为
            path.remove(path.size()-1);
        }      }

40. 组合总和 II

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

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

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:[  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]public List<List<Integer>> combinationSum2(int[] arr, int t) {        List<List<Integer>> res = new ArrayList<>();        List<Integer> path = new ArrayList<>();
        Arrays.sort(arr);//排序是剪枝的前提
        dfs(res,path,0,arr,t);
        return res;
    }	// s 可以看成层数， i可以看成这一层从第几个开始    void dfs(List<List<Integer>> res,List<Integer> path,int s,int[] arr, int t){
        if(t <= 0){
            if(t == 0){
                res.add(new ArrayList<>(path));
            }            return;
        }        for(int i = s; i < arr.length; i++){ 
                        if(arr[i] > t){ //由于数组已经有序，当前这个数应该小于等于剩余数t
                break;
            }            //保证递归树的同一个层级不出现相同的元素            if(i > s && arr[i] == arr[i - 1]) continue;
            path.add(arr[i]);
            dfs(res,path,i+1,arr,t-arr[i]); 
            path.remove(path.size()-1);
        }      }

如果觉得本文对你有帮助，可以点赞关注支持一下，也可以关注我公众号，上面有更多技术干货文章以及相关资料共享，大家一起学习进步！

技术干货（二）:LeetCode21-40题详解

21. 合并两个有序链表

归并思想

递归

22. 括号生成

23. 合并K个升序链表

分治+ 归并

优先队列

24. 两两交换链表中的节点

25. K 个一组翻转链表

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

27. 移除元素

28. 实现 strStr()

29. 两数相除

30. 串联所有单词的子串

32. 最长有效括号

33. 搜索旋转排序数组

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

35. 搜索插入位置

36. 有效的数独

37. 解数独

38. 外观数列

39. 组合总和

40. 组合总和 II