一、智者说:无聊的时候来几道算法题,可以训练训练自己的思维嘛!难怪之前人家说数学好的人编程起来事半功倍,写算法的过程中真是深有体会啊!感觉就像是在做大学的高数题......本博文仅用来记录自己学习算法的历程,不定时更新。参考自《编程之美》,加上些自己的理解。有啥不对的地方,还请大家不吝指教!
二、求二进制数中1的个数(对于一个字节(8bit)的变量,求其二进制中"1"的个数,要求算法的执行效率尽可能高)
public class One
{
public static void main(String[] args)
{
int v = 0b10101010;
System.out.println(count(v));
System.out.println(count2(v));
System.out.println(count3(v));
}
/*解法一:对于2进制来说,把他除以2就是向左移了一位,余数为0,代表最后一位为0。余数为1,代表最后一位为1*/
public static int count(int v)
{
int count = 0;
while (v != 0) {
if (v % 2 == 1) {
count++;
}
v = v / 2;
}
return count;
}
/*解法二:使用位操作,每次向右移动1位,即抛弃一位。跟00000001进行与运算判断是否为1*/
public static int count2(int v){
int count=0;
while (v!=0){
count += v & 0B00000001;
v=v>>1;
}
return count;
}
/*解法三:前面两种解法的时间复杂度都是O(log2n),通过二进制数每次和(二进制-1)进行与运行,都会使二进制中少了一个1*/
public static int count3(int v){
int count=0;
while (v!=0){
v=v&(v-1);
count++;
}
return count;
}
/*拓展题:给定两个正整数(二进制表示的A和B),请问把A变成B需要改变多少位?也就是说A和B的二进制表示中有多少位是不同的
* 原理:
* 1. A & B,得到的结果C中的1的位表明了A和B中相同的位都是1的位;
* 2. A | B, 得到的结果D中的1的位表明了A和B在该位至少有一个为1的位,包含了A 与 B 都是1的位数,经过前两步的位运算,,C 中1的位表明了A 和 B在该位都是1,D中为0的位表明了A 和 B 在该位都是0 ,所以进行第三步。
* 3. C ^ D,E 中为1的位表明了A 和 B不同的位。
* */
public static int diff(int A,int B){
int sum=0;
int C = A & B;
int D = A | B;
int E = C ^ D;
sum=count2(E);
return sum;
}
}
三、1、给定一个整数N,那么N的阶乘N!末尾有几个0呢?
2、求N!的二进制表示中最低位1的位置
public class Two
{
public static void main(String[] args)
{
System.out.println(count(27));
System.out.println(count2(27));
System.out.println(count3(27));
}
/*问题一的解法一
* 解答思路:N!=K*10^m(m>=0),那么m的个数就是末尾0的个数。
* N!=2^x * 3^y * 5^z * 7^n…… 不可否认任何一个数都可以这样分解开来,其中这个因式分解中
* 2^x * 5^z 能够组成多少10^m的数,取决于min(x,z)。想想就知道被2整除的频率比被5整除的频
* 率高多了,所以只要计算N!因式分解中5的指数。
* */
public static Integer count(final int N){
int sum=0;
for(int i=1;i<=N;i++){
int j=i;
while(j % 5==0){
sum++;
j/=5;
}
}
return sum;
}
/*问题一的解法二
*解题思路:Z=N/5 + N/5^2 + N/5^3……(不用担心这会是一个无穷的运算,因为总存在一个K,使得5^k>N,则 N/5^k=0)
* 公式中,N/5表示不大于N的数中5的倍数贡献一个5,N/5^2 表示不大于N的数中5^2的倍数再贡献一个5.
*
* 上面是《编程之美》的解释?反正我没看懂,下面说一下个人见解:
* 比如 一个数 26 那么 26 / 5= 5 表示26的阶乘里面有 5 10 15 20 25 五个数可以贡献 5
* 26 / 25=1 表示25的阶乘里面有 25 可以贡献 5 ,所以25 又贡献了一次
* */
public static Integer count2(int N){
int sum=0;
while (N!=0){
sum+=N/5;
N=N/5;
}
return sum;
}
/*问题二的解法
* 这么理解:二进制除以2相当于向左移了一个小数点(参照10进制除以10),余数为0表示可以被除断,
* 为1表示有余数不能被除断。所以 求N!的二进制表示中最低位1的位置,就可以求最低位1
* 后面有几个零,把他加1 就可以了。
* 而 1 后面有几个零,取决于N!中2的个数,因为每存在一个2,则在数的最低位多1个0
* */
public static Integer count3(int N){
int sum=0;
while (N!=0){
N = N >> 1;//相当于N=N/2
sum+=N;
}
return sum+1;
}
}
四、传说,Tango有一大“水王”,他不但喜欢发帖,还会回复其他ID发的帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上的帖子(包括回帖)的列表,其中帖子作者的ID也在其中,你能快速找出这个传说中的Tango水王吗?
public class Three
{
public static void main(String[] args)
{
Tango[] tangos=new Tango[8];
Tango tango=new Tango(1);
Tango tango2=new Tango(2);
Tango tango3=new Tango(3);
tangos[0]=tango3;
tangos[1]=tango;
tangos[2]=tango;
tangos[3]=tango2;
tangos[4]=tango;
tangos[5]=tango;
tangos[6]=tango;
tangos[7]=tango2;
Tango tango1 = find(tangos);
System.out.println(tango1);
}
/*
* 解题思路:原理:如果每次删除两个不同的ID(不管是否包含“水王”的ID),那么,在剩下的ID列表中,“水王”ID出现的次数
* 仍然超过次数的一半。
*
* 这里的解题思路是先把tangos数组中的第一个假设成“水王”tango,如果tangos第二个与第一个不一样,
* 就不管这两个了,然后把第三个再假设成“水王”,如果第四个ID和第三个一样,那么nTiames就变成了2,
* 也就是说,数组后面至少要有两个与现在假设的ID不一样,才会引起tango的重新赋值,而这样一直到最少,
* 剩下的就是那个“水王”了。
*
* 当然,你也可以对数组排序,那么N/2 位置的就一定是“水王”了(因为"水王"出现的次数超过了总数的一半)
* */
public static Tango find(Tango[] tangos){
Tango tango=null;
int nTiames=0;
for (int i=0;i<tangos.length;i++){
if (nTiames==0){
tango=tangos[i];
nTiames=1;
}else {
if (tango.equals(tangos[i])){
nTiames++;
}else {
nTiames--;
}
}
}
return tango;
}
/*扩展题:随着Tango的发展,管理员发现,“超级水王”没有了。统计结果说明,有三个发帖很多的ID,他们的发帖数目
* 都超过了帖子宗数目的N的1/4。你能从发帖ID列表中快速找出他们的ID吗?
* */
public static Tango[] find2(Tango[] tangos){
if (tangos==null) return null;
Tango tango=null,tango1=null,tango2=null;
int num1=0,num2=0,num3=0;
int len=tangos.length;
for (int i=0;i<len;i++){
if(num1==0 && tangos[i]!=tango1 && tangos[i]!=tango2){
tango=tangos[i];
num1++;
}
else if (num2==0 && tangos[i]!=tango && tangos[i]!=tango2){
tango1=tangos[i];
num2++;
}
else if (num3==0 && tangos[i]!=tango1 && tangos[i]!=tango2){
tango2=tangos[i];
num3++;
}
else if (tangos[i]!=tango && tangos[i]!=tango1 && tangos[i]!=tango2){
num1--;
num2--;
num3--;
}
else if (tangos[i]==tango){
num1++;
}
else if (tangos[i]==tango1){
num2++;
}
else if (tangos[i]==tango2){
num3++;
}
}
Tango[] result={tango,tango1,tango2};
return result;
}
}