剑指Offer试题——Java实现（四）

4.1 在不使用±*/的条件下，计算两个整数相加

这里考察的就是对位运算的掌握情况
public static int addWithoutOperator(int num1,int num2){
	while(num2!=0){
		//计算个位
		int tmp=num1^num2;
		//计算进位
		num2=(num1&num2)<<1;
		num1=tmp;
	}
	return num1;
}

4.2 计算1~n的和，不得使用流程控制关键字

//所谓流程控制，也就是循环、条件判断三元表达式
//这里使用递归来代替循环
//同时使用
public static int sumSolution(int n){
	int sum=n;
	//终止递归
	boolean result=(n>0)&&((sum+=sumSolution(n-1))>0);
	return sum;
}

4.3 约瑟夫环问题

注释中的解题思路不是我的，所以附上原文链接。
好像也不是这个作者的，不过没关系，他在文章中也附上连接了。

/**
* 作者：wdg666
* 链接：https://www.zhihu.com/question/20065611/answer/148654996
* 来源：知乎
* 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*
* 假设问题是从n个人编号分别为0...n-1，取第k个，则第k个人编号为k-1的淘汰，剩下的编号为  0,1,2,3...k-2,k,k+1,k+2...此时因为从刚刚淘汰那个人的
* 下一个开始数起，因此重新编号把k号设置为0,则
* k    0
* k+1 1
* ...
* 0 n-k
* 1 n-k+1
* 假设已经求得了n-1个人情况下的最终胜利者保存在f[n-1]中，则毫无疑问，
* 该胜利者还原到原来的真正编号即为 (f[n-1]+k)%n （因为第二轮重新编号的时候，相当于把每个人的编号都减了k，因此重新+k即可恢复到原来编
* 号）。由此，我们可以想象，当最终只剩下一个人的时候，该人即为胜利者，此时重新编号，因为只有一个人，所以此时f[1]=0这样f[2]=(f[1]+k)%2,这
* 样就可以求出最终胜利者在2个人的时候的情况下的编号，由递推公式f[n]=(f[n-1]+k)%n,可递推到最初编号序列中该胜利者的编号。因此用这个方法，
* 只需一遍On的扫描，即可求出最终答案不过该题要求编号从1开始，只要把f[n]+1即可，同时，该题指定了第一个要删除的人必须为编号为m的人，其
* 实也不难，求出f[n]之后，把原本编号为0的位置移到跟m只相距k的位置即可实现第一次删除的编号为m。所以最终 ans=(f[n]+1+m-k);
*/
public static int lastRemain(int n,int m){
	if(n==0)
		return -1;
	if(n==1)
		return 0;
	else
		return (lastRemain(n-1,m)+m)%n;
}

4.4 计算输入的整数用二进制表示有多少1

/**
* n&(n-1)运算会将n的最右边一位变为0，循环x次后n变为0，则1的个数为x
*/
public static int calNumberOf1(int n){
	int count=0;
	while(n!=0){
		n=n&(n-1);
		count++;
	}
	return count;
}