|
锁定老帖子 主题：公司笔试算法题
精华帖 (0) :: 良好帖 (2) :: 新手帖 (0) :: 隐藏帖 (3)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-03-17
最后修改：2011-03-17
哎,排列组合的知识快忘记光了,试着做做吧:
1.先排4-------5个位置中选一个为c(5,1) 2.再排1,3,5---5个位置中选3个,和顺序有关即p(5,3).考虑到3和5不能在一起,把3和5当作一个整体, 则5个位置变为4个位置,为c(4,1);再3和5是顺序相关的,则再乘2.此轮排序最后结果 为p(5,3)-c(4,1)*2 3,最后剩下的2个2对结果无影响. 故最后结果为c(5,1) * { p(5,3)-c(4,1)*2} = 260 回顾了下排列组合的知识,希望没错. ------------------------------------------------- 写完才发现即使这步做完了离解题还远着, 10分钟我做不好. |
| 返回顶楼 | |
|
发表时间：2011-03-17
int str2()
{ int i = (6*5*4*3*2*1 - 5*4*3*2*1 - 2*5*4*3*2*1 + 2*3*3*2)/2; return i; } 1，2，2，3，4，5看成1,2,3,4,5，6进行处理 后者的结果必然是前者的两倍 因此用排列组合的的方法 全部的是6*5*4*3*2*1 排除第三位为4的5*4*3*2*1 排除53相连的的，把两位看成一个整体处理，有53、35两种可能，5*4*3*2*1*2个 再加上53相连同时第三位为4的，这是被重复排除的，2*3*3*2种可能性 因此结果是6*5*4*3*2*1 - 5*4*3*2*1 - 2*5*4*3*2*1 + 2*3*3*2 这个结果是我们需要结果的两倍。 |
| 返回顶楼 | |
|
发表时间：2011-03-17
int str1() { int i, j, num = 0; char numberBuf[6]; char buffer[10]; char ch; int pos3, pos5; for(i = 122345; i <= 543221; i++) { memset(buffer, 0, sizeof(buffer)); memset(numberBuf, '0', sizeof(numberBuf)); sprintf(buffer, "%d", i); for(j = 0; j < 6; j++) { ch = buffer[j]; if(ch < '1' && ch > '5') continue; else { numberBuf[ch - '1'] += 1; if('3' == ch) pos3 = j; if('5' == ch) pos5 = j; } } if(0 == strncmp(numberBuf, "12111", 5)) { if((buffer[2] != '4') && (pos3 - pos5 != 1) && (pos3 - pos5 != -1)) num++; } } return num; } //这是用遍历的方法 |
| 返回顶楼 | |
|
发表时间：2011-03-17
int str3()
{ int i, j, num = 0; char numberBuf[7]; char buffer[10]; char ch; int pos3, pos5; for(i = 123456; i <= 654321; i++) { memset(buffer, 0, sizeof(buffer)); memset(numberBuf, '0', sizeof(numberBuf)); snprintf(buffer, 7, "%d", i); for(j = 0; j < 6; j++) { ch = buffer[j]; if(ch < '1' && ch > '6') continue; else { numberBuf[ch - '1'] += 1; if('3' == ch) pos3 = j; if('5' == ch) pos5 = j; } } if(0 == strncmp(numberBuf, "111111", 6)) { if((buffer[2] != '4') && (pos3 - pos5 != 1) && (pos3 - pos5 != -1)) num++; } } return num / 2; } //这是把122345看成123456遍历，最后除2的的方法，最后的结果都是198 |
| 返回顶楼 | |
|
发表时间：2011-03-17
挺好的。数据结构决定了算法，也禁锢了算法。而这个数据结构其实呢是关乎建模的。
|
| 返回顶楼 | |
|
发表时间：2011-03-18
果断递归。
|
| 返回顶楼 | |
|
发表时间：2011-03-21
递归就好了。
|
| 返回顶楼 | |
|
发表时间：2011-03-25
最后修改：2011-03-26
字符串匹配很干净不容易出错也容易测试。
|
| 返回顶楼 | |
|
发表时间：2011-07-04
最后修改：2011-07-04
scnustar 写道 解题思路：
1.对数组进行全排列 2.去掉不符合条件的排列 public class Test {
public static void main(String[] args) {
int[] initData = { 1, 2, 3, 4, 5 };
// 对数组进行全排列
perm(initData, 0, initData.length);
}
/**
* 对数组进行全排列，并打印符合条件的数组（4不能在第3位，3跟5不能相连）
*
* @param t 要排列的数组
* @param start 起始位置
* @param end 结束位置
*/
public static void perm(int[] t, int start, int end) {
if (start == end) {
// 如果4在第三位或者3跟5相连，则不打印
if (t[2] == 4 || is3NextTo5(t)) {
} else {
// 打印符合条件的数据
for (int i = 0; i < t.length; i++) {
System.out.print(t[i]);
}
System.out.println();
}
} else {
for (int i = start; i < end; i++) {
int temp = t[start];
t[start] = t[i];
t[i] = temp;
//递归
perm(t, start + 1, end);
temp = t[start];
t[start] = t[i];
t[i] = temp;
}
}
}
/**
* 判断3跟5是否相连
*
* @param t 数组
* @return true or false
*/
public static boolean is3NextTo5(int[] t) {
for (int i = 0; i < t.length - 1; i++) {
if (t[i] == 3 && t[i + 1] == 5)
return true;
}
for (int i = 0; i < t.length - 1; i++) {
if (t[i] == 5 && t[i + 1] == 3)
return true;
}
return false;
}
}修改如下： package test;
public class Test {
public static void main(String[] args) {
int[] initData = { 1,2, 2, 3, 4, 5 };
// 对数组进行全排列
perm(initData, 0, initData.length);
}
/**
* 对数组进行全排列，并打印符合条件的数组（4不能在第3位，3跟5不能相连）
*
* @param t 要排列的数组
* @param start 起始位置
* @param end 结束位置
*/
public static void perm(int[] t, int start, int end) {
if (start == end) {
// 如果4在第三位或者3跟5相连，则不打印
if (t[2] == 4 || is3NextTo5(t)) {
} else {
// 打印符合条件的数据
for (int i = 0; i < t.length; i++) {
System.out.print(t[i]);
}
System.out.println();
}
} else {
for (int i = start; i < end; i++) {
int temp = t[start];
t[start] = t[i];
t[i] = temp;
//递归
perm(t, start + 1, end);
temp = t[start];
t[start] = t[i];
t[i] = temp;
}
}
}
/**
* 判断3跟5是否相连
*
* @param t 数组
* @return true or false
*/
public static boolean is3NextTo5(int[] t) {
for (int i = 0; i < t.length - 1; i++) {
if (t[i] +t[i + 1] == 8)
return true;
}
return false;
}
}
结果 396个 |
| 返回顶楼 | |
|
发表时间：2011-07-18
楼上没有考虑两个2。
|
| 返回顶楼 | |
