老鼠和毒酒問題：1000瓶酒其中1瓶有毒，用10只老鼠找出毒酒。
解題方法1：折半查找法。取500瓶內(nèi)各一滴，看老鼠是否死亡，以此排除一半的酒。
解題方法2：轉(zhuǎn)換為二進(jìn)制法。1-1000都可以用10位2進(jìn)制數(shù)表示，設(shè)x10 = 10010111012，則將第x瓶酒滴入二進(jìn)制位為1的位對應(yīng)的碗中，然后讓10只老鼠各喝一個(gè)碗中的酒，可得到毒酒對應(yīng)的二進(jìn)制。子數(shù)組最大和問題：輸入一個(gè)整數(shù)數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，求子數(shù)組和的最大值。要求時(shí)間復(fù)雜度為O(n)。
解法：動態(tài)規(guī)劃。
設(shè)dp[i]表示以第i個(gè)數(shù)結(jié)束的子數(shù)組的最大和，那么dp[i+1] = max(dp[i] + nums[i+1], nums[i+1])。子數(shù)組和的最大值為dp數(shù)組中的最大值。買飲料問題：三個(gè)瓶蓋可以換一瓶飲料，要喝100瓶飲料，最少需要買多少瓶？
解法：2瓶飲料+1個(gè)瓶蓋 = 3瓶飲料+1個(gè)瓶蓋。因此需要買2 x (100/3) + 1 = 67瓶。最后一瓶正好作為啟動。生成數(shù)組（不能用除法）：給你一個(gè)數(shù)組A[1..n]，請你在O(n)的時(shí)間里構(gòu)造一個(gè)新的數(shù)組B[1..n]，使得B[i]=A[1] x A[2] x … x A[n] / A[i]。你不能使用除法運(yùn)算。
解題方法：改造輔助數(shù)組。任意B[i] = A[1] x A[2] x ... x A[i-1] x A[i+1] x ... x A[n]。構(gòu)造輔助數(shù)組C[1..n-1], D[1..n-1]，其中C[i] = A[1] x A[2] x ... x A[i]，D[i] = A[i] x ... x A[n]。構(gòu)造C、D數(shù)組都是O(n)復(fù)雜度，最后由C、D數(shù)組得到B數(shù)組也是O(n)復(fù)雜度。互信息的計(jì)算：I(A, B) = log2P(AB)/(P(A)P(B)) = log2p(A|B)/P(A) = log2P(B|A)/P(B)
算法設(shè)計(jì)題：已知計(jì)算機(jī)有以下原子操作：1). 賦值操作：b = a; 2). ++a和a+1; 3). for( ){ ***}有限循環(huán)； 4). 操作數(shù)只能為0或者正整數(shù)； 5). 定義函數(shù)實(shí)現(xiàn)加減乘操作。要求實(shí)現(xiàn)加減乘除操作。
解題hint：首先想辦法實(shí)現(xiàn)-1的功能。
fun_dec(n){
a = 0
b = 0
for(n times){
b = a
++a
}
return b
}
有了-1功能即可實(shí)現(xiàn)減法，有了加法減法即可實(shí)現(xiàn)乘法除法。
【數(shù)據(jù)結(jié)構(gòu)類】實(shí)現(xiàn)一個(gè)對鏈表排序的算法，C/C++可以使用std::list<int>,Java使用LinkedList<integer>要求先描述算法，然后再實(shí)現(xiàn)，算法效率盡可能高效。
解題hint：遞歸進(jìn)行歸并排序。使用快慢指針可以快速找到鏈表的中間位置（滿指針走一步，快指針走兩步，塊指針到達(dá)鏈表末尾則慢指針到達(dá)鏈表中間位置）。匈牙利法求最優(yōu)任務(wù)分配。
走兩趟格子：有n*n個(gè)格子，每個(gè)格子里有正數(shù)或者0，從最左上角往最右下角走，只能向下和向右，一共走兩次（即從左上角走到右下角走兩趟），把所有經(jīng)過的格子的數(shù)加起來，求最大值SUM，且兩次如果經(jīng)過同一個(gè)格子，則最后總和SUM中該格子的計(jì)數(shù)只加一次。
解題報(bào)告：一篇博文
需要DP兩次走的狀態(tài)。
狀態(tài)轉(zhuǎn)移：
if(i != j)
DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j - 1], DP[s - 1, i, j]) + W[s,i] + W[s,j]
else
DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j]) + W[s,i]
N個(gè)整數(shù)（數(shù)的大小為0-255）的序列，把它們加密為K個(gè)整數(shù)（數(shù)的大小為0-255）.再將K個(gè)整數(shù)順序隨機(jī)打亂，使得可以從這亂序的K個(gè)整數(shù)中解碼出原序列。設(shè)計(jì)加密解密算法,且要求K<=15N.如果是：
1). N<=16,要求K<=16N.
2). N<=16,要求K<=10N.
3). N<=64,要求K<=15N.
我表示連題都看不懂，看了網(wǎng)上答案發(fā)現(xiàn)主要是對第i個(gè)數(shù)字第k位是什么進(jìn)行編碼。一個(gè)字符串中含有n個(gè)字符，其中有m個(gè)不同的字符，n>>m，用最少的時(shí)間和空間找到包含所有這m個(gè)字符的最短的字串，不考慮特殊字符，只考慮字母數(shù)字即可。
例如：abccbaddac, 返回：cbad
aabcadbbbcca，返回：bcad
解題方法：設(shè)不同的字母共有m個(gè)，首先從左往右找到第一個(gè)包含所有字母的子串，長度為L，然后從L-m處開始重新尋找。取找到的最短長度即可。
