LeetCode刷题日志（三）

分手后的思念是犯贱 2022-02-27 12:52 260阅读 0赞

之前看的是链表的问题，现在主要是研究关于递归的问题，对初学者来说递归问题的理解是比较困难的。我也是通过一些问题的逐步分析来进行判断和理解。

这篇博客主要是针对leetcode的某一类问题进行分析。这些是关于组合求和的问题

**目录**

1.组合总和

2.组合总和 II

3.电话号码的字母组合

--------------------

# 1.组合总和 #

给定一个**无重复元素**的数组 `candidates` 和一个目标数 `target` ，找出 `candidates` 中所有可以使数字和为 `target` 的组合。

`candidates` 中的数字可以无限制重复被选取。

**说明：**

*  所有数字（包括 `target`）都是正整数。
 *  解集不能包含重复的组合。

这道问题，首先来看解集不能包含重复的组合而且每个数字可以重复使用，题目给了一个示例。

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

首先，我们将这个数组进行排序。为了保证不出现重复的组合，我们在以2为首元素的时候，只考虑2，3和,5。同理向后递推，以3为首元素的时候，只考虑3，5.。每次将数组中的数字放入栈中，如果发现当前的和与target相同，就将栈中的元素进行遍历。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    	        List<List<Integer>> result = new ArrayList<List<Integer>>();
    	        if(candidates.length == 0)
    	        	return result;
    	       Arrays.sort(candidates);
    	        Stack<Integer> stack = new Stack<Integer>();
    	        generate(0,result,stack,0,target,candidates);
    	        return result;
    	    }

主函数如上，如果数组为空，返回一个空的链表。

算法的核心是generate方法。

private void generate(int i, List<List<Integer>> result, Stack<Integer> stack, int sum, int target,int[] candidates) {
    		if(i==candidates.length || sum > target)//不符合条件循环结束
    			return ;
    		if(sum == target){
    			List<Integer> list  = new ArrayList<Integer>();
    			for(Integer num : stack){
    				list.add(num);
    			}
    			result.add(list);
    		}
    		for(int index = i;index<candidates.length;index++){
    			stack.push(candidates[index]);
    			generate(index,result,stack,sum+candidates[index],target,candidates);
    			stack.pop();
    		}
    	}

这个函数也是调用了递归的思想，sum用来记录当前栈中的数值总和。如果发现遍历到了数组的末尾或者发现和超过了target，那么此次方法调用返回。接下来。如果sum和target相同，那么直接将栈中的值遍历插入链表中。

可以看到接下里的for循环就是将数组中index位置的数字放入栈中，然后递归下一个数字（因为可以重复，所以下一次递归调用也是从index开始的）。如果跳出了递归函数（generate方法）。说明放入的数字导致sum值过大，所以将栈顶元素进行弹出。

## 2.组合总和 II ##

给定一个数组 `candidates` 和一个目标数 `target` ，找出 `candidates` 中所有可以使数字和为 `target` 的组合。

`candidates` 中的每个数字在每个组合中只能使用一次。

**说明：**

*  所有数字（包括目标数）都是正整数。
 *  解集不能包含重复的组合。

与上题不同，数组中包含重复数字，同样解集不可以重复。所以在递归调用的时候需要对传入的index值进行判断。这道题和上一道题的思路相同，所以把代码先写出来。

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            	List<List<Integer>> result = new ArrayList<List<Integer>>();
            	if(candidates.length == 0)
            		return result;
            	Arrays.sort(candidates);
            	Stack<Integer> stack = new Stack<Integer>();
            	backTrace(0,candidates,target,0,result,stack);
            	return result;
        }
    	private void backTrace(int index, int[] candidates, int target, int sum, List<List<Integer>> result,Stack<Integer> stack) {
    		if(index >candidates.length || sum>target)
    			return ;
    		if(sum == target){
    			List<Integer> list = new ArrayList<Integer>();
    			for(Integer num : stack){
    				list.add(num);
    			}
    			result.add(list);
    			System.out.println(list);
    		}
    		for(int i = index;i<candidates.length;i++){
    			if(sum+candidates[i] > target)
    				break;
    			if(i > index && candidates[i] == candidates[i-1])
    				continue;
    			stack.push(candidates[i]);
    			backTrace(i+1, candidates, target, sum+candidates[i], result, stack);
    			stack.pop();
    		}
    }

我将核心的for循环部分粘贴出来

for(int i = index;i<candidates.length;i++){
    			if(sum+candidates[i] > target)
    				break;
    			if(i > index && candidates[i] == candidates[i-1])
    				continue;
    			stack.push(candidates[i]);
    			backTrace(i+1, candidates, target, sum+candidates[i], result, stack);
    			stack.pop();
    		}

首先这个数组是经过排序的，所以发现sum+candidates\[i\]超过target，那么就没有必要去遍历i之后的元素了。因为一定会只有的值和sum相加也一定会超过target（整个数组是递增的）。

其次，关于第二个if条件是为了防止重复。参考实例

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

这个数组排序后位1,1,2,5,6,7,10。target为8.当我们判断了1（index=0）和7 为结果之后。i=index=0时的backTrace方法执行完毕。此时i++为1，这个时候i>index且candidates\[1\] = candidates\[0\]。这个时候如果考虑这个1，那么就会和之后的7再次组成结果。为了防止重复，使用了这个if判断。其他的就和上道题完全相同了。

## 3.电话号码的字母组合 ##

给定一个仅包含数字 `2-9` 的字符串，返回所有它能表示的字母组合。

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

![200px-Telephone-keypad2.svg.png][]

**示例:**

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

这道题和上面两道题的思路是相通的，只不过这道题很类似于掷骰子的问题

就像将A数组中n个数和B数组中的m个数还有C数组中的j个数进行全排列得到n\*m\*j个结果。

public List<String> letterCombinations(String digits) {
    		  List<String> result = new ArrayList<String>();
    		  if(digits == null||"".equals(digits))
    			  return result;
    		  char[][] dictionary =  {
    				  {},{},
    				  {'a','b','c'},{'d','e','f'},{'g','h','i',}
    				  ,{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}	  
    		  };
    		  char[] digs = digits.toCharArray();
    		 
    		  Set<String> set = new HashSet<String>();
    		  Stack<Character> item = new Stack<Character>();
    		  generate(0,dictionary,digs,result,set,item);
    		  return result;
    	    }
    	private void generate(int i,char[][] dictionary, char[] digs, List<String> result, Set<String> set,  Stack<Character> item) {
    		if(i>=digs.length){
    			if(!set.contains(item)){
    				String s = "";
    				for(Character c : item){
    					s+=c;
    				}
    				set.add(s);
    				result.add(s);
    			}
    			return ;
    		}
    		int num = Integer.valueOf(digs[i])-'0';//找到对应字典中的位置
    		for(int j = 0;j<dictionary[num].length;j++){
    			item.push(dictionary[num][j]);
    			generate(i+1, dictionary, digs, result, set, item);
    			item.pop();
    		}
    	}

主要的方法依旧是generate方法。其中的i表示第i个数字，也就是将第i个数字从字典中找到合适的字符数组进行遍历。

j就是从第i个数字对应的字典中的数组进行遍历。思路和上面两道题完全相同，只不过这道题在加入结果的时候需要去重，因为给定的digits可能会出现重复的数字，因此我采用了一个set进行了去重。

[200px-Telephone-keypad2.svg.png]: /images/20220227/5fc7f35c542a4910b7f74a101bafc373.png