牛客网算法——名企高频面试题143题（12）

1.给一个数组和目标值，求数组中和为目标值的所有组合，数组中每个值可以重复使用。

比如：数组【2，3，6，7】，目标值7

所有组合：【2，2，3】，【7】

package 复现代码;

import java.util.*;

/**
 * @Classname Main
 * @Description TODO
 * @Date 2020/12/20 13:31
 * @Created by xjl
 */
public class 目标值和dfs {
    static ArrayList list = new ArrayList();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int target = sc.nextInt();
        int[] num = new int[m];
        for (int i = 0; i < m; i++) {
            num[i] = sc.nextInt();
        }
        ArrayList res = combinationSum2(num, target);
        for (ArrayList li : res) {
            for (int i : li) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
        System.out.println(res.size());
    }

    public static ArrayList combinationSum2(int[] num, int target) {
        ArrayList ls = new ArrayList();
        if (num == null || num.length == 0) {
            return list;
        }
        Arrays.sort(num);
        dfs(num, 0, target, ls);
        return list;
    }

    private static void dfs(int[] arr, int index, int sum, ArrayList ls) {
        if (sum < 0) {
            return;
        }
        if (sum == 0 && !list.contains(ls)) {
            list.add(new ArrayList(ls));
            return;
        }
        for (int i = index; i < arr.length; i++) {
            ls.add(arr[i]);
            dfs(arr, i + 1, sum - arr[i], ls);
            ls.remove(ls.size() - 1);
        }
    }
}

反转链表

package 复现代码;

/**
 * @Classname 反转链表II
 * @Description TODO
 * @Date 2020/12/21 12:56
 * @Created by xjl
 */
public class 反转链表II {
    public class ListNode {
        int val;
        ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }


    public ListNode rever(ListNode head){
        if (head==null){
            return null;
        }
        ListNode pre=null;
        ListNode curr=head;
        while (curr!=null){
            ListNode future=curr.next;
            curr.next=pre;
            pre=curr;
            curr=future;
        }
        return pre;
    }
}