代码随想录-Day29

491. 非递减子序列

给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。

示例 1:
输入:nums = [4,6,7,7]
输出:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2:
输入:nums = [4,4,3,2,1]
输出:[[4,4]]
在这里插入图片描述

class Solution {
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums,0);
        return res;
    }

    private void backtracking (int[] nums, int start) {
        if (path.size() > 1) {
            res.add(new ArrayList<>(path));
        }

        int[] used = new int[201];
        for (int i = start; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
                    (used[nums[i] + 100] == 1)) continue;
            used[nums[i] + 100] = 1;
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

这段代码定义了一个名为Solution的类,该类包含方法用于寻找给定整数数组nums中所有递增的非空子序列。递增子序列是指数组中数字按顺序排列(每个数字可以重复)的子集。以下是代码的详细解析:

类成员变量

  • path: 一个List<Integer>类型的变量,用于存储当前递归路径上的数字,即当前正在构建的递增子序列。
  • res: 另一个List<List<Integer>>类型的变量,用于存储所有找到的递增子序列。

方法 findSubsequences

  • 功能: 接收一个整型数组nums作为输入,返回该数组的所有递增非空子序列。
  • 实现: 首先调用backtracking方法启动回溯过程,并返回最终结果列表res

方法 backtracking

  • 输入参数:
    • nums: 整型数组,全局输入数据。
    • start: 整型变量,表示当前回溯搜索的起始位置,避免重复使用已经确定不在子序列中的元素。
  • 功能: 通过回溯算法递归地构建所有递增子序列。
回溯核心逻辑
  1. 剪枝: 如果当前路径path的大小超过1(意味着至少有两个元素),说明找到了一个有效的递增子序列,将其添加到结果列表res中。

  2. 避免重复: 引入一个整型数组used来标记当前层递归中nums[i]是否已经被使用过,以避免生成重复子序列。数组大小为201,是因为整数范围为-100到100,通过加100映射到数组索引中,这样可以使用正数索引,简化判断和访问逻辑。

  3. 遍历与选择: 从start位置开始遍历nums数组,对于每个元素,执行以下操作:

    • 如果当前路径非空且新元素小于路径尾部元素,或者当前元素在当前层已使用过(由used数组判断),则跳过此次循环继续下一个元素,这是为了保证子序列递增且不重复。
    • 标记当前元素在当前层已使用。
    • 将当前元素加入路径path
    • 以当前位置的下一个元素为起点,进行下一层递归调用。
    • 回溯:从路径中移除最后一个元素,恢复到上一步状态,尝试下一个可能的选择。

最终,当回溯过程完成,所有递增子序列会被收集在res中,并由findSubsequences方法返回。

46. 全排列

给定一个不含重复数字的数组 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]]
在这里插入图片描述

class Solution {

    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0){
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

这段代码定义了一个名为Solution的类,其中主要实现了获取一个整型数组所有可能的排列组合的功能。下面是详细的解析:

类成员变量

  • result: 类型为List<List<Integer>>,用于存储所有满足条件的排列结果。
  • path: 类型为LinkedList<Integer>,作为一个临时列表,用于在递归过程中暂存当前排列。
  • used: 类型为boolean[],标记数组中的元素在当前排列中是否已被使用过,避免重复选择。

方法 permute

  • 功能: 接收一个整型数组nums作为输入,返回该数组所有可能的排列组合。
  • 逻辑:
    • 首先检查输入数组是否为空,若为空直接返回空结果列表。
    • 初始化布尔数组used,长度与输入数组相同,用于记录每个元素的使用状态。
    • 调用辅助函数permuteHelper(nums)来进行实际的排列生成。

方法 permuteHelper

  • 功能: 实现深度优先搜索(DFS)回溯算法来生成所有排列。
  • 逻辑:
    • path的大小等于原数组长度时,说明已经生成了一个完整的排列,将其添加到结果列表result中,然后返回。
    • 对于数组nums中的每个元素,进行以下操作:
      • 若该元素已经在当前排列中使用过(used[i] == true),则跳过,避免重复。
      • 标记该元素为已使用(used[i] = true),将它添加到path中。
      • 递归调用permuteHelper(nums)生成剩余元素的排列。
      • 在递归调用返回后(即处理完以当前元素为固定位置的所有情况),需要“撤销”选择:将used[i]重置为false,并将nums[i]path中移除,回溯到上一层继续尝试其他元素。

综上所述,这个程序利用回溯算法深度优先遍历所有可能的排列组合情况,有效地解决了给定数组元素的全排列问题。

相关推荐

  1. 代码随想Day29

    2024-06-11 23:42:01       15 阅读
  2. 代码随想day21

    2024-06-11 23:42:01       27 阅读
  3. 代码随想day24

    2024-06-11 23:42:01       20 阅读
  4. 代码随想Day24

    2024-06-11 23:42:01       13 阅读
  5. 代码随想Day27

    2024-06-11 23:42:01       13 阅读
  6. 代码随想day27

    2024-06-11 23:42:01       9 阅读
  7. 代码随想day24

    2024-06-11 23:42:01       13 阅读
  8. 代码随想Day28

    2024-06-11 23:42:01       8 阅读

最近更新

  1. shell判断语句练习

    2024-06-11 23:42:01       0 阅读
  2. MySQL周内训参照2、DDL与DML语句

    2024-06-11 23:42:01       0 阅读
  3. Scala学习笔记12: 高阶函数

    2024-06-11 23:42:01       0 阅读
  4. 详解 Flink CDC 的介绍和入门案例

    2024-06-11 23:42:01       0 阅读
  5. Nginx之Stream(TCP/UDP)负载均衡

    2024-06-11 23:42:01       0 阅读
  6. Sklearn简介、安装教程、入门学习

    2024-06-11 23:42:01       0 阅读
  7. Golang - 连接MySQL执行查询脚本

    2024-06-11 23:42:01       0 阅读

热门阅读

  1. Dubbo动态服务下线

    2024-06-11 23:42:01       4 阅读
  2. threading.Lock()互斥锁

    2024-06-11 23:42:01       2 阅读
  3. 内连接和外连接

    2024-06-11 23:42:01       3 阅读
  4. RapidJosn

    RapidJosn

    2024-06-11 23:42:01      4 阅读
  5. C# —— 显示转换

    2024-06-11 23:42:01       3 阅读
  6. springboot接收byte[]字节

    2024-06-11 23:42:01       3 阅读
  7. 深度学习在老年痴呆检测中的应用:数据集综述

    2024-06-11 23:42:01       4 阅读
  8. C语言学习第四天

    2024-06-11 23:42:01       4 阅读