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