CC150小結概念與算法

2019-11-08 18:38:29

字體：大中小

來源：轉載

供稿：網友

位操作

常用操作與& 、或|、非~、異或^, 左移，右移。獲取,得到第i位的知否為1。置位，將第i位設置為1.清零，00010000 取反得到掩碼 11101111，然后利用與操作。將最高位到i（含）清零，(1<< i) - 1,進行與操作。將i位至0位（含）清零~(（1 << (i + 1)） - 1)再與 ~0 表示1串1。

5.2給定一個介于0和1之間的實數（如0.72），類型為double，打印它的二進制表示。如果無法精確地用32位以內的二進制表示，則打印“ERROR”。

public String numTobin(double num){ if (num >= 1 || num <= 0){ return "ERROR"; } StringBuffer sb = new StringBuffer(); sb.append("0."); while(num > 0){ num *= 2; if (num >= 1){ num -= 1; sb.append(1); }else { sb.append(0); } if (sb.length() >= 32){ return "ERROR"; } } return sb.toString(); }

5.3給定一個正整數，找出其二進制表示中1的個數相同、且大小最相近的那兩個數，一個略大，一個略小。

思路：1.位操作，較大的數：注意要判斷非拖尾0的存在,要將右邊有1的第一個0(位置為p = C0 (拖尾0的個數)+ C1（右邊1的個數）)變為1,將p后面的數據全部清零，然后補上C1個1，要判斷更大值是否存在。較小的數：注意C1是拖尾1的個數，C0是緊鄰拖尾1的左方一連串的個數，要從1變為0 的數右側必須包含0.否則數會大。根據位操作的簡化，可以得到out of box的算法，依據之前的數。

5.6交換某個整數的二級制表示下的奇數位和偶數位，使用指令越少越好。

思路：利用掩碼提取奇數位，右移。利用掩碼提取偶數位，左移。然后相或得到。

智力題

6.5有棟建筑高100層，若從N層或者更高層扔雞蛋，雞蛋破，若從第N層以下的樓層扔下來不會破。給兩個雞蛋，扔的最小的情況下得到N

思路：負載均衡下，要求x1 + x2 的值保持穩定，則假設從 a扔，若有一種算法保證x1多扔一次，x2就少扔一次。a + (a - 1) + (a - 2) + … + 1 = 100, a = 14.

數學與概率

生成素數的數列：埃拉托斯尼篩法，設計出一個boolean數組，從小到大劃去因子出現數組中的數。兩個子函數 void cossOff（boolean[] flags, int PRime）,從prime * prime 開始 int getNextPrime(boolean[] flags, int prime) 找到數組長度內，大于prime的下一個值 java類型的范圍

在JAVA中一共有八種基本數據類型，他們分別是

byte、short、int、long、float、double、char、boolean 其中byte、short、int、long都是表示整數的，只不過他們的取值范圍不一樣 byte的取值范圍為-128~127，占用1個字節（-2的7次方到2的7次方-1） short的取值范圍為-32768~32767，占用2個字節（-2的15次方到2的15次方-1） int的取值范圍為（-2147483648~2147483647），占用4個字節（-2的31次方到2的31次方-1） +-21億的數據量，一般可以滿足需求 long的取值范圍為（-9223372036854774808~9223372036854774807），占用8個字節（-2的63次方到2的63次方-1）在通常情況下，如果JAVA中出現了一個整數數字比如35，那么這個數字就是int型的，如果我們希望它是byte型的，可以在數據后加上大寫的 B：35B，表示它是byte型的，同樣的35S表示short型，35L表示long型的，表示int我們可以什么都不用加，但是如果要表示long型的，就一定要在數據后面加“L”。 float和double是表示浮點型的數據類型，他們之間的區別在于他們的精確度不同 float 3.402823e+38 ~ 1.401298e-45（e+38表示是乘以10的38次方，同樣，e-45表示乘以10的負45次方）占用4個字節 double 1.797693e+308~ 4.9000000e-324 占用8個字節 double型比float型存儲范圍更大，精度更高，所以通常的浮點型的數據在不聲明的情況下都是double型的，如果要表示一個數據是float型的，可以在數據后面加上“F”。

7.4實現整數的乘法、減法和除法操作

面試官想要找的就是這種能以邏輯思考逐步解決問題的人 顯示代碼的復用能力思路：自己實現正號變負號，負號變正號的操作，加與乘法都可以處理，

public int negate(int a){ int neg = 0; int d = a < 0 ? 1 : -1; while(a != 0){ neg += d; a += d; } return neg;}乘法是注意判斷，讓小的數a迭代

7.6在二維平面上，有一些點，找出經過點數最多的那條線。

思路：兩點之間確定直線，時間復雜度O(n*n),利用HashMap進行次數的存儲。

7.7有些數的因子只有3、5、7，找出其中的第k個數。

思路：這個方法與素數篩選法類似，關鍵是要想得到，首先插入數據1，然后將3*1輸入到隊列3Q，5*1輸入到5Q，然后將7*1輸入到7Q，下一個數從這三個隊列中給出來。沒有最優解原因，算法不是最簡算法，部分拼寫錯誤

public int getKNum(int k){ if (k < 0){ return 0; } Queue<Integer> quene3 = new LinkedList<Integer>(); Queue<Integer> quene5 = new LinkedList<Integer>(); Queue<Integer> quene7 = new LinkedList<Integer>(); quene3.add(1); int val = 1; for (int i = 0; i < k; i++){ int v3 = quene3.size() > 0 ? quene3.peek() : Integer.MAX_VALUE; int v5 = quene5.size() > 0 ? quene5.peek() : Integer.MAX_VALUE; int v7 = quene7.size() > 0 ? quene7.peek() : Integer.MAX_VALUE; val = (int)Math.min(v3, Math.min(v5, v7)); if (val == v3){ quene3.remove(); quene3.add(3 * val); quene5.add(5 * val); } else if (val == v5){ quene5.remove(); quene5.add(5 * val); } else { quene7.remove(); } quene7.add(7 * val); } return val; }

面向對象設計

打造優雅，易于維護的面向對象代碼。單例模式，只構造這一個對象，訪問與修改都是通過內部方法統一進行。

8.3運用面向對象原則，設計一款音樂點唱機。

處理本類問題思路：處理不明確的地方，定義核心對象，分析對象關系，設計對象動作系統組件：點唱機（Jukebox），CD，歌曲（Song），藝術家（Artist），播放列表（PlayList），顯示屏（Display，在屏幕上顯示詳細信息）動作：新建播放列表（新增、刪除、隨機播放）、CD選擇器、歌曲選擇器、將歌曲放進到播放隊列、獲取播放列表中的下一首；用戶：添加，刪除

public class Jukebox(){ private CDPlayer cdPlayer; private User user; private Set<CD> cdCollection; private SongSelector ts; public Jukebox(CDPlayer cdPlayer, User user, Set<CD> cdCollection, SongSelector ts){ } public Song getCurrentSong(){ return ts.getCurrentSong(); } public void setUser(User u){ this.user = u; }}public class CDPlayer{ private Playlist p; private CD c; /*構造函數*/ /*播放歌曲*/ /*getter and setter */}Playlist類管理當前播放的歌曲和待播放的下一首歌曲。本質上是播放隊列的包裹類，還提供了一些操作上更方便的方法。public class PlayList { private Song song; private Quene<Song> quene; public Playlist(Song song, Quene<Song> quene){ ```` } public Song getNextSToPlay(){ return quene.peek(); } public void queneUpSong(Song s){ quene.add(s); }}public class CD { /* 識別碼、藝術家、歌曲等 */}public class Song{ /* 識別碼、CD（可能為空）}public class User { private String name; private long ID; public User getUser(){ return this; }}

8.7設計一個聊天服務器系統

系統的難點：如何確定某人在線，如何處理沖突信息，如何讓服務器在任何負載下，都能應付自如，如何預防拒絕服務攻擊。

8.10設計并實現一個散列表，使用鏈接（即鏈表）處理碰撞沖突。

思路：存儲一個由鏈表組成的數組，鏈表元素為包含key 以及 value 的對象，防止沖突。

final 它可以修飾非抽象類、非抽象類成員方法和變量。你可能出于兩種理解而需要阻止改變：設計或效率。static變量前可以有private修飾，表示這個變量可以在類的靜態代碼塊中，或者類的其他靜態成員方法中使用（當然也可以在非靜態成員方法中使用–廢話），但是不能在其他類中通過類名來直接引用，這一點很重要。實際上你需要搞明白，private是訪問權限限定，static表示不要實例化就可以使用，這樣就容易理解多了。static前面加上其它訪問權限關鍵字的效果也以此類推。

構造函數前面不要加void 沒有ac的原因模板類沒有處理好，未考慮到items[index]為null的情況

public class MyHashMap<K, V> { private final int MAX_SIZE = 100; private LinkedList<Cell<K, V>>[] items; public MyHashMap(){ items = (LinkedList<Cell<K, V>>[])new LinkedList[MAX_SIZE]; } public int getIndex(K k){ return k.toString().length() % items.length; } public void put(K k, V v){ int index = getIndex(k); if (items[index] == null){ items[index] = new LinkedList<Cell<K, V>>(); } LinkedList<Cell<K, V>> temp = items[index]; Cell data = new Cell(k, v); for (Cell c : temp){ if (c.isEqual(data)){ temp.remove(c); } } temp.add(data); } public V get(K key){ int index = getIndex(key); if (null == items[index]){ return null; } LinkedList<Cell<K, V>> temp = items[index]; for (Cell c : temp){ if (c.getKey().equals(key)){ return (V) c.getValue(); } } return null; }}public class Cell<K, V> { private K key; private V value; public Cell(K key, V value){ this.key = key; this.value = value; } public boolean isEqual(K k){ return key.equals(k); } public boolean isEqual(Cell<K, V> c){ return isEqual(c.getKey()); } public K getKey(){ return this.key; } public V getValue(){ return this.value; }}

遞歸與動態規劃

遞歸結束條件，得到遞歸返回值，計算本身返回值, 動態規劃有時是緩存了遞歸的結果的遞歸優化版。能用迭代盡量不適用遞歸。

9.1爬臺階問題，n階臺階，小孩一次可以上1,2,3階，實現算法計算多少種爬法。

思路：斐波那契數列改進版，

9.2設想有個機器人在坐在X*Y網格的左上角，智能向下、向右移動，機器人從（0,0）到（X,Y）有多少種移動方法？加入有些點不能訪問，找出一條合理路徑。

最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在多個線程訪問Hashtable時，不需要自己為它的方法實現同步，而HashMap 就必須為之提供外同步(Collections.synchronizedMap)。 Hashtable和HashMap采用的hash/rehash算法都大概一樣，所以性能不會有很大的差異。

//如果需要，可以設計出一個對象，包含boolean 和 LinkedlList public boolean getPath(int x, int y, LinkedList<Point> path, Map<Point, Boolean> cache){ Point temp = new Point(x, y); if (cache.containsKey(temp)){ return cache.get(temp); } if (x == 0 && y == 0){ for (Point p : path ){ System.out.print(" (" + p.x +"," + p.y + ")"); } return true; } path.add(temp); System.out.print(" 訪問節點 (" + temp.x +"," + temp.y + ")"); boolean success = false; if (!success && isFree(x, y - 1)){ success = getPath(x, y-1, path, cache); } if (x >=1 && isFree(x - 1, y) ){ success = getPath(x - 1, y, path, cache); } if (!success){ path.remove(temp); //此處進行了優化，原來的設置是path.add.書中意思應該是看一下都訪問了哪些結點。 //遞歸與動態規劃的結合 } return success; }

9.3魔術索引，改造二分法

9.4返回某集合所有子集

思路：1.遞歸進化迭代，第n個子集是第n - 1個子集再加上第 n - 1個子集與第n個數的和 2.數學組合方法，對每一個元素的存在與否進行1,0表示，1表示選擇，0表示不選擇 注意操作鏈表的時候，需要新建并且加入，不可以直接賦值，否則無法完成操作

迭代的方法public ArrayList<ArrayList<Integer>> getAll(ArrayList<Integer> list){ if (null == list){ return null; } int len = list.size(); ArrayList<ArrayList<Integer>> resu = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> temp = new ArrayList<Integer>(); resu.add(temp); for (int i = 0; i < len; i++){ ArrayList<ArrayList<Integer>> newresu = new ArrayList<ArrayList<Integer>>(); newresu.addAll(resu); for (ArrayList<Integer> single : resu){ ArrayList<Integer> singletemp = new ArrayList<Integer>(); singletemp.addAll(single); singletemp.add(list.get(i)); newresu.add(singletemp); } resu = newresu; } return resu; } //數學組合方法 public ArrayList<ArrayList<Integer>> getSubsets2(ArrayList<Integer> list){ ArrayList<ArrayList<Integer>> newresu = new ArrayList<ArrayList<Integer>>(); int max = 1 << list.size(); for (int k = 0; k < max; k++){ newresu.add(coverIntToList(k, list)); } return newresu; } public ArrayList<Integer> coverIntToList(int num, ArrayList<Integer> list){ ArrayList<Integer> temp = new ArrayList<Integer>(); int index = 0; for (int k = num; k > 0; k >>= 1){ if ((k & 1) != 0){ temp.add(list.get(index)); } index++; } return temp; }

9.5編寫一個方法確定字符串的所有排列組合

思路：從字符串的單個字符串出發，每次都進行遞歸添加。沒有bugfree的原因為： Set的底層實現應該是 HashSet

public Set<String> getSubStrings(String str){ return getSubHelp(str, str.length() - 1); } public Set<String> getSubHelp(String str, int index){ if (null == str){ return null; } if (index == 0){ Set<String> set = new HashSet<String>(); set.add(str.substring(0, 1)); return set; } Set<String> set = getSubHelp(str, index - 1); Set<String> resu = new HashSet<String>(); for (String single : set){ for (int i = 0; i <= single.length(); i++){ resu.add(addChar(single, str.charAt(index), i)); } } return resu; } public String addChar(String str, char c, int pox){ return str.substring(0, pox) + c + str.substring(pox, str.length()); }

9.6實現一個算法，打印n對括號的全部有效組合

思路：采用遞歸的方式，是由前一個進行增加處理，插入括號的位置依據左括號的位置進行處理，注意重復問題，用set。還有一種記錄左右括號的數目，如果還有左括號可以使用，就插入左括號，然后遞歸，如果左括號用的多，就插入右括號。 enum表示枚舉例如 public enum Color {Black, White, Red, Yellow, Green}

9.8給定數量不限的25,10,5,1類型硬幣，計算有幾種表示法

當涉及到路徑問題時，遞歸的參數要有single路徑

public void makeChange(ArrayList<ArrayList<Integer>> list, int count, ArrayList<Integer> single){ if (count < 0){ return; } if (count == 0){ list.add(single); } if (count >= 25){ ArrayList<Integer> temp = new ArrayList<Integer>(); temp.addAll(single); temp.add(25); makeChange(list, count - 25, temp); } if (count >= 10){ ArrayList<Integer> temp = new ArrayList<Integer>(); temp.addAll(single); temp.add(10); makeChange(list, count - 10, temp); } if (count >= 5){ ArrayList<Integer> temp = new ArrayList<Integer>(); temp.addAll(single); temp.add(5); makeChange(list, count - 5, temp); } if (count >= 1){ ArrayList<Integer> temp = new ArrayList<Integer>(); temp.addAll(single); temp.add(1); makeChange(list, count - 1, temp); } } public ArrayList<ArrayList<Integer>> getChange(int count){ ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> single = new ArrayList<Integer>(); makeChange(result, count, single); return result; }

插補一下動態規劃中的最長子序列問題，用一個數組進行緩存，index + 1位置上放的是處于當前位置上最小的值

9.10一堆箱子，寬w，高h，深d，將箱子堆起來時，下面箱子的寬，高，深必須大于上面的箱子。實現一個方法，打出最高的一堆箱子。

思路：典型的解決思路是利用遞歸得到每一個箱子作為底的高度，然后取出最大值，加上動態規劃的緩存，不存在順序問題。

擴展性與存儲限制

評估分解棘手問題的能力，以及運用所學知識解決問題的能力。步驟大膽假設，切合實際，解決問題

10.2設計超大型社交網站，設計算法實現兩個人之間的“連接關系”或“社交途徑”

思路：查找表，分批進行存儲，在兩個端點進行廣度優先查找

10.4給定一個數組，包含1到N的整數，N最大為32000，N取值不定，輸出數組中重復元素，4KB內存，也就是空間復雜度。

沒有bugfree的原因，忽略了數據是從1開始，而bitmap卻是從0開始操作的。

public void prinDup(int [] nums){ MyBitSet bit = new MyBitSet(32000); for (int num : nums){ if (bit.get(num - 1)){ System.out.print(" " + num); } else { bit.set(num - 1); } } } public class MyBitSet{ private int[] bitset; public MyBitSet(int size){ //int 類型數據包含4個字節變量 bitset = new int[size >> 5];//32 } public boolean get(int index){ int WordNum = index >> 5; int bitNum = index & 0x1f;//對32 取余數 return ((bitset[wordNum] >> bitNum) & 0x01) == 1; } public void set(int index){ int wordNum = index >> 5; int bitNum = index & 0x1f;//對32 取余數 bitset[wordNum] |= 0x01 << bitNum; } }

排序與查找

學習掌握常見的排序和查找算法，回報巨大歸并排序（Merge Sort）,時間復雜度 O（n*log(n)）,空間復雜度看情況，快速排序（Quick Sort），平均時間O(n*log(n))，最差O(n平方)，空間O（n*log(n)）基數排序（Radix Sort）（桶排序）

歸并 public void mergeSort(int[] nums, int left, int right){ if (left < right){ int mid = left + ((right - left) >> 1); mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); merge(nums, left, mid, right); } } public void merge(int[] nums,int left,int mid,int right){ int[] temp = new int[nums.length]; for (int i = left; i <= right; i++){ temp[i] = nums[i]; } int c = left; int num = mid + 1; while(c <= right){ if ((left <= mid) && ((temp[left] < temp[num]) || (num > right))){ nums[c] = temp[left++]; } else { nums[c] = temp[num++]; } c++; } }快排注意的問題，函數調用,符號注意 public void quickSort(int nums[], int left, int right){ int index = position(nums, left, right); if (left < index - 1){ quickSort(nums, left, index - 1); } if (index < right){ quickSort(nums, index, right); } } public int position(int nums[] , int left, int right){ int mid = nums[left + ((right - left) >> 1)]; while (left <= right){ while (nums[left] < mid){ left++; } while (nums[right] > mid){ right--; } if (left <= right){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left ++;//找到并交換后，要進行位置處理操作 right--; } } return left; }

11.2編寫一個方法，對字符串數組進行排序，將所有變位詞排在相鄰的位置。

思路：由于沒有要求總體排序方法，可以用基數排序。

基數排序的一個例子 public void RadixSort(String[] strs){ Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>(); String key = null; for (String s : strs){ key = changeSort(s.toCharArray()); if (!map.containsKey(key)){ map.put(key, new ArrayList<String>()); } List<String> temp = map.get(key); temp.add(s); } int index = 0; for (String mapkey : map.keySet()){ List<String> list = map.get(mapkey); for (String s : list){ System.out.println(s); strs[index++] = s; } } } public String changeSort(char[] carray){ Arrays.sort(carray); return new String(carray); }

11.3給定一個排序后的數組，包含n個整數，但這個數組已經被旋轉過，旋轉次數不詳，找出數組中的某個元素。

思路：不論如果旋轉，二分查找必然有一塊是正常順序排列的，先對正常順序的判斷，不在就遞歸非正常那一半。注意多個數值連續相等的情況。沒有bugfree的原因為，在遞歸調用函數的時候，沒有return返回值

public int findIndex(int[] nums, int tar, int left, int right){ if (left > right){ return -1; } int mid = left + ((right - left) >> 1); if (nums[mid] == tar){ return mid; } if (nums[left] < nums[mid]){//左 if ((tar >= nums[left]) && (tar <= nums[mid])){ return findIndex(nums, tar, left, mid -1); } else { return findIndex(nums, tar, mid + 1, right); } } else if (nums[mid] < nums[right]){//右 if ((tar >= nums[mid]) && (tar <= nums[right])){ return findIndex(nums, tar, mid + 1, right); } else { return findIndex(nums, tar, left, mid -1); } } else { if (nums[left] == nums[mid]){//左 if (nums[mid] != right){ return findIndex(nums, tar, mid + 1, right); } else { int result = findIndex(nums, tar, left, mid - 1); if (result == -1){ result = findIndex(nums, tar, mid + 1, right); } return result; } } } return -1; }

11.7疊羅漢表演，上面的人要比下面的矮一點、輕一點。最多疊加幾個人。

思路：先用典型的動態規劃與遞歸解一下

遞歸一般代碼量較小 public int getNum(Employ[] nums, Employ em, Map map){ if (em != null && map.containsKey(em)){ return (int)map.get(em); } int max = 0; int value = 0; for (int i = 0; i < nums.length; i++){ if ((nums[i].wei < em.wei) && (nums[i].hei < em.hei)){ value = getNum(nums, nums[i], map); } if (value > max){ max = value; } } max++; map.put(em, max); return max; } public int getNum(Employ[] nums){ Map map = new HashMap(); int max = 0; int temp = 0; for (int i = 0; i < nums.length; i++){ temp = getNum(nums, nums[i], map); if (temp > max){ max = temp; } } return max; }

11.8假設你正在對去一串整數。每隔一段時間，你希望找出x的秩（小于或等于x的數目）。實現數據結構和算法支持這一操作。

思路：現在給出二叉查找樹的操作：

public class RankNode { public int left_size; public int data; public RankNode left; public RankNode right; public RankNode(int d){ data = d; } public void insert(int d){ if (d <= data){ //left if (left == null){ left = new RankNode(d); } else { left.insert(d); } left_size++; } else { if (right == null){ right = new RankNode(d); } else { right.insert(d); } } } public int getRankNum(int d){ if (data == d){ return left_size; } else if (d < data){ if (left == null){ return -1; } return left.getRankNum(d); } else { if (right == null){ return -1; } return left_size + 1 + right.getRankNum(d); } }}

14 java

14.6實現CircularArray類，支持類似數組的數據結構，這些數據結構可以高效地進行旋轉。使用泛型，通過標準的 for (Obj o : circularArray)語法支持迭代操作。

錯誤點：注意 items = (T[]) new Object[size];

這個可以快速的完成移位的操作。public class CircularArray <T> implements Iterable<T>{ private T[] items; private int head = 0; public CircularArray(int size){ items = (T[])new Object[size]; } private int convert(int index){ if (index < 0){ index += items.length; } return (head + index) % items.length; } public void rotate(int shiftright){ head = convert(shiftright); } public T get(int i){ if (i < 0 || i >= items.length){ throw new java.lang.IndexOutOfBoundsException("out of bound"); } return items[convert(i)]; } public void set(int i, T item){ items[convert(i)] = item; } @Override public Iterator<T> iterator() { return new CircularArrayIterator<T>(this); } private class CircularArrayIterator<TI> implements Iterator<TI>{ private int _current = -1; private TI[] _items; public CircularArrayIterator(CircularArray <TI> ite){ _items = ite.items; } @Override public boolean hasNext() { return _current < _items.length - 1; } @Override public TI next() { _current ++; return _items[convert(_current)]; } }}

上一篇：Easyui的簡單tree

下一篇：swift初體驗