找出所有相加之和是 n 的 k 个数的组合。组合中只含有 0~9的正整数,且保证每种组合中不含有相同的数字。 保证一定有解。结果按字典序升序输出。-笔试面试资料

这是qklbishe.com第19149 篇笔试面试资料
提供答案分析,通过本文《找出所有相加之和是 n 的 k 个数的组合。组合中只含有 0~9的正整数,且保证每种组合中不含有相同的数字。 保证一定有解。结果按字典序升序输出。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

找出所有相加之和是 n 的 k 个数的组合。组合中只含有 0~9的正整数,且保证每种组合中不含有相同的数字。
保证一定有解。结果按字典序升序输出。
Java

找出所有相加之和是 n 的 k 个数的组合。组合中只含有 0~9的正整数,且保证每种组合中不含有相同的数字。    保证一定有解。结果按字典序升序输出。 零葬

为了按字典序升序输出结果,那么我们给候选集的时候就给个有序的,然后从左往右尝试取数凑目标值,而凑数采用经典的回溯算法就好。

import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param k int整型       * @param n int整型       * @return int整型二维数组      */     ArrayList<ArrayList<Integer>> results = new ArrayList<>();     int[] candicates = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};     public int[][] combination (int k, int n) {         // write code here         boolean[] used = new boolean[9];         dfs(n, k, 0, used, new ArrayList<>());         int[][] res = new int[results.size()][];         for(int i = 0; i < res.length; i++){             res[i] = new int[results.get(i).size()];             for(int j = 0; j < results.get(i).size(); j++){                 res[i][j] = results.get(i).get(j);             }         }         return res;     }          private void dfs(int rest, int k, int depth, boolean[] used, ArrayList<Integer> path) {         if(rest < 0){             return;     // 凑过头了,本次组合无效         }         if(path.size() == k){             // 够k个数且凑足目标值了就添加答案             if(rest == 0){                 results.add(new ArrayList<>(path));             }         }else{             for(int i = depth; i < candicates.length; i++){                 if(used[i]) continue;                 used[i] = true;                 path.add(candicates[i]);                 dfs(rest - candicates[i], k, i + 1, used, path);                 // 回溯                 used[i] = false;                 path.remove(path.size() - 1);             }         }     } }

今天 11:54:14 回复(0)
C++

找出所有相加之和是 n 的 k 个数的组合。组合中只含有 0~9的正整数,且保证每种组合中不含有相同的数字。    保证一定有解。结果按字典序升序输出。 区块链毕设学生438919385号

要求是每种组合中不含有相同的数字,结果按字典序升序输出。
那么结果组合中,必定是升序排列,一个数字至少比前一个大1。
假设第一个数字是i,k个数,和是n,判断后续能否有合法组合的条件就是
(i+1) + (i+2) + … + ((i+1)+(k-1)) <=n-i,这样才能保证后续有合法组合。
class Solution { public:     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param k int整型       * @param n int整型       * @return int整型vector<vector<>>      */     vector<vector<int> > combination(int k, int n) {         lst.resize(k);                  serchCombin(k, n, 1);                  return result;     }      private:     vector<vector<int> > result;     vector<int> lst;     int idx=0;     void serchCombin(int k, int n, int start) {         if(1==k) {             lst[idx]=n;             result.push_back(lst);             return;         }         --k;         for(int i=start;((i+1)+(i+1+k-1))*k/2<=(n-i);++i) {             lst[idx++]=i;             serchCombin(k, n-i, i+1);             --idx;         }     } };

今天 10:17:47 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 找出所有相加之和是 n 的 k 个数的组合。组合中只含有 0~9的正整数,且保证每种组合中不含有相同的数字。 保证一定有解。结果按字典序升序输出。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情