12days?
章節結構
00 算法前導課-編程基礎（自學的視頻）
01 位運算的奇巧淫技
02 查找與排序（上）
03 數組、查找與排序(下)
04 多維數組與矩陣
05 字符串專題
06 基本數學問題
06 遞歸、DFS、剪枝、回溯等問題
07 貪心策略與動態規劃
08 線性結構:列表、鏈表、棧、隊列
09 哈希表、哈希映射
10 樹結構
11 圖論
推薦書籍
《程序員面試金典》【cc150 ：crack the code of interview】、《挑戰程序設計競賽》、《程序員代碼面試指南》、《劍指offer》、《編程之美》、《算法導論》
學習方法
多敲多理解多復習
位運算與進制基礎
進制基礎：
? ? ? ? 十進制、二進制、八進制、十六進制（A-F代表10-15）
進制轉換方法：
? ? ? ? 十轉二、二轉十、二轉八、八轉二、二轉十六、十六轉二
位運算：
????????按位與（&）、按位或（|）、按位異或（^）、按位取反（~）
? ? ? ? 左移（<<）、右移（>>）
判斷奇偶數
使用&運算
?// 判斷一個數是奇數還是偶數 public class BitwiseTricks {// 方法：判斷奇偶數public static boolean isEven(int num) {// 與1進行按位與操作，如果結果為0，則是偶數，否則是奇數return (num & 1) == 0;}public static void main(String[] args) {int num1 = 10; int num2 = 7;System.out.println(num1 + " is even: " + isEven(num1)); System.out.println(num2 + " is even: " + isEven(num2)); } }
- 在
isEven方法中，num & 1只保留了num的最低位。如果num是偶數，其最低位為 0，與 1 按位與結果為 0；如果是奇數，最低位為 1，與 1 按位與結果為 1。獲取二進制位是 1 還是 0
?
- 方法一：位移和按位與
? &運算用1做運算即保留，用0做運算即消除// 獲取整數指定位置的二進制位是1還是0（方法一：位移和按位與） public class BitwiseTricks {// 方法：獲取指定位置的位public static int getBit(int num, int i) {// 將num右移i位，然后與1進行按位與操作return (num >> i) & 1;}public static void main(String[] args) {int num = 13; // 二進制為1101int bitPosition = 2; System.out.println("The bit at position " + bitPosition + " of " + num + " is: " + getBit(num, bitPosition)); } }
這里
num >> i將num的第i位移動到最低位，然后與 1 按位與，得到該位的值（0 或 1）。方法二：掩碼操作
?// 獲取整數指定位置的二進制位是1還是0（方法二：掩碼操作） public class BitwiseTricks {// 方法：獲取指定位置的位public static int getBit(int num, int i) {// 創建掩碼，將1左移i位int mask = 1 << i;// 與num進行按位與操作return (num & mask) != 0 ? 1 : 0;}public static void main(String[] args) {int num = 13; // 二進制為1101int bitPosition = 2; System.out.println("The bit at position " + bitPosition + " of " + num + " is: " + getBit(num, bitPosition)); } }
1 << i創建了一個只有第i位為 1 的掩碼，與num按位與后，如果結果不為 0，則num的第i位為 1，否則為 0。交換兩個整數變量的值
?// 交換兩個整數變量的值 public class BitwiseTricks {// 方法：交換兩個整數public static void swap(int[] nums, int i, int j) {// 利用異或操作交換兩個數nums[i] = nums[i] ^ nums[j];nums[j] = nums[i] ^ nums[j];nums[i] = nums[i] ^ nums[j];}public static void main(String[] args) {int[] nums = {5, 10};System.out.println("Before swap: num1 = " + nums[0] + ", num2 = " + nums[1]);swap(nums, 0, 1);System.out.println("After swap: num1 = " + nums[0] + ", num2 = " + nums[1]);} }
- 原理與前面 C/C++ 的示例相同，通過三次異或操作實現兩個數的交換，而不需要額外的臨時變量。
不用判斷語句，求整數的絕對值
?// 不用判斷語句求整數的絕對值 public class BitwiseTricks {// 方法：求整數的絕對值public static int abs(int x) {// 得到符號位擴展后的結果int mask = x >> 31;// 利用異或操作求絕對值return (x + mask) ^ mask;}public static void main(String[] args) {int num1 = -5;int num2 = 7;System.out.println("The absolute value of " + num1 + " is: " + abs(num1));System.out.println("The absolute value of " + num2 + " is: " + abs(num2));} }
x >> 31對于正數得到 0，對于負數得到-1（在 Java 中int是 32 位有符號整數，-1的二進制表示為全 1）。對于正數，(x + mask) ^ mask = x ^ 0 = x；對于負數，x + mask相當于x - 1，然后與mask異或得到其絕對值。
題解
題1:找出唯一成對的數
????????1-1000這1000個數放在含有1001個元素的數組中，只有唯一的一個元素值重復，其它均只出現一次。每個數組元素只能訪問一次，設計一個算法，將它找出來；不用輔助存儲空間，能否設計一個算法實現?
//使用異或運算
public class 找出唯一成對的數 {public static void main(String[] args) {int N = 1001;int []arr= new int[N];for(int i = 0;i<arr.length-1;i++){arr[i]=i+1;}//生成最后一個隨機數arr[arr.length-1]=new Random().nextInt(N-1)+1;//隨機下標//這個先實現不了for (int i = 0; i < arr.length; i++) {System.out.print(" "+arr[i]);}int x1=0;for(int i=1;i<=N-1;i++){x1=(x1^i);}for(int i=0;i<N;i++){x1=x1^arr[i];}System.out.println();System.out.println(x1);}
}
題2:找出落單的那個數
????????一個數組里除了某一個數字之外，其他的數字都出現了兩次。請寫程序找出這個只出現一次的數字。
- 使用?
str.charAt(i) - '0'?將字符轉換為對應的整數值。 - 這種方法利用了字符在ASCII表中的順序特性。
題3:二進制中1的個數
????????請實現一個函數，輸入一個整數，輸出該數二進制表示中1的個數。
????????例:9的二進制表示為1001，有2位是1
題4:是不是2的整數次方
????????用一條語句判斷一個整數是不是2的整數次方。
失敗的藍橋準備工作：經驗教訓以后別懶
)
