做电商的进货网站,北京网站建设外包公司排名,网页游戏交易网站,我们公司想做个网站刷题顺序及思路来源于代码随想录#xff0c;网站地址#xff1a;https://programmercarl.com 目录
77. 组合
216. 组合总和 III
17. 电话号码的字母组合
39. 组合总和
40. 组合总和 II 77. 组合
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的…刷题顺序及思路来源于代码随想录网站地址https://programmercarl.com 目录
77. 组合
216. 组合总和 III
17. 电话号码的字母组合
39. 组合总和
40. 组合总和 II 77. 组合
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
输入n 4, k 2
输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;/*** author light* Description 组合** 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。** 你可以按 任何顺序 返回答案。* create 2023-08-27 10:50*/
public class CombineTest {public static void main(String[] args) {Scanner inputnew Scanner(System.in);int n input.nextInt();int k input.nextInt();System.out.println(combine(n, k));}public static ListListInteger resnew ArrayList(); //存放结果集public static ListInteger pathnew ArrayList(); //存放路径变量public static ListListInteger combine(int n, int k) {backtracking(n,k,1);return res;}//startIndex:记录每层递归数组起始位置---防止数组元素重复---组合private static void backtracking(int n, int k, int startIndex) {if(path.size()k){res.add(new ArrayList(path));return;}//剪枝操作可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。//如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了那么就没有必要搜索了。/*接下来看一下优化过程如下已经选择的元素个数path.size();还需要的元素个数为: k - path.size();在集合n中至多要从该起始位置 : n - (k - path.size()) 1开始遍历为什么有个1呢因为包括起始位置我们要是一个左闭的集合。*/for (int i startIndex; i n-(k- path.size())1; i) {path.add(i);backtracking(n,k,i1);//回溯path.remove(path.size()-1);}}
}216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
输入: k 3, n 7
输出: [[1,2,4]]
解释:
1 2 4 7
没有其他符合的组合了。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;/*** author light* Description 组合总和III** create 2023-08-27 11:18*/
public class CombinationSum3Test {public static void main(String[] args) {Scanner inputnew Scanner(System.in);int n input.nextInt();int k input.nextInt();System.out.println(combinationSum3(k, n));}public static ListListInteger resnew ArrayList();public static ListInteger pathnew ArrayList();public static ListListInteger combinationSum3(int k, int n) {backtracking(k,n,1,0);return res;}private static void backtracking(int k, int n, int startNum,int sum) {if(sumn){return;}if(path.size()k){if(sumn){res.add(new ArrayList(path));}return;}for (int i startNum; i 9-(k- path.size())1 ; i) {path.add(i);sumi;backtracking(k,n,i1,sum);//回溯path.remove(path.size()-1);sum-i;}}
}17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf] import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;/*** author light* Description 电话号码的字母组合* create 2023-08-27 12:15*/
public class LetterCombinationsTest {public static void main(String[] args) {Scanner inputnew Scanner(System.in);String digitsinput.next();System.out.println(letterCombinations(digits));}public static ListString listnew ArrayList();public static ListString letterCombinations(String digits) {if(digitsnull||digits.length()0){return list;}//初始对应所有的数字为了直接对应2-9新增了两个无效的字符串String[] numString {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};backtracking(digits,numString,0);return list;}public static StringBuilder sbnew StringBuilder();private static void backtracking(String digits, String[] numString, int num) {if(numdigits.length()){list.add(sb.toString());return;}String stringnumString[digits.charAt(num)-0];for (int i 0; i string.length() ; i) {sb.append(string.charAt(i));backtracking(digits,numString,num1);sb.deleteCharAt(sb.length()-1);}}
} 39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。
输入candidates [2,3,6,7], target 7
输出[[2,2,3],[7]]
解释
2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。
7 也是一个候选 7 7 。
仅有这两种组合。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;/*** author light* Description 组合总和** create 2023-08-27 15:58*/
public class CombinationSumTest {public static void main(String[] args) {Scanner inputnew Scanner(System.in);int ninput.nextInt();int[] candidatesnew int[n];for (int i 0; i n; i) {candidates[i]input.nextInt();}int target input.nextInt();System.out.println(combinationSum(candidates, target));}public static ListListInteger resnew ArrayList();public static ListInteger pathnew ArrayList();public static ListListInteger combinationSum(int[] candidates, int target) {backtracking(candidates,target,0,0);return res;}private static void backtracking(int[] candidates, int target, int sum, int startIndex) {if(sumtarget){res.add(new ArrayList(path));return;}if(sumtarget){return;}for (int i startIndex; i candidates.length; i) {path.add(candidates[i]);sumcandidates[i];backtracking(candidates,target,sum,i);path.remove(path.size()-1);sum-candidates[i];}}
}40. 组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。
输入: candidates [10,1,2,7,6,1,5], target 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;/*** author light* Description 组合总和II* create 2023-08-27 16:11*/
public class CombinationSum2Test {public static void main(String[] args) {Scanner inputnew Scanner(System.in);int ninput.nextInt();int[] candidatesnew int[n];for (int i 0; i n; i) {candidates[i]input.nextInt();}int target input.nextInt();System.out.println(combinationSum2(candidates, target));}public static ListListInteger resnew ArrayList();public static ListInteger pathnew ArrayList();public static ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);int[] usednew int[candidates.length]; //判断集合重元素是否重复使用Arrays.fill(used,0);backtracking(candidates,target,0,used);return res;}private static void backtracking(int[] candidates, int target,int startIndex,int[] used) {if(target0){res.add(new ArrayList(path));return;}for (int i startIndex; i candidates.lengthtarget-candidates[i]0; i) {//要进行树层去重横向if(i0candidates[i]candidates[i-1]used[i-1]0){continue;}path.add(candidates[i]);target-candidates[i];used[i]1;backtracking(candidates,target,i1,used);path.remove(path.size()-1);targetcandidates[i];used[i]0;}}
}
