1樓：密期望
可追溯化資料結構。
實現則是用平衡樹維護各個操作即可。全部操作都是O(log n)。
而其他資料結構的可追溯化簡直鬼才。比如堆。（然而我不會）
2樓：劉正
如果了解了演算法的本質，你會發現，所有的演算法問題都歸結為資訊的傳遞效率提公升，具有非常明顯共性思維。
同時，九成九的演算法都能最終在生活中找到相應的場景模擬。
比如將資訊的傳遞模擬為物流問題。
我面試的時候經常問的乙個問題，從北京到廣州，運輸一百萬噸貨物，怎樣提公升效率？
幾乎所有的方法都跳不開以下幾種思維方式：
1，分治思維
典型應用小到如二分歸併，快排，大到雲計算如dag，mapreduce。
具體到問題，從北京到廣州，一輛車不夠我兩輛，兩輛不夠我用一百輛～
2，空間換時間
最經典的應用莫過於遞迴，快取與索引，犧牲空間換取效能。
具體到問題，北京到廣州經過上海，上海與北京之間鐵路方便，廣州到上海之間船運方便，於是我在上海建立大型貨運中轉倉提公升效率。
3，通道的擴容或者有效資訊的壓縮
經典的應用比如頻寬提公升，hash演算法，布隆過濾器。
具體到問題，北京到廣州，我從國道改為高速，高速不行我用鐵路，鐵路不行我過天津用萬噸巨輪，同時提公升貨櫃有效容積率～
就好像三原色組成了世界一般，幾乎所有精妙的演算法，在本質上都是這三種思維的組合與衍生。
再往上走一層，三種思維都是同一種思維的衍生，求同存異～這裡就不展開了。
同時，所有的演算法問題，幾乎都能在生活中找到相同的模型。
想想jdk1.7的ConcurrentHashMap的分段演算法，它和我們在火車站買票是不是很相似？
JVM，作為這個星球上最好的記憶體管理系統，把它模擬成乙個倉庫，你會發現，它和乙個倉庫管理系統如此相似～
Alphago的強化學習演算法很複雜，但其原理與蟻群思維互相印證～
RSA 非對稱加密，和銀行的隔離門其實是一種思維。
如果在日常程式設計中，將演算法與生活相互模擬，相互印證，以生活中實際的模型去驗證演算法的可行性，做到知行合一，一通百通～
恭喜你好嗨哦～感覺人生已經達到了高潮～
你仍然是條肥胖死宅的單身碼狗
咋滴？你還以為你是馮諾依曼咩？
3樓：LightGHLi
很多問題都是解決完之後拍案叫絕，過了一段時間便索然無味。
但這個問題不是。
考慮求出圖 的 MST（最小生成樹） ，然後從 中移除 的所有邊，繼續求剩餘圖的 MST ，持續這樣的操作直到圖不連通，如果可以進行 次這樣的操作，那麼我們可以得到 ，共 棵生成樹。
那麼問題來了，如果 比較大，比如 ，如何才能較快地求出這 棵生成樹？
我們可以通過斐波那契堆優化的 Prim 演算法，在 的時間複雜度內得到答案。但拍案叫絕不在這裡，而在於我們有更快的，時間複雜度為 的演算法。
接下來，我將通過四個步驟闡述這個演算法。
(A)令 為 按權重從小到大排序後的邊。令 ，即為 按權重從小到大排序後的前 條邊的集合。令 為通過 Kruskal 演算法插入 中的邊後，被形成的生成森林使用的邊的集合。
以此類推，對於 0" eeimg="1"/>，令 ，並令 為通過 Kruskal 演算法插入 中的邊後，被形成的生成森林使用的邊的集合。
那麼，我們可以得到乙個性質，即 分別為 的邊集。
下面我們採用數學歸納法來證明 為 的邊集。
1. 當 時。當前沒有被使用的邊的集合為 。
所以 Kruskal 演算法會依次插入 中的邊，又因為圖連通，所以形成的生成森林一定是一棵生成樹，即 。故 為 的邊集，命題成立。
2. 假設當 時成立。則當 時，當前沒有被使用的邊的集合為 。
所以 Kruskal 演算法會依次插入 中的邊，又因為圖連通，所以形成的生成森林一定是一棵生成樹，即 。故 為 的邊集，命題成立。
綜上所述，對於 0" eeimg="1"/>， 為 的邊集。
(B)在 (A) 的條件下，如果有兩個頂點 在圖 中屬於同乙個連通分量，那麼對於所有的 都有 在圖 中也屬於同乙個連通分量。
由於 (A) 使用了 Kruskal 演算法，而 Kruskal 演算法在插入邊的時候，會判斷該邊的兩個頂點是否屬於同乙個連通分量，如果屬於同乙個連通分量，則放棄這條邊，否則將兩個頂點分別屬於的連通分量合併為乙個連通分量。
所以 中的每一條邊，都在插入 中被放棄過，即 中的每一條邊的兩個頂點，在圖 中都屬於同乙個連通分量。因為 在圖 中屬於同乙個連通分量，所以在圖 中 到 有一條路徑，又因為這一條路徑上的每一條邊的兩個頂點，在圖 中屬於同乙個連通分量，所以 在圖 中也屬於同乙個連通分量。
(C)令 為通過 Kruskal 演算法插入 中的邊時，在 上定義的並查集。
假設我們有 和邊 。那麼我們可以在 的時間複雜度內，找到 所屬於的生成樹 。
根據 (B) 我們可以二分 ，從而找到最小的 0" eeimg="1"/>，使得頂點 和 在圖 中屬於兩個不同的連通分量。所以 屬於 ，即屬於生成樹 。
通過並查集判斷 和 是否屬於同乙個連通分量的時間複雜度為 ，二分的時間複雜度為 ，故總的時間複雜度為 。
(D)根據 (A)(B)(C)，我們可以得到時間複雜度為 的演算法。
首先，將 的邊集按權重從小到大排序，時間複雜度 。其次，對於每一條邊依次按照 (C) 中的方法，找到它所屬於的生成樹 ，並將這一條邊插入到第 個並查集中，時間複雜度 。注意，如果沒有建立第 個並查集，則建立第 個並查集。
因為 條邊最多建立 個並查集，每次申請空間並建立並查集的時間複雜度為 ，所以該操作的時間複雜度為 。
綜上所述，總體的時間複雜度為 。
是不是拍案叫絕？
好吧，還是落入了索然無味的俗套（逃
4樓：北海以北北北北
某次刷題，就看見乙個人做題都是一次0一次AC,開啟一看全是的if（測試資料）然後輸出結果（我們題庫提交了可以看測試資料）
你就是欺負我題庫資料水。
5樓：鄭子穎
我是在做到LeetCode 「169. Majority Element」和「229. Majority Element II」的時候百思不得其解，然後看了答案才知道Boyer–Moore。
當時驚為天人。
Majority Element - LeetCodeMajority Element II - LeetCode
6樓：
a和b倆個數交換
你首先想到的方法是借助t。那麼我現在的要求是不可以借助其他變數可以完成麼？
這是我應聘某公司筆試的一道題，也是唯一的一道題。（留點空白大家思考一下）
其實很簡單
a=a+b;
b=a－b;
a=a－b;
7樓：隨心而流
不算演算法問題。只是乙個很簡單的小演算法練習題，題是什麼不重要，重要的是，迴圈裡面全是用的i……哦不對，是1=1;1不要問我怎麼找到的，我只是幫他寫了一遍突然想到的
8樓：及她
輸入a和b的值，交換輸出。
int a，b；
scanf（「%d %d「,&a,&b);
printf(「%d %d」,b,a);
return 0;
抖個機靈233
9樓：Vik Paruchuri
在學習中來講，這種「拍案叫絕」可能是督促我們學習的最好動力（這裡的學習是指一般性的學習，並沒有特指程式設計或資料科學領域）。下面是我從事外事工作時的乙個有關程式設計的故事：
how-learning-to-code-kept-me-sane
10樓：圖納豆
n階台階，你每次能上一階或者兩階，有多少種方法到達第n階int a=1,b=1;
while(n--) a=(b+=a)-a;
return a;
11樓：Tanyboye
知乎上看到的
關於求24點的演算法
(0!+0!+0!+0!)!=24
'0'>>(!0)=24
lenlt;< len24
'0'/(('0'+'0')/'0')=240000=24
((W')!+(X')!+(Y')!+(Z')!)!=24
12樓：鬼眸
看到有回答雞兔同籠的我再說乙個更簡單的辦法兩步就可以有一堆雞和兔子數頭50 數腿120 各多少還是先訓練這些動物然後讓它們同時抬起一半的腳 120/2=60 這時雞有乙隻腳兔子有兩隻也就是說雞頭和腳的數量一樣兔子是每只腳比頭多乙個所以60－50=10就是兔子的數量
語文不太好不過其實列個方程就能一下看明白設兔子x4x＋2(50－x)=120
化簡100+2x=120
變形一下 50+x=120/2
13樓：HuananZuna
大一的時候吧
有次做了個進製轉換的程式
一開始年輕用int定義資料型別，然後因為int只有-2147483648~+2147483647，二進位制那裡有事沒事就因為溢位報個錯給我看看。
那可怎麼辦，用double也多不了多少啊。然後有一天我們老師知道了這個事，就跟我說，要不你試試自己寫個四則運算的演算法出來。
然後我就成功的寫出了乙個輔助演算法比原程式還要長的東西
14樓：dmumatt
補充一下。
題目要求是常數空間複雜度，不是時間複雜度，仔細審題哦然後關於 Array 的 reverse操作，一般頭尾挨個swap就好啦，最多引入乙個中間temp變數
下面是原答案咯
leetcode上看到的乙個題目，應該比較經典。
reverse 一句話。比如，輸入 「i love you」, 輸出「you love i」。假設單詞長度最多可能沒有上限，要求除了輸入值以外，引入的其他變數為O(1)空間複雜度
苦思冥想。。。
沒想出來
然後看了下答案
只要把整個string reverse一遍然後再把每個單詞 reverse一遍就好了。
15樓：
題意大概是二維座標軸上n個人，有的在（p[i],0）位置,有的在（0,p[i]）。
第i個人在t[i]時刻垂直自己所在的座標軸出發，所有人速度相同數值為1。
到達邊界位置x=w或者y=h的地方就停止。
且兩個人相撞就交換方向。
問每個人最後的位置。
這道看起來複雜的題目竟然可以非常簡單又好寫地解決（這種題目其實不少，就是想法題）。
考慮t[i]時刻出發的人呢相當於位置從（p[i],0）變成（p[i],-t）（在y軸同理），然後0時刻出發。
現在所有人都是0時刻出發，我們看他們新的座標（x,y），如果有幾個點x+y相同那麼他們之間就會相撞，但不是兩兩都撞。我們就把點按x+y分組。
乙個組裡的點的終點位置只會和同乙個組裡的點發生交換。
重要的是他們不管怎麼撞，互相的相對位置沒有發生變化。 就是說拿幾個平行 y=x 的直線可以把他們的路徑分隔開。
然後同乙個組的終點都算出來（(p,-t)終點就是(p,h)，(-t,p)終點就是(w,p)），然後起點和終點分別排序，這個排序就是按照 x-y 排序（y-x 也可以），再對應起來就行了。
然後因為我們是分組後排序，這個分組也可以寫在排序裡，也就是先按 x+y 排序，x+y 相同再按 x-y 排序。
這道題是 cf849D。
#include
#define rep(i,l,r) for(int i=l,_=r;i<_;++i)
using
namespace
std;
const
intN
=201000
;struct
nodea[
N],b[
N];intansx[N
],ansy[N
];bool
cmp(
nodea,
nodeb)
bool
cmp2
(nodea,
nodeb)
intmain();
elsea[
i]=(
node);
b[i]
=a[i
];}sort(a
,a+n
,cmp
);sort(b
,b+n
,cmp2
);rep(i
,0,n
)rep(i
,0,n
)printf
("%d %d\n"
,ansx[i
],ansy[i
]);return0;}
有哪些遊戲讓你拍案叫絕？
胡藝蕭 魂系列3D關卡設計的巔峰，下一秒不知道怎麼死系列 重力眩暈 PSV唯一一款親女兒作品，呼叫了PSV的全部機能，前無古人後無來者系列 怪物獵人 不知道為什麼被這樣虐著就是有一種難言的快感系列 地獄空降兵 我來支援你們了，隊友被我砸死了！總部給我支援了，我被總部炸死了！隊友開著機械人好帥，我被隊...
哪些歌詞讓你拍案叫絕？
Jessie靈性之旅 施人誠的路過人間 真的是聽了一千遍的歌！貪嗔愛痴怨路過人間就忙這這些 經歷過的就懂 每次都在心底暗暗發誓這是最後一次犯傻了 可是人真的只要有機會 就又一次淪陷 儘管那些愛情和承諾虛無縹緲 可是還是選擇的去相信吧 大魔王 在家閒到一句一句看歌詞 我的翻譯 折磨我的任何事，都讓我感...
哪些書名讓你拍案叫絕？
黑駝山人 魯大維的著作，原名 Martial Spectacles of the Ming Court 中譯名為 神武軍容耀天威 明代皇室的尚武活動 感覺氣勢一下子就出來了 木頭 安娜卡列尼娜 剛開始看的時候沒有什麼感覺，但是當我通讀了整本書的時候感慨了好久，托爾斯泰真牛！安娜直到死都叫安娜卡列尼娜...