1. 括号生成

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

示例 1：

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1

输出：["()"]

提示：

1 <= n <= 8

出处：

https://edu.csdn.net/practice/23843565

代码：

import java.util.Stack;
import java.util.List;
import java.util.ArrayList;
public class generateParenthesis {
    public static class Solution {
        void gen(Stack<String> p, int lc, int rc, List<String> r, int n) {
            if (lc > n) {
                return;
            }
            if (lc == n && rc == n) {
                StringBuilder sb = new StringBuilder();
                for (String l : p) {
                    sb.append(l);
                }
                r.add(sb.toString());
            }
            p.push("(");
            lc++;
            gen(p, lc, rc, r, n);
            p.pop();
            lc--;
            if (lc > rc) {
                p.push(")");
                rc++;
                gen(p, lc, rc, r, n);
                p.pop();
                rc--;
            }
        }
        public List<String> generateParenthesis(int n) {
            List<String> results = new ArrayList<String>();
            Stack<String> p = new Stack<String>();
            gen(p, 0, 0, results, n);
            return results;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.generateParenthesis(3));
        System.out.println(s.generateParenthesis(1));
        System.out.println(s.generateParenthesis(2));
    }
}

输出：

[((())), (()()), (())(), ()(()), ()()()]

[()]

[(()), ()()]

代码2：回溯法

import java.util.ArrayList;
import java.util.List;
public class generateParenthesis2 {
    public static class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();
            if (n <= 0) {
                return res;
            }
            backtrack(res, new StringBuilder(), 0, 0, n);
            return res;
        }
        private void backtrack(List<String> res, StringBuilder sb, int left, int right, int n) {
            if (sb.length() == n * 2) { // 已经添加了 n 对括号
                res.add(sb.toString());
                return;
            }
            if (left < n) { // 添加左括号
                sb.append("(");
                backtrack(res, sb, left + 1, right, n);
                sb.deleteCharAt(sb.length() - 1);
            }
            if (right < left) { // 添加右括号
                sb.append(")");
                backtrack(res, sb, left, right + 1, n);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.generateParenthesis(3));
        System.out.println(s.generateParenthesis(1));
        System.out.println(s.generateParenthesis(2));
    }
}

输出：

[((())), (()()), (())(), ()(()), ()()()]

[()]

[(()), ()()]

代码3： 动态规则

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class generateParenthesis3 {
    public static class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();
            if (n <= 0) {
                return res;
            }
            List<String>[] dp = new List[n + 1];
            dp[0] = Arrays.asList("");
            for (int i = 1; i <= n; i++) {
                List<String> list = new ArrayList<>();
                for (int j = 0; j < i; j++) {
                    List<String> s1 = dp[j];
                    List<String> s2 = dp[i - j - 1];
                    for (String str1 : s1) {
                        for (String str2 : s2) {
                            list.add("(" + str1 + ")" + str2);
                        }
                    }
                }
                dp[i] = list;
            }
            return dp[n];
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.generateParenthesis(3));
        System.out.println(s.generateParenthesis(1));
        System.out.println(s.generateParenthesis(2));
    }
}

输出：

[()()(), ()(()), (())(), (()()), ((()))]

[()]

[()(), (())]

2. 子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

输入：nums = [1,2,3]

输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

提示：

1 <= nums.length <= 10

-10 <= nums[i] <= 10

nums 中的所有元素互不相同

出处：

https://edu.csdn.net/practice/23843566

代码：回溯算法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class subsets {
    public static class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            List<Integer> tmp = new ArrayList<>();
            res.add(tmp);
            if (nums.length == 0)
                return res;
            helper(nums, 0, tmp, res);
            return res;
        }
        public void helper(int[] nums, int start, List<Integer> tmp, List<List<Integer>> res) {
            for (int i = start; i < nums.length; i++) {
                tmp.add(nums[i]);
                helper(nums, i + 1, tmp, res);
                res.add(new ArrayList<Integer>(tmp));
                tmp.remove(tmp.size() - 1);
            }
        }
    }
    private static int[] ArraySlice(int[] arr, int start, int end) {
        // 等价于： Arrays.copyOfRange(arr[], start, end)
        int[] slice = new int[end - start];
        for (int i = 0; i < slice.length; i++) {
            slice[i] = arr[start + i];
        }
        return slice;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,2,3};
        System.out.println(s.subsets(nums));
        System.out.println(s.subsets(ArraySlice(nums,1,3)));
        System.out.println(s.subsets(ArraySlice(nums,0,1)));
        System.out.println(s.subsets(Arrays.copyOfRange(nums, 1, 3)));
        System.out.println(s.subsets(Arrays.copyOfRange(nums, 0, 1)));
    }
}

输出：

[[], [1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3]]

[[], [2, 3], [2], [3]]

[[], [1]]

[[], [2, 3], [2], [3]]

[[], [1]]

代码2： 回溯算法

import java.util.ArrayList;
import java.util.List;
public class subsets {
    public static class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            backtracking(res, nums, new ArrayList<>(), 0);
            return res;
        }
        private void backtracking(List<List<Integer>> res, int[] nums, List<Integer> subset, int start) {
            res.add(new ArrayList<>(subset)); // 将当前子集加入结果集
            for (int i = start; i < nums.length; i++) {
                subset.add(nums[i]); // 加入当前元素
                backtracking(res, nums, subset, i + 1); // 递归加入下一个元素
                subset.remove(subset.size() - 1); // 回溯，移除最后一个元素
            }
        }
    }
    private static int[] ArraySlice(int[] arr, int start, int end) {
        // 等价于： Arrays.copyOfRange(arr[], start, end)
        int[] slice = new int[end - start];
        for (int i = 0; i < slice.length; i++) {
            slice[i] = arr[start + i];
        }
        return slice;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,2,3};
        System.out.println(s.subsets(nums));
        System.out.println(s.subsets(ArraySlice(nums,1,3)));
        System.out.println(s.subsets(ArraySlice(nums,0,1)));
    }
}

输出：

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

[[], [2], [2, 3], [3]]

[[], [1]]

代码3： 迭代法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class subsets {
    public static class Solution {
        public static List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            res.add(new ArrayList<>()); // 加入空集
            for (int i = 0; i < nums.length; i++) {
                int size = res.size(); // 获取当前结果集的大小
                for (int j = 0; j < size; j++) {
                    List<Integer> subset = new ArrayList<>(res.get(j)); // 复制已有子集
                    subset.add(nums[i]); // 加入新元素
                    res.add(subset); // 加入结果集
                }
            }
            return res;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,2,3};
        System.out.println(s.subsets(nums));
        System.out.println(s.subsets(Arrays.copyOfRange(nums, 1, 3)));
        System.out.println(s.subsets(Arrays.copyOfRange(nums, 0, 1)));
    }
}

输出：

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

[[], [2], [3], [2, 3]]

[[], [1]]

代码4： 位运算

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class subsets {
    public static class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            int n = nums.length;
            int m = 1 << n; // 共有2^n个子集
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                List<Integer> subset = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    if (((i >> j) & 1) == 1) { // 判断第j位是否为1
                        subset.add(nums[j]); // 将第j个元素加入子集
                    }
                }
                res.add(subset); // 将当前子集加入结果集
            }
            return res;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,2,3};
        System.out.println(s.subsets(nums));
        System.out.println(s.subsets(Arrays.copyOfRange(nums, 1, 3)));
        System.out.println(s.subsets(Arrays.copyOfRange(nums, 0, 1)));
    }
}

输出：

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

[[], [2], [3], [2, 3]]

[[], [1]]

3. 分发糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。

评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1：

输入：[1,0,2]

输出：5

解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：[1,2,2]

输出：4

解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。

第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

出处：

https://edu.csdn.net/practice/23843567

代码：贪心算法

public class candy {
    public static class Solution {
        public int candy(int[] ratings) {
            int len = ratings.length;
            int[] left = new int[len];
            int[] right = new int[len];
            left[0] = 1;
            right[len - 1] = 1;
            for (int i = 1; i < len; i++) {
                if (ratings[i] > ratings[i - 1]) {
                    left[i] = left[i - 1] + 1;
                } else {
                    left[i] = 1;
                }
            }
            for (int i = len - 2; i >= 0; i--) {
                if (ratings[i] > ratings[i + 1]) {
                    right[i] = right[i + 1] + 1;
                } else {
                    right[i] = 1;
                }
            }
            int res = 0;
            for (int i = 0; i < len; i++) {
                res += Math.max(left[i], right[i]);
            }
            return res;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,0,2};
        System.out.println(s.candy(nums));
        int[] nums1 = {1,2,2};
        System.out.println(s.candy(nums1));
    }
}

输出：

代码2：原理一样，数组元素全部初始化为1，简化代码

import java.util.Arrays;
public class candy {
    public static class Solution {
        public int candy(int[] ratings) {
            int n = ratings.length;
            int[] candy = new int[n];
            Arrays.fill(candy, 1); // 每个孩子至少分配到 1 个糖果
            // 从左向右扫描，满足评分更高的孩子必须比他左侧的邻位孩子获得更多的糖果
            for (int i = 1; i < n; i++) {
                if (ratings[i] > ratings[i - 1]) {
                    candy[i] = candy[i - 1] + 1;
                }
            }
            // 从右向左扫描，满足评分更高的孩子必须比他右侧的邻位孩子获得更多的糖果
            for (int i = n - 2; i >= 0; i--) {
                if (ratings[i] > ratings[i + 1]) {
                    candy[i] = Math.max(candy[i], candy[i + 1] + 1);
                }
            }
            // 统计总共需要的糖果数
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum += candy[i];
            }
            return sum;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,0,2};
        System.out.println(s.candy(nums));
        int[] nums1 = {1,2,2};
        System.out.println(s.candy(nums1));
    }
}