17. 电话号码的字母组合

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

答案

class Solution {List<String> res = new ArrayList();StringBuilder sb = new StringBuilder();public List<String> letterCombinations(String digits) {if(digits.length()==0){return res;}String[] strs = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};deal(digits,0,strs);return res;}void deal(String digits,int startIndex,String[] strs){if(startIndex==digits.length()){res.add(sb.toString());return;}int num = digits.charAt(startIndex) - '0';String str = strs[num];for(int i=0;i<str.length();i++){sb.append(str.charAt(i));deal(digits,startIndex+1,strs);sb.deleteCharAt(sb.length()-1);}}
}

77. 组合

题目

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

答案

class Solution {List<List<Integer>> res = new ArrayList();List<Integer> list = new LinkedList();public List<List<Integer>> combine(int n, int k) {deal(n,1,k);return res;}void deal(int n,int startIndex,int k){if(list.size()==k){res.add(new ArrayList(list));return;}for(int i=startIndex;i<=n;i++){list.add(i);deal(n,i+1,k);list.removeLast();}}
}

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 {List<List<Integer>> res = new ArrayList();List<Integer> list = new LinkedList();boolean[] used;public List<List<Integer>> permute(int[] nums) {used = new boolean[nums.length];deal(nums);return res;}void deal(int[] nums){if(list.size()==nums.length){res.add(new ArrayList(list));return;}for(int i=0;i<nums.length;i++){if(used[i]){continue;}used[i] = true;list.add(nums[i]);deal(nums);used[i] = false;list.removeLast();}}
}

39. 组合总和

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

答案

class Solution {List<List<Integer>> res = new ArrayList();List<Integer> list = new LinkedList();public List<List<Integer>> combinationSum(int[] candidates, int target) {deal(candidates,0,target,0);return res;}void deal(int[] candidates,int startIndex,int target,int sum){if(sum>target){return;}if(sum==target){res.add(new ArrayList(list));}for(int i=startIndex;i<candidates.length;i++){sum += candidates[i];list.add(candidates[i]);deal(candidates,i,target,sum);sum -= candidates[i];list.removeLast();}}
}

22. 括号生成

题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

答案

class Solution {List<String> res = new ArrayList();StringBuilder sb = new StringBuilder();public List<String> generateParenthesis(int n) {deal(n,0,0);return res;}void deal(int n,int openNum,int closeNum){if(sb.length()==2*n){res.add(sb.toString());return;}if(openNum<n){sb.append('(');deal(n,openNum+1,closeNum);sb.deleteCharAt(sb.length()-1);}if(closeNum<openNum){sb.append(')');deal(n,openNum,closeNum+1);sb.deleteCharAt(sb.length()-1);}}
}

108. 将有序数组转换为二叉搜索树

题目

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡二叉搜索树。

答案

class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums==null){return null;}TreeNode res = deal(nums,0,nums.length);return res;}   TreeNode deal(int[] nums,int left,int right){if(right-left<1){return null;}if(right-left==1){return new TreeNode(nums[left]);}int mid = left + (right-left)/2;TreeNode curr = new TreeNode(nums[mid]);curr.left = deal(nums,left,mid);curr.right = deal(nums,mid+1,right);return curr;}
}

23. 合并 K 个升序链表

题目

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

答案

class Solution {public ListNode mergeKLists(ListNode[] lists) {ListNode res = null;for(ListNode curr : lists){res = deal(res,curr);}return res;}//合并两个链表ListNode deal(ListNode p,ListNode q){if(p==null){return q;}if(q==null){return p;}ListNode dummy = new ListNode(0);ListNode tail = dummy;while(p!=null && q!=null){if(p.val<q.val){tail.next = p;p = p.next;tail = tail.next;}else{tail.next = q;q = q.next;tail = tail.next;}}tail.next = (p!=null)? p : q;return dummy.next;}}