1. 格雷碼

• 定義：格雷碼是一個(gè)數(shù)列集合，每個(gè)數(shù)使用二進(jìn)制表示，每兩個(gè)相鄰的數(shù)之間只有一個(gè)位元的值不同，同時(shí)最后一個(gè)數(shù)與第一個(gè)數(shù)之間也只有一個(gè)位元值不同。
• 性質(zhì)：
  • 奇數(shù)項(xiàng)： 它與前一個(gè)格雷碼相比只改動了最右邊一個(gè)位元的值
  • 偶數(shù)項(xiàng)： 相對前一個(gè)格雷碼只改變了從右數(shù)第一個(gè)1左邊的一個(gè)位元的值

2. 循環(huán)移動

• 問題：給定長度為n的數(shù)組和數(shù)字i，將數(shù)組循環(huán)左移i位
• 思路：根據(jù)i將原數(shù)組分為ab兩部分，原問題就變?yōu)橥ㄟ^ab求ba，此時(shí)可以將a翻轉(zhuǎn)，將b翻轉(zhuǎn)，最后將數(shù)組整體翻轉(zhuǎn)。這種方式時(shí)間與空間都消耗的較少。
• 如：將數(shù)組0123456789循環(huán)左移3位
  • 數(shù)組分為a: 012 b: 3456789
  • ab分別翻轉(zhuǎn)： 210 9876543
  • ab整體翻轉(zhuǎn)： 3456789012

3. 找出小于n的所有素?cái)?shù)

• 思路：從2開始，將1~n中所有2的倍數(shù)去除，3的倍數(shù)去除，直到根號n結(jié)束，剩下的數(shù)就是小于n的所有素?cái)?shù)。

4. 找出一個(gè)字符串中有重復(fù)的且長度最長的子字符串及其長度。

   1. 對與字符串按照子字符串長度從大到小遞減的方式掃描
   2. 查找源字符串中是否有重復(fù)的子字符串，若有，就結(jié)束。沒有就減小子字符串的長度并重復(fù)改步驟。

5. 魔幻方陣

• 定義： 一個(gè)n階的幻方是一個(gè)由整數(shù)1、2、3……n^2組成的方陣，方陣的每行的整數(shù)和、每列上的整數(shù)和、及兩條對角線中的每條整數(shù)和都等于同一個(gè)整數(shù)s，s被稱為改幻方的幻和。
• 楊輝斜排法（僅適用于n為奇數(shù)的情況）
  1. 將1放在第一行的中間，其余數(shù)按順序、按以下規(guī)則放置
  2. 其余整數(shù)放在當(dāng)前整數(shù)的斜右上方，其中有幾種放置數(shù)的情況
     1. 若要放置的數(shù)處于第一行的上面，則將它置于最底行的對應(yīng)列位置
     2. 若要放置的書在最右邊一列的右側(cè)，則將其放置于對應(yīng)行的最左邊一列。
     3. 若要放置的數(shù)字應(yīng)放置的位置已經(jīng)有數(shù)字放置，則將該數(shù)字置于上個(gè)放置好的數(shù)字的正下方。

6. 尋找最大的n個(gè)數(shù)

• 問題： 從一些各不相同的無序數(shù)中，找到最大的n個(gè)數(shù)
  • 直觀想法： 利用快排對數(shù)據(jù)排序，然后取出最大的n個(gè)數(shù)，假設(shè)共有m個(gè)數(shù)，則時(shí)間復(fù)雜度為mlogm
    但是
  • 但若m很大，數(shù)據(jù)很多，無法一次全部都入到內(nèi)存，則直接排序不再適用，此時(shí)可以考慮挑選數(shù)據(jù)集前n個(gè)數(shù)放入數(shù)組中，然后遍歷升序的書，發(fā)現(xiàn)比數(shù)組n中最小的數(shù)大的數(shù)，就將數(shù)組中最小的數(shù)替換出來，找出n個(gè)數(shù)中最小的數(shù)可以使用小根堆，根節(jié)點(diǎn)的值最小，每次替換后需對數(shù)組排序，堆排序時(shí)間復(fù)雜度為logn，則總的時(shí)間復(fù)雜度為mlogn。

7. 查找數(shù)組中的最大值和最小值

• 直觀想法： 遍歷數(shù)組，同時(shí)與最大值、最小值作比較，一次遍歷即可得到結(jié)果，這個(gè)過程中元素比較次數(shù)為2n
• 優(yōu)化解法
  1. 將數(shù)組元素兩兩分為一組，進(jìn)行組內(nèi)排序，小的放前面，大的放后面。這種操作在原始數(shù)組上進(jìn)行，無需額外空間，此時(shí)比較n/2次
  2. 在原始數(shù)組下標(biāo)為奇數(shù)的數(shù)據(jù)中找出最大值，此時(shí)比較n/2次
  3. 在原始數(shù)組下標(biāo)為偶數(shù)的數(shù)據(jù)中找出最小值，此時(shí)比較n/2次
     這種方法總共比較了3n/2次，較2n次少

8. 遍歷一次單鏈表找到它的中間節(jié)點(diǎn)
   設(shè)置兩個(gè)指針p和q，讓p每次前進(jìn)2個(gè)節(jié)點(diǎn)，q每次前進(jìn)1個(gè)節(jié)點(diǎn)，當(dāng)p走到終點(diǎn)時(shí)，q恰好在中間位置

9. 判斷單鏈表是否有環(huán)
   設(shè)置連個(gè)指針p和q，讓p每次前進(jìn)2個(gè)節(jié)點(diǎn)，q每次前進(jìn)1個(gè)節(jié)點(diǎn)，這樣如果存在環(huán)，p指針一定會與q指針相遇，若無環(huán)，則p指針必定會先成為null

10. 判斷兩個(gè)鏈表是否相交
    若兩個(gè)單鏈表相交，則他們相交節(jié)點(diǎn)之后的所有節(jié)點(diǎn)應(yīng)該是兩個(gè)鏈表共有的，所以最后一個(gè)節(jié)點(diǎn)必然相等，我們只要找到兩個(gè)鏈表的尾節(jié)點(diǎn)，判斷它們是否相等即可，這種思想的時(shí)間按復(fù)雜度為length(h1)+length(h2)

11. 蝸牛爬桿問題

一根31cm長的細(xì)桿，2cm、7cm、12cm、17cm、25cm處各有一只蝸牛。開始時(shí)，蝸牛頭朝做還是朝右是任意的，他們只會向前走或調(diào)頭，但不會后退，當(dāng)任意兩只蝸牛碰頭時(shí)，它們會同時(shí)調(diào)頭走，但速度不變，每秒走0.5cm，計(jì)算蝸牛全部離開桿的最長時(shí)間和最短時(shí)間。

• 思路：蝸牛相遇時(shí)，同時(shí)調(diào)頭，速度不變，可理解為倆蝸?！安良缍^”，方向，速度都未變，此時(shí)蝸牛離開的最長時(shí)間按為處于2cm的那只蝸牛走到最右邊的時(shí)間(31-2)/0.5=58s,蝸牛離開的最短時(shí)間為處于“中間”的那只走到離它最近的一邊的時(shí)間(31-17)/0.5=28s