前言判断一个数是否为2的幂不使用if while forswitchgoto等关键字实现100行代码打印出1000个helloworld不使用实现一个加法函数不使用-实现减法函数实现BMP算法打靶问题总结
最近正在紧锣旗鼓的准备面试，期间遇到了许多好精巧的算法问题。于是大致实现了下，做个笔记。
这个题有两种解法，一个是常规的，思路如下：
不断的将这个数除2，求得余数。当余数为1的时候，判断当前除数和2的大小关系，如果大于2，则说明此数不是2的幂，如果小于2则说明此数为2的幂。
另外一个方法就比较hack了，思路如下：
如果一个数为2的幂，则二进制首位必为1，其余位为0. 将这个数减一，得到的数与该数相与，结果为0则说明此数为2的幂数，否则不是。
代码可以大致写成这样。
public boolean isPowerOf2(int number) { return ((number-1)&number)==0?true:false;}这样是不是既高效又简便呢？
按照常规理解，这是不可能的了。那么要怎么实现呢？
我个人倒是觉得绕开这些关键字倒是个不错的方法，比如使用更底层的语言。高级语言之下不是还有诸如汇编语言，机器语言这些的嘛，虽然可读性会很差，但是也不失为一个好办法。
但是非得让用某一个语言来实现，要怎么做呢？
答案之一就是用递归来实现。且看下面的代码。
# coding: utf8number = 0def 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 "共执行了{}次，得到了{}个Hello World!".format(number, number)得到的结果呢？ 
这样，使用递归的方式便可以实现100行以内的代码获取到大于1000行Hello World！的输出了。
这就有点难为人了，反正我是怎么想也没想出来。后来参考网上的思路，使用模拟与数字电路的方式可以实现。
原理就是：
两个数先异或运算两个数相与的结果左移一位递归判断，获取返回结果使用代码实现起来可能如下：
public static int addWithoutOperators(int number1, int number2) { // 如果有一个数为0，则直接返回另一个数 if(number2 == 0) return number1; if(number1 == 0) return number2; // 先异或运算 int sum = number1 ^ number2; //求出进位，这时对于01,10,00都是不产生进位的，只有11才会产生进位 int carry = ( number1 & number2 ) << 1; return addWithoutOperators(sum, carry); }运算测试 
两数相减，就是一个数加上另一个数的相反数呗。我们常规就是这么理解的，那么怎样才能获取一个数的相反数呢？
求相反数很简单，直接取反加一即可。也就是 
负数同样适用。
那么利用这一点，就可以轻松的实现减法函数了。
public static int subtractWithoutOperators(int number1, int number2) { if(number1 == number2) return 0; int reverse = addWithoutOperators(~number2, 1); return addWithoutOperators(number1, reverse); }运算结果如下： 
除此之外，还有一个直接操作二进制的方式，
int Subtract(int a, int b){ while (b != 0) { int sameBits = a & b; a ^= sameBits; b ^= sameBits; a |= b; b <<= 1; } return a;}还有其他的乘除运算的实现方法，详情请参考下面的链接： http://www.cppblog.com/qingbizhu/archive/2012/03/30/168148.html
求子字符串在字符串中第一次出现的位置，这倒是一个挺简单的实现，至于那个改进版的，我还不太理解，就不写了。
/** * @Date 2017年3月5日 * * @author 郭 璞 * */package interview;/** * @author 郭 璞 * * 关于字符串中字串位置的查找相关的几个实现 * */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; }}运算结果如下：
2打靶10次，得到90分的方式有几种? 像这种问题还有很多，什么鸡兔同笼啊，百钱白鸡啊，都是类似的。
一方面我们可以采用枚举法来暴力破解，另一方面就只能采用递归。两者各有利弊吧，今天的这个打靶问题，我就用递归来实现一下。
/** * @Date 2017年3月3日 * * @author 郭 璞 * */package interview;/** * @author 郭 璞 * * 打靶的递归实现 * */public class ShootTest { /** * 设置为11位的数组是因为下边按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替代，但是根据不同的要求还需要硬编码替换！ 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("-----------------------------------"); }}运算结果： 
好像面试的时候好多问题都是为了问题而问题，这样的考察我觉得不是很好，毕竟实际中不会有这么偏门的问题吧。但是为了更好的充实自己，了解一下还是不错的。
这篇文章就先这样啦，以后再遇到这类问题，也许会更新一下，也会会另写一篇。
如果看到了此文的你有类似的好的面试题的解法，也可以在下面留言评论，让我们一起进步吧。
新闻热点
疑难解答
