2012年5月14日
#
近兩個月里，又開始了新的跳槽。誠然，我之前跳槽次數確實過多了，但出于在當前公司的工作內容、待遇、職稱評定等方面的不滿，最終還是下定了跳槽的決心。（當然，也對之前的求職做了回顧，畢竟我也不想再有這種頻繁的跳槽了，我也想穩定下來了。）
而在一開始，就已經有朋友勸我，在簡歷中得弄點虛假和夸張，否則很難找到好的工作。可惜，本人對這種夸大優點，剔除一切不利信息的簡歷制作實在是難以為之！最終，想而易知，我所投出的簡歷所得到的回應是少得可憐。期間，我聽說了一些通過在簡歷上的“美化”而取得求職成功的例子，也陸續的有幾個朋友勸我在簡歷上不要太老實，得做些變通，如，“將中間的某兩個公司的經歷合寫成一個公司的經歷”、“某些內容可以不要寫到簡歷上”、“某些內容應該再做些擴充，并對某些詞替換成更吸引人點的詞”等等。我也確有幾次去嘗試調整簡歷，可是，以到這弄虛假、夸張、隱瞞時，我卻又實在是下不了手。沒辦法，或許這就是本性難移吧。
還好，回應總算還是有一些，而且目前也拿到了一份還算滿意的Offer。在即將進入的新公司里，還是好好干吧！~
哎！~這可怕的求職市場啊，實在太令人心冷了！~
2012年4月23日
#
摘要: 此篇內容屬C++控制臺編程的一點基礎應用，所以嘛，偶就偷個懶，不再做文字的講解，直接代碼。
哦，對了！代碼之前，先就代碼的組成作個簡單說明。代碼的內容共分為三塊：
以宏RUN_ATEXIT_SAMPLE標識的atexit調用樣例以宏RUN_SETC...
閱讀全文
2012年4月5日
#
這是《劍指Offer——名企面試官精講典型編程題》一書中的面試題50，此題針對所給條件的不同，將需要截然不同的解題思路和方法。書中給出了針對此題的3種不同條件的解題，本文所要講解的是對其第3種條件的一個改進解法。具體的題目及條件如下。
【題目】：
輸入兩個樹結點，求它們的最低公共祖先。
【補充條件】：
樹是普通的樹，而且樹中的結點沒有指向父節點的指針。
針對上述的題目和條件，書中給出了如下解決方案。
【原方案】：
使用兩個鏈表，對樹進行兩次遍歷以查找兩個樹結點，并保持路徑到兩個鏈表中，從而將問題轉化為求兩個鏈表的最后一個公共結點。
從該方案中，觀察到兩次樹結點查找的遍歷中，其中一個結點的遍歷過的樹結點序列將完全覆蓋查找另一結點時所遍歷的樹結點序列。由此入手，本文提出了如下的改進解決方案。
【改進方案】：
深度優先遍歷樹，并記錄路徑，當找到第一個結點后，在當前基礎上繼續遍歷搜索第二個結點，并記錄第一個結點路徑的變化程度，直到找到第二個結點。最后，根據棧信息和記錄的結點路徑變化程度得到最低公共祖先。如圖1，假設輸入的兩個樹結點為D和K，樹的根節點為R，則求D和K的最低公共結點的過程如下表：
|
步驟 |
棧 |
第一個結點 |
第二個結點 |
路徑變化程度 |
|
1 |
R |
— |
— |
— |
|
2 |
R，A |
— |
— |
— |
|
3 |
R，A，F |
— |
— |
— |
|
4 |
R，A，F，J |
— |
— |
— |
|
5 |
R，A，F，G |
— |
— |
— |
|
6 |
R，A，F，K |
K |
— |
0（或K） |
|
7 |
R，A，C |
K |
— |
1（或A） |
|
8 |
R，A，C，E |
K |
— |
2（或A） |
|
9 |
R，A，C，I |
K |
— |
2（或A） |
|
10 |
R，A，D |
K |
D |
1（或A） |
|
è 得出結果，最低公共祖先結點為A |
從中，可以看到，改進后的方案，只需對樹執行一次遍歷。而在輔助空間的需求上， 只需使用一個棧（外加少量結點指針變量和1個表示路徑變化程度的整型變量）。而且，如果采用遞歸的方式實現，該棧所需保存的信息，還可以通過遞歸時的函數調用棧得以保存。
【附注】：
- 此處，有如下一個問題：
假設待查找公共祖先的兩樹結點，其中一結點在以另一結點為根的子樹上（包括兩結點相同）時，公共祖先的確定規則——
“作為子樹根結點的那個結點”還是“子樹根結點的父節點”？
例如：對上面圖1中的那棵樹，如果待查結點為根結點R和結點F，那么最終的查找結果是為R呢，還是因為R是根結點無父結點而得出NULL？
此問題在書中未提及，但查看書中代碼，確認是選擇了后者；而在本人的樣例代碼中則采用了前面的觀點。 - 在樣例代碼中，對樹結點在棧中的存儲方式略有改動。
- 樣例代碼工程所使用的環境為 Visual C++ 2010；
其中：tree.h/cpp為功能代碼文件，TestLowestCommonAncestor.h/cpp為相應的UT代碼文件；
UT采用gtest所編寫，編譯鏈接請根據gtest在自己本機的路徑狀況修改gtest_link.props文件中相應的鏈接項。
2012年3月30日
#
摘要: 最近，在看《劍指Offer——名企面試官精講典型編程題》一書，當看到“面試題47：不用加減乘除做加法”時，經過一分鐘左右思考后，得出了思路，跟書上一對照，基本一致，呵呵O(∩_∩)O~。于是，隨即又開始思考：加法是實現了，那么減法、乘法還有除法又該怎么實現呢？一番思考與分析后，得出算法，寫出代碼，測試通過，Happy！！\(^...
閱讀全文
2012年3月17日
#
在計算一個浮點數（雙精度或單精度）的整數次方時，一般的，我們會直接使用 C++ 本身所提供的 pow 函數，事實上也推薦直接使用 pow 函數（為了稱呼簡便，后面稱該 pow 函數為系統 pow 函數）。
但是，當我們準備寫一個自己的 pow 時，我們又會怎么寫呢？一般的，我們會寫上一個 for 循環來循環冪的指數次，而且每次循環都會去執行一次浮點數的乘法操作。但是，當我們拿這個 pow 函數來跟系統 pow 函數作一運行比較時，就會發現，我們的 pow 實在是太低效了。那么怎么樣才能使我們自己寫的 pow 也能有系統函數那樣的時間效率呢？
仔細分析，我們用的那個求冪值的循環過程，就能發現，其實我們還是做了很多不必要的浮點數乘法炒作。整個計算過程太過按步就班了。譬如說在計算 val（待傳入pow 函數求冪的浮點數，下同） 的4次方，我們總是先計算出3次方的值，然后再根據3次方的值和原始值來求4次方的值；然而，我們其實本可以在計算出2次方值后，平方2次方值來得到4次方的值的。接下來，就是探索算法，以減少浮點數乘法的事了。
通過所學的指數函數的知識，我們知道指數函數有著這樣的性質：
另外，對于整數，有如下性質：
-
2n = (1 << n) ;這里 << 是向左移位的操作符。
-
C++中的任何一個正整數（負整數同，但須處理好符合位）都可以表示為以下形式：
n = 2a1 + 2a2 + ... + 2ak
(其中，a1, a2, ... , ak 為閉區間 [0, 30] 上的整數值，且互不相同。)
由此，我們就可以事先依次計算出 val, val2, val4, ... , val30 預存備用，然后再根據 val 相應 bit 上是 1 還是 0，來選取相應的預存數據進行相乘，從而得到最終的結果。當然，合理設計邏輯，還可以減少所需的預存數據。下面是我的Pow 代碼，歡迎點評。
#define INTBITS_WITHOUT_SIGN 31 // the bit-size of type int with the sign bit being excluded.
bool IsZero(double val, double precision /**//*= DEFAULT_PRECISION*/)
{
if (precision >= 0) {
return (-precision <= val) && (val <= precision);
} else {
return (precision <= val) && (val <= -precision);
}
}
double Pow(double val, int exponent)
{
if (IsZero(val)) {
return 0.0;
}
if (0 == exponent) {
return 1.0;
}
bool bIsExponentMinus = false;
if (exponent < 0) {
exponent = -exponent;
bIsExponentMinus = true;
}
double tempVal[INTBITS_WITHOUT_SIGN];
memset(tempVal, 0, INTBITS_WITHOUT_SIGN);
tempVal[0] = val;
double result = 1.0;
int index = 0;
while (exponent != 0) {
if ((exponent & 1) != 0) {
result *= tempVal[index];
}
exponent >>= 1;
if (exponent != 0) {
tempVal[index + 1] = tempVal[index] * tempVal[index];
++index;
}
}
if (bIsExponentMinus) {
result = 1.0 / result;
}
return result;
}
【補充】：
1. 在指數中，0的負數次方和0的0次方，都是沒有意義的，所以對“if (IsZero(val))”分支內的處理如果能加上一些異常的輸出就更好了，如：
在Widows下，可通過 SetLastError(...) 來設置錯誤碼。
2. Pow中的 “double tempVal[INTBITS_WITHOUT_SIGN];” 一句，改寫為
double * pTempVal = new double[sizeof(int) * 8 - 1];
(當然，后面代碼中的tempVal 也都要改為相應的 pTempVal，同時須記得在return 前把delete [] pTempVal)
就可以使代碼也能夠適應于64位系統的處理。對于無符號整數的為指數的情況，則輔助值空間應為“sizeof(unsigned int) * 8”，同時，無需再考慮負指數的情況。
(這里，很感謝春秋十二月的補充。)
2012年3月14日
#
摘要: 在前面的例子中，我們看到：采用 new 來為單件對象分配空間，如果采用手動調用 delete 或封裝了 delete 的 Release 操作，一旦遇到全局對象的析構有調用單件對象，就會使得無法在代碼中找到適合釋放單件對象的時機。那么，是否可以讓系統來自動選擇時機，調用釋放呢？如果可以，又該怎么在代碼中構建單件對象的自動釋放機制呢? 對這兩個問題，在進行了一番思考和嘗試后，終于找到了答...
閱讀全文
2012年3月13日
#
摘要: 前面對C++的Singleton模式的探討還都是針對通過靜態變量來創建對象。但學習嘛，多走點總不是壞事。
接下來就來看看通過 new 來創建單件對象的單件類設計。既然是用 new 來創建了，那自然就不能忽略需要用 delete 來釋放。
好了，先來看看代碼：
Code highlighting produced by Actipro CodeHighlighter (freeware)htt...
閱讀全文
2012年3月12日
#