汽配人网做网站,代理网点,网站被篡改处理,2018做网站站长491. 非递减子序列
给你一个整数数组 nums #xff0c;找出并返回所有该数组中不同的递增子序列#xff0c;递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素#xff0c;如出现两个整数相等#xff0c;也可以视作递增序列的一种特殊情…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 ListInteger path new ArrayList();private ListListInteger res new ArrayList();public ListListInteger 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: 一个ListInteger类型的变量用于存储当前递归路径上的数字即当前正在构建的递增子序列。res: 另一个ListListInteger类型的变量用于存储所有找到的递增子序列。
方法 findSubsequences
功能: 接收一个整型数组nums作为输入返回该数组的所有递增非空子序列。实现: 首先调用backtracking方法启动回溯过程并返回最终结果列表res。
方法 backtracking
输入参数: nums: 整型数组全局输入数据。start: 整型变量表示当前回溯搜索的起始位置避免重复使用已经确定不在子序列中的元素。 功能: 通过回溯算法递归地构建所有递增子序列。
回溯核心逻辑 剪枝: 如果当前路径path的大小超过1意味着至少有两个元素说明找到了一个有效的递增子序列将其添加到结果列表res中。 避免重复: 引入一个整型数组used来标记当前层递归中nums[i]是否已经被使用过以避免生成重复子序列。数组大小为201是因为整数范围为-100到100通过加100映射到数组索引中这样可以使用正数索引简化判断和访问逻辑。 遍历与选择: 从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 {ListListInteger result new ArrayList();// 存放符合条件结果的集合LinkedListInteger path new LinkedList();// 用来存放符合条件结果boolean[] used;public ListListInteger 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: 类型为ListListInteger用于存储所有满足条件的排列结果。path: 类型为LinkedListInteger作为一个临时列表用于在递归过程中暂存当前排列。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中移除回溯到上一层继续尝试其他元素。
综上所述这个程序利用回溯算法深度优先遍历所有可能的排列组合情况有效地解决了给定数组元素的全排列问题。
