一些小的算法，都是java版的，网络上大量的题都是针对C++的，因此java的实现很少，但是都是考的基础，
实现都是一样，可以开阔一下思路，有益无敝。
/**
* 1 跳台阶问题
* 题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。
* 求总共有多少总跳法，并分析算法的时间复杂度。
* 是一个组合题， 完全正确很难，
* 总共有m台阶 n为2个台阶
* O( ( m - n) * (2n - 1)) )
*/
public class JumpFootstep {
public static void main(String[] args) {
jumpStepWay(10);
}
private static void jumpStepWay(int n) {
int twoStep = 1;
while (2 * twoStep <= n) {
printLeftJoin(twoStep, n);
for (int i = 1; i <= twoStep; i++) {
int oneStep = n - 2 * twoStep;
List<Integer> ls = new ArrayList<Integer>();
for (int j = 1; j <= oneStep; j++) {
for (int k = 0; k < (twoStep - i); k++) {
ls.add(2);
}
for (int m = 0; m < j; m++) {
ls.add(1);
}
for (int m = 0; m < i; m++) {
ls.add(2);
}
for (int m = 0; m < oneStep - j; m++) {
ls.add(1);
}
print(ls);
ls.clear();
}
if (i != twoStep) {
for (int j = 1; j <= oneStep; j++) {
for (int m = 0; m < j; m++) {
ls.add(1);
}
for (int m = 0; m < i; m++) {
ls.add(2);
}
for (int m = 0; m < oneStep - j; m++) {
ls.add(1);
}
for (int k = 0; k < (twoStep - i); k++) {
ls.add(2);
}
print(ls);
ls.clear();
}
}
}
twoStep++;
}
}
private static void printLeftJoin(int twoStep, int n){
for (int i = 1; i <= twoStep; i++) {
System.out.print(2);
}
for (int i = 1; i <= n - 2 * twoStep; i++) {
System.out.print(1);
}
System.out.println();
}
private static void print(List<Integer> ls ){
for (int m = 0; m < ls.size(); m++) {
System.out.print(ls.get(m));
}
System.out.println();
}
}
跳台阶的答案中有重复的输出，是一个待解决之问题！
/**
* 2 整数的二进制表示中1的个数
* 题目：输入一个整数，求该整数的二进制表达中有多少个1。
* 例如输入10，由于其二进制表示为1010，有两个1，因此输出2。
*
* @author wangjichen
*
*/
public class BinaryOneCount {
public static void main(String[] args) {
long b = 1101;
long i = 1;
int count = 0;
int time = 0;
while (i > 0) {
long f = i & b;
f >>= time;
if (f == 1) {
count++;
}
i <<= 1;
time++;
}
System.out.println(count);
}
}
千万不能把b的值向右移动，来和i=1相比较，会出现死循环，想一想为什么吧。。。
/**
* 3 在从1到n的正数中1出现的次数
* 题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。
* 例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。 分析：这是一道广为流传的google面试题。
*
* @author wangjichen
*
*/
public class DecimalOneCount {
public static void main(String[] args){
judge(111);
}
private static void judge(int n){
int result = 0;
for(int i = n; i >= 0; i --){
result += eachJudge(i);
}
System.out.println(result);
}
private static int eachJudge(int n){
int count = 0;
while(n > 0){
int f = n % 10;
if(f == 1){
count ++;
}
n /= 10;
}
return count;
}
}
第二道题的答案是，当b为负数时，就是死循环了。
不知道考官是不是想考这个，不过大体思路大家都会，估计左右移动的方向就是招人的分界线了。
谨慎是金哪！