前言判斷一個(gè)數(shù)是否為2的冪不使用if while forswitchgoto等關(guān)鍵字實(shí)現(xiàn)100行代碼打印出1000個(gè)helloworld不使用實(shí)現(xiàn)一個(gè)加法函數(shù)不使用-實(shí)現(xiàn)減法函數(shù)實(shí)現(xiàn)BMP算法打靶問題總結(jié)
最近正在緊鑼旗鼓的準(zhǔn)備面試，期間遇到了許多好精巧的算法問題。于是大致實(shí)現(xiàn)了下，做個(gè)筆記。
這個(gè)題有兩種解法，一個(gè)是常規(guī)的，思路如下：
不斷的將這個(gè)數(shù)除2，求得余數(shù)。當(dāng)余數(shù)為1的時(shí)候，判斷當(dāng)前除數(shù)和2的大小關(guān)系，如果大于2，則說明此數(shù)不是2的冪，如果小于2則說明此數(shù)為2的冪。
另外一個(gè)方法就比較hack了，思路如下：
如果一個(gè)數(shù)為2的冪，則二進(jìn)制首位必為1，其余位為0. 將這個(gè)數(shù)減一，得到的數(shù)與該數(shù)相與，結(jié)果為0則說明此數(shù)為2的冪數(shù)，否則不是。
代碼可以大致寫成這樣。
public boolean isPowerOf2(int number) { return ((number-1)&number)==0?true:false;}這樣是不是既高效又簡(jiǎn)便呢？
按照常規(guī)理解，這是不可能的了。那么要怎么實(shí)現(xiàn)呢？
我個(gè)人倒是覺得繞開這些關(guān)鍵字倒是個(gè)不錯(cuò)的方法，比如使用更底層的語言。高級(jí)語言之下不是還有諸如匯編語言，機(jī)器語言這些的嘛，雖然可讀性會(huì)很差，但是也不失為一個(gè)好辦法。
但是非得讓用某一個(gè)語言來實(shí)現(xiàn)，要怎么做呢？
答案之一就是用遞歸來實(shí)現(xiàn)。且看下面的代碼。
# coding: utf8number = 0def p1(): global number number += 1 得到的結(jié)果呢？
這樣，使用遞歸的方式便可以實(shí)現(xiàn)100行以內(nèi)的代碼獲取到大于1000行Hello World！的輸出了。
這就有點(diǎn)難為人了，反正我是怎么想也沒想出來。后來參考網(wǎng)上的思路，使用模擬與數(shù)字電路的方式可以實(shí)現(xiàn)。
原理就是：
兩個(gè)數(shù)先異或運(yùn)算兩個(gè)數(shù)相與的結(jié)果左移一位遞歸判斷，獲取返回結(jié)果使用代碼實(shí)現(xiàn)起來可能如下：
public static int addWithoutOperators(int number1, int number2) { // 如果有一個(gè)數(shù)為0，則直接返回另一個(gè)數(shù) if(number2 == 0) return number1; if(number1 == 0) return number2; // 先異或運(yùn)算 int sum = number1 ^ number2; //求出進(jìn)位，這時(shí)對(duì)于01,10,00都是不產(chǎn)生進(jìn)位的，只有11才會(huì)產(chǎn)生進(jìn)位 int carry = ( number1 & number2 ) << 1; return addWithoutOperators(sum, carry); }運(yùn)算測(cè)試 
兩數(shù)相減，就是一個(gè)數(shù)加上另一個(gè)數(shù)的相反數(shù)唄。我們常規(guī)就是這么理解的，那么怎樣才能獲取一個(gè)數(shù)的相反數(shù)呢？
求相反數(shù)很簡(jiǎn)單，直接取反加一即可。也就是 
負(fù)數(shù)同樣適用。
那么利用這一點(diǎn)，就可以輕松的實(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); }運(yùn)算結(jié)果如下： 
除此之外，還有一個(gè)直接操作二進(jìn)制的方式，
int Subtract(int a, int b){ while (b != 0) { int sameBits = a & b; a ^= sameBits; b ^= sameBits; a |= b; b <<= 1; } return a;}還有其他的乘除運(yùn)算的實(shí)現(xiàn)方法，詳情請(qǐng)參考下面的鏈接： http://www.cppblog.com/qingbizhu/archive/2012/03/30/168148.html
求子字符串在字符串中第一次出現(xiàn)的位置，這倒是一個(gè)挺簡(jiǎn)單的實(shí)現(xiàn)，至于那個(gè)改進(jìn)版的，我還不太理解，就不寫了。
/** * @Date 2017年3月5日 * * @author 郭 璞 * */package interview;/** * @author 郭 璞 * * 關(guān)于字符串中字串位置的查找相關(guān)的幾個(gè)實(shí)現(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; }}運(yùn)算結(jié)果如下：
2打靶10次，得到90分的方式有幾種? 像這種問題還有很多，什么雞兔同籠啊，百錢白雞啊，都是類似的。
一方面我們可以采用枚舉法來暴力破解，另一方面就只能采用遞歸。兩者各有利弊吧，今天的這個(gè)打靶問題，我就用遞歸來實(shí)現(xiàn)一下。
/** * @Date 2017年3月3日 * * @author 郭 璞 * */package interview;/** * @author 郭 璞 * * 打靶的遞歸實(shí)現(xiàn) * */public class ShootTest { /** * 設(shè)置為11位的數(shù)組是因?yàn)橄逻叞?開始到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 * 打印的時(shí)候是按照第一槍到第number槍來計(jì)算的，因?yàn)橐先祟愂澜绲膹?開始的計(jì)算。 */ private static void print(int[] record2) { for (int index = 1; index < record2.length; index++) { System.out.print("/t" + record2[index]); } System.out.println("-----------------------------------"); }}運(yùn)算結(jié)果： 
好像面試的時(shí)候好多問題都是為了問題而問題，這樣的考察我覺得不是很好，畢竟實(shí)際中不會(huì)有這么偏門的問題吧。但是為了更好的充實(shí)自己，了解一下還是不錯(cuò)的。
這篇文章就先這樣啦，以后再遇到這類問題，也許會(huì)更新一下，也會(huì)會(huì)另寫一篇。
如果看到了此文的你有類似的好的面試題的解法，也可以在下面留言評(píng)論，讓我們一起進(jìn)步吧。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
