精华内容
下载资源
问答
  • 字符串排列组合

    2016-07-05 09:51:40
    实现字符串所有组合数,以及全排列
  • 主要为大家详细介绍了java实现字符串排列组合问题,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Backtracking 求解迷宫以及字符串排列组合
  • 主要为大家详细介绍了JAVA实现abc字符串排列组合,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 字符串排列组合(去重)

    千次阅读 2019-05-09 16:49:46
    字符串排列组合 一、 字符串排列 要求字符串:abc产生abc |acb|bac|bca|cab|cba 思路: 1、固定一个位置第一个位置,数组中该位置之后的元素与该位置元素交换, 2、在1的基础之上,固定第二个位置,数组数...

    字符串排列组合

    一、 字符串排列

    要求字符串:abc产生abc |acb|bac|bca|cab|cba

    思路:
    1、固定一个位置第一个位置,数组中该位置之后的元素与该位置元素交换,
    2、在1的基础之上,固定第二个位置,数组数组中该位置之后的元素与该位置元素交换
    3、递归退出条件:当位置指针等于当前数组的长度,返回当前字符串排序
    4、递归:
    (1)交换元素
    (2)递归调用下一位置
    (3)将数组还原
    5、去重方式
    (1)通过Hashset去重
    (2)通过增加isSwap()//目的在于判断当前位置的元素在前边数组中已经已经出现

    补充,由于本人在牛客测试,由于最终结果与标准结果顺序存在差别,可以自己添加比较器

    class Compare implements Comparator<String> {
    	@Override
    	public int compare(String o1, String o2) {
    	 	 return o1.compareTo(o2);
       		}
      }
    

    代码

    import java.util.ArrayList;
    import java.util.HashSet;
    class Permutation {
    	ArrayList<String> list = new ArrayList<>();
    	HashSet<String> set = new HashSet<>();
    	//主函数
    	public ArrayList<String> Permutation(String str) {
    		char[] c = str.toCharArray();
    		int pointer = 0;
    		oper(pointer, c);
    		return list;
    	}
    	/**
    	 * 字符串排列并去重
    	 * 
    	 * @param pointer
    	 * @param c
    	 */
    	public void oper(int pointer, char[] c) {
    		if (pointer == c.length) {
    			String end = String.valueOf(c);
    			if (!set.contains(end)) {
    				list.add(end);
    				set.add(end);
    			}
    		} else {
    			for (int i = pointer; i < c.length; i++) {
    				swap(c, pointer, i);
    				oper(pointer + 1, c);
    				swap(c, i, pointer);
    
    			}
    		}
    	}
    }
    

    二、字符串组合

    要求:abc==>a|b|c|ab|ac|bc|abc

    1、定义空字符串用来存储递归跳出的的结果
    2、递归跳出条件:指针等于数组长度(需要将字符串转化为字符数组)
    3、递归函数:
    (1)下一个字符串不包含当前位置元素
    (2)下一个字符串包含当前位置元素
    4、去重:通过HashSet去重

    代码

    import java.util.ArrayList;
    import java.util.HashSet;
    class Permutation {
    	ArrayList<String> listc = new ArrayList<>();
    	HashSet<String> setc = new HashSet<>();
    	//主函数
    	public ArrayList<String> Combination(String str) {
    		char[] c = str.toCharArray();
    		int pointer = 0;
    		combin(c, pointer,"");
    		listc.remove("");
    		return listc;
    	}
    	/**
    	 * 字符串组合
    	 * @param str
    	 * @param pointer
    	 */
    
    	private void combin(char[] c, int pointer,String res) {
    		if(pointer == c.length ) {
    			if(!setc.contains(res)){
    				listc.add(res);
    				setc.add(res);
    				return ;
    			}	
    		}else{
    			combin(c, pointer+1, res+c[pointer]);//下一个包含该字符串
    			combin(c, pointer+1, res);//下一个不包含该字符串
    		}
    		
    	}
    }
    

    测试

    public static void main(String[] args) {
    		String string = "aab";
    		Permutation per = new Permutation();
    		ArrayList<String> res = per.Permutation(string);
    		System.out.println("==============字符串排列==============");
    		for (String str : res) {
    			System.out.print(str + "|");
    		}
    		System.out.println();
    		
    		ArrayList<String> com = per.Combination(string);
    		System.out.println("==============字符串组合==============");
    		for (String str : com) {
    			System.out.print(str + "|");
    		}
    	}```
    
    
    展开全文
  • PHP多个字符串排列组合的算法,组二,组三,彩票统计中奖注数的算法中会经常用到
  • 一道字符串排列组合算法题/** * 编程列出一个字符串的全字符组合情况,原始字符串中没有重复字符 * 例如: * 原始字符串是"abc",打印得到下列所有组合情况 * "a" "b" "c" * "ab" "bc" "ca" "ba" "cb" "ac" *...

    一道字符串排列组合算法题

    /**
         * 编程列出一个字符串的全字符组合情况,原始字符串中没有重复字符
         *  例如:
         * 原始字符串是"abc",打印得到下列所有组合情况
         * "a" "b" "c" 
         * "ab" "bc" "ca" "ba" "cb" "ac"
         * "abc" "acb" "bac" "bca" "cab" "cba"
         * @author mo
         * 
         * 分析:初始前缀""   后缀"abc"(要排列的字符串)
         *      1.从后缀取出第一个字符,和前缀拼,拼完就打印或者存起来
         *      2.然后把后缀里取出的字符删除后,作为新后缀。上一步拼完的字符串作为新前缀
         *      3.把新前缀后缀重复1.2.步,直到后缀只剩一个字符
         *      4.后缀只剩一个字符时,只需要前后缀拼一起即可
         *      5.第一个字符的排列组合完毕,从后缀中取出第二个字符,重复1234步
         *
         */
        private static void strPaiLie(String left, String right) {
            if(right.length() == 1){
                System.out.println(left+right);
                return;
            }
            for(int i=0;i<right.length();i++){
                StringBuilder sb = new StringBuilder();
                sb.append(right);
                String str = left+right.substring(i,i+1);
                //如果只需要abc,bca,cba,bac等,相同位数的排列,把这里的打印语句注释掉即可
                System.out.println(str);
                strPaiLie(str,sb.deleteCharAt(i).toString());
            }
        }
    展开全文
  • 字符串排列组合算法

    千次阅读 2016-10-07 20:00:30
    全排列所谓全排列,就是打印出字符串中所有字符的所有排列。例如输入字符串abc,则打印出 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba 。#include #include static int number=0; void ...

    第二个算法是我笔试题遇到的,当时没有做出来,在网上看到别人写的算法,感觉太精妙了,就在这里分享出来。


    全排列

    所谓全排列,就是打印出字符串中所有字符的所有排列。例如输入字符串abc,则打印出 a、b、c 所能排列出来的所有字符串 abcacbbacbcacabcba


    #include<stdio.h>
    #include<string.h>
    
    
    
    static int number=0;
    
    void Swap(char *a ,char *b)
    {
    	char temp = *a;
    	*a = *b;
    	*b = temp;
    }
    
    void AllRange(char* str,int start,int length)
    {
    	if(start == length-1)
    	{
    		printf("%s\n",str);
    		number++;
    	}
    	else
    	{
    		for(int i=start;i<=length-1;i++)	
    		{
    			Swap(&str[start],&str[i]); 
    			AllRange(str,start+1,length);
    			Swap(&str[start],&str[i]); 
    		}
    	}
    }
    
    void Permutation(char* str)
    {
    	if(str == NULL)
    		return;
    
    	AllRange(str,0,strlen(str));
    }
    
    void main()
    {
    	char str[] = "abcde";
    	Permutation(str);
    	printf("number=%d\n",number);
    
    }
    

    全组合

    如果不是求字符的所有排列,而是求字符的所有组合应该怎么办呢?还是输入三个字符 a、b、c,则它们的组合有a b c ab ac bc abc。当然我们还是可以借鉴全排列的思路,利用问题分解的思路,最终用递归解决。不过这里介绍一种比较巧妙的思路 —— 基于位图。

    假设原有元素 n 个,则最终组合结果是 2n1 个。我们可以用位操作方法:假设元素原本有:a,b,c 三个,则 1 表示取该元素,0 表示不取。故取a则是001,取ab则是011。所以一共三位,每个位上有两个选择 0 和 1。而000没有意义,所以是 2n1 个结果。

    这些结果的位图值都是 1,2…2^n-1。所以从值 1 到值 2n1 依次输出结果:

    001,010,011,100,101,110,111 。对应输出组合结果为:a,b,ab,c,ac,bc,abc
    因此可以循环 1~2^n-1,然后输出对应代表的组合即可。有代码如下:

    #include<stdio.h>
    #include<string.h>
    
    static int number=0;
    
    void Combination(char *str)
    {
    	if(str == NULL)
    		return ;
    	int len = strlen(str);
    	int n = 1<<len;
    	printf("n=%d\n",n);
    	for(int i=1;i<n;i++)    //从 1 循环到 2^len -1
    	{
    		for(int j=0;j<len;j++)
    		{
    			int temp = i;
    			if(temp & (1<<j))   //对应位上为1,则输出对应的字符
    			{
    				printf("%c",*(str+j));
    			}
    		}
    		number++;
    		printf("\n");
    	}
    }
    
    void main()
    {
    	char str[] = "abcdef";
    	Combination(str);
    	printf("number:%d\n",number);
    }
     
    



    反转字符串

    main.c

    #include<stdio.h>
    #include<string.h>
    
    void print(char *str)
    {
       if(*str!='\0')  print(str+1);
       if(*str!='\0') 
    	
    printf("%c",*str);
    }
    
    int main(int argc,char **argv)
    {
    	char *buff="hello world";
    	print(buff);
    	printf("\n");
    	return 0;
    }
    


    展开全文
  • 字符串排列组合

    2019-09-26 17:05:28
    // 输出给定的字符串的所有的组合 //输入:“AAB” //输出:8 //解释:可能的序列为 “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”。 //MAX_Len(Str) == 7 public static void main(String[] ...

    // 输出给定的字符串的所有的组合
    //输入:“AAB”
    //输出:8
    //解释:可能的序列为 “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”。
    //MAX_Len(Str) == 7

    	public static void main(String[] args) {
            System.out.println(subStrCount("aab")); // 8
            System.out.println(subStrCount("abc")); // 15
        }
        
        static int subStrCount(String str) {
            Map<Character, Integer> map = new HashMap<>();
            for (int i =0 ; i< str.length(); i++) {
                char ch = str.charAt(i);
                if (map.containsKey(ch)) map.put(ch, map.get(ch) + 1);
                else map.put(ch ,1);
            }
    
            int[] temp = new int[9];
            for (int i = 0; i< 9 ;i++) temp[i] = 0;
            Set<Character> set = map.keySet();
            for (Character ch :set) {
                for (int i = 7; i> 0; i--) temp[i+1] += cnm(i + map.get(ch), i) * temp[i];
                for (int i = 1; i<= map.get(ch); i++) temp[i] = temp[i] + 1;
            }
    
            int result = 0;
            for (int i = 1; i< 8; i++) result += temp[i];
            return result;
        }
    
        /**
         * 计算 组合数 公式
         * @param n 元素总个数
         * @param m 参与选择的元素个数
         * @return
         */
        static int cnm(int n, int m) {
            int result = 1;
            for (int i= 1; i <= m ; i++) {
                result = result * (n - i + 1);
            }
            for (int i= 1; i <= m ; i++) {
                result = result / i;
            }
            return result;
        }
    
    展开全文
  • 字符串排列组合问题

    千次阅读 2018-09-03 14:19:54
     求一个字符串的所有能组合的情况,如ABC的所有的组合为A、B、C、AB、AC、BC、ABC,即,举一个例子,从ABC中选出n=2个不同的字符有哪些选法?从A遍历到C,如果选了A就从剩下的BC中再选出一个字符即可,如果没选A,...
  • 题目:输入一个字符串,按字典序打印出该字符串中字符的所有排列。 题目:输入一个字符串,求字符的所有组合。 题目:输入一个含有8个数字的数组,把这8个数字放在正方体的8个顶点上,使得正方体上相对的面上的4个...
  • 数字/字符串排列组合(Leetcode) 总结

    千次阅读 2018-04-08 12:47:34
    综述: 使用递归求解问题有时往往令人费解,博主对递归也是头痛不已,以下问题,利用递归很容易求解。... 参考资料: 字符串全排列 Leetcode 欢迎大家扫描关注公众号:编程真相,获取更多精彩的编程技术文章!
  • using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { public static long GetA(int m, int n) {
  • python下实现字符串排列组合

    千次阅读 2017-08-27 15:57:40
    字符串排列 组合
  • 主要介绍了C#查找字符串所有排列组合的方法,涉及C#字符串操作的相关技巧,非常具有实用价值,需要的朋友可以参考下
  • 字符串排列组合(C语言实现)

    千次阅读 2013-08-17 00:13:21
    这里主要介绍字符串排列组合问题,高中数学常见的题目,不用详细介绍,看例子就可以解决问题 "1212" 全排列结果为 1212,1221,1122,2112,2121,2211 组合结果是 1,2,12 我所理解的排列组合结果是 1,2...
  • 字符串排列组合

    2014-09-07 23:56:55
    字符串组合,有字符串abc,它的所有组合为a,b,c,ab,ac,abc求字符串组合可以使用递归的方法,程序如下: void print(string &s,int start,vector &t) { if(start==s.size()) { return ; } int i=0; for(i=...
  • 主要介绍了Java排列组合字符串的方法
  • 编写一种方法,计算某字符串的所有排列组合字符串每个字符均不相同。 示例1: 输入:S = "qwe" 输出:["qwe", "qew", "wqe", "weq", "ewq", "eqw"] 示例2: 输入:S = "ab" 输出:["ab", "ba"] 提示: 字符都是...
  • 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述:输入一个字符串,长度不超过9(可能有字符重复),...
  • 编写一种方法,计算某字符串的所有排列组合字符串每个字符均不相同 class Solution { public String[] permutation(String S) { List<String> res=new ArrayList<>(); func(S.toCharArray(),0,S....
  • 字符串排列组合的JAVA实现

    千次阅读 2016-09-17 11:01:16
    字符串组合: 给一个字符串,比如ABC, 把所有的组合,即:A, B, C, AB, AC, BC, ABC, 都找出来。 解题思路: 假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 90,625
精华内容 36,250
关键字:

字符串排列组合