Algorithm & DataStructure

算法
, ,

记录一下算法书上出现的各种算法的java实现,推荐全部手写/IDE敲一次.

包括实现ds,这里一般采用最简的模型,没多使用泛型T. 尽量关注本质. 其中java主函数特有的static其它语言去掉就行. 比如方法开头的private static,我就不一一去了. 然后别搞一堆get/set方法做算法题.特别是OJ时.

这里还列一下常用的java输入情况,以及处理方式. 不然在线IDE会经常遇到小问题.

1. 位运算

Q1. 输入一个整数,输出二进制中1的个数? (三种思路)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private static void countBinaryOne1(int i) {
        int count = 0;
        while (i != 0){
            if((i & 1)==1) count++;
            i = i >> 1;
        }
        System.out.println(count);
    }



private static void countBinaryOne2(int i) {
        int count = 0;
        int temp = 1;
        while (temp != 0){
            if((i & temp)!=0) count++;
            temp = temp << 1;
        }
        System.out.println(count);
    }
 //最优思路
 private static void countBinaryOne3(int i) { //数&(数-1) 等价于把这个数的二进制位第一位1变0
        int count = 0;
        while (i != 0){
            i = (i-1) & i;
            count++;
        }
        System.out.println(count);
    }

然后从上面最优思路,我们衍生出的变形.

Q1.1 一条语句判断一个整数是否是2的整数次方?

1
2
//规律是2的n次方转为二进制,有且只有一位是1,运用上面的思路,把那个1变成0,就全为0了.
System.out.println((i & (i-1))==0?"true":"false");

Q2. 计算m,n两个数二进制位不同有几位? (比如 1011 跟 1100 差3)

1
2
3
4
5
6
7
8
9
private static void countDiffDigit(int m, int n) {
        int count = 0;
        int diff = m ^ n;
        while (diff != 0){
            diff = diff & (diff - 1);
            count++;
        }
        System.out.println(count);
    } //会发现本质就是,先用^算出异或,根据异或特性不同为1,然后用上述思路求一次就行了.