大家把自己遇到的最具启发性的面试算法都贴上来吧~~

俺对算法比较弱，特别是贪心法，背包，kmp算法，排列组合都比较水

2010支付宝西安最新笔试题..求高手给出算法和思路....这是我1年前发的帖子，现在都不知道该怎么处理这种问题尴尬http://topic.csdn.net/u/20091013/10/d5d371dc-6dec-4034-bf31-432a47ffce96.html

也不是什么面试题，就是个 O(lgN) 计算乘方的小代码，不知道在各位眼中算不算法？public static double pow(double base, int exponent) {
    if (exponent < 0)
        return 1 / pow(base, -exponent);
    double power = 1;
    while(exponent > 0) {
        if((exponent & 1) == 1) {
            power *= base;
        }
        base *= base;
        exponent >>= 1;
    }
    return power;
}

面试中还木有碰到有人问算法
太杯具
http://poj.org/problem?id=2406
这个问题比较好玩，
kmp的实际应用

记得有一题，不难，但是觉得还是挺有意思的：假设有长度为L的一根尺子，在尺子的单位刻度上随机放n只蚂蚁，蚂蚁的头随机向左或向右。设蚂蚁的速度为匀速v,当两只蚂蚁相遇时，就会各自掉头朝反方向走。问所有蚂蚁都走出木棍的最大和最小时间。

我觉得八皇后算法蛮复杂的，特别是用swing或awt 输出一个棋盘，真有点复杂

可以分段取嘛
只用保存 100 个数就够了
后边读一个就与最小堆的根比较下
比根大的就替换最小堆的根然后调整堆时间复杂度也就是 lg(100) * N(N为所有的数的数量)
如果找到的 100 个数需要是排序好的
1.可以利用上边的最小堆找到前 100 个数，然后再排序
2.也可以借用插入排序的思想，往长度为100的数组中进行插入排序，最后得到的100数就是排序好的前100个

exponent >>= 1;
还是第一次看到这个运算符，呵呵。二进制的思路~嗯，又学招了

1．一个字符串参数（value）由字母（a-z,A-Z）组成，且最大字符位数为40，要求写一个函数（maxLength）返回该参数中连续相同字母的最大个数及该字母，如果最大位数有多个，则返回第一个。例：字符串“aaaddxxxxddddxxxx”，返回值为：“x,4”。
要求：请考虑代码执行的效率并注意编码的风格。/*
1．一个字符串参数（value）由字母（a-z,A-Z）组成，且最大字符位数为40，
要求写一个函数（maxLength）返回该参数中连续相同字母的最大个数及该字母，
如果最大位数有多个，则返回第一个。例：字符串“aaaddxxxxddddxxxx”，返回值为：“x,4”。
要求：请考虑代码执行的效率并注意编码的风格。
*/public class Test{
    public static void main(String[] args){
        String content = "aaaddxxxxddddxxxx";
        getMaxLength(content);
    }    private static void getMaxLength(String content){
        if(content == null || content.length() == 0){
            throw new IllegalArgumentException("content is invalid.");
        }        String maxStr = null;

        int maxCount = 0;        String tempStr = null;
        int tempCount = 0;        while(content.length() != 0){
            tempStr = content.substring(0,1);            tempCount = content.length() - content.replaceAll(tempStr,"").length();            content = content.replaceAll(tempStr,"");            if(tempCount > maxCount){
                maxStr = tempStr;
                maxCount = tempCount;
            }
        }        System.out.println("maxStr: " + maxStr + " Total: " + maxCount);
    }
}

我写了这个呵public class Test12 {

public static void getMax(String str){
int length = str.length();
char str_ary[] = str.toCharArray();
Map <String,Integer>map = new HashMap<String, Integer>();
for(int i = 0;i<length;i++){
String str1 = ""+str_ary[i];
map.put(str1, 0);
}
for(int i = 0;i<length;i++){
String str1 = ""+str_ary[i];
int val = map.get(str1)+1;
map.put(str1, val);
}
Iterator m = map.entrySet().iterator();
while(m.hasNext()){
System.out.println(m.next());
}
}

public static void main(String []args){
getMax("aabbccaa");
}
}

这个题没必要这么复杂的public class Test { public static void main(String[] args) {
String str = "aaaddxxxxddddxxxx";
getMaxLength(str);
} public static void getMaxLength(String arr) {
char[] cArr = arr.toCharArray();
int cur_length = 1;
int max_length = 1;
int index = 0;
for (int i = 0; i < cArr.length; i++) {
if(cArr[i] == cArr[index]){
cur_length++;
}else{
index = i;
max_length = max_length > cur_length ? max_length : cur_length;
cur_length = 0;
}
}
System.out.printf("maxStr: %c, Count: %d",cArr[index], max_length);
}
}

30楼的如果把字符串改为 str="abcdefffg"那么求出的结果就是错误的结果了啊

30楼的代码有问题，其实这个问题的解如果用正则表达式的话最好。转自一高手的代码：public String maxlength(String str){
String rs="";
Pattern p=Pattern.compile("([a-z|A-Z])\\1+");
Matcher m=p.matcher(str);
while(m.find()){
rs=rs.length()>m.group().length() ? rs:m.group();
}
if(rs.length()>=1)
return rs.substring(0,1)+","+rs.length();
else
return "god";

}

谢谢 32 和 34 楼的朋友
居然有BUG 了
呵呵我再看看

我修改了下 30 楼的代码
先前忽视了一个问题哎再次感谢 30 34 楼的两位朋友public class Test { public static void main(String[] args) {
String str = "aabcdefffg";
getMaxLength(str);
} public static void getMaxLength(String arr) {
char[] cArr = arr.toCharArray();
int cur_length = 1;
int max_length = 1;
int cur_index = 0;
int max_index = 0;
for (int i = 1; i < cArr.length; i++) {
if(cArr[i] == cArr[cur_index]){
cur_length++;
}else{
if(max_length < cur_length){
max_length = cur_length;
max_index = cur_index;
}
cur_index = i;
cur_length = 1;
}
}
System.out.printf("maxStr: %c, Count: %d",cArr[max_index], max_length);
}
}

郁闷自己又发现了个问题再传次
太伤自尊了public class Test { public static void main(String[] args) {
String str = "aabcdefffgggg";
getMaxLength(str);
} public static void getMaxLength(String arr) {
char[] cArr = arr.toCharArray();
int cur_length = 1;
int max_length = 1;
int cur_index = 0;
int max_index = 0;
for (int i = 1; i < cArr.length; i++) {
if(cArr[i] == cArr[cur_index]){
cur_length++;
}else{
if(max_length < cur_length){
max_length = cur_length;
max_index = cur_index;
}
cur_index = i;
cur_length = 1;
}
}
if(max_length < cur_length){
max_length = cur_length;
max_index = cur_index;
}
System.out.printf("maxStr: %c, Count: %d",cArr[max_index], max_length);
}
}

楼上的连了三帖了，为避免再发现小bug时不能及时贴上，帮楼上的顶顶：）

37楼的不错了！不过我比较36楼后知道，你新加的那两行代码是因为36的没有做最后一次比较！其实可以直接在for()那儿改成for (int i = 1; i < cArr.length+1; i++) {就行了吧？！呵呵

调试易

大家把自己遇到的最具启发性的面试算法都贴上来吧~~

解决方案 »