|
给定一组数字，相邻两个数组组合，组合的数不能超过26.问有多少种组合。 |
|
|
没太明白题意, lz想说只有两个相邻 的数才可以组合吗?
比如 2345, 可以有2, 3, 4, 5, 23, 34, 45,…..但是24就算错误？ 那lz可以直接排序, 然后从第一个数开始输出连续一个, 连续两个:
for(int i=0; i<a.length. ++i){ // 确定输出上界
for(int j=i; j<a.length; ++j){ // 确定输出下界
if( i - j >= 26 ){
break;
}
for(int k=i; k<=j; ++k){ // 输出i, j直接的内容
System.out.println(a[k]);
}
}
}
或者向2, 3, 4, 5, 23, 34, 45,…这样,先输出长度为一的,在输出长度为二的….只有有一定规律就行 |
|
|
2345的组合只能是{2,3,4,5}，{23,45}，{2,3,45}，{2,34,5}，{23,4,5}，但是其中第2,3,4种有超过26的元素。不符合要求。只有第1,5两种组合成立 |
|
|
说一个思路，如果有bug的话告诉我一声，我也没考虑全面:
首先，解决一个问题，就是说一串数究竟能有多少1位和两位数的组合方式。（后面均是建立在相邻的基础上）设里面有x个1位的，y个2位的，数字长度为n。那么x+2y=n(0=<x=<n，x,y只能取整数)这是一层循环，内层我们考虑对x个1位和y个2位有多少种组合方式，如1122,2211,2112,2121…我们有x+y个位置，其中x个1,y个2,用组合就能得到x的位置有多少种。(C下标：x+y,上标:x)剩下的就是y的位置。遍历所有可能的x取值得到一串数的1位和2位的所有组合方式数目。我们使解决这个问题的方法签名为f(n) 然后 ，遍历一下数字每一位找出大于26的组合,对组合内的所有内容进行下面的运算，比如数字是1238290，38大于26，前面有2位，后面有3位，我们计算f(2)+f(3)…把这些结果加起来得到sum 最后 f(n)-sum就是我们要的组合数 |
|
|
人家要具体输出，你给方法数，不管对不对，题目就没看清。
另外，我看楼主的意思，应该是给一堆，从小到大排序后，dfs写法就可以了。 void dfs(int index, int cnt) { |
|
|
不要排序。不要改变数字的顺序。 |
|
|
额, 如果只是求数量, 那么可以使用这个:
for( int i=0; i<a.length; ++i ){
if( a[i] < 3 ){
count++;
}
else if( a[i] < 7 ){
b[j] = count + 1;
count = 0;
j++;
}
else if( count != 0 ){
b[j] = count;
count = 0;
j++;
}
}
int result = 1;
for( int i=0; i<j; i++ ){
result *= b[i];
}
result就是种类数 |
|
|
少了几句初始化:
int a[] = { 2, 3, 4, 5 };
int b[] = new int[a.length];
int count = 0;
int j = 0;
|
|
|
如果需要打印所有序列, 则可以使用动态规划,
public static void main(String[] argc){
int a[] = { 2, 1, 2, 3, 4, 5, 1, 2 };
print(a, 0, "");
}
public static void print(int[] a, int origin, String prefix){
if(origin < a.length-1){
prefix = ( prefix.equals("") ? "" : prefix+", " ); // 添加逗号分隔数字
print(a, origin+1, prefix+a[origin]);
if(a[origin]*10 + a[origin+1] <= 26){
print(a, origin+2, prefix+a[origin]+a[origin+1]);
}
}
else if(origin == a.length-1 ){ // 还剩一个直接加到队尾即可
System.out.println( prefix + "," + a[origin] );
}
else{
System.out.println( prefix );
}
}
|
|
|
代码没看的很明白，不过我运行了一下，举个特殊的例子{2,1,1,2,3}，跑出来的结果是5.现在我们来列举一下可能性：1_{2,1,1,2,3} 2_{21,1,2,3} 3_{21,12,3} 4_{21,1,23} 5{2,1,12,3} 6_{2,1,1,23}….明显不只是有5个的 |
|
|
这个例子不算特殊, 是我忘了, 上课的时候还记得, 下课就忘了….
public static void main(String[] argc){
int a[] = {2,1,1,2,3};
int b[] = new int[a.length];
int count = 0;
int j = 0;
for( int i=0; i<a.length; ++i ){
if( a[i] < 3 ){
count++;
}
else if( a[i] < 7 ){
b[j] = count + 1;
count = 0;
j++;
}
else if( count != 0 ){
b[j] = count;
count = 0;
j++;
}
}
int result = 1;
for( int i=0; i<j; i++ ){
result *= conver(b[i]);
}
System.out.println(result);
}
public static int conver(int i){ // 契科夫数列
if( i < 3 ){
return i;
}
return conver(i-1) + conver(i-2);
}
|
|
|
额, 又错了:
for( int i=0; i<a.length; ++i ){
if( a[i] < 3 ){
count++;
}
else if( (a[i]<7) || (i>0 && a[i-1]<2) ){
b[j] = count + 1;
count = 0;
j++;
}
else if( count != 0 ){
b[j] = count;
count = 0;
j++;
}
}
if( count != 0 ){
b[j] = count;
j++;
}
是这样的, 我们需要将整个数组划分成若干个部分, 每个部分符合这样的规则: |
|
|
11L讲的对
解释一下为什么是斐波那契数列，如果我们要知道5个数字的组合方式，5个数字可以由3个数字的任意组合加上一个2位数字（4,5位组合）也可以由4个数字的任意组合加上一个1位数字（第5位）。5个数字的组合方式有f(5)种，4个数字的组合f(4)种，3个数字的组合f(3)种，所以f(5)=f(4)+f(3) |
|
|
你说的一部分我能理解。的确不管怎么分组，“前面的数小于等于2”。但是为什么“ 如果倒数第二个数为1, 那么最后一个数为3-9” ？数字是可以重复使用。也就是说“11”这种组合是可以存在的。同理“如果倒数第二个数为2”的话也应该可以重复使用的。 |
|
| 40分 |
额, 我的意思是找出如下的序列
1212225 或者 1211212219 就是说, 最后两个数 ( 25 或者 19 ) 小于等于 26, 且最后一个数大于3, 比如 ( 5 , 9 ), 这就意味着, 这几个数是一组, 不管后面怎么添加字符, 都不能和最后一个数组合. 那么, 整个数字串就会被分为若干个孤立的片段, 比如这样: 1123 2218 8 7 18 那么, 他们有多少种组合呢? 由于1123里面的任意两个相邻的数都可以组合, 而 第一组最后的3和第二组第一个2大于26, 是不能组合的, 同理这里的每个数字只能和同组的相邻数的组合, 那么, 再往下就是高中数学的东西了: 1123有5种写法(1, 1, 2, 3) (11, 2, 3) (1, 12, 3) (1, 1, 23) (11, 23) 2218也有5中写法 8有一种写法( 8 ) 7有一种写法 18 有俩种写法 (1, 8) (18) 那么这个数字串又多少种写法? |
|
我大概明白你的意思了。大概就是把整个数字串，分成若干个不含有超过26的有效的基础数字串。然后再简单算出每一个不用考虑超过26的情况的相邻数字的全组合数。再进行相乘就是有效的 小于26的组合数 |
|
CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明求相邻数字组合的种类（算法）！
