精华内容
下载资源
问答
  • Leetcode 排列组合

    2020-06-17 18:15:44
    给出两个整数n和k,返回从1到n中取k个数字的所有可能的组合 例如: 如果n=4,k=2,结果为 [↵ [2,4],↵ [3,4],↵ [2,3],↵ [1,2],↵ [1,3],↵ [1,4],↵] 思路:基本的搜索题 思路一:递归方式 即返回start ...

    题目描述

    给出两个整数n和k,返回从1到n中取k个数字的所有可能的组合

    例如:

    如果n=4,k=2,结果为

    [↵  [2,4],↵  [3,4],↵  [2,3],↵  [1,2],↵  [1,3],↵  [1,4],↵]

     

    思路:基本的搜索题  

    思路一:递归方式  即返回start end之间 k大小的序列

    返回结果与前一个元素组配即可  相当于子问题求解思路

    缺点:需要组配vetcor向量 带来一定的开销

    vector<vector<int>> fun(int start,int end,int k)  //返回从 start 到 end之间选取K个数的序列
        {
            vector<vector<int>> res;
            if(end-start+1<k)  //无法返回k个数字
                return res;
            if(k==1)
            {
                
                for(int i=start;i<=end;i++)
                {  
                   vector<int> one;
                   one.push_back(i);
                   res.push_back(one);
                }
                return res;//仅仅一个数字
            }
            //思路  确定第一个数字  剩余序列选取余下的k-1个数字
            for(int i=start;i<=end-k+1;i++)
            {
                vector<vector<int>> next=fun(i+1,end,k-1);//剩余的序列组合
                for(int j=0;j<next.size();j++)
                {
                    vector<int> one;
                    one.push_back(i);//第一个数字为i
                    for(int k=0;k<next[j].size();k++)
                        one.push_back(next[j][k]); //组合序列
                    res.push_back(one);
                    
                }
                
                
            }    
            return res;      
        }

     

    思路二:采取dfs搜索方式,引用&方式 设定一个path路径 

    当depth即深度等于k时,将path放入最终结果res中 

    优点:节约空间,同时省去组配vector开销    注意点:dfs返回后需要改回原先path(多结果dfs常见问题)

     void dfs(int start,int end,int depth,vector<int>& road,int k)
        {
            if(depth==k) //完成了k个搜索   
            {
                res.push_back(road);//将该搜索分支加入最终res中
                return;//需要及时返回
            }
            for(int i=start;i<=end-(k-road.size())+1;i++) //当前加入序列的可能元素
            { 
                road.push_back(i);
                dfs(i+1,end,depth+1,road,k);
                road.pop_back();//弹出 
            }
        }
        

     

    展开全文
  • leetCode排列组合/搜索问题 文章目录leetCode排列组合/搜索问题前言一、常见题型1. [子集](https://leetcode-cn.com/problems/subsets/)2.[组合总和](https://leetcode-cn.com/problems/combination-sum/)3.[分割...

    leetCode排列组合/搜索问题


    前言

    很多排列组合问题和搜索问题都题目中常有“所有可能”字样,且很大可能使用深度优先搜索,回溯。


    一、常见题型

    1. 子集

    2.组合总和

    3.分割回文串

    在这些涉及到排列组合的问题中,为避免元素重复使用,可以先给数组排个序。

    其中,分割/切割问题也可以看做排列组合问题(在哪些位置(数字)切)。

    二、关于去重的问题

    为了避免元素重复使用,可以在循环中使用如下语句来选取代表(即在相同元素出现多次时,总是选择第一次出现的,使用这个的前提是数组是有序的):

    if (i !== startIndex && candidates[i] === candidates[i - 1]) {
                    continue;
    }
    

    总结

    在碰到关于搜索所有可能数显的情况的题时,考虑DFS回溯。

    展开全文
  • leetcode 排列组合系列

    2020-08-21 16:27:11
    下面总结一下leetcode中的排列组合问题。 排列 排列问题一般是对原数组进行交换,然后维护一个全局变量的结果集合,每当符合要求将当前状态下的原数组加入到结果集合之中。 题目: 46 全排列 vector<vector<...

    排列组合是回溯算法的经典问题,有固定的模板写法,包括重复元素以及非重复元素。下面总结一下leetcode中的排列组合问题。

    排列
    排列问题一般是对原数组进行交换,然后维护一个全局变量的结果集合,每当符合要求将当前状态下的原数组加入到结果集合之中。

    题目: 46 全排列
    在这里插入图片描述

        vector<vector<int>> res;
        vector<vector<int>> permute(vector<int>& nums) {
            backtrack(nums, 0);
            return res;
    
            
        }
        void backtrack(vector<int> & nums, int depth)
        {
            if(depth==nums.size()) res.emplace_back(nums);
            for(int i=depth;i<nums.size();i++)
            {
                swap(nums[i], nums[depth]);
                backtrack(nums, depth+1);
                swap(nums[i], nums[depth]);
            }
        }
    

    注意,backtrack里面depth表示的是深度,需要不断加1

    题目:47全排列 ||
    在这里插入图片描述
    包含重复元素的序列,需要返回不重复的全排列,如果不从结果出发(使用一个set<vector >保存),需要保证在每一层交换时,不能有两个重复元素别交换到头位置。

        vector<vector<int>> res;
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            // sort(nums.begin(), nums.end());
            backtrack(nums, 0);
            return res;
        }
        void backtrack(vector<int> & nums, int index)
        {
            if(index==nums.size()){
                res.push_back(nums); return ;
            } 
            // 去除重复的关键在于同一深度不能有相同的元素
            unordered_set <int> record;
            
            for(int i = index;i<nums.size();i++)
            {
                // cout << "test " << index << " " << i << endl;
                // 因为换完顺序之后 不能保证index之后的元素其顺序性   如果使用这种不能交换元素
                // for(int j=0;j<nums.size();j++) cout << nums[j] << " ";
                // if(i>index && nums[i]==nums[i-1]) continue;
                
                if(record.find(nums[i])!=record.end()) continue; 
                record.insert(nums[i]);
                swap(nums[i], nums[index]);
                
                backtrack(nums, index+1);
                swap(nums[i], nums[index]);
    
                
                
            }
        }
    

    组合
    组合问题与排列问题不同,原数组是不能进行删除操作的,需要手动维护一个当前结果的序列(一般使用vector),然后每个元素都有添加与不添加两种选择。

    这里的depth表示选择哪个元素 不再表示深度

    在这里插入图片描述经典的组合问题, 无重复元素,不重复解。
    需要注意的是数字可以无限制被选取。

    无重复元素意味着不需要对每个选择的元素进行判断

    无限制选取意味着下一次还可以从当前元素选起

        vector<vector<int>> ans;
        
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<int> vc;
            // sort(candidates.begin(), candidates.end());
            backtrack(candidates, vc, target,0);
            return ans;
    
            
        }
    
        void backtrack(vector<int> & candidates, vector<int> & vc, int target, int index)
        {
            if(target==0){
                ans.emplace_back(vc);
                return;
            }
            if(target < 0) return;
            for(int i=index;i<candidates.size();i++)
            {
                vc.push_back(candidates[i]);
                // 下标下标下标
                backtrack(candidates,vc,target-candidates[i],i);
                vc.pop_back();
            }
        }
    

    题目 40 组合总数||
    在这里插入图片描述
    重复元素: for循环里面不能选择相同的元素
    每个元素只能使用一次: 回溯函数选择一个元素i之后,下次递归时下标为i+1

        vector<vector<int>> res;
        vector<int> vc;
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            // N = candidates.size();
            // vector<bool> visited(N, false);
            // memset(visited, false, (N)*sizeof(bool));
            backtrack(candidates, target, 0);
            return res;
    
            
        }
        // 下一次元素位置位于i+1位置
        void backtrack(vector<int> candidates, int target, int index)
        {
            if(target==0) {
                res.push_back(vc);
                return;
            }
    
            for(int i=index;i<candidates.size();i++)
            {
                // 利用升序性质
                if(target-candidates[i]<0) break;
                if(i>index && candidates[i] == candidates[i-1]) continue;
                vc.push_back(candidates[i]);
                backtrack(candidates, target-candidates[i], i+1);
                vc.pop_back();
            }
    

    需要先进行一次排序,方便for循环里面根据前后元素大小去除重复解。
    然后另外需要注意的就是递归的时候下标为i+1.

    题目: 216 组合总和 |||
    在这里插入图片描述
    题目分析:本体本质上还是组合问题,但是需要注意的是引入了深度,需要根据判断是否找到解。
    还有一点就是没有一个可操作数组,直接使用index同时代表下标以及数值即可

        vector<vector<int>> res;
        vector<int> vc;
        vector<vector<int>> combinationSum3(int k, int n) {
            backTrack(1, n, k, 0);
            return res;
    
        }
        // index表示选择的起始值, depth表示当前深度用于判断是否到达k
        void backTrack(int index,int target, int k, int depth)
        {
            if(target==0)
            {
                if(depth==k)
                {
                    res.push_back(vc);
                    
                }
                return;
            }
            if(target<0 || depth> k) return;
            for(int i=index; i<=9;i++)
            {
                vc.push_back(i);
                backTrack(i+1, target-i, k, depth+1);
                vc.pop_back();
            }
        }
    

    题目:377 组合总和IV
    在这里插入图片描述
    题目分析:

    不限制选择次数,那么只要保证每次选择的不是同一个数字,那么最后得到的就是不同解。
    与前面的组合问题区别在于, 1 1 2 与 1 2 1算是两种不同解,这样就没有顺序之分了。
    

    记忆化递归解法:

        unordered_map<int, int> map;
        int combinationSum4(vector<int>& nums, int target) {
            return backTrack(nums, target);
        }
        int backTrack(vector<int> & nums,  int target)
        {
            if(target==0) {
                return 1;
            }
            if(target < 0) return 0;
            if(map.find(target)!=map.end()) return map[target];
            int sum = 0;
            for(int i=0;i<nums.size();i++)
            {
                
                sum +=backTrack(nums, target-nums[i]);
            }
            map[target] = sum;
            return sum;
        }
    

    动态规划解法:

        // 完全背包问题
        int combinationSum4(vector<int>& nums, int target) {
            unsigned long long dp[target+1];
            memset(dp, 0,sizeof(dp));
            dp[0] = 1;
            for(int i=1;i<=target;i++)
            {
                for(int j=0;j<nums.size();j++)
                {
                    if(nums[j]<=i)
                    {
                        dp[i] += dp[i-nums[j]];
                    }
                }
            }
            return (int)dp[target];
        }
    

    排列变种:

    题目: 31下一个排列

    在这里插入图片描述
    题目分析:
    根据当前的排列,1 2 3-> 1 3 2等 ,如果想求出下一个排列,肯定是想让更大的数字能够提前一些与前面的小数进行交换。问题是怎么能够刚好能够比当前排列大一点点呢?
    希望下一个数增加的幅度尽可能小,那么就需要

    1. 尽可能在靠右的位置进行交换,从后往前查找这个位置
    2. 将一个尽可能小的大数字与前面的小数进行交换 1 2 3 4 6 5 应该将5 与4 进行交换,而不是6
    3. 将大数字换完之后,后面的数字需要从小到大排列。

    转化为算法的思想就是:
    4在这里插入代码片. 从后往前查找第一个相邻的升序对,满足A[i-1] < A[i]
    5. 在i之后的元素中找到最小的可以满足大于A[i-1]的元素,与A[i-1]进行交换
    6. 将i-1与end之间的元素进行reverse

        void nextPermutation(vector<int> & nums)
        {
            int l = nums.size()-1;
            // 找到第一个逆序 0 1 5 4 3
            while(l>=1 && nums[l] <= nums[l-1])
            {
                l--;
            }
            // l-1之后是降序序列 
            reverse(nums.begin()+l, nums.end());
            if(l>0)
            {
                for(int i=l;i<nums.size();i++)
                {
                    if(nums[i]>nums[l-1]) {
                        swap(nums[i], nums[l-1]);
                        break;
                    }
                }
            }
        }
    

    题目:60 第k个排列
    在这里插入图片描述
    题目分析:
    m个元素的排列个数为m!个,题目给定n个元素以及求解的第k个排列。
    根据 k-1/(n-1)!的值,可以确定排列中的第一个元素。
    比如 k = (n-1)! 时, 此时第一个元素应该是1,而不是2,这就是为什么提前k-1的原因。
    然后k%=(n-1)!,重复操作直到求解出n个元素的值。
    需要注意的一点是: 在取元素的时候需要不断将已确定的元素删除掉

        string getPermutation(int n, int k)
        {
            int f[10];
            f[0] = 1;
            for(int i=1;i<=n;i++) f[i] = i*f[i-1];
            string s = "123456789";
            return getkPermutation(s, k, f, n);
    
        }
        string getkPermutation(string &s,int k, int f[],  int n)
        {
            // 小于结果的有k-1个 
            k = k -1;
            string res = "";
            for(int i=n-1;i>=0;i--)
            {
                int base = f[i];
                int index = k/base;
                
                k = k%base;
                res+=s[index];
                s.erase(s.begin()+index);
            }
            return res;
        }
    

    题目:leetcode 回文全排列||
    在这里插入图片描述
    题目分析:
    统计字符串中字符出现次数,等奇数个数超过1的时候,表示不能有回文串。
    对于偶数次数的字符,应该是一半位于左侧,一半位于右侧,将字符加入空字符串中,加入num/2次,num为出现次数。
    然后就是重复元素的全排列问题。

    vector<string> res;
    void permute(string t, int depth, string mid)
    {
    	if(depth==t.size())
    	{
    		res.push_back(t+mid+string(t.rbegin(), t.rend()));
    		return;
    	}
    	unordered_set<char> set;
    	for(int i=depth;i<t.size();i++)
    	{
    		if(set.find(t[i])!=set.end()) continue;
    		set.insert(t[i]);
    		swap(t[i],t[depth]);
    		permute(t,depth+1,mid);
    		swap(t[i],t[depth]);
    	}
    	
    }
    
    
    vector<string> generatePalindroms(string s)
    {
    	unordered_map<char, int> map;
    	int count = 0;// 奇数个数
    	for(auto a:s) ++map[a];
    	string mid = "";
    	string t = "";
    	for(auto item: map)
    	{
    		if(item.second%2==1) mid+=item.first;
    		else t+=string(item.second/2, item.first);
    		if(mid.size() > 1) return{};
    	}
    	
    	permute(t, 0, mid);
    	return res;
    		
    	
    } 
    
    展开全文
  • class Solution { public: vector<vector<int>> outer; vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<int>...
  • LeetCode排列组合问题合集

    千次阅读 2017-07-16 15:11:43
    算法思想:往当前已有的组合中添加 for ( int i : nums) { List<List<Integer>> tmp = new ArrayList(); for (List<Integer> a : result) { List<Integer> sub = new ArrayList(a); sub .add(i); ...

    78. Subsets

    Given a set of distinct integers, nums, return all possible subsets.
    给定一组非重复数字,求出所有可能的子集

    解析:

    例如 [1,2,3],解法:
    首先放[],然后往已有的[]中放1
    1. 首先放1
    此时已有[ [], 1 ]
    2. 然后对[ [], 1 ] 放2
    于是此时有 [ [], [1], [2], [1,2] ]
    3. 然后对[ [], [1], [2], [1,2] ] 放3
    此时[ [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] ] 求出解

    算法

    public class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            result.add(new ArrayList<Integer>());
    
            Arrays.sort(nums);
            //算法思想:往当前已有的组合中添加
            for (int i : nums) {
                List<List<Integer>> tmp = new ArrayList<>();
                for (List<Integer> a : result) {
                    List<Integer> sub = new ArrayList<>(a);
                    sub.add(i);
                    tmp.add(sub);
                }
                result.addAll(tmp);
            }
            return result;
        }
    }
    展开全文
  • class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list = new ArrayList<>... if(nums == null || nums.length == 0){ ...}
  • leetcode上关于数字排列组合问题有四个,分别是: (1)Next Permutation :已知一个数组代表某个排列组合,求出比其代表的数字大的下一个排列组合,通过重组数组中的数字实现 (2)Permutations:已知一组数字,求...
  • leetcode-排列组合问题

    2020-11-05 23:05:17
    1.无重复字符串的排列组合-面试题 08.07-简单 无重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合,字符串每个字符均不相同。 输入:S = “qwe” 输出:[“qwe”, “qew”, “wqe”, “weq”, ...
  • class Solution { public: vector<vector<int>>ans; vector<vector<... combine(int n, int k) { ... // 遍历可能的搜索起点,这里i的上限可以从n优化至n - (k - path.size()) + 1,因为是选择起点,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,821
精华内容 3,528
关键字:

leetcode排列组合