[劍指Offer] 第2章課後題詳解[劍指Offer] 第2章課後題詳解

<a href="#%e5%89%91%e6%8c%87offer-%e7%ac%ac2%e7%ab%a0%e8%af%be%e5%90%8e%e9%a2%98%e8%af%a6%e8%a7%a3">劍指offer 第2章課後題詳解</a>

<a href="#%e7%9b%ae%e5%bd%95">目錄</a>

<a href="#%e6%9c%89%e5%ba%8f%e6%95%b0%e7%bb%84%e7%9a%84%e6%8f%92%e5%85%a5">有序數組的插入</a>

<a href="#%e5%88%86%e6%9e%90">分析</a>

<a href="#%e6%ad%a3%e5%b8%b8%e8%a7%a3%e6%b3%95">正常解法</a>

<a href="#%e9%9d%9e%e4%b8%bb%e6%b5%81%e8%a7%a3%e6%b3%95">非主流解法</a>

<a href="#%e4%b8%a4%e4%b8%aa%e9%98%9f%e5%88%97%e5%ae%9e%e7%8e%b0%e6%a0%88">兩個隊列實作棧</a>

<a href="#%e5%88%86%e6%9e%90-1">分析</a>

<a href="#%e8%a7%a3%e6%b3%95">解法</a>

<a href="#2%e7%9a%84%e6%95%b4%e6%95%b0%e6%ac%a1%e6%96%b9">2的整數次方</a>

<a href="#%e5%88%86%e6%9e%90-2">分析</a>

<a href="#%e8%a7%a3%e6%b3%95-1">解法</a>

<a href="#%e4%b8%8d%e5%90%8c%e4%bd%8d%e6%95%b0">不同位數</a>

<a href="#%e5%88%86%e6%9e%90-3">分析</a>

<a href="#%e8%a7%a3%e6%b3%95-2">解法</a>

本題為《劍指offer》“面試題4：替換空格”一節中的“相關題目”。

有兩個排序的數組a1和a2，記憶體在a1的末尾有足夠多的空餘空間容納a2。請實作一個函數，把a2中的所有數字插入到a1中并且所有數字是排序的。

其實這道題就是實作一個歸并排序，隻是在數組中，資料是順序存儲的，如果在數組頭部進行歸并排序，每一次操作都會移動後面所有的資料，開銷很大。是以應該從尾部進行操作。

使用标準庫中的vector（可變大小數組）和泛型算法會讓代碼變得相當簡單，但相應地算法的時間複雜度會受到影響（因為會進行一次排序）。

本題為《劍指offer》“面試題7：用兩個棧實作隊列”一節中的“相關題目”。

棧聲明如下：

根據隊列的先進先出原則和棧的後進先出原則，可以進行如下設計：先将入棧元素依次加入到隊列1中，出棧時，将隊列1除隊尾元素外依次加入到隊列2中，再彈出隊列1中的最後一個元素（隊尾元素）。再有元素入棧時，就加入到隊列2中，出棧時，将隊列2除隊尾元素外依次加入到隊列1中，再彈出隊列2中的最後一個元素（隊尾元素）。之後元素入棧，又加入到隊列1中，依此類推。

本題為《劍指offer》“面試題10：二進制中1的個數”一節中的“相關題目”。

用一條語句判斷一個整數是不是2的整數次方。

一個整數如果是2的整數次方，那麼它的二進制表示中有且隻有一位是1，而其他所有位都是0。把這個數減去1之後，原本為1的那一位會變成0，而在這一位之後的所有0都會變成1。把這個整數與它減一後的數做與運算則結果為0。

輸入兩個整數m和n，計算需要改變m的二進制中多少位才能得到n。

問題等價于m和n中有多少位不同，是以将m和n進行異或運算再計算結果二進制中的1的個數就完成求解。