前言

最近正在緊鑼旗鼓的準(zhǔn)備面試，期間遇到了許多好精巧的算法問題。于是大致實現(xiàn)了下，做個筆記。

判斷一個數(shù)是否為2的冪

這個題有兩種解法，一個是常規(guī)的，思路如下：

不斷的將這個數(shù)除2，求得余數(shù)。當(dāng)余數(shù)為1的時候，判斷當(dāng)前除數(shù)和2的大小關(guān)系，如果大于2，則說明此數(shù)不是2的冪，如果小于2則說明此數(shù)為2的冪。

另外一個方法就比較hack了，思路如下：

如果一個數(shù)為2的冪，則二進制首位必為1，其余位為0.
將這個數(shù)減一，得到的數(shù)與該數(shù)相與，結(jié)果為0則說明此數(shù)為2的冪數(shù)，否則不是。

代碼可以大致寫成這樣。

public boolean isPowerOf2(int number) {
        return ((number-1)&number)==0?true:false;
}

這樣是不是既高效又簡便呢？

不使用if, while, for,switch，goto等關(guān)鍵字實現(xiàn)100行代碼打印出1000個helloworld

按照常規(guī)理解，這是不可能的了。那么要怎么實現(xiàn)呢？

我個人倒是覺得繞開這些關(guān)鍵字倒是個不錯的方法，比如使用更底層的語言。高級語言之下不是還有諸如匯編語言，機器語言這些的嘛，雖然可讀性會很差，但是也不失為一個好辦法。

但是非得讓用某一個語言來實現(xiàn)，要怎么做呢？

答案之一就是用遞歸來實現(xiàn)。且看下面的代碼。

# coding: utf8
number = 0

def p1():
    global number 
    number += 1
    print "Hello World"

def p2():
    p1()
    p1()

def p3():
    p2()
    p2()
    p2()

def p4():
    p3()
    p3()
    p3()
    p3()

def p5():
    p4()
    p4()
    p4()
    p4()
    p4()

def p6():
    p5()
    p5()
    p5()
    p5()
    p5()
    p5()

def p7():
    p6()
    p6()
    p6()
    p6()
    p6()
    p6()
    p6()
if __name__ == '__main__':
    p7()
    print "共執(zhí)行了{}次，得到了{}個Hello World!".format(number, number)

得到的結(jié)果呢？

獲取結(jié)果

這樣，使用遞歸的方式便可以實現(xiàn)100行以內(nèi)的代碼獲取到大于1000行Hello World！的輸出了。

不使用+實現(xiàn)一個加法函數(shù)

這就有點難為人了，反正我是怎么想也沒想出來。后來參考網(wǎng)上的思路，使用模擬與數(shù)字電路的方式可以實現(xiàn)。

原理就是：

兩個數(shù)先異或運算
兩個數(shù)相與的結(jié)果左移一位
遞歸判斷，獲取返回結(jié)果

使用代碼實現(xiàn)起來可能如下：

public static int addWithoutOperators(int number1, int number2) {
        // 如果有一個數(shù)為0，則直接返回另一個數(shù)
        if(number2 == 0)
            return number1;
        if(number1 == 0)
            return number2;
        // 先異或運算
        int sum = number1 ^ number2;
        //求出進位，這時對于01,10,00都是不產(chǎn)生進位的，只有11才會產(chǎn)生進位
        int carry = ( number1 & number2 ) << 1;
        return addWithoutOperators(sum, carry);
    }

運算測試

加法運算結(jié)果

不使用-實現(xiàn)減法函數(shù)

兩數(shù)相減，就是一個數(shù)加上另一個數(shù)的相反數(shù)唄。我們常規(guī)就是這么理解的，那么怎樣才能獲取一個數(shù)的相反數(shù)呢？

求相反數(shù)很簡單，直接取反加一即可。也就是

求正數(shù)的相反數(shù)

負數(shù)同樣適用。

那么利用這一點，就可以輕松的實現(xiàn)減法函數(shù)了。

public static int subtractWithoutOperators(int number1, int number2) {
        if(number1 == number2) 
            return 0;
        int reverse = addWithoutOperators(~number2, 1);
        return addWithoutOperators(number1, reverse);
    }

運算結(jié)果如下：

實現(xiàn)減法函數(shù)的結(jié)果

除此之外，還有一個直接操作二進制的方式，

int Subtract(int a, int b)
{
    while (b != 0) 
    {
        int sameBits = a & b;
        a ^= sameBits;
        b ^= sameBits;
        a |= b;
        b <<= 1;
    }

    return a;
}

還有其他的乘除運算的實現(xiàn)方法，詳情請參考下面的鏈接：
http://www.cppblog.com/qingbizhu/archive/2012/03/30/168148.html

實現(xiàn)BMP算法

求子字符串在字符串中第一次出現(xiàn)的位置，這倒是一個挺簡單的實現(xiàn)，至于那個改進版的，我還不太理解，就不寫了。

/**
 * @Date 2017年3月5日
 *
 * @author 郭  璞
 *
 */
package interview;

/**
 * @author 郭 璞
 *
 *         關(guān)于字符串中字串位置的查找相關(guān)的幾個實現(xiàn)
 *
 */
public class StringPiexl {

    public static void main(String[] args) {
        String original = "hello world!";
        String substr = "llo";

        StringPiexl piexl = new StringPiexl();
        System.out.println(piexl.bmp(original, substr));

    }

    public int bmp(String original, String substr) {
        if (original.length() < substr.length())
            return -1;

        char[] originals = original.toCharArray();
        char[] substrs = substr.toCharArray();

        for (int outter = 0; outter < originals.length - substrs.length; outter++) {

            for (int inner = 0; inner < substrs.length;) {
                if (originals[outter++] == substrs[inner++]) {
                    if (inner == substrs.length - 1) {
                        return outter - inner;
                    }
                } else {
                    outter = outter - inner;
                    break;
                }
            }
        }
        return -1;

    }

}

運算結(jié)果如下：

2

打靶問題

打靶10次，得到90分的方式有幾種?
像這種問題還有很多，什么雞兔同籠啊，百錢白雞啊，都是類似的。

一方面我們可以采用枚舉法來暴力破解，另一方面就只能采用遞歸。兩者各有利弊吧，今天的這個打靶問題，我就用遞歸來實現(xiàn)一下。

/**
 * @Date 2017年3月3日
 *
 * @author 郭  璞
 *
 */
package interview;

/**
 * @author 郭 璞
 * 
 *         打靶的遞歸實現(xiàn)
 *
 */
public class ShootTest {

    /**
     * 設(shè)置為11位的數(shù)組是因為下邊按1開始到10來使用！
     */
    public static int[] record = new int[11];
    public static int totalMethods = 0;

    public static void main(String[] args) {
        shoot(90, 10);
        System.out.println("共有的可能的解法為：" + totalMethods);
    }

    public static void shoot(int score, int number) {
        // 此處score > number*10 可用90替代，但是根據(jù)不同的要求還需要硬編碼替換！
        if (score < 0 || score > number * 10) {
            return;
        }
        if (number == 1) {
            record[10-number] = score;
            print(record);
            totalMethods ++;
        }
        for (int index = 0; index <= 10; index++) {
            record[10-number] = index;
            shoot(score - index, number - 1);
        }
    }

    /**
     * @param record2
     * 打印的時候是按照第一槍到第number槍來計算的，因為要符合人類世界的從1開始的計算。
     */
    private static void print(int[] record2) {
        for (int index = 1; index < record2.length; index++) {
            System.out.print("\t" + record2[index]);
        }
        System.out.println("-----------------------------------");

    }

}

運算結(jié)果：

打靶問題結(jié)果

總結(jié)

好像面試的時候好多問題都是為了問題而問題，這樣的考察我覺得不是很好，畢竟實際中不會有這么偏門的問題吧。但是為了更好的充實自己，了解一下還是不錯的。

這篇文章就先這樣啦，以后再遇到這類問題，也許會更新一下，也會會另寫一篇。

如果看到了此文的你有類似的好的面試題的解法，也可以在下面留言評論，讓我們一起進步吧。