lintcode之排列问题

爱被打了一巴掌 2022-07-14 11:17 171阅读 0赞

#### 子集 ####

给定一个含不同整数的集合，返回其所有的子集

#####  注意事项 #####

子集中的元素排列必须是非降序的，解集必须不包含重复的子集

您在真实的面试中是否遇到过这个题？

Yes

样例

如果 S = `[1,2,3]`，有如下的解：

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

class Solution {
        /**
         * @param S: A set of numbers.
         * @return: A list of lists. All valid subsets.
         */
        public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
            // write your code here
            ArrayList<ArrayList<Integer>> res = new ArrayList<>();
            ArrayList<Integer> resItem = new ArrayList<>();
            res.add(resItem);
            if(nums == null){
                return res;
            }
            
            Arrays.sort(nums);
            for(int i = 1; i <= nums.length; i++){
                resItem.clear();
                subsetHelper(res, resItem, 0, i, nums);
            }
            return res;
        }
        
        /**
         * @param res the result
         * @param resItem one of the result 
         * @param pos 第pos个resItem
         * @param number resItem存放几个元素
         * @param nums the input array
         * 
        */
        public void subsetHelper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> resItem, int pos , int number, int[] nums){
            if(number == resItem.size()){
                res.add(new ArrayList<Integer>(resItem));
                return;
            }
            for(int i = pos; i < nums.length; i++){
                resItem.add(nums[i]);
                subsetHelper(res, resItem, i + 1,number,nums);
                resItem.remove(resItem.size() - 1);
            }
            
        }
    }

2、

#### 带重   复元素的子集 ####

#### 给定一个可能具有重复数字的列表，返回其所有可能的子集   注意事项  子集中的每个元素都是非降序的  两个子集间的顺序是无关紧要的  解集中不能包含重复子集  您在真实的面试中是否遇到过这个题？  Yes  样例  如果 S = `[1,2,2]`，一个可能的答案为：  `[ [2], [1], [1,2,2], [2,2], [1,2], [] ]`  ``  `class Solution { /** * @param nums: A set of numbers. * @return: A list of lists. All valid subsets. */ public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] nums) { // write your code here ArrayList<ArrayList<Integer>> res = new ArrayList<>(); ArrayList<Integer> resItem = new ArrayList<>(); res.add(resItem); if(nums == null){ return res; } Arrays.sort(nums); for(int i = 1; i <= nums.length; i++){ resItem.clear(); subsetsWithDupHelper(res , 0, i , resItem, nums); } return res; } /** * @param res the result * @param resItem one of the result * @param pos 第pos个resItem * @param number resItem存放几个元素 * @param nums the input array * */ public void subsetsWithDupHelper(ArrayList<ArrayList<Integer>> res, int pos , int number, ArrayList<Integer> resItem, int[] nums){ if(number == resItem.size()){ res.add(new ArrayList<Integer>(resItem)); return; } for(int i = pos; i < nums.length; i++){ if(i > 0 && i != pos && nums[i] == nums[i-1]){ continue; } resItem.add(nums[i]); subsetsWithDupHelper(res, i + 1, number, resItem, nums); resItem.remove(resItem.size() - 1); } } }`           ####

#### `class Solution { /** * @param nums: A set of numbers. * @return: A list of lists. All valid subsets. */ public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] nums) { // write your code here ArrayList<ArrayList<Integer>> res = new ArrayList<>(); ArrayList<Integer> resItem = new ArrayList<>(); res.add(resItem); if(nums == null){ return res; } Arrays.sort(nums); for(int i = 1; i <= nums.length; i++){ resItem.clear(); subsetsWithDupHelper(res , 0, i , resItem, nums); } return res; } /** * @param res the result * @param resItem one of the result * @param pos 第pos个resItem * @param number resItem存放几个元素 * @param nums the input array * */ public void subsetsWithDupHelper(ArrayList<ArrayList<Integer>> res, int pos , int number, ArrayList<Integer> resItem, int[] nums){ if(number == resItem.size()){ res.add(new ArrayList<Integer>(resItem)); return; } for(int i = pos; i < nums.length; i++){ if(i > 0 && i != pos && nums[i] == nums[i-1]){ continue; } resItem.add(nums[i]); subsetsWithDupHelper(res, i + 1, number, resItem, nums); resItem.remove(resItem.size() - 1); } } }`      ####