给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4]，
  [3,4]，
  [2,3]，
  [1,2]，
  [1,3]，
  [1,4]，
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

使用模板解决：

我们直接使用组合型枚举的算法模板来解决这个问题。具体步骤如下：

1. 使用递归的方式生成所有可能的组合。
2. 确定组合中的元素个数为 k。
3. 确定组合的起始位置为 1。
4. 根据递归终止条件，在组合中的元素个数达到 k 时，输出当前组合。

代码示例：

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        generateCombinations(result, new ArrayList<>()， 1, n, k);
        return result;
    }
    private void generateCombinations(List<List<Integer>> result, List<Integer> combination, int start, int n, int k) {
        // 递归终止条件：组合中的元素个数达到k时
        if (combination.size() == k) {
            result.add(new ArrayList<>(combination)); // 将当前组合添加到结果中
            return;
        }
        // 递归生成组合
        for (int i = start; i <= n; i++) {
            combination.add(i); // 添加当前元素到组合中
            generateCombinations(result, combination, i + 1, n, k); // 递归生成剩余元素的组合
            combination.remove(combination.size() - 1); // 回溯，移除当前元素
        }
    }
}

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

示例 2：

输入：nums = [0,1]
输出：[[0,1]，[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

使用模板解决：

我们直接使用排列型枚举的算法模板来解决这个问题。具体步骤如下：

1. 使用递归的方式生成所有可能的排列。
2. 确定排列中的元素包含了数组 nums 中的所有元素。
3. 使用一个标记数组 visited 记录每个元素的访问状态。
4. 根据递归终止条件，在排列中包含了所有元素时，输出当前排列。

代码示例：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        generatePermutations(nums, new ArrayList<>()， new boolean[nums.length]， result);
        return result;
    }

    private void generatePermutations(int[] nums, List<Integer> permutation, boolean[] visited, List<List<Integer>> result) {
        // 递归终止条件：排列中包含了所有元素
        if (permutation.size() == nums.length) {
            result.add(new ArrayList<>(permutation)); // 将当前排列添加到结果中
            return;
        }
        // 递归生成排列
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true; // 标记当前元素已访问
                permutation.add(nums[i]); // 添加当前元素到排列中
                generatePermutations(nums, permutation, visited, result); // 递归生成剩余元素的排列
                permutation.remove(permutation.size() - 1); // 回溯，移除当前元素
                visited[i] = false; // 恢复当前元素的未访问状态
            }
        }
    }
}

在上面的代码中，permute 方法接收整数数组 nums，返回其所有可能的全排列。通过调用 generatePermutations 方法生成所有排列，并将结果保存在 result 列表中。最后，在 main 方法中调用 permute 方法，并输出所有可能的排列。

从 1∼ n个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式：

输入一个整数 n。

输出格式:

每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。
对于没有选任何数的方案，输出空行。
各行（不同方案）之间的顺序任意。

示例：

输入：3
输出：3
     2
     2 3
     1
     1 3
     1 2
     1 2 3

使用模板解决：

我们可以使用指数型枚举的算法模板来解决这个问题。具体步骤如下：

1. 对于集合中的每个元素，用二进制位表示是否选择该元素。通过枚举二进制数来遍历集合的所有子集。
2. 对于每个生成的子集，输出选择了的元素。

代码示例：

import java.util.*;

public class SubsetGenerator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取输入的整数n
        List<List<Integer>> subsets = generateSubsets(n); // 调用函数生成所有可能的选择方案
        // 遍历所有的选择方案
        for (List<Integer> subset : subsets) {
            if (!subset.isEmpty()) { // 如果当前方案不为空
                for (int i = 0; i < subset.size(); i++) {
                    if (i > 0) {
                        System.out.print(" "); // 输出当前元素之前先输出一个空格
                    }
                    System.out.print(subset.get(i)); // 输出当前元素
                }
                System.out.println(); // 换行
            } else {
                System.out.println(); // 如果当前方案为空，输出一个空行
            }
        }
    }

    // 生成所有可能的选择方案
    public static List<List<Integer>> generateSubsets(int n) {
        List<List<Integer>> subsets = new ArrayList<>(); // 存储所有的选择方案
        // 通过枚举子集的二进制表示来生成所有可能的选择方案
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>(); // 当前的选择方案
            // 对于每个子集，判断是否选择了当前元素
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) > 0) { // 如果选择了当前元素
                    subset.add(i + 1); // 将当前元素加入到选择方案中
                }
            }
            subsets.add(subset); // 将当前选择方案加入到结果集中
        }
        return subsets; // 返回所有的选择方案
    }
}

在上面的代码中，我们通过枚举子集的二进制表示来生成所有可能的选择方案。对于每个子集，我们将其转换为对应的整数，并输出选择了的元素。最终得到的结果即为从 1 到 n 个整数中随机选取任意多个的所有可能的选择方案。

题目描述:

给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+'， '-'， '*'， '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。

你须遵守以下规则:

• 除法运算符

  '/'
  

  表示实数除法，而不是整数除法。

  • 例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。

• 每个运算都在两个数字之间。特别是，不能使用

  “-”
  

  作为一元运算符。

  • 例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。

• 你不能把数字串在一起

  • 例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。

如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。

示例 1:

输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24

示例 2:

输入: cards = [1, 2, 1, 2]
输出: false

运行限制:

最大运行时间：1s
最大运行内存: 128M

题目解析：

我们可以通过枚举所有可能的运算表达式来判断是否可以得到结果为24的表达式。

以下是一个使用枚举法的解题思路：

1. 枚举所有可能的排列和组合： 首先，我们可以枚举所有可能的排列和组合，即将4个数字进行排列和组合，得到不同的数学表达式。

2. 枚举所有可能的运算符排列： 对于每个数字排列，我们需要枚举所有可能的运算符排列，包括 +、-、*、/，以及括号的位置。

3. 计算表达式的值： 对于每个得到的表达式，我们计算其值并检查是否等于24。

boolean judgePoint24(int[] cards) {
    List<Double> nums = new ArrayList<>();
    for (int card : cards) {
        nums.add((double) card);
    }
    return dfs(nums);
}

boolean dfs(List<Double> nums) {
    if (nums.size() == 1) {
        // 比较两个浮点数之间是否非常接近
        return Math.abs(nums.get(0) - 24) < 1e-6; // 判断是否等于24
    }
    for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < nums.size(); j++) {
            if (i != j) {
                List<Double> next = new ArrayList<>();
                for (int k = 0; k < nums.size(); k++) {
                    if (k != i && k != j) {
                        next.add(nums.get(k));
                    }
                }
                for (int k = 0; k < 4; k++) { // 枚举所有运算符
                    if (k < 2 && j > i) {
                        continue; // 加法和乘法交换律，避免重复计算
                    }
                    if (k == 0) {
                        next.add(nums.get(i) + nums.get(j)); // 加法
                    } else if (k == 1) {
                        next.add(nums.get(i) * nums.get(j)); // 乘法
                    } else if (k == 2) {
                        next.add(nums.get(i) - nums.get(j)); // 减法
                    } else if (k == 3) {
                        if (Math.abs(nums.get(j)) < 1e-6) {
                            continue; // 除数为0，跳过
                        } else {
                            next.add(nums.get(i) / nums.get(j)); // 除法
                        }
                    }
                    if (dfs(next)) { // 递归计算下一步
                        return true;
                    }
                    next.remove(next.size() - 1); // 回溯
                }
            }
        }
    }
    return false;
}

这段代码使用了深度优先搜索（DFS）来枚举所有可能的计算表达式，逐步计算并判断是否等于24。

之后会详细讲解 DFS 和 BFS 和递归递推，这里理解枚举的思想就行

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

解题思路：
要找到单链表的中间结点，可以使用快慢指针的方法。快慢指针的核心思想是同时从链表的起始位置出发，慢指针每次移动一步，快指针每次移动两步，当快指针到达链表末尾时，慢指针刚好处于链表的中间位置。

具体步骤如下：

1. 初始化快指针和慢指针，都指向链表的头结点。
2. 使用循环遍历链表，快指针每次移动两步，慢指针每次移动一步，直到快指针到达链表的末尾（即快指针的下一个节点为null）。
3. 当快指针到达末尾时，慢指针所指的节点就是链表的中间结点。

如果链表中的结点数为偶数，则返回第二个中间结点。

通过两个指针以不同的步长同时移动，从而找到问题的解，这种方法在查找链表中的中间结点、环检测等问题中被广泛应用。

代码示例：

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next; // 快指针每次移动两步
            slow  = slow.next;
        }
        // 当快指针到最后的时候，慢指针就到了中间
        return slow;
    }
}

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15]， target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4]， target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3]， target = 6
输出：[0,1]

实例代码：

由于题目给的数组不是有序的，所以用哈希会更快一点，这里主要理解对撞指针

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 复制并排序原始数组
        int[] sortedNums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortedNums);

        // 定义左指针和右指针
        int left = 0, right = sortedNums.length - 1;

        // 循环直到左指针超过右指针
        while (left < right) {
            // 计算当前左右指针位置的两个数的和
            int sum = sortedNums[left] + sortedNums[right];

            // 如果和等于目标值，则在原始数组中查找对应的下标
            if (sum == target) {
                // 查找第一个数的下标
                int index1 = -1;
                for (int i = 0; i < nums.length; i++) {
                    if (nums[i] == sortedNums[left]) {
                        index1 = i;
                        break;
                    }
                }
                // 查找第二个数的下标
                int index2 = -1;
                for (int i = nums.length - 1; i >= 0; i--) {
                    if (nums[i] == sortedNums[right]) {
                        index2 = i;
                        break;
                    }
                }
                // 返回结果
                return new int[] {index1, index2};
            } else if (sum < target) { // 如果和小于目标值，则将左指针向右移动一位
                left++;
            } else { // 如果和大于目标值，则将右指针向左移动一位
                right--;
            }
        }

        // 如果未找到符合条件的解，则返回空数组
        return new int[0];
    }
}

给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。

一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。

请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。

• 子数组指的是数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [1,-1,-3,-2,3]， k = 3, x = 2
输出：[-1,-2,-2]
解释：总共有 3 个 k = 3 的子数组。
第一个子数组是 [1, -1, -3] ，第二小的数是负数 -1 。
第二个子数组是 [-1, -3, -2] ，第二小的数是负数 -2 。
第三个子数组是 [-3, -2, 3] ，第二小的数是负数 -2 。

示例 2：

输入：nums = [-1,-2,-3,-4,-5]， k = 2, x = 2
输出：[-1,-2,-3,-4]
解释：总共有 4 个 k = 2 的子数组。
[-1, -2] 中第二小的数是负数 -1 。
[-2, -3] 中第二小的数是负数 -2 。
[-3, -4] 中第二小的数是负数 -3 。
[-4, -5] 中第二小的数是负数 -4 。

示例 3：

输入：nums = [-3,1,2,-3,0,-3]， k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解释：总共有 5 个 k = 2 的子数组。
[-3, 1] 中最小的数是负数 -3 。
[1, 2] 中最小的数不是负数，所以美丽值为 0 。
[2, -3] 中最小的数是负数 -3 。
[-3, 0] 中最小的数是负数 -3 。
[0, -3] 中最小的数是负数 -3 。

题解：

使用有序哈希表。具体思路如下:

1. 使用一个有序哈希表(TreeMap)来存储数组中的元素及其索引列表。
2. 初始化第一个长度为k的子数组，将其所有元素及其索引存入有序哈希表中。
3. 计算第一个子数组的美丽值，并存入结果数组中。
4. 对于后续的每个子数组，我们只需要从有序哈希表中移除旧元素及其索引，添加新元素及其索引。
5. 在有序哈希表中，我们可以很方便地找到第x小的元素，从而计算出当前子数组的美丽值。
6. 重复步骤4-5，直到遍历完整个数组。

核心思路是:

1. 我们使用一个TreeMap来存储数组中的元素及其索引列表。TreeMap会自动按照键(元素值)的大小进行排序。
2. 在初始化第一个窗口时，我们将所有元素及其索引存入TreeMap中。
3. 在移动窗口时，我们从TreeMap中移除旧元素及其索引，添加新元素及其索引。
4. 编写了一个辅助函数getBeauty来计算美丽值。该函数遍历TreeMap中的条目，累加每个元素的索引列表大小。当累加的大小达到或超过x时，就找到了第x小的元素，返回它的值(如果是负数)或0(如果是非负数)。

这种解法的时间复杂度为O(n * k * log k)。其中，移动窗口的操作需要O(log k)的时间复杂度，因为需要在TreeMap中插入和删除元素。而获取第x小的元素的时间复杂度为O(k * log k)，因为需要遍历TreeMap中的所有条目。

相比基于排序的解法，这种解法避免了每次都完全排序的开销，效率会有所提升。同时，它也比使用优先队列的解法更加简洁直观。

示例代码：

class Solution {

    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        int[] result = new int[n - k + 1]; // 结果数组，存储每个长度为k的子数组的美丽值
        TreeMap<Integer, List<Integer>> map = new TreeMap<>(); // 有序哈希表，存储元素值及其索引列表

        // 初始化第一个长度为k的窗口
        for (int i = 0; i < k; i++) {
            // 如果元素第一次出现，则创建一个新的索引列表
            map.computeIfAbsent(nums[i]， v -> new ArrayList<>()).add(i);
        }

        // 计算第一个窗口的美丽值
        result[0] = getBeauty(map, x);

        for (int i = k; i < n; i++) {
            // 移除窗口左侧的旧元素
            List<Integer> indices = map.get(nums[i - k]); // 获取旧元素的索引列表
            indices.remove(indices.size() - 1); // 移除最后一个索引(即窗口左侧的索引)
            if (indices.isEmpty()) {
                // 如果索引列表为空，则从哈希表中移除该元素
                map.remove(nums[i - k]);
            }

            // 添加窗口右侧的新元素
            map.computeIfAbsent(nums[i]， v -> new ArrayList<>()).add(i);

            // 计算当前窗口的美丽值
            result[i - k + 1] = getBeauty(map, x);
        }

        return result;
    }

    private int getBeauty(TreeMap<Integer, List<Integer>> map, int x) {
        int count = 0;
        // 遍历有序哈希表中的条目
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            count += entry.getValue().size(); // 累加当前元素的索引列表大小
            if (count >= x) {
                // 如果累加的大小达到或超过x,说明找到了第x小的元素
                return entry.getKey() < 0 ? entry.getKey() : 0;
            }
        }
        // 如果没有找到第x小的负数，则返回0
        return 0;
    }
}

1. 初始化第一个长度为k的窗口:

   • 我们使用一个for循环遍历数组的前k个元素。
   • 对于每个元素，我们检查它是否第一次出现在有序哈希表中。
   • 如果是第一次出现，我们创建一个新的索引列表，并将当前元素的索引添加到该列表中。
   • 如果元素已经存在，我们直接将当前索引添加到对应的索引列表中。

2. 移动窗口:

   • 我们使用另一个for循环来移动窗口，遍历数组中从第k个元素开始的所有元素。
   • 对于每个新的窗口位置，我们首先需要移除旧元素及其索引。
   • 我们从有序哈希表中获取旧元素的索引列表。
   • 我们移除该索引列表中的最后一个元素，因为它对应着窗口左侧被移除的元素。
   • 如果索引列表变为空，我们从有序哈希表中移除该元素。
   • 然后，我们将新元素及其索引添加到有序哈希表中。
   • 最后，我们调用getBeauty函数计算当前窗口的美丽值，并将结果存储到结果数组中。

3. 计算美丽值:

   • getBeauty函数接受有序哈希表和目标位置x作为参数。
   • 我们使用一个变量count来累加每个元素的索引列表大小。
   • 我们遍历有序哈希表中的所有条目。
   • 对于每个条目，我们将其索引列表的大小累加到count中。
   • 如果count达到或超过x,说明我们找到了第x小的元素。
   • 我们返回该元素的值(如果是负数)或0(如果是非负数)。
   • 如果遍历完整个有序哈希表还没有找到第x小的负数，我们返回0。

这种基于有序哈希表的解法充分利用了TreeMap的有序性质，可以高效地在移动窗口时维护元素的顺序。同时，通过存储索引列表，我们可以在常数时间内移除或添加元素，避免了重复的索引查找操作。