• 前言
• 0. *經驗總結
  • 0.1 程式員面試金典 P94
  • 0.2 Java中的位運算相關代碼
    • 1. 算數移位
    • 2. 邏輯移位
    • 3. 獲取數位
    • 4. 設定數位
    • 5. 清零數位
    • 6. 更新數位
  • 0.3 Java判斷double是否為整數的方法
  • 0.4 Java進制轉換API
  • 0.5 Math類常用API
  • 0.6 位操作技巧（重要）
  • 0.7 Java運算優先級
  • 0.8 Java中常用基本型別的取值范圍
  • 0.9 特殊二進制
• 1. 插入 [easy]
  • 1.1 考慮點
  • 1.2 解法
    • 1.2.1 位運算（優）
• 2. 二進制數轉字串 [medium]
  • 2.1 考慮點
  • 2.2 解法
    • 2.2.1 count計數法
    • 2.2.2 折半比較法（優）
• 3. 翻轉數位 [easy]
  • 3.1 考慮點
  • 3.2 解法
    • 3.2.1 逐個遍歷法
    • 3.2.2 滑動視窗法（優）
• 4. 下一個數 [medium]
  • 4.1 考慮點
  • 4.2 解法
    • 4.2.1 位運演算法（優）
    • 4.2.2 暴力窮舉法
    • 4.2.3 看不懂啥方法
• 6. 整數轉換（漢明距離） [easy]
  • 6.1 考慮點
  • 6.2 解法
    • 6.2.1 異或遍歷法（優）
• 7. 配對交換 [easy]
  • 7.1 考慮點
  • 7.2 解法
    • 7.2.1 隔位操作法
    • 7.2.2 特殊二進制法（優）
• 8. 繪制直線 [medium]
  • 8.1 考慮點
  • 8.2 解法
    • 8.2.1 逐組分析法
    • 8.2.2 位運算（優）
• 最后

前言

本系列筆記主要記錄筆者刷《程式員面試金典》演算法的一些想法與經驗總結，按專題分類，主要由兩部分構成：經驗值點和經典題目，其中重點放在經典題目上；

0. *經驗總結

0.1 程式員面試金典 P94

• 位操作是優化代碼的一種技巧；

• 一些操作技巧：（1s和0s表示一串1和0）

  • 乘2：左移1位；
  • 異或^：同0異1；
  • 某數與111100做與&運算：將某數最后2位清零；

  異或	與	或
  x ^ 0s = s	x & 0s = 0	x | 0s = x
  x ^ 1s = ~x	x & 1s = x	x | 1s = 1s
  x ^ x = 0	x & x = x	x | x = x

  • 根據正數求復數：所有取反加1，符號位變為1；
  • 邏輯右移與算數右移：對于數 1 0110101（-75）；
    • **邏輯右移 >>> **：移位后 0 1011010（90），最終得到0；
    • **算數右移>> **：移位后 1 1011010（-38），最終得到-1；

0.2 Java中的位運算相關代碼

1. 算數移位

算數左移乘2補0；算數右移除2，正數補0復數補1；持續算移得-1或0；

int repeatedAritmeticShift(int x, int count){
	for(int i = 0; i < count; i++){
		x >>= 1;  //算數右移1位
	}
	return x;
}

2. 邏輯移位

邏輯左移乘2補0；邏輯右移除2補0；持續邏移得0；

int repeatedLogicalShift(int x, int count){
	for(int i = 0; i < count; i++){
		x >>>= 1;  //邏輯右移1位
	}
	return x;
}

3. 獲取數位

將1算數左移i位得0001000（假設i為3），接著與num做位與&運算，將除i位外的位清零，保留i位，檢查結果為1（或0），則num第i位為1（或0）；

boolean getBit(int num, int i){
	return ((num & (1 << i)) != 0);
}

4. 設定數位

將1算數左移i位得0001000（假設為3），接著與num做位或|運算，將i位設定為1；

int setBit(int num, int i){
	return num | (1 << i);
}

5. 清零數位

清零第i位：

將1算數左移i位后取反得1110111（假設i為3），接著與num做位與&運算，將i位清零，其余位不變；

int clearBit(int num, int i){
	int mask = ~(1 << i);
	return num & mask;
}

清零最高位到第i位（包括最高和第i位）：

將1算數左移i位得0001000（假設i為3），減1得0000111，接著與num做位與&運算，保留后i位；

int clearBitMSBthroughI(int num, int i){
	int mask = (1 << i) - 1;
	return num & mask;
}

清零第i位到第0位（包括第i位和第0位）：

將全1構成的數 1111111 算數左移i位得 1111000，接著與num做位與&運算保留前面；

int clearBitsIthrough0(int num, int i){
	int mask = (-1 << (i+1));
	return num & mask;
}

6. 更新數位

將第i位設定為v：先將1算數左移i位取反得1110111（假設i為3），與num做位與&運算將i位清零，得結果1，將待寫入值v左移i位得結果2：0001000（或0000000），結果1與結果二做位或|運算即可；

int updateBit(int num, int i, boolean bitIs1){
	int value = https://www.cnblogs.com/dlhjw/p/bitIs1 ? 1 : 0;
	int mask = ~(1 << i);
	return (num & mask) | (value << i);
}

0.3 Java判斷double是否為整數的方法

Math.abs(num - (int)num) < 0.000001

0.4 Java進制轉換API

• Integer類的靜態方法：
• static String toBinaryString(int i)：回傳數字i的二進制數字串；
• static String toOctalString(int i)：回傳數字i的八進制數字串；
• static String toHexString(int i)：回傳數字i的十六進制數字串；
• static int parseInt(String s)： 將字串引數s決議為帶符號的十進制整數；
• static int parseInt(String s, int radix)： 將整數字串s（radix用來指明s是幾進制）轉換成10進制的整數；

0.5 Math類常用API

• static double abs(double a)：回傳double值的絕對值；
• static double ceil(double a)：向上取整，回傳大于等于引數的最小的整數；
• static double floor(double a)：向下取整，回傳小于等于引數最大的整數；
• static long round(double a)：回傳最接近引數的long；(相當于四舍五入方法)
• static int max(int a, int b) ：回傳a與b中較大值；
• static int min(int a, int b)：回傳a與b中較小值；
• static double log10(double a)：回傳 double值的基數10對數；
• static double pow(double a, doubl b) ：a^b；
• static double sqrt(double a) ：回傳 double值的正確舍入正平方根；

0.6 位操作技巧（重要）

0.7 Java運算優先級

0.8 Java中常用基本型別的取值范圍

0.9 特殊二進制

在一些方法中利用特殊二進制有妙招（如：7.配對交換）；

1. 插入 [easy]

1.1 考慮點

• 解決多位操作的問題時，需要進行測驗，否則很容易犯下差一位的錯誤；

1.2 解法

1.2.1 位運算（優）

public int insertBits(int N, int M, int i, int j) {
    int mask = ~(((int)Math.pow(2, j-i+1)-1)<<i);
    int m = M<<i;
    int result = (N & mask);
    return result | m;
}

• 執行時間：100.00%；記憶體消耗：95.99%；

2. 二進制數轉字串 [medium]

2.1 考慮點

• 注意準備好測驗用例；

2.2 解法

2.2.1 count計數法

public String printBin(double num) {
    int count = 0;
    boolean isFind = false;
    while(count <= 30 && !isFind){
        num*=2;
        count++;
        if(Math.abs(num - (int)num) < 0.000001){
            isFind = true;
        }
    }
    if(isFind){
        StringBuilder sb = new StringBuilder();
        sb.append("0."); //這里注意不要寫成 sb.append(0.)
        int n = (int)num;
        while(n != 0){
            n/=2;
            count--;
        }
        for(int i = 0; i < count; i++){
            sb.append(0);
        }
        sb.append( Integer.toBinaryString( (int)num) );
        return sb.toString();
    } else {
        return "ERROR";
    }
}

• 執行時間：100.00%；記憶體消耗：45.18%；
• 統計需要乘多少個2才變成整數，減去轉成二進制后的位數，得有效位0的數量；

2.2.2 折半比較法（優）

public String printBin(double num) {
    String str = "0.";
    double i = 0.5;
    while(str.length() < 32){
        if(num-i >= 0){
            str += "1";
            num = num - i;
        }else{
            str += "0";
        }
        if(num == 0){
            return str;
        }
        i /= 2;
    }
    return "ERROR";
}

• 執行時間：100.00%；記憶體消耗：97.48%；
• num逐個減去 2^-1、2^-2、2^-3……減法成功則為添1，否則添0；

3. 翻轉數位 [easy]

3.1 考慮點

• 注意num為負數的情況，num=-1時，其二進制數為32個1；

3.2 解法

3.2.1 逐個遍歷法

public int reverseBits(int num) {
    //注意num為-1的情況
    if(num == -1){
        return 32;
    }
    String binaryString = Integer.toBinaryString(num);
    int a = 0;
    int b = 0;
    int max = 0;
    int count = 0;
    for(int i = 0; i < binaryString.length(); i++){
        if(binaryString.charAt(i) == '0'){
            a = b;
            b = count;
            count = 0;
            if(a+b > max){
                max = a+b;
            }
        } else {
            count++;
        }
    }   
    //最后一位不為0時，count的數出不來；
    if(count != 0){
        max = Math.max(b+count, max);
    }
    return max+1;
}

• 執行時間：100.00%；記憶體消耗：61.13%；
• 時間復雜度：O(n)，n為整數的位數；注意需要跟面試官說明n的含義，不然有可能會有歧義；
• 空間復雜度：O(1)；
• 需要注意最后一位不為0的情況與num為負數的情況；

3.2.2 滑動視窗法（優）

public int reverseBits(int num) {
    int max = 0;
    int count = 0;
    boolean flag = false;
    int start = 0;
    for (int i = 31; i >= 0; i--) {
        int i1 = (num >> i) & 1;
        if (i1 == 1) {
            count++;
            max = Math.max(max, count);
        } else {
            if (!flag) {
                count++;
                flag = true;
                start = i;
                max = Math.max(max, count);
            } else {
                count = 0;
                i = start;
                flag = false;
            }
        }
    }
    return max;
}

• 執行時間：100.00%；記憶體消耗：99.05%；

4. 下一個數 [medium]

4.1 考慮點

• 注意特殊值，兩個邊界范圍；
• 注意移位方向；

4.2 解法

4.2.1 位運演算法（優）

public int[] findClosedNumbers(int num) {
    if(num == 1){
        return new int[]{2,-1};
    }
    if(num == 2147483647){  //注意特殊值
        return new int[]{-1,-1};
    }
    //較大：從右往左遍歷，找到遇到1后的一個0（期間統計1的個數count1），交換0和1，
    //如果n不為1，需要把其余1后移；如果n為1，不做處理；
    boolean isFound0 = false;
    int count1 = 0;
    int i = 0;
    while(!isFound0){
        if(count1 != 0 && ((num >> i) & 1) == 0){ //注意加括號，不然優先級不夠
            isFound0 = true;
        }
        if(((num >> i) & 1) == 1){
            count1++;
        }
        i++;
    }
    int moreNum = 0;
    if(count1 == 1){
        moreNum = num >> (i-1);
        moreNum++;
        moreNum = moreNum << (i-1);
    } else {
        moreNum = num >> i-1;
        moreNum++;
        moreNum = moreNum << (i-count1);
        for(int k = 0; k < count1-1; k++){
            moreNum = moreNum << 1;
            moreNum++;
        }
    }
    //較小：從右往左遍歷，找到第一個1（統計期間0的個數count0），
    //如果m不為0，則該1退一位；反之，遍歷到有0后的第一個1，該1退位，后面1補上接著；
    boolean isFound1 = false;
    int count0 = 0;
    int j = 0;
    while(!isFound1){
        if(((num >> j) & 1) == 1){
            isFound1 = true;
        } else {
            count0++;
        }
        j++;
    }
    int lessNum = 0;
    if(count0 == 0){
        isFound0 = false;
        isFound1 = false;
        count1 = 1;
        while(!isFound0){
            if(((num >> j) & 1) == 0){
                isFound0 = true;
            } else {
                count1++;
            }
            j++;
        }
        while(!isFound1){
            if(((num >> j) & 1) == 1){
                count1++;
                isFound1 = true;
            }
            j++;
        }
        lessNum = num >> j;
        lessNum = lessNum << 1;
        for(int k = 0; k < count1; k++){
            lessNum = lessNum << 1;
            lessNum++;
            j--;
        }
        lessNum = lessNum << (j-1);
    } else {
        lessNum = num >> j; //注意方向
        lessNum = lessNum << 2;
        lessNum++;
        lessNum = lessNum << (j-2);
    }
    return new int[]{moreNum, lessNum};
}

• 執行時間：100.00%；記憶體消耗：89.61%；

4.2.2 暴力窮舉法

public int[] findClosedNumbers(int num) {
    if(num == 1){
        return new int[]{2,-1};
    }
    if(num == 2147483647){  //注意特殊值
        return new int[]{-1,-1};
    }
    int up = num + 1;//向上列舉
    int down = num - 1;//向下列舉
    int count = findOneCount(num);//num的1的個數
    while (findOneCount(up) != count) {
        up++;
        if (up < 0) {//越界了那就是找不到，設定為-1
            up = -1;
            break;
        }
    }
    while (findOneCount(down) != count) {
        down--;
        if (down < 0) {//變為負數了那就是找不到了，設定為-1
            down = -1;
            break;
        }
    }
    return new int[]{up, down};
}
//求數的二進制1的個數
private static int findOneCount(int num) {
    int count = 0;
    while (num != 0) {
        num &= num - 1;
        count++;
    }
    return count;
}

• 執行時間：100.00%；記憶體消耗：55.20%；

4.2.3 看不懂啥方法

public int[] findClosedNumbers(int num) {
    int mx = nextOne(num), mi = ~nextOne(~num);
    return new int[]{mx > 0 ? mx : -1, mi > 0 ? mi : -1};
}
public int nextOne(int x){
    long lowbit = x & (-x);
    long toZero = x + lowbit;
    return (int)((x & ~toZero) / lowbit >> 1 | toZero);
}

• 執行時間：100.00%；記憶體消耗：45.16%；
• 如果1的個數不同直接往低位加，這里要求相同，所以只能把最右邊的連續1左移，然后保留連續1區間的最左一個，剩下的（連續長度-1）個的搬到全域最右邊，步驟：
  • 1.先求出二進制最右邊的1得到 lowbit = x & (-x)；
  • 2.求出最左1也就是消去連續1得到連續0 toZero = x + lowbit；
  • 3.把（最右連續1長度-1）個1搬到全域最優 (x & ~toZero) / lowbit >> 1；
  • ps: ~toZero 與 x 進行并得到最右連續1部分 /lowbit 后把1搬到右邊 這里因為相加進位，所以要右移去掉一個1

6. 整數轉換（漢明距離） [easy]

6.1 考慮點

• 將最低位清零的寫法n = n & (n-1)；

6.2 解法

6.2.1 異或遍歷法（優）

//第一種寫法
public int convertInteger(int A, int B) {
    int C = A ^ B;
    int count = 0;
    for(int i = 0; i < 32; i++){
        if(((C >> i) & 1) == 1){
            count++;
        }
    }
    return count;
}
//第二種寫法
public int convertInteger(int A, int B) {
    int count = 0;
    for(int C = A ^ B; C != 0; C = C >>> 1){
        count += C & 1;
    }
    return count;
}
//第三種寫法（優）
public int convertInteger(int A, int B) {
    int count = 0;
    for(int C = A ^ B; C != 0; C = C & (C-1)){
        count++;
    }
    return count;
}

• 執行時間：100.00%；記憶體消耗：12.36%；
• 先做異或操作，再遍歷每一位統計1的個數；
• 第三種寫法的c = c & (c-1)是清除最低位1；

7. 配對交換 [easy]

7.1 考慮點

• 可以詢問面試官需要處理的資料位數；

7.2 解法

7.2.1 隔位操作法

public int exchangeBits(int num) {
    int moreNum = num << 1;
    int lessNum = num >> 1;
    int result = lessNum;
    for(int i = 1; i < 31; i+=2){
        if(((moreNum >> i) & 1) != ((lessNum >> i) & 1)){
            result = change(result, i);
        }
    }
    return result;
}

public int change(int lessNum, int i){
    int mask = ~(1 << i);
    // i位清零
    int result = lessNum & mask;
    if(result != lessNum){
        return result;
    } else {
        return (result | (1 << i));
    }	
}

• 執行時間：100.00%；記憶體消耗：63.11%；

7.2.2 特殊二進制法（優）

public int exchangeBits(int num) {
    //奇數
    int odd = num & 0x55555555;
    //偶數
    int even = num & 0xaaaaaaaa;
    odd = odd << 1;
    even = even >>> 1;
    return odd | even;
}
//簡短寫法
public int exchangeBits(int num) {
    return ((num&0x55555555) << 1) | ((num&0xaaaaaaaa) >>> 1);
}

• 執行時間：100.00%；記憶體消耗：48.19%；
• 分別取出奇數位和偶數位，移動后做或運算；
• 0x55555555 = 0b0101_0101_0101_0101_0101_0101_0101_0101
• 0xaaaaaaaa = 0b1010_1010_1010_1010_1010_1010_1010_1010
• 用這兩個數做與運算，把奇數位和偶數位取出來，然后位左移奇數位，右移偶數位，再把奇數位和偶數位做或運算；
• 這里運用邏輯右移而不是算數右移是因為我們希望符號位被0填充；
• 上述代碼實作的是32位整數，處理64位整數需要修改掩碼；

8. 繪制直線 [medium]

題目理解：

8.1 考慮點

• 一個簡單的做法是：用for回圈迭代，從x1到x2，一路設定每個像素，但這樣做太沒勁，效率不高；
• 處理這個問題需要十分細心，其中有很多陷阱和特殊情況；比如需要考慮x1到x2出于同一個位元組的情況；

8.2 解法

8.2.1 逐組分析法

public int[] drawLine(int length, int w, int x1, int x2, int y) {
    int higth = length*32/w; //螢屏高度
    int intNum = w/32; //一行有多少個int
    int[] result = new int[length];
    int index = 0;

    //前面第0 ~ y-1行為0，y*intNum個0
    //第y行輸出數字，intNum個數字
    //后面第y+1 ~ hight-1行開始為0，(hight-y-1)*intNum個0
    
    //對于陣列，前面至下標(x1+y*w)/32-1為0；從下標(x2+y*w)/32+1開始到結尾為0；中間為數
    //第一個數，下標為i
    int i = (x1+y*w)/32;
    int min = Math.min( ((x1 / 32 + 1) * 32 - x1), (x2-x1+1));
    for (int j = 0; j < min; j++) {
        result[i] = result[i] << 1;
        result[i]++;
    }
    if(min == x2-x1+1){
        result[i] = result[i] << (32-x2-1);
    }
    i++;
    //中間-1的個數numOne
    int numOne = 0;
    if(x2/32 != x1/32){
        numOne = x2/32 - x1/32 -1;
    }
    if(numOne != 0){
        for(int j = i; j < numOne + i; j++){
            result[j] = -1;
        }
    }
    //最后一個數，下標為i+numOne
    i = i + numOne;
    if(i < length && (x2-x1)/32 > 0){
        for (int j = 0; j < (x2 - (x2 / 32) * 32 + 1); j++) {
            result[i] = result[i] << 1;
            result[i]++;
        }
        result[i] = result[i] << (32 - x2 + (x2/32)*32 -1);
        if( (x2 - (x2/32)*32 + 1) == 32){
            result[i] = -1;
        }
    }
    return result;
}

• 執行時間：100.00%；記憶體消耗：67.24%；
• 需要注意大量細節，包括中間-1的個數numOne，以及考慮最后一個數可以跟以一個重合的情況(x2-x1)/32 > 0；
• 過于復雜，思路相同的不同實作方法如下；

8.2.2 位運算（優）

public int[] drawLine(int length, int w, int x1, int x2, int y) {  
    int[] ans=new int[length];
    int low=(y*w+x1)/32;
    int high=(y*w+x2)/32;
    for(int i=low;i<=high;i++){
        ans[i]=-1;
    }
    ans[low]=ans[low]>>>x1%32;
    ans[high]=ans[high]&Integer.MIN_VALUE>> x2 % 32;
    return ans;
}

• 執行時間：100.00%；記憶體消耗：51.73%；

最后

新人制作，如有錯誤，歡迎指出，感激不盡！ 歡迎關注公眾號，會分享一些更日常的東西！ 如需轉載，請標注出處！

標籤：其他

上一篇：2021年在北京建一個網站一般需要多少錢呢？

下一篇：使用 swagger-ui 可視化 Kubernetes API 檔案