今天来看LeetCode21-40题详解
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
归并思想
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy; while(l1 != null && l2 != null){
if(l1.val <= l2.val){
curr.next = l1; l1 = l1.next; }else{
curr.next = l2; l2 = l2.next; } curr = curr.next; } curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
递归
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2); return l1;
}else{
l2.next = mergeTwoLists(l1, l2.next); return l2;
} }
22. 括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例:
输入:n = 3
输出:[ "((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
使用String,每次状态变更都会创建新的对象,不需要状态重置。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
String sb = "";
dfs(n, n, res, sb); return res;
} void dfs(int l,int r, List<String> res, String sb){
if(l == 0 && r == 0){
res.add(sb);
return;
} //保证一旦右括号先出现就停止
if(l > r) return;
if(l > 0) dfs(l - 1, r, res, sb + "(");
if(r > 0) dfs(l, r - 1, res, sb + ")");
}
}
使用StringBuilder,需要状态重置。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
dfs(n, n, res, sb); return res;
} void dfs(int l,int r, List<String> res, StringBuilder sb){
if(l == 0 && r == 0){
res.add(sb.toString());
return;
} if(l > r) return;
if(l > 0){
sb.append("(");
dfs(l - 1, r, res, sb);
sb.deleteCharAt(sb.length() -1);
} if(r > 0) {
sb.append(")");
dfs(l, r - 1, res, sb);
sb.deleteCharAt(sb.length() -1);
} }}
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 = [[]]
输出:[]
提示:
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] 按 升序 排列
- lists[i].length 的总和不超过 10^4
分治+ 归并
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
return merge(lists, 0 , lists.length - 1);
} ListNode merge(ListNode[] lists, int l, int r){ if(l == r) return lists[l];
int mid = l + r >>> 1;
ListNode l1 = merge(lists, l , mid); ListNode l2 = merge(lists, mid + 1, r);
return mergeTwoLists(l1, l2);
} ListNode mergeTwoLists(ListNode l1, ListNode l2){ if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2); return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next); return l2;
} }}
优先队列
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
for (ListNode node: lists) {
if (node != null) {
pq.offer(node); } } ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead; while (!pq.isEmpty()) {
ListNode minNode = pq.poll(); tail.next = minNode; tail = minNode; if (minNode.next != null) {
pq.offer(minNode.next); } } return dummyHead.next;
}}
24. 两两交换链表中的节点
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
for(ListNode p = dummy; p.next != null && p.next.next != null; ){
ListNode a = p.next,b = a.next;
p.next = b;
a.next = b.next;
b.next = a;
p = a; } return dummy.next;
}
25. K 个一组翻转链表
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例:
给你这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
说明:
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
// 区间 [a, b) 包含 k 个待反转元素 ListNode a, b; a = b = head; for (int i = 0; i < k; i++) {
// 不足 k 个,不需要反转,base case if (b == null) return head;
b = b.next;
} // 反转前 k 个元素, 返回的值就是反转之后的head ListNode newHead = reverse(a, b);
// 递归反转后续链表并连接起来 a.next = reverseKGroup(b, k);
return newHead;
} //反转 [head, tail) ListNode reverse(ListNode head ,ListNode tail){
ListNode p = head, pre = null, next = null;
while(p != tail){
next = p.next;
p.next = pre;
pre = p; p = next;
} return pre;
}
26. 删除排序数组中的重复项
给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
public int removeDuplicates(int[] nums) {
if( nums.length == 0) return 0;
//慢指针
int i = 0;
//快指针
for(int j = 1; j < nums.length; j ++){
if(nums[j] != nums[i]) nums[++i] = nums[j];
}
//返回长度
return i + 1;
}
27. 移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
public int removeElement(int[] nums, int val) {
int k = 0;
for(int i = 0; i < nums.length; i ++){
if(nums[i] != val){
nums[k++] = nums[i];
}
}
return k;
}
28. 实现 strStr()
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
class Solution {
public int strStr(String haystack, String needle) {
int m = haystack.length(), n = needle.length();
if (n == 0) return 0;
for(int i = 0;i <= m - n ; i ++){
//if(haystack.substring(i , i + n).equals(needle)) return i;
if(check(haystack.substring(i , i + n), needle)) return i;
} return -1;
} //相当于equals函数 boolean check(String s1, String s2){ int k = 0;
while(k < s2.length()){
if(s1.charAt(k) != s2.charAt(k)) return false;
k ++; } return true;
}}
29. 两数相除
给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。
将被除数和除数都转成正数或负数进行计算,由于在Java中,当t=Integer.MIN_VALUE时(t取相反数依旧是它本身)此时可能存在越界问题,因此都用负数进行计算
//O(N) 时间复杂度 超时
public int divide(int a, int b) {
//特殊情况
if(a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;
//k标识a与b是否同号
boolean k = (a > 0 && b > 0) || (a < 0 && b < 0);
int res = 0;
//转化为负数
a = -Math.abs(a);
b = -Math.abs(b);
//循环减相当于除法操作
while(a <= b){
a -= b;
res ++;
}
return k? res : -res;
}
使用二分法改善,a每次减去2n2n个b,res每次加上2n2n
//O(log(n))
public int divide(int a, int b) {
//特殊情况
if(a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;
//k标识a与b是否同号
boolean k = (a > 0 && b > 0) || (a < 0 && b < 0);
int res = 0;
//转化为负数
a = -Math.abs(a);
b = -Math.abs(b);
//循环减相当于除法操作
while(a <= b){
int temp = b;
int c = 1;
//每次减去2^n
while(a - temp <= temp){
temp = temp << 1;
c = c << 1;
}
a -= temp;
res += c;
}
return k? res : -res;
}
30. 串联所有单词的子串
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。
示例 1:
输入:
s = "barfoothefoobarman",
words = ["foo","bar"]
输出:[0,9]解释:从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2:
输入:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出:[]public List<Integer> findSubstring(String s, String[] words) { List<Integer> res = new ArrayList<>(); int wordNum = words.length; if(wordNum == 0) return res;
int wordLen = words[0].length();
// allWords存储所有单词
HashMap<String, Integer> allWords = new HashMap<>(); for(String w : words) allWords.put(w, allWords.getOrDefault(w, 0) + 1);
// 遍历所有子串
for(int i = 0; i < s.length() - wordNum * wordLen + 1; i ++){
// hasWords存储当前扫描的字符串含有的单词
HashMap<String, Integer> hasWords = new HashMap<>(); int num = 0;
// 判断该子串是否符合
while(num < wordNum){
//每次取一段
String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
if(allWords.containsKey(word)){
hasWords.put(word, hasWords.getOrDefault(word, 0) + 1);
// 判断当前单词的value 和 allWords中该单词的value
if(hasWords.get(word) > allWords.get(word)) break;
}else{
break;
} num ++; } // 判断是不是所有的单词都符合条件
if(num == wordNum) res.add(i);
}
return res;
}
31. 下一个排列
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,31,1,5 → 1,5,1
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
//找到第一个不再递增的位置
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--; } //如果到了最左边,就直接倒置输出 if (i < 0) {
reverse(nums, 0);
return;
} //找到刚好大于 nums[i]的位置 int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--; } //交换 swap(nums, i, j); //利用倒置进行排序
reverse(nums, i + 1);
} private void swap(int[] nums, int i, int j) {
int temp = nums[j];
nums[j] = nums[i]; nums[i] = temp; } private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j); i++; j--; } }
32. 最长有效括号
给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"//")()(" --> 1001
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>(); int n = s.length();
char[] chs = s.toCharArray(); int[] mark = new int[n];
int left = 0, len = 0, ans = 0;
for(int i = 0; i < n; i ++){
if(chs[i] == '(') stack.push(i);
else{
//没有匹配的左括号的右括号,置1
if(stack.isEmpty())mark[i] = 1;
//如果有匹配的左括号,弹出
else stack.pop();
} } // System.out.println(Arrays.toString(mark)); //多余的左括号,置1
while(!stack.isEmpty()){
mark[stack.pop()] = 1;
} //找到最长连续0的长度
for(int i = 0; i < n; i ++){
if(mark[i] == 1){
len = 0;
continue;
} len ++; ans = Math.max(ans , len); } return ans;
}
33. 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1public int search(int[] nums, int target) {
if(nums.length == 0) return -1;
int l = 0, r = nums.length -1;
//找到最小值的索引位置
while(l < r){
int mid = l + r >> 1;
if( nums[mid] <= nums[nums.length -1 ])
r = mid; else
l = mid + 1;
}//此时l == r == k if( target <= nums[nums.length -1])
//[k,len-1]
r = nums.length -1;
else {
//左边那段中寻找[0,k-1]
l = 0;
r --; //因为上面二分完之后找到了第二段的第一个索引,因此r = r-1
} while(l < r){
int mid = l + r >> 1;
if( nums[mid] >= target) r = mid;
else l = mid + 1;
} //二分得出的是第一个>=target的值,需要判断一下是否就是寻找的那个数 if( nums[l] == target) return l;
return -1;
}
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]public int[] searchRange(int[] nums, int t) {
if(nums.length == 0) return new int[]{-1, -1};
int l = 0, r = nums.length -1;
//找第一个数
while(l < r){
int mid = l + r >>> 1;
//假设mid位置为8,前面可能还有,r = mid
if(nums[mid] >= t){
r = mid; }else{
l = mid + 1;
} } //将会二分出大于等于t的第一个数如果不等于t 则不存在 if(nums[r] != t) return new int[]{-1, -1};
int start = r;
l = 0;
r = nums.length -1;
while(l < r){
//这里条件 l = mid, 注意这里向上取整
int mid = l + r + 1 >>> 1;
//找到第一个 <= target的数
if( nums[mid] <= t){
l = mid; }else{
r = mid - 1;
} } int end = r;
return new int[]{start, end};
}
35. 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1public int searchInsert(int[] nums, int target) {
if(nums.length == 0 || nums[nums.length-1] < target) return nums.length;
int l = 0, r = nums.length -1;
//找到 >= target的第一个坐标
while( l < r){
int mid = l + r >> 1;
if( nums[mid] >= target){
r = mid; }else{
l = mid + 1;
} } return r;
}
36. 有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字,空白格用 '.' 表示。
示例 2:
输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
- 一个有效的数独(部分已被填充)不一定是可解的。
- 只需要根据以上规则,验证已经填入的数字是否有效即可。
- 给定数独序列只包含数字 1-9 和字符 '.' 。
- 给定数独永远是 9x9 形式的。
public boolean isValidSudoku(char[][] board) {
// 记录某行,某位数字是否已经被摆放 boolean[][] row = new boolean[9][9];
// 记录某列,某位数字是否已经被摆放 boolean[][] col = new boolean[9][9];
// 记录某 3x3 宫格内,某位数字是否已经被摆放 boolean[][] block = new boolean[9][9];
for(int i = 0; i < 9; i ++){
for(int j = 0; j < 9; j ++){
//.的情况不用考虑
if(board[i][j] == '.') continue;
//数字为1-9
int num = board[i][j] - '1';
//映射到子数独中
int index = i / 3 * 3 + j / 3;
if(row[i][num] || col[j][num] || block[index][num])
return false;
else{
row[i][num] = true;
col[j][num] = true;
block[index][num] = true;
}
}
}
return true;
}
37. 解数独
编写一个程序,通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则:
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
一个数独。
答案被标成红色。
提示:
- 给定的数独序列只包含数字 1-9 和字符 '.' 。
- 你可以假设给定的数独只有唯一解。
- 给定数独永远是 9x9 形式的。
public void solveSudoku(char[][] board) {
boolean flag = dfs(board, 0 ,0);
return;
}
boolean dfs(char[][] board, int i , int j){
if(i == 9) return true;
//到最后一列,换下一行
if(j == 9) return dfs(board, i + 1, 0);
if(board[i][j] != '.') return dfs(board, i , j + 1);
//选择列表1 - 9
for(char c = '1'; c <= '9'; c ++){
if (!isValid(board, i ,j ,c)) continue;
//选择
board[i][j] = c;
//下一层
if (dfs(board, i, j + 1)) return true;
//撤销选择
board[i][j] = '.';
}
return false;
}
boolean isValid(char[][] board , int x , int y ,char n){
for (int i = 0;i < 9; i ++){
//列重复
if (board[i][y] == n) return false;
//行重复
if (board[x][i] == n) return false;
}
//找到九宫格左上元素,依次遍历
for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i ++){
for (int j = y / 3 * 3;j < y / 3 * 3 + 3; j ++){
if (board[i][j] == n) return false;
}
}
return true;
}
38. 外观数列
给定一个正整数 n(1 ≤ n ≤ 30),输出外观数列的第 n 项。
注意:整数序列中的每一项将表示为一个字符串。
「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下:
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1
描述前一项,这个数是 1 即 “一个 1 ”,记作 11
描述前一项,这个数是 11 即 “两个 1 ” ,记作 21
描述前一项,这个数是 21 即 “一个 2 一个 1 ” ,记作 1211
描述前一项,这个数是 1211 即 “一个 1 一个 2 两个 1 ” ,记作 111221
示例 1:
输入: 1
输出: "1"
解释:这是一个基本样例。
示例 2:
输入: 4
输出: "1211"
解释:当 n = 3 时,序列是 "21",其中我们有 "2" 和 "1" 两组,"2" 可以读作 "12",也就是出现频次 = 1 而 值 = 2;类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起,也就是 "1211"。public String countAndSay(int n) {
String s = "1";
//循环n - 1次
for(int i = 0; i < n - 1 ; i ++){
StringBuilder sb = new StringBuilder(); //每一次记录相同一段的个数
for(int j = 0; j < s.length(); j ++){
int k = j;
while(k < s.length() && s.charAt(k) == s.charAt(j)){
k++; } //个数 String count = k - j + "";
//个数 + 字符
sb.append(count + s.charAt(j)); j = k - 1;
} s= sb.toString();
} return s;
}
39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
- 所有数字(包括 target)都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入:candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
https://www.cnblogs.com/summerday152/p/13615904.html
public List<List<Integer>> combinationSum(int[] arr, int t) {
List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>();
Arrays.sort(arr);//排序是剪枝的前提
dfs(res,path,0,arr,t);
return res;
} void dfs(List<List<Integer>> res,List<Integer> path,int s,int[] arr, int t){
if(t <= 0){
if(t == 0){
res.add(new ArrayList<>(path));
} return;
} for(int i = s; i < arr.length; i++){
if(arr[i] > t){ //由于数组已经有序,当前这个数应该小于等于剩余数t
break;
} path.add(arr[i]);
dfs(res,path,i,arr,t-arr[i]); //因为
path.remove(path.size()-1);
} }
40. 组合总和 II
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明:
- 所有数字(包括目标数)都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:[ [1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]public List<List<Integer>> combinationSum2(int[] arr, int t) { List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>();
Arrays.sort(arr);//排序是剪枝的前提
dfs(res,path,0,arr,t);
return res;
} // s 可以看成层数, i可以看成这一层从第几个开始 void dfs(List<List<Integer>> res,List<Integer> path,int s,int[] arr, int t){
if(t <= 0){
if(t == 0){
res.add(new ArrayList<>(path));
} return;
} for(int i = s; i < arr.length; i++){
if(arr[i] > t){ //由于数组已经有序,当前这个数应该小于等于剩余数t
break;
} //保证递归树的同一个层级不出现相同的元素 if(i > s && arr[i] == arr[i - 1]) continue;
path.add(arr[i]);
dfs(res,path,i+1,arr,t-arr[i]);
path.remove(path.size()-1);
} }
如果觉得本文对你有帮助,可以点赞关注支持一下,也可以关注我公众号,上面有更多技术干货文章以及相关资料共享,大家一起学习进步!