欢迎使用CSDN-markdown编辑器
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了欢迎使用CSDN-markdown编辑器,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4410字,纯文字阅读大概需要7分钟。
内容图文
字符串的组合:
给一个字符串,比如ABC, 把所有的组合,即:A, B, C, AB, AC, BC, ABC, 都找出来。
解题思路:
假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符,我们有两种选择:一是把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选取m-1个字符;二是不把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。
字符串的排列:
[java]
publicstaticvoidcombiantion(char chs[]){
if(chs.length == 0) return ;
Stack<Character> stack = new Stack<Character>();
for(int i = 1; i <= chs.length; i++){
combine(chs, 0, i, stack);
}
}
//从字符数组中第begin个字符开始挑选number个字符加入list中 publicstaticvoidcombine(char []chs, int begin, int number, Stack<Character> stack){
if(number == 0){
System.out.println(stack.toString());
return ;
}
if(begin == chs.length){
return;
}
stack.push(chs[begin]);
combine(chs, begin + 1, number - 1, stack);
stack.pop();
combine(chs, begin + 1, number, stack);
}
//上代码生成的toString()形式的字符串形式为[‘ ‘,‘ ‘,......],修改最后组合的字符串格式为“ ”package Permution;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;
import org.junit.Test;
publicclassCombination {
LinkedList<String> stack2=new LinkedList<String>();
publicvoidcombination(String str){
char[] chr=str.toCharArray();
LinkedList<Character> stack=new LinkedList<Character>();
int length=chr.length;
for(int i=1;i<=length;i++)
comb(chr,0,i,stack);
for(String s : stack2)
System.out.println(s);
}
publicvoidcomb(char[] chr,int begin,int number,LinkedList<Character> stack){
if(number==0){
int i=0;
char[] carr=newchar[stack.size()];
for(char ch:stack)
carr[i++]=ch;
stack2.add
(String.valueOf(carr
));
return;
}
if(begin==chr.length){
return;
}
stack.push(chr[begin]);
comb(chr,begin+1,number-1,stack);
stack.pop();
comb(chr,begin+1,number,stack);
}
@Testpublicvoidtest(){
String str="abcde";
combination(str);
}
}
给一个字符串,比如ABC, 把所有的排列,即:ABC, ACB, BAC, BCA, CAB, CBC 都找出来。
解题思路:
对于一个n 位的字符串来讲,它是n-1位字符串的排列 加上 没有在 n -1 位字符串里 那个字符 的排列。 有点难理解,用例子说明:
对于字符串ABC来讲,它所有的排列就是 A + BC 的排列 加上 B + AC 的排列,再加上 C + AB的排列。
而BC的排列是 B + C 的排列 加上 C + B 的排列。
所以,对一个字符串,我们从中去一个值,然后求剩余部分的排列,然后把它们再组合在一起。所有,代码如下:
[java]
// str has been sorted. publicstatic LinkedList<String> permutation(String str) {
LinkedList<String> linkedString = new LinkedList<String>();
if (str.length() <= 1) {
linkedString.add(str);
return linkedString;
}
for (int i = 0; i < str.length() ; i++) {
char ch = str.charAt(i);
//consider the case in which the characters may be duplicated. if (i > 0 && ch == str.charAt(i - 1)) {
continue;
}
String newStr = remove(str, i);
LinkedList<String> newStrList= permutation(newStr);
for (int j = 0; j < newStrList.size(); j++) {
linkedString.add(ch + newStrList.get(j));
}
}
return linkedString;
}
//remove the ith character from the string publicstatic String remove(String str, int i) {
if (i == 0) returnstr.substring(1, str.length());
if (i == str.length() - 1) returnstr.substring(0, i );
returnstr.substring(0, i) + str.substring(i + 1, str.length());
}
这里贴出另一个permutation 的版本:
[java] view plain copy
staticvoid swap(char[] arr, int idx1, int idx2) {
char temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
staticvoid permutation(char[] arr, intindex, int size) {
if (index == size) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
} else {
for (int i = index; i < size; i++) {
if(i != index && arr[i] == arr[index])
continue;
swap(arr, i, index);
permutation(arr, index+1, size);
swap(arr, i, index);
}
}
}
}
//利用TreeSet解决顺序问题以及重复串问题
package Permution;
import java.util.*;
publicclassSolution {
ArrayList<String> astr=new ArrayList<String>();
TreeSet<String> hashStr=new TreeSet<String>();
public ArrayList<String> Permutation(String str) {
if(str==null||str.isEmpty())
return astr;
char[] chr=str.toCharArray();
permution(chr,0);
astr.addAll(hashStr);
for(String lstr:astr)
System.out.println(lstr);
return astr;
}
publicvoid permution(char[] chr,int begin){
if(begin==chr.length){
hashStr.add(String.valueOf(chr));
}
for(int i=begin;i<chr.length;i++){
char temp=chr[i];
chr[i]=chr[begin];
chr[begin]=temp;
permution(chr,begin+1);
temp=chr[begin];
chr[begin]=chr[i];
chr[i]=temp;
}
}
}
原文:http://blog.csdn.net/u010744711/article/details/51331937
内容总结
以上是互联网集市为您收集整理的欢迎使用CSDN-markdown编辑器全部内容,希望文章能够帮你解决欢迎使用CSDN-markdown编辑器所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。