算法内容

组合题，类型：数组，回溯，中等难度 组合中和，类型：数组，中等难度 反转链表||，类型：链表，中等难度

第一题组合算法描述

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

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

java代码解答如下

import java.util.*; public class Solution77 { List<List<Integer>> output = new LinkedList<>(); int n; int k; public void traceback(int first, LinkedList<Integer> current) { if (current.size() == k) { output.add(new LinkedList<Integer>(current)); System.out.println(output); return; } for (int i = first; i <= n; i++) { current.add(i); traceback(i + 1, current); current.removeLast(); } } public List<List<Integer>> combine(int n, int k) { this.n = n; this.k = k; traceback(1, new LinkedList<>()); return output; } }

第二题组合总和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]]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5, 所求解集为:[[1,2,2],[5]]

java代码解答如下

class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); List<List<Integer>> res = new ArrayList<List<Integer>>(); if (candidates.length == 0 || target < candidates[0]) return res; List<Integer> tmp = new ArrayList<Integer>(); helper(candidates, target, 0, tmp, res); return res; } public void helper(int[] a, int target, int start, List<Integer> tmp, List<List<Integer>> res) { if (target < 0) return; if (target == 0) { res.add(new ArrayList<Integer>(tmp)); return; } for (int i = start; i < a.length; i++) { tmp.add(a[i]); int newtarget = target - a[i]; helper(a, newtarget, i + 1, tmp, res); tmp.remove(tmp.size() - 1); if (newtarget <= 0) break; while (i + 1 < a.length && a[i] == a[i + 1])// 组合中有重复元素，不要重复开头 i++; } } }

第三题反转链表||算法描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1 输出：[5]

提示：

链表中节点数目为 n 1 <= n <= 500 -500 <= Node.val <= 500 1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

java代码解答如下

class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode pre = dummy; for (int i = 1; i < m; i++) { pre = pre.next; } head = pre.next; for (int i = m; i < n; i++) { ListNode nex = head.next; head.next = nex.next; nex.next = pre.next; pre.next = nex; } return dummy.next; } }