Re: 一著名软件公司的java笔试算法题！
原题如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求： "4 "不能在第三位， "3 "与 "5 "不能相连.
我看了回贴都没有很好解决，主要是没有排除重复。
解决思路：强化题目，用1、2、2、3、4、5这六个数字排列“递增”序列。其他要求不变。
算法思路：显然是递归，初始序列122345，先从末两位(45)变化(45,54),然后末三位(345) ... 直到最后六位.怎样解决重复问题？很简单，由于是递增序列，每生成新序列可与前一生成序列比较，如 <放弃当前序列。当然有更好效率，如预先预测。代码如下：
class test
{
// 当前固定部分
private String CurFixPart;
private String PreGenNum;
public static void main(String[] args)
{
test t=new test();
t.GenControll( "122345 ");
}
// 调整字符串s位置pos字符到最前
private String shift(String s, int pos)
{
String newStr;
if (s.length()> pos+1)
newStr=s.substring(pos, pos+1)
+s.substring(0, pos)
+s.substring(pos+1);
else
newStr=s.substring(pos)
+s.substring(0, pos);
return newStr;
}
protected int Validate(String newNum)
{
String newGenNum=CurFixPart+newNum;
if (Integer.valueOf(newGenNum) <=Integer.valueOf(PreGenNum))
return 0;
if (newGenNum.substring(2,3).equals( "4 ") ||
(newGenNum.indexOf( "35 ")!=-1) || (newGenNum.indexOf( "53 ")!=-1))
return 0;
PreGenNum=newGenNum;
System.out.println(newGenNum);
return 0;
}
public void GenControll(String Base)
{
PreGenNum= "0 ";
CurFixPart= " ";
GenNext(Base, 0);
}
void GenNext(String varPart, int curPos)
{
if (varPart.length()==2)
{
Validate(varPart);
Validate(shift(varPart, 1));
return;
}
// Next Layer
String newGen=shift(varPart, curPos);
String SavedFixPart=CurFixPart;
CurFixPart=CurFixPart+newGen.substring(0,1);
GenNext(newGen.substring(1), 0);
CurFixPart=SavedFixPart;
// 同层递增
if (curPos==varPart.length()-1)
return;
GenNext(varPart, curPos+1);
}
}
序列122345测试通过。
有什么意见请大家多多提点。
[解决办法]
1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2 显然这个结果集还未达到题目的要求。从以下几个方面考虑：
1. 3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。
2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果
3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。
采用二维数组定义图结构，最后的代码是：
import java.util.Iterator;
import java.util.TreeSet;
public class TestQuestion {
private String[] b = new String[]{ "1 ", "2 ", "2 ", "3 ", "4 ", "5 "};
private int n = b.length;
private boolean[] visited = new boolean[n];
private int[][] a = new int[n][n];
private String result = " ";
private TreeSet set = new TreeSet();
public static void main(String[] args) {
new TestQuestion().start();
}
private void start() {
// Initial the map a[][]
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;
// Begin to depth search.
for (int i = 0; i < n; i++) {
this.depthFirstSearch(i);
}
// Print result treeset.
Iterator it = set.iterator();
while (it.hasNext()) {
String string = (String) it.next();
// "4 " can not be the third position.
if (string.indexOf( "4 ") != 2) {
System.out.println(string);
}
}
}
private void depthFirstSearch(int startIndex) {
visited[startIndex] = true;
result = result + b[startIndex];
if (result.length() == n) {
// Filt the duplicate value.
set.add(result);
}
for(int j = 0; j < n; j++) {
if (a[startIndex][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
} else {
continue;
}
}
// restore the result value and visited value after listing a node.
result = result.substring(0, result.length() -1);
visited[startIndex] = false;
}
}
3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。
代码中请注意这几行：
// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;
只要这样定义图，根本不用在代码中写IF ELSE语句。
实际上基于图的算法好处在于，只要你能定义好满足题目要求的图结构，遍历的结果就是你要的结果，不用任何对遍历结果做任何处理。包括本题中的：4不能在第三位置，3，5不能相连，唯一
性要求，其实都可以在体现在构造的图形结构里，然后直接遍历图取得自己要的结果。而不用再次处理结果集。
只是说这里实际上对其它要求要体现在图结构里有困难（理论上是可以的），但起码3，5不能相接是很好构造的，就是上面的代码段来解释的。
关于图形数据结构建议先看看数据结构的书，主要是将如何利用二维数组描述图结构，再看看图的深度遍历实现原理。最后再应用到这个问题上来，自然就不难明白了。
[解决办法]
学习一下啊，今天没时间了
[解决办法]
本来以为很简单，用递归一下就搞定的问题，结果按照递归的常规思路，在打印的时候碰到了很麻烦的问题，费了我不少脑筋，结果答案还是很简单，弄得我做出来了过后都准备把结果放到博客商保存了。其实我做的是字符串排列显示的问题，其中打印时的条件判断语句是根据楼主的特殊要求添加的，诸位参考：
import java.util.*;
public class test {
public static void main(String[] arg) {
Scanner r=new Scanner(System.in);
String s=r.nextLine();
Pailie(s, " ");
}
static void Pailie(String s, String p) {
if(s.length() <1) {
String t=p+s;
if(t.charAt(2)!= '4 ' && t.contains( "35 ")==false)
System.out.println(t);
}
else {
for(int i=0; i <s.length(); i++) {
Pailie(s.substring(1),p+s.substring(0,1));
s=s.substring(1)+s.substring(0,1);
}
}
}
}
[解决办法]
可以参考一下：求N!全排列。
http://bbs.kaoyan.com/thread-1697273-1-2.html
比求1-6强多了
下面的地址也有提到上面的有关内容
http://community.csdn.net/Expert/topic/5201/5201506.xml?temp=.5158502
[解决办法]
先排列1，2，3，4，5
再插入2，当插入点是2的邻位时，只插左边或只插右边
[解决办法]
学习
[解决办法]
厉害```学习收藏!!
[解决办法]
谢谢楼主的好贴，收藏起来！
[解决办法]
收下学习
[解决办法]
up
[解决办法]
收藏学习，UP
[解决办法]
up
[解决办法]
mark
[解决办法]
最小是122345,最大是543221
如
for(i=122345;i <=543221;i++)
if(第三位不能为四)
{
循环截取两位,如果不为 '35 '或 '53 '的都打印出来
}
[解决办法]
不懂Java，贴个C语言版的：
#include <stdio.h>
#define MAXN 6
int a[MAXN], o[MAXN], used[256] = { 0 }, count = 0;
void print()
{
int i;
for (i = 0; i < MAXN; ++i)
printf( "%d ", o[i]);
printf( "\n ");
}
void solve(const int depth)
{
int i;
for (i = 0; i < MAXN; ++i)
{
if (used[i] > 0)
{
--used[i];
if (
!(i + 1 == 4 && depth == 2) && // 4 at position 3
!(i + 1 == 3 && depth > 0 && o[depth - 1] == 5) && // 53
!(i + 1 == 5 && depth > 0 && o[depth - 1] == 3) // 35
)
{
o[depth] = i + 1;
if (MAXN - 1 == depth)
{
++count;
print();
}
else
solve(depth + 1);
}
else
{
i = i;
}
++used[i];
}
}
}
int main()
{
int i;
a[0] = 1;
a[1] = 2;
a[2] = 2;
a[3] = 3;
a[4] = 4;
a[5] = 5;
for (i = 0; i < MAXN; ++i)
++used[a[i] - 1];
solve(0);
printf( "Total count: %d\n ", count);
return 0;
}
运行结果：
122345
122543
123245
123254
123425
123452
125234
125243
125423
125432
132245
132254
132425
132452
132524
132542
142325
142523
143225
143252
145223
145232
152234
152243
152324
152342
152423
152432
212345
212543
213245
213254
213425
213452
215234
215243
215423
215432
221345
221543
223145
223154
223415
223451
225134
225143
225413
225431
231245
231254
231425
231452
231524
231542
232145
232154
232415
232451
232514
232541
241325
241523
242315
242513
243125
243152
243215
243251
245123
245132
245213
245231
251234
251243
251324
251342
251423
251432
252134
252143
252314
252341
252413
252431
312245
312254
312425
312452
312524
312542
315224
315242
315422
321245
321254
321425
321452
321524
321542
322145
322154
322415
322451
322514
322541
325124
325142
325214
325241
325412
325421
341225
341252
341522
342125
342152
342215
342251
342512
342521
345122
345212
345221
412325
412523
413225
413252
415223
415232
421325
421523
422315
422513
423125
423152
423215
423251
425123
425132
425213
425231
431225
431252
431522
432125
432152
432215
432251
432512
432521
451223
451232
451322
452123
452132
452213
452231
452312
452321
512234
512243
512324
512342
512423
512432
513224
513242
513422
521234
521243
521324
521342
521423
521432
522134
522143
522314
522341
522413
522431
523124
523142
523214
523241
523412
523421
541223
541232
541322
542123
542132
542213
542231
542312
542321
543122
543212
543221
Total count: 198
[解决办法]
同意楼上的作法 c处理数学问题还是有他很大的优势的
[解决办法]
天呐，我什么时候才能做出来这种题，我都大一了。。。哎
[解决办法]
这种有逻辑难度的问题真是让人喜欢，希望以后能经常碰到这种问题！
我写了一个，大家看看。
public class Test{
String s = "22 ";
String sc[] = { "22 "};
int ii = 0;
public void doAdd(String ss){
String sc1[] = new String[sc.length*(sc[0].length()+1)];;
for(int i=0;i <sc.length;i++){
String s = sc[i];
String sc2[] = getStrArray(s,ss);
for(int j=0;j <sc2.length;j++){
sc1[i*sc2.length+j] = sc2[j];
}
}
sc = sc1;
}
public String[] getStrArray(String s,String ss){
String newSc[] = new String[s.length()+1];
for(int i=0;i <=s.length();i++){
String s1 = s.substring(0,i);
String s2 = s.substring(i);
newSc[i] = s1+ss+s2;
}
return newSc;
}
public Test(){
for(int i=3;i <6;i++){
doAdd(i+ " ");
}
doAdd(1+ " ");
}
public static void main(String arg[]){
Test t = new Test();
int j = 0;
for(int i=0;i <t.sc.length;i++){
String s = t.sc[i];
if(!(s.indexOf( "35 ")> -1||s.indexOf( "53 ")> -1||s.indexOf( "4 ")==2)){
System.out.println( " 打印 S ： "+s);
j++;
}
}
System.out.println( " 符合条件的数共有： "+j+ "个 ");
}
}
[解决办法]
#include "stdafx.h "
#include <vector>
#include <iostream>
using namespace std;
ostream& operator < < (ostream& os, vector <int> & v)
{
for(vector <int> ::iterator i = v.begin(); i != v.end(); ++i)
{
cout < < *(i) < < " ";
}
return os;
}
bool CanPrint(const vector <int> & position)
{
if(position[4] == 2)
{
return false;
}
else if(position[3] - position[5] == 1 || position[3] - position[5] == -1)
{
return false;
}
else if(position[1] > position[2])
{
return false;
}
else
{
return true;
}
}
void Print(const vector <int> & position, const vector <int> & value)
{
static unsigned n = 0;
if(CanPrint(position))
{
++n;
vector <int> out(position.size());
for(unsigned i = 0; i < out.size(); ++i)
{
out[position[i]] = value[i];
}
cout < < n < < ": " < < out < < endl;
}
}
vector <int> SwapItem(int i, int j, const vector <int> & position)
{
vector <int> result = position;
int temp = result[i];
result[i] = result[j];
result[j] = temp;
return result;
}
void Calculate(unsigned depth, const vector <int> & position, const vector <int> & value)
{
Print(position, value);
for(unsigned i = depth; i < position.size() - 1; ++i)
{
for(unsigned j = i + 1; j < position.size(); ++j)
{
Calculate(i + 1, SwapItem(i, j, position), value);
}
}
}
void main(void)
{
vector <int> position(6);
vector <int> value(6);
position[0] = 0;
position[1] = 1;
position[2] = 2;
position[3] = 3;
position[4] = 4;
position[5] = 5;
value[0] = 1;
value[1] = 2;
value[2] = 2;
value[3] = 3;
value[4] = 4;
value[5] = 5;
Calculate(0, position, value);
}
[解决办法]
baidu在线考试题，在线等……
1， 一个文本文件有多行，每行为一个URL。请编写代码，统计出URL中的文件名及出现次数。
a） 文件名不包括域名、路径和URL参数，例如http://www.rs.com/n.op/q/rs?id=1中的文件名是rs。
b） 部分URL可能没有文件名，例如http://www.abc.com/，这类统计为“空文件名”。
c） 出现在不同URL中的相同文件名视为同一文件名，例如http://www.ceshi.com/hi.php
和ftp://ftp.cdef.com/hi.php为同一文件名
文件内容示例如下：
http://www.test.com/abc/de/fg.php?id=1&url=http://www.test.com/index.html
http://www.ceshi.com/hi.jsp
ftp://ftp.ceshi.com/hi.jsp
http://www.hello.com/cw/hi.jsp?k=8
http://www.hi.com/jk/l.html?id=1&s=a.html
http://www.rs.com/n.op/q/rs?id=1
http://www.abc.com/