LeetCode解题报告—— Combination Sum & Combination Sum II & Multiply Strings

2022-09-19 12:39:14

1. Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is:

[

  [7],

  [2, 2, 3]

]

解析：从一组不重复的数字中选择若干个，和为指定的数字，注意单个数字能重复选择，找出所有这种组合。一个可行的想法是利用递归的思想来解决，每当选一个值 a 后，剩下的是如何从数字组中找出和为 target-a 的组合，其实是相同的问题。

基本递归思路：保持一个“全局”的 List<List<integer>> 用于存储符合条件的数字对 ——> 保持一个临时存储遍历到的数字对的集合 tempList ——> 用一个remain来记录target减去临时数字集合后剩下的值，用一个start来记录数组递归遍历的开始位置 ——> 从数组的第一位开始递归遍历，将数字加入到临时集合中，这个时候判断 remain的正负，如果小于0表明这个值不应该加入到当前的 tempList中，直接跳出，返回到上一层递归；如果等于0，则表明当前的tempList中的数字对之和正好为target，直接加入到 List<List<integer>> 中；如果大于0则继续向下递归。

import java.util.*;

public class LeetCode{

    public static void main(String[] args){

        Scanner sc=new Scanner(System.in);

        String input=sc.nextLine().replaceAll("\\]|\\[| ","");  //这里 ] 好像一定要在 [ 的前面，要不然不能正确替换

        int target=sc.nextInt();

        String[] strs=input.split(",");

        int[] nums=new int[strs.length];

        for(int i=0;i<strs.length;i++)

            nums[i]=Integer.parseInt(strs[i]);　　//对于char可以直接减字符0转为整数但是对于String是不行的

        List<List<Integer>> list=new ArrayList<>();

        backtrack(list, new ArrayList<Integer>(), nums, target,0);

        for(List<Integer> i:list){

            for(int a:i)

                System.out.print(a+" ");

            System.out.println();

        }

    }

    public static void backtrack(List<List<Integer>> list, List<Integer> tempList,int[] nums, int remain, int start){

        if(remain<0) return;

        else if(remain==0) list.add(new ArrayList<>(tempList));　　//以tempList中的数字实例化新的List再放入到集合中，不能直接放tempList

        else{

            for(int i=start;i<nums.length;i++){

                tempList.add(nums[i]);

                backtrack(list,tempList,nums,remain-nums[i],i);　　//i不加1是因为能再选nums[i]

                tempList.remove(tempList.size()-1);

            }

        }

    }

}

关于上面学到的一点是，如果往集合里加集合，那么加入的貌似是它的引用。试了先将 List<List<integer>> 中加入一个空的List<Integer>, 之后这个List<Integer>怎么改变，原List<List<Integer>>也会改变。这也解释了为什么每次要以tempList中的数字实例化新的List再放入到集合中，而不能直接放tempList。

2. Combination Sum II

上面题目的一种变体，区别就是数字不能重复选择了。

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,

A solution set is:

[

  [1, 7],

  [1, 2, 5],

  [2, 6],

  [1, 1, 6]

]

解法和上面的类似：

import java.util.*;

public class LeetCode{

    public static void main(String[] args){

        Scanner sc=new Scanner(System.in);

        String sc_r=sc.nextLine().replaceAll("\\]| |\\[","");

        int target=sc.nextInt();

        String[] scs=sc_r.split(",");

        int[] array=new int[scs.length];

        for(int i=0;i<scs.length;i++){

            array[i]=Integer.parseInt(scs[i]);

        }

        List<List<Integer>> res=combinationsSum2(array,target);

        for(List<Integer> list:res){

            for(int a:list)

                System.out.print(a+" ");

            System.out.println();

        }

    }

    static List<List<Integer>> combinationsSum2(int[] cand, int target){

        Arrays.sort(cand);

        List<List<Integer>> res=new ArrayList<List<Integer>>();

        List<Integer> path=new ArrayList<Integer>();

        dfs_com(cand,0,target,path,res);

        return res;

    }

    static void dfs_com(int[] cand, int cur, int target, List<Integer> path, List<List<Integer>> res){

        if(target==0){

            res.add(new ArrayList(path));

            return;

        }

        if(target<0)return;

        for(int i=cur;i<cand.length;i++){

            if(i>cur&&cand[i]==cand[i-1]) continue;

            path.add(path.size(),cand[i]);

            dfs_com(cand,i+1,target-cand[i],path,res);

            path.remove(path.size()-1);

        }

    }

}

3. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

  1. The length of both num1 and num2 is < 110.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

思路：这题的要求很明显，就是对字符串形式的两个数字，不实用内置的字符串转整数方法来实现两者之间的乘法。基本思路是现将字符串转为数字数组，再观察下乘法的规律，当然了，涉及到数组，那么就要找到单个数字乘法与数组索引之间的规律。一个重点是：

Start from right to left, perform multiplication on every pair of digits, and add them together. Let’s draw the process! From the following draft, we can immediately conclude:

 num1[i] * num2[j] will be placed at indices [i + j, i + j + 1]

LeetCode解题报告—— Combination Sum & Combination Sum II & Multiply Strings

找到了这个规律，那么便可以使用两层循环来实现乘法，数字和数字相乘时，和应该是乘积加上一轮循环计算中得到的相应位置低位值，然后分别利用除法和取余来更新高位和低位的数字，注意这里高位还要加上原有位置计算得到的值。

import java.util.*;

public class LeetCode{

    public static void main(String[] args){

        Scanner sc=new Scanner(System.in);

        String num1=sc.nextLine();

        String num2=sc.nextLine();

        System.out.println(multiply(num1,num2));

    }

    static String multiply(String num1, String num2){

        int m=num1.length(),n=num2.length();

        int[] pos=new int[m+n];

        for(int i=m-1;i>=0;i--){

            for(int j=n-1;j>=0;j--){

                int mul=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');

                int p1=i+j,p2=i+j+1;

                int sum=mul+pos[p2];

                pos[p1]+=sum/10;　　//高位是除法后加上上一次循环时得到的高位的值

                pos[p2]=sum%10;　　 //低位直接取余

            }

        }

　　　// 将pos数组转为字符创，不要前面的0

        StringBuilder sb=new StringBuilder();

        for(int p:pos)if(!(sb.length()==0&&p==0)) sb.append(p);　　//去除pos数组中前面的0，一开始当sb中没有值并且遇到的是数组中前面的0时，不将数字放入到sb中

        return sb.length()==0? "0":sb.toString();

    }

}
上一篇：【LeetCode】43. Multiply Strings 解题报告（Python & C++）


下一篇：【LeetCode】43. Multiply Strings