外观数列
给定一个正整数 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”。
分析：
水题，我们只需要模拟流程即可，这个流程也很简单，每次直接从前往后枚举即可，枚举的每个小间断寻找一个元素，知道元素内容和个数之后添加到新串后面即可。
对于实现的代码，别用String就行，这里先用了StringBuilder：
public String countAndSay(int n) { if(n==1)return "1"; StringBuilder sBuilder=new StringBuilder("1"); while (--n>0) { StringBuilder s2=new StringBuilder(); int index=1; int i=0; for(i=0;i<sBuilder.length()-1;i++) { if(sBuilder.charAt(i)==sBuilder.charAt(i+1)) index++; else { s2.append(index).append(sBuilder.charAt(i)); index=1; } } s2.append(index).append(sBuilder.charAt(i)); //System.out.println(sBuilder.toString()+" "+i); sBuilder=s2; } return sBuilder.toString(); }
效果的话一般般3ms
class Solution { public String countAndSay(int n) { if(n==1)return "1"; int a[]=new int[5000]; a[0]=1; int b[]=new int[5000]; int len=1; int index=0; while (--n>0) { int num=1; int i=0; for(i=0;i<len-1;i++) { if(a[i]==a[i+1]) num++; else { b[index++]=num; b[index++]=a[i]; num=1; } } b[index++]=num; b[index++]=a[i]; //交换 int team[]=a; a=b; b=team; len=index; index=0; } StringBuilder sBuilder=new StringBuilder(""); for(int j=0;j<len;j++) { sBuilder.append(a[j]); } return sBuilder.toString(); } }
组合总和
题目
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1： 输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ] 示例 2： 输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500
分析，这题的话首先搞懂题意：
- 数组元素不相等
- 数组中任意凑使得数据等于target
- 每个数值可以用任意多次
- 最终的序列不能重复，需要去重或者采取合理措施。
对于这种需要不断试探列举的题，肯定是回溯算法没错了，回溯也是经典dfs算法的一种，在本题的回溯过程中， 需要用一个List储存数值，在回溯向下的过程就加入合法元素，回来之后要把对应元素删除复原。如果当前列表中数值总和和target相等，那么需要将它添加到结果集中。
对于回溯的过程我们应该如何考虑呢，初试状态从0开始，下一次从何开始呢？从当前index开始。因为最终序列不能有重复，所以下一次回溯递归需要从它当前编号开始不能从0开始。
比如 2 3 8 组成8，从2 开始有2 2 2 2，2 3 3,从3开始如果3 2 3或者3 3 2其实都已经重复了，换言之2这个元素作为元素首位已经被使用过，其他在它后面的元素再回溯的时候不需要再经过它，所以从3开始正确应该是3 3 3试探失败3 8试探失败而回去。
思路搞明白之后，直接giao代码就可以了，附上代码：
List<Integer>list=new ArrayList<Integer>();//list用来回溯过程中储存元素 List<List<Integer>> val=new ArrayList<List<Integer>>();//结果 public List<List<Integer>> combinationSum(int[] candidates, int target) { dfs(0,0,candidates,target); return val; } /* * index 表示当前编号 count 表示当前数值的和 */ private void dfs(int index,int count, int[] candidates, int target) { if(target==count) { List<Integer>vaList=new ArrayList<Integer>(); vaList.addAll(list); val.add(vaList); } for(int i=index;i<candidates.length;i++) { if(count+candidates[i]<=target) { list.add(candidates[i]); dfs(i, count+candidates[i], candidates, target); list.remove(list.size()-1); } } }
一发AC还是可以的。
