- 浏览: 1638536 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (405)
- C/C++ (16)
- Linux (60)
- Algorithm (41)
- ACM (8)
- Ruby (39)
- Ruby on Rails (6)
- FP (2)
- Java SE (39)
- Java EE (6)
- Spring (11)
- Hibernate (1)
- Struts (1)
- Ajax (5)
- php (2)
- Data/Web Mining (20)
- Search Engine (19)
- NLP (2)
- Machine Learning (23)
- R (0)
- Database (10)
- Data Structure (6)
- Design Pattern (16)
- Hadoop (2)
- Browser (0)
- Firefox plugin/XPCOM (8)
- Eclise development (5)
- Architecture (1)
- Server (1)
- Cache (6)
- Code Generation (3)
- Open Source Tool (5)
- Develope Tools (5)
- 读书笔记 (7)
- 备忘 (4)
- 情感 (4)
- Others (20)
- python (0)
最新评论
-
532870393:
请问下,这本书是基于Hadoop1还是Hadoop2?
Hadoop in Action简单笔记(一) -
dongbiying:
不懂呀。。
十大常用数据结构 -
bing_it:
...
使用Spring MVC HandlerExceptionResolver处理异常 -
一别梦心:
按照上面的执行,文件确实是更新了,但是还是找不到kernel, ...
virtualbox 4.08安装虚机Ubuntu11.04增强功能失败解决方法 -
dsjt:
楼主spring 什么版本,我的3.1 ,xml中配置 < ...
使用Spring MVC HandlerExceptionResolver处理异常
上次gx同学问我一道又重复数字的全排列的问题,我当时用set保存,然后直接回溯。这这种做法,效率比较低,没有去剪枝,从而像1,1,1,1,1这样的序列都需要回溯很多次。今天写了一个剪枝的。
c++ STL algorithm中有next_permutation可以直接调用,ACM的时候经常偷懒用这个,呵呵。
学以致用:poj 1731
http://acm.pku.edu.cn/JudgeOnline/problem?id=1731
poj1256 http://acm.pku.edu.cn/JudgeOnline/problem?id=1256
这道题需要一种特殊的数序输出:
An upper case letter goes before the corresponding lower case letter.
So the right order of letters is 'A'<'a'<'B'<'b'<...<'Z'<'z'.
我们只需要定义一个正确的比较函数就可以了
或者
这样我们的代码就出来了:
我们还是用STL来爽爽这道题吧:
public class Permutation { private int[] a; public Permutation(int[] a) { this.a = a; } public boolean isOk(int b,int e){//判断是否重复 if(b < e){ for(int i = b; i < e; i++){ if(a[i] == a[e]) return false; } } return true; } public void permutation(int k){ if(k >= a.length){ print(); }else{ for(int i = k; i < a.length; i++){ if(isOk(k,i)){ swap(i,k); permutation( k+1 ); swap(i,k); } } } } private void swap( int i, int k ) { int temp = a[i]; a[i] = a[k]; a[k] = temp; } private void print() { for( int i = 0; i < a.length; i++ ) { System.out.print(a[i] + " "); } System.out.println(); } public static void main( String[] args ) { Permutation p = new Permutation(new int[]{1,2,2,2}); p.permutation( 0 ); } }
c++ STL algorithm中有next_permutation可以直接调用,ACM的时候经常偷懒用这个,呵呵。
学以致用:poj 1731
http://acm.pku.edu.cn/JudgeOnline/problem?id=1731
#include<iostream> #include<algorithm> #include<vector> #include<string> using namespace std; string goods; vector<string> v; void swap(string &str,int i, int j){ char temp = str[i]; str[i] = str[j]; str[j] = temp; } bool ok(int i, int j){ if( i < j){ for(int k = i; k < j; k++){ if(goods[k] == goods[j]) return false; } } return true; } void backtrack(int i){ if(i >= goods.length()){ v.push_back(goods); } for(int j = i; j < goods.length(); j++){ if(ok(i,j)){ swap(goods,i,j); backtrack(i + 1); swap(goods,i,j); } } } int main(){ cin >> goods; backtrack(0); sort(v.begin(),v.end()); for(int i = 0; i < v.size(); i++){ cout << v[i] << endl; } }
poj1256 http://acm.pku.edu.cn/JudgeOnline/problem?id=1256
这道题需要一种特殊的数序输出:
An upper case letter goes before the corresponding lower case letter.
So the right order of letters is 'A'<'a'<'B'<'b'<...<'Z'<'z'.
我们只需要定义一个正确的比较函数就可以了
bool cmp(const string &str1,const string &str2){ int i; int m_len = min(str1.length(), str2.length()); for(i = 0; i < m_len; i++){ if(str1[i] != str2[i]) break; } if(i == m_len){ return str1.length() < str2.length(); }else if(tolower(str1[i]) == tolower(str2[i])) { return str1[i] < str2[i]; }else{ return tolower(str1[i]) < tolower(str2[i]); } }
或者
bool cmp(char c1,char c2){ if(tolower(c1) == tolower(c2)) return c1 < c2; else return tolower(c1) < tolower(c2); }
这样我们的代码就出来了:
#include<iostream> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<cmath> using namespace std; string str; vector<string> permutations; bool cmp(const string &str1,const string &str2){ int i; int m_len = min(str1.length(), str2.length()); for(i = 0; i < m_len; i++){ if(str1[i] != str2[i]) break; } if(i == m_len){ return str1.length() < str2.length(); }else if(tolower(str1[i]) == tolower(str2[i])) { return str1[i] < str2[i]; }else{ return tolower(str1[i]) < tolower(str2[i]); } } void swap(int i,int j){ char temp = str[i]; str[i] = str[j]; str[j] = temp; } bool isOk(int i,int j){ if(i < j){ int k; for(k = i; k < j; k++){ if(str[k] == str[j]) return false; } } return true; } void backtrack(int i){ if( i >= str.length()){ permutations.push_back(str); return; } int j; for(j = i; j < str.length(); j++){ if(isOk(i,j)){ swap(i,j); backtrack(i+1); swap(i,j); } } } int main(){ int n; cin >> n; int i,j; for(i = 0; i < n; i++){ cin >> str; permutations.clear(); backtrack(0); sort(permutations.begin(),permutations.end(),cmp); for(j = 0; j < permutations.size(); j++){ cout << permutations[j] << endl; } } }
我们还是用STL来爽爽这道题吧:
#include<iostream> #include<string> #include<cstring> #include<algorithm> using namespace std; string str; bool cmp(char c1,char c2){ if(tolower(c1) == tolower(c2)) return c1 < c2; else return tolower(c1) < tolower(c2); } int main(){ int n; cin >> n; int i,j; for(i = 0; i < n; i++){ cin >> str; sort(str.begin(),str.end(),cmp); cout << str << endl; while(next_permutation(str.begin(),str.end(),cmp)){ cout << str << endl; } } return 0; }
发表评论
-
二分查找之变型题目
2010-10-24 12:40 2117二分查找算法在各个公司的笔试面试题大量出现,通常不是简单一眼就 ... -
一道笔试题(创新工厂)解法
2010-10-21 17:44 1815一个帖子http://www.iteye.com/topic/ ... -
[zz]大数据量,海量数据 处理方法总结
2010-08-27 22:24 2242大数据量的问题是很多面试笔试中经常出现的问题,比如baidu ... -
Trie and suffix array
2010-04-13 20:54 1897字典数Trie和后缀数组suffix array是处理字符串操 ... -
金币问题
2009-11-09 08:41 1990今年某公司的笔试题: 一个矩阵地图,每一个元素值代表金币数, ... -
楼梯问题
2009-11-09 08:19 1543hl给我的几道某公司的算法题: 1、 有个 100 级的 ... -
一道考察模拟乘法的题目
2009-11-07 22:37 1395今天hl和我讨论一道题目: 写道 整形数组如a={1,4, ... -
链表归并
2009-11-07 21:40 1002以前gx同学问的某某公司的笔试题,写一下练练(纯手写,没编译过 ... -
找出出现次数超过一半的数字
2009-11-07 21:23 1863hl同学问我一道这个题,想了一种方法,感觉还是不错的,只扫描一 ... -
有道难题以超低分晋级
2009-06-10 11:36 1532有道难题比赛居然晋级了,可以领到一个t-shirt。 -
逆序数/逆序数对
2009-06-09 23:17 3739逆序数是个常遇到的问题,主要有两种解法: O(n^2)的方法: ... -
有道难题topcoder
2009-05-31 23:55 2426今天做了有道topcoder的题目,也是第一次在topcode ... -
百度之星第一场题目
2009-05-31 00:03 3593由于不符合参赛条件,未能参加百度之星,看了题目还挺有意思,把题 ... -
一个对字符串很好的Hash函数ELFHHash
2009-05-03 21:41 2241#include<stdio.h> #defin ... -
最大流Ford-Fulkerson算法
2009-04-22 17:33 9627算法导论对最大流算法有很详细的介绍,今天实现了最大流Ford- ... -
大数/高精度加减乘除取模[收藏]
2009-04-16 19:38 5026#include <iostream> #i ... -
差分约束系统
2009-04-15 16:00 3686(本文假设读者已经有以下知识:最短路径的基本性质、Bellma ... -
二分图匹配
2009-04-15 15:40 3698二分图最大匹配的匈牙利算法 二分图是这样一个图,它的顶点可以分 ... -
线段树
2009-03-24 10:58 1655把问题简化一下: 在自然数,且所有的数不大于30000的 ... -
树状数组
2009-03-24 10:39 2306树状数组是一种非常优雅的数据结构. 当要频繁的对数 ...
相关推荐
生成这些字符的不重复的全排列,并将结果打印到标准输出上。 【输入形式】 从标准输入上读入一个由字母、数字组成的字符串,字符串的长度小于100,其中包含重复的字符。 【输出形式】 向标准输出印...
算法分析课程作业,C语言编写,可能需要用input.txt输入,有重复数字的全排列代码
1、输入n个数(不重复),求n个数字的全排列 如:n=3 全排列的数字为 1 2 3 则输出 123 132 213 231 321 312 2、输入n和k(n》=k)求n个数字的(n,k)排列 如n=3,k=2 输入的三个数位1 2 3 则输出 12 13 21 23 31...
输出自然数1到n的所有不重复的排列,即n的全排列。
这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时,要求[i,j)中没有与第j个数相等的数。下面给出...
由1~n组成的所有不重复的数字序列,每行一个序列。 Sample Input 3 Sample Output 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Source elba 程序如下 const maxn=1000; var a:array[0..maxn] of longint; n,k:long...
去重全排列的递归实现 去掉重复数字的 全排列的 递归实现
为方便起见,用123来示例下。123的全排列有123、132、213、231、312、321这六种。...因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后,递归的代码就很容易写出来了:
# 给定一个可包含重复数字的序列,返回所有不重复的全排列 # 示例: # 输入: [1,1,2] # 输出: # [ # [1,1,2], # [1,2,1], # [2,1,1] # ]
各行上的全排列不重复。输出各行遵循“小数优先”原则, 在各全排列中,较小的数尽量靠前输出。如果将每行上的输出看成一个数字,则所有输出构成升序数列。具体格式见输出样例。 【样例输入1】1 【样例输出1】1 ...
剑指 Offer II 083. 没有重复元素集合的全排列标签:数组、回溯难度:中等题目大意给定一个不含重复数字的数组 nums 。若未被访问过则将其加入排列中
剑指 Offer II 083. 没有重复元素集合的全排列标签:数组、回溯难度:中等题目大意给定一个不含重复数字的数组 nums 。若未被访问过则将其加入排列中
剑指 Offer II 084. 含有重复元素集合的全排列标签:数组、回溯难度:中等题目大意给定一个可包含重复数字的序列 nums 。解题思路这道题跟「剑指 O
求一个序列的全排列,字典序,序列中的元素无重复,在实际应用过程中,可以按下标来做计算
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。示例 1:输出:示例 2:输出:[[1,2,3],[1,3,2],[2,1,3],
题目:有 1、2、3、4 四个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 程序分析:可填在百位、十位、个位的数字都是 1、2、3、4,组成所有的排列后再去掉不满足条件的排列。
给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 思路:深度优化搜索 先看题目,以所给数组 [1, 2...
输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。 输入格式 一个整数n。 输出格式 由1~n组成的所有不重复的数字序列,每行一个序列。 每个数字保留 5个场宽。 ...
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1: 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2: 输入:nums = ...
全排列给定一个 没有重复 数字的序列,返回其所有可能的全排列。示例:输入: [1,2,3]输出:var permute = function(nums) {