編程之美擴展問題

1. 學的c++能看《編程之美》嗎

可以的。
《編程之美——微軟技術面試心得》收集了約60道演算法和程序設計題目，這些題目大部分在近年的筆試，面試中出現過，或者是被微軟員工熱烈討論過。作者試圖從書中各種有趣的問題出發，引導讀者發現問題，分析問題，解決問題，尋找更優的解法。
這本書裡面主要涉及到的是各種演算法的討論，以及對程序設計思路的引導。對於任何語言的學習者都是有幫助的。其中大部分演算法描述更是採用了C語言作為例子，所以，學習C++看編程之美是沒有障礙的。
但是，由於這本書裡面涉及到的一些演算法比較困難，對於初學者來說會有些偏難，所以最好在C++有一定功底後再去閱讀。

2. 計算機有哪些必讀的經典書籍

計算機專業學習的過程中，大家學習了程序語言C/C++、數據結構、資料庫、計算機組成原理、操作系統和計算機網路等基礎課，但是還有許多經典書籍值得我們一讀，閱讀這些書籍不但對我們個人能力提升而且對個人應聘找工作都有很大的幫助。下面羅列出一些經典書籍供大家參考。
1. 程序語言方面
C語言作為最經典的語言，也是計算機專業最先學習的一門語言。首先推薦幾本C語言經典書籍：
《C和指針》
《C缺陷與陷阱》
《C專家編程》
《C語言深度剖析》

Expert C Programming
其中《C專家編程》從C的歷史、語言特性、聲明、數組指針、鏈接、運行時內存等問題進行了細致的講解和深入的分析，全書展示出很多優秀的編碼技巧，特別適合有一點C語言基礎的人觀看。《C語言深度剖析》是國內寫的一本書，重點講解了C語言里的一些晦澀難度的問題。
C++語言經典書籍：
《C++ Primer 5th》
《Effective C++》
《深度探索C++對象模型》
《STL源碼解析》

C++ Primer
以上幾本是學好C++必讀的書籍，《C++ Primer 5th》由淺入深全面的講解了C++的語法與程序設計，是C++程序員必讀的一本書，《深度探索C++對象模型》對C++運行原理作了一個很好的剖析，詳細的講解了對象內存模型以及調用運行的本質，對深入理解C++內部機制來說是一本非常好的書籍。計算機底層書籍：
《編碼》
《編譯原理》
《匯編語言》
《C++反匯編與逆向分析》
Code
《編碼》深度形象的講解了計算機的原理，看完此書後你會對計算機的工作原理有較深刻的理解，強烈推薦大家看一看。
2. 演算法、數據結構相關
《演算法導論》
《編程珠璣》
《編程之美》
《演算法藝術與信息學競賽》
《演算法導論》是演算法領域的聖經，這本書很厚並且理論知識較強，很難從頭到尾認真的看一遍，大家可以選擇性地看，當然能完整的看完就更好了。《編程珠璣》和《編程之美》這兩本書也非常經典，裡面注重的是解決問題的思路，看的時候要認真思考裡面的問題。最後一本是關於ACM方面的書，如果自己能力足夠強的話，看看這本書也還是挺不錯的
LeetCode 中國
當然，這里不得不向大家推薦的就是 LeetCode 在線技術平台了，專注於做演算法、學習、求職和計算機科學相關的內容，被譽為計算機界的刷題神器。目前，LeetCode 也已經進入中國，有自己的中文網站（ leetcode-cn ），不僅提供了 LeetCode 的全部服務，還有中英文題目對照和中文社區，總算可以愉快的刷題了。
3. 操作系統相關
《深入理解操作系統》
《linux內核完全注釋》
《自己動手寫操作系統》
《Windows內核原理與實現》
Linux內核完全注釋
《Linux內核完全注釋》一書選取了代碼量不超過2萬行的linux 0.11內核，對內核代碼的每一個細節都作出了詳細的講解，麻雀雖小，五臟俱全，看完這本書對linux操作原理會有一個很深的理解，是國內一本非常優秀的書。
4. 軟體開發、設計相關
《Head First 設計模式》
《設計模式-可復用面向對象軟體的基礎》
《重構與模式》
《代碼大全》
《設計模式》（GOF）
Head First - 設計模式
設計模式在工作中重要性尤其突出，良好的軟體設計對於後期的維護、擴展有著重要的作用，對於大型軟體，首先要做的就是設計好整個軟體架構，這也是整個軟體開發過程中最難的一個環節。
5. 資料庫
《資料庫系統概念》
《資料庫系統實現》
《Mysql技術內幕：sql編程》
《MySQL技術內幕: InnoDB存儲引擎》

3. 求不連續子數組最大和的值

這是一道典型的動態規劃問題，書中循序漸進地通過分析給出了一個時間復雜度為O(N)空間復雜度為O(1)的最優解。我在面試時碰到了這道題的一道有趣變體，即同樣給定一個數組，寫一個在其中找出不連續子數組和的最大值，也就是說子數組里的任意相鄰的兩個元素，在原數組里都必須是不相鄰的才行。同樣以數組{1, -2, 3, 5, -1, 2}為例，則和最大的不連續子數組是{1, 5, 2}，函數返回值是8。
顯然，最直接的思路我們可以採用窮舉法，對於此類尋找符合條件的子數組的問題，無非就是對原數組上每位元素是否屬於子數組做一次遍歷判斷。由於每位元素都有屬於和不屬於子數組兩種可能性，那麼窮舉的時間復雜度為O(2^N)。即使考慮「不連續」這個限制條件，即某位元素被選中屬於子數組後，則其相鄰元素就一定不能被選中，也對時間復雜度的數量級不會有太多影響。因此很明顯，這絕對是個愚蠢的答案……
從《編程之美》一題中得到啟發，我們是不是也可以用動態規劃的方法來解這道題呢？假設從原數組a第i位開始的最大不連續子數組和為m[ i ]，那麼它的值有兩種可能，一種是當前元素a[ i ]與隔一位上子問題解m[ i+2 ]之和（由不連續性質決定），另一種是不包含當前元素而直接等於前一位上子問題解m[ i+1 ]，那麼我們可以寫出遞推公式為：m[ i ] = max(a[ i ] + m[ i+2 ], m[ i+1 ])。
等等，也許你要說，好像這個遞推式有漏洞啊，因為前一位上的解m[ i+1 ]本身就有可能是包含或不包含a[ i+1 ]，假如m[ i+1 ]不包含a[ i+1 ]，那麼豈不是還要考慮a[ i ]+m[ i+1 ]這種可能性呢？
這個遞推式真的經不起推敲嗎？我們不妨重新整理一下思路：由於原數組上每一元素都有取與不取兩種可能，那麼也就對應有包含和不包含該元素的兩個子數組的最大和。對於原數組a中第i位上的元素，假設包含a[ i ]元素的子數組最大和為s[ i ]，而不包含元素a[ i ]的子數組最大和為ns[ i ]，因此所要求的不連續子數組最大和m[ i ] = max(s[ i ], ns[ i ])。那麼根據題意我們可以整理出遞推關系如下：
s[ i ] = max(a[ i ] + ns[ i+1 ], a[ i ] + m[ i+2 ])
ns[ i ] = m[ i+1 ]
m[ i ] = max(a[ i ] + ns[ i+1 ], a[ i ] + m[ i+2 ], m[ i+1 ])
有趣的地方在於ns[ i ] = m[ i+1 ]這一項上，根據它我們可以得到ns[ i+1 ] = m(i+2)，也就是說假如m[ i+1 ]不包含a[ i+1 ]的話，那麼它一定等於m[ i+2 ]，所以a[ i ]+ns[ i+1 ]等價於a[ i ] + m[ i+2 ]，遞推式m[ i ] = max(a[ i ] + m[ i+2 ], m[ i+1 ])是正確的！
從《編程之美》給出的解法中得到啟發，我們也只需要使用兩個變數來記錄m[ i+2 ]和m[ i+1 ]的值就行了，而且同樣只需要O(N)的復雜度就可以解這道題，代碼如下：
int maxsum(int* a, int n)
{
int m2 = 0;
int m1 = a[ n-1 ];
for(int i = n - 2; i >= 0; i--)
{
if(m2 < 0) m2 = 0; //處理最後一位為負數或全為負數的情況
int tmp = m1;
m1 = max(a[ i ] + m2, m1);
m2 = tmp;
}
return m1;
}

我的做法：
s[0]=a[0]
s[1]=max{a[0],a[1]}
s[i]=max{s[i-1],s[i-2]+a[i]}, i>=2
int maxSum(int a[],int n){
assert(n>0);
if(n==1)
return a[0];
if(n==2)
return max(a[0],a[1]);

int* s=new int[n];
s[0]=a[0];
s[1]=max(a[0],a[1]);
for(int i=2;i<n;i++){
s[i]=max(s[i-1],s[i-2]+a[i]);
}
int ms=INT_MIN;
for(int i=0;i<n;i++){
if(s[i]>ms)
ms=s[i];
}
delete []s;
return ms;
}

4. 編程之美的內容簡介

該書收集了約60道演算法和程序設計題目，這些題目大部分在近年的筆試，面試中出現過，或者是被微軟員工熱烈討論過。作者試圖從書中各種有趣的問題出發，引導讀者發現問題，分析問題，解決問題，尋找更優的解法。
本書的內容分為下面幾個部分：
游戲之樂：從游戲和其他有趣問題出發，化繁為簡，分析總結。
數字之魅：編程的過程實際上就是和數字及字元打交道的過程。這一部分收集了一些好玩的對數字進行處理的題目。
結構之法：匯集了常見的對字元串、鏈表、隊列，以及樹等進行操作的題目。
數學之趣：列舉了一些不需要寫具體程序的數學問題，鍛煉讀者的抽象思維能力。
書中絕大部分題目都提供了詳細的解說。 每道題目後面還有一至兩道擴展問題，供讀者進一步鑽研。
書中還講述了面試的各種小故事，告訴讀者微軟需要什麼樣的技術人才，重視什麼樣的能力，如何甄別人才。回答讀者關於IT業面試，招聘，職業發展的疑問。這本書的很多題目會出現在IT 行業的各種筆試，面試中。但本書更深層的意義在於引導讀者思考，和讀者共享思考之樂，編程之美。