前言
最近正在紧锣旗鼓的准备面试，期间遇到了许多好精巧的算法问题。于是大致实现了下，做个笔记。
判断一个数是否为2的幂
这个题有两种解法，一个是常规的，思路如下：
不断的将这个数除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;
}
这样是不是既高效又简便呢？
不使用if, while, for,switch，goto等关键字实现100行代码打印出1000个helloworld
按照常规理解，这是不可能的了。那么要怎么实现呢？
我个人倒是觉得绕开这些关键字倒是个不错的方法，比如使用更底层的语言。高级语言之下不是还有诸如汇编语言，机器语言这些的嘛，虽然可读性会很差，但是也不失为一个好办法。
但是非得让用某一个语言来实现，要怎么做呢？
答案之一就是用递归来实现。且看下面的代码。
# 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 "共执行了{}次，得到了{}个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
实现BMP算法
求子字符串在字符串中第一次出现的位置，这倒是一个挺简单的实现，至于那个改进版的，我还不太理解，就不写了。
/**
* @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("-----------------------------------");
}
}
运算结果：
总结
好像面试的时候好多问题都是为了问题而问题，这样的考察我觉得不是很好，毕竟实际中不会有这么偏门的问题吧。但是为了更好的充实自己，了解一下还是不错的。
这篇文章就先这样啦，以后再遇到这类问题，也许会更新一下，也会会另写一篇。
如果看到了此文的你有类似的好的面试题的解法，也可以在下面留言评论，让我们一起进步吧。
