1樓：獨銘鳴
主席樹區間k大，笛卡爾樹單調棧優化的O（n）建樹。
堆，斜堆，左偏樹，莫隊。
第一次見莫隊，覺得好厲害啊，真tm優雅的暴力，然後遇到了個普通莫隊搞不定的題——歷史研究，然後就知道了個回滾莫隊這麼個東西。
第一次寫堆，感覺這東西好厲害。後來知道了左偏樹，怎麼能這麼短。再後來，斜堆，emmmm，還能這麼玩？
自從學會了笛卡爾樹，看什麼題都像笛卡爾樹。
主席樹可是好東西。就是空間開的有點大
------2019.9.14
cdq分治，整體二分是個好東西，特別是整體二分可以寫帶修區間k大，比樹套樹好多了。
珂朵莉樹。。。。。真是個神奇的演算法。
2樓：reaver
菜雞來說乙個。。。
判斷陣列是否越界，一般都是用兩個判斷條件實現，即i＜0 或 i＞max，但是在宣告我們的下標i時，偷偷把宣告寫成unsigned int
就可以只用i＞max來判斷了！
想不到吧(*σ`)σ
3樓：力扣（LeetCode）
說到哪些精妙的演算法能讓力扣君眼前一亮的？就先讓我們先來看乙個程式：
#include
using
namespace
std;
intmain
()請問輸出的 a 是多少？
熟悉 C 的同學很快就可以發現這個程式會輸出 20 ，其中 a << 2 表示將 a 左移兩位，即將為 5（二進位制：101）向左移動兩位變成 20（二進位制：10100），這個是向左移位，同理還有向右移位，這個是位運算的知識。
在學習的過程中可能老師對於對應的知識點只是有所提及，但是似乎在我們的實際應用中較少地使用到了這個知識，本文將盤點一下這個看上去與我們的實際開發結合不緊密的操作到底有什麼作用。
刷過力扣君第 136 道題的同學一定不陌生
只出現一次的數字 - 力扣（LeetCode）
題目描述：
給定乙個非空整數陣列，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。
說明：你的演算法應該具有線性時間複雜度。 你可以不使用額外空間來實現嗎？
對於這道題的常規解法我們可能會考慮放乙個字典，依次進行遍歷：
class
Solution
(object
):def
singleNumber
(self
,nums
):"""
:type nums: List[int]
:rtype: int
34;""
hash_table={}
fori
innums
:try
:hash_table
.pop(i
)except
:hash_table[i
]=1return
hash_table
.popitem
()[0
]但是這樣子做的話想法就太常規了，奇技淫巧的做法如下（使用 XOR，即異或運算）
class
Solution
(object
):def
singleNumber
(self
,nums
):"""
:type nums: List[int]
:rtype: int
34;""a=
0foriin
nums:a
^=ireturn
a我們再來看看另乙個題目，如何不使用語言自帶的 + 來計算 a+b，先補充乙個關於異或運算的背景知識，對於 A 和 B 的異或運算來說，規則是這樣的：
我們假設有兩個二進位制的數，比如 3（011）和 5（101），按照每一位對應異或的結果便是：110（看，最低位沒有進製，其他位正常相加了），所以如果要實現乙個加法的話，可以考慮用異或的方式解決，但是需要手動考慮一下進製的問題。
那什麼時候該進製呢？肯定是兩個地方都是 1 的地方，所以我們需要乙個與（&）運算來確定，如果兩個都是 1 ，那麼 & 的結果一定是 1 ，否則是 0，有了這樣的思路之後我們就可以寫出如下程式：
intadd
(inta,
intb
)returna;
}2 的冪次的含義是，是否是 2，4，8，16 之類的數，我們通過二進位制的方法來看，可以發現一些特徵，他們對應的二進位制是：10，100，1000，從中可以發現對應的數的二進位制形式只有乙個 1，這樣的情況下我們可以通過與（&）的方法消去乙個 1 ，通過判斷是否消去了那個唯一的 1 來判斷原始數是否只有唯一的乙個 1，程式如下：
bool
check
(intn)
看，即使是我們平時少有關注的位運算也可以在這些題目（或者需求）中發揮非常重要的作用，極大地降低了問題解決的時間複雜度，提高了程式效率，當大家都在各種線段樹，紅黑樹的時候，默默地關注了一下位運算的相關技巧，或許就是面試制勝的關鍵一步。
4樓：
舞蹈鏈！高德納成名之作
斐波那契數列四種解法，代表不同水平！
Zobrist雜湊，博弈的基礎！
這幾個代表我最膜拜的經典資料結構技巧
5樓：hzwer
del(x)
x->r->l=
x->l,
x->l->r=
x->rrev(x
)x->
l->r=
x,x->
r->l=
x* 並查集的根可以不指自己，存乙個負數，其絕對值為這個集合的大小find_root(x) // fa[x] 表示 x 的父親return fa[x] < 0 ? x : fa[x] = find_root(fa[x])
size(x)
return - fa[find_root(x)];
* 不帶路徑壓縮的並查集，可以斷開最後連線的邊來撤銷最後一次合併* NOIP2017 day2T3 的一小步，用樹狀陣列實現查詢數列中的第 K 個非 0 數，支援修改
樹狀陣列記 lowbit 段有多少個非 0，就可以在樹狀陣列上二分 （@九條可憐 教我的）
* 斜堆，O(nlogn)合併線段樹
* 可持久化並查集，可持久化字典樹
* 商業互吹 @Memphis
非旋轉Treap及可持久化[Merge,Split]
6樓：
函式式程式設計裡，寫乙個複雜度 O1的佇列。
由於不可變，沒辦法儲存狀態。用 map 來存頭尾以及當前所在位置，雖然能保證 O1 ，但不優雅。
可以這樣子做，用兩個 List（鍊錶）：
L1: [1,2,3]
L2:插入佇列時，往 L2逆序插（逆序是因為往第乙個插複雜度是 O1）。如插入4，5
L1: [1,2,3]
L2: [5,4]
出隊時， L1 出： 出1，2
L1: [3]
L2: [5,4]
出完時，L1作L2用,L2 逆轉作 L1用：
L1 : [4,5]
L2: [ ]
當然我還是更喜歡自己用 map。
def init_list():
% }出隊時， head-1即可, 不需要對 data 做操作。% }
7樓：xxx
小白來答一波~
樹堆treap的rotate函式，相當巧妙。第一次看的時候完全不知道修改時如何進行的，因為引用符號太容易被漏掉了！盯了半個小時突然靈光咋現看到了引用符號！
感覺全世界充滿了光明！然後整個樹堆的旋轉豁然貫通！
另外乙個就是一道題的資料結構解法。
輸入n個數，對於第i個數，求其之前與其差的絕對值最小的數。
一般人都是用樹結構來做的！但是那是nlogn的效率！我奇蹟般地看到了乙個鍊錶做法，效率為O(n)！
有讚更解法！各位可以先嘗試嘗試？雖然我知道可能我的修為不深，但是那個解法確實讓我感到美麗啊！
8樓：Belleve
Yao's protocol.
「如何讓兩個女士比較出誰更胖——在她們都不想洩漏體重的前提下？」
問題是這樣的：假設 Alice 手上有乙個隱私函式 f，Bob 有隱私資料 x，那麼請為他們設計乙個協議，讓雙方互相不給任何人透露自己隱私的情況下，計算出 f(x) 的數值？（從 f(x) 的結果推斷 x 或者 f 不算在內；雙方始終遵守協議。
）實現是這樣的：考慮乙個 k 個 bit 到乙個 bit 的簡單函式 f（更複雜的函式可以簡化到這個樣子），alice 可以打出 f 的真值表來，然後她產生 k+1 對隨機數，表示 k 個輸入 bit（）和輸出 bit 的 0/1 值（）。
接著她按照這些隨機數加密真值表，比如如果 f(1, 1)=0，則她用兩個隨機數作為金鑰加密產生乙個密文。她可以把加密的真值表連同表示結果的隨機數發給 Bob。
接下來 Bob 需要按照自己的資料（x）找 Alice 要 k 個隨機數解碼他拿到的真值表，真值表中只有一項可以被解碼，解碼的結果就是 f(x)，其他的則無法解碼。
要隨機數的過程是基於 Oblivious Transfer，這個協議要求：
Bob 根據自己的選擇獲取 Alice 兩條私密訊息中的一條，另一條則無法解密；
而 Alice 不能得知 Bob 的選擇。
過程是：
Alice 生成 RSA 公鑰-金鑰對，她把公鑰發給 Bob，Bob 根據自己的選擇獲取。以下計算均在上進行。Alice 生成兩個隨機數發給 Bob。
Bob 生成隨機數 k，計算發給 Alice。由於 k 是私密的，Alice 無法解密出 c 來。
Alice 計算，傳送給 Bob。
Bob 計算（因為），而對於另一條訊息，他就無法成功解碼。
有關 @aricatamoy「為什麼不用天平」，那麼請問：兩個人該怎麼做才能保證天平上面沒被動過手腳，暗地裡收集她們的體重呢？
9樓：小王做IT
演算法導論中有不少經典（一般資料結構書不會涉及）：
平攤分析，逆序對問題，貪婪演算法的理論證明過程，NP同理問題。
程式設計藝術（高爺爺經典）一書中，處處美妙，當時做隨機數的效能分析，看了下本書的隨機數分析，大開眼界。
編譯原理（龍書虎書）：
編譯器前端自動生成技術，詞法分析，語法分析等等。
10樓：IceCamel
以上很多朋友都說了各種資料結構中的精巧設計，我這裡再補充乙個好玩的，就是Linux核心中關於鍊錶的實現。
一般的鍊錶都是專門有乙個鍊錶資料結構，然後這個資料結構中有各種元素以及前後向指標。
但在Linux核心中，鍊錶資料結構並不包含任何實際元素，就只有簡單的前向後向指標，然後在實際的特殊資料結構裡包含這個鍊錶資料結構，大大提高了鍊錶的可復用性。
struct list_head {
struct list_head *next, *prev;
如何理解「程式 演算法 資料結構」這句話？
小凡 本來想來找答案的，後來感覺還是把十幾年工作經驗簡單分享下。程式 資料結構 演算法，這句話呢，如果放在現實世界，有個簡單的小例子，假如有件事，我需要知道附近有多少個人。這個問題，在計算機的世界應該怎麼表達，首先應該有個地圖。地圖的組織結構就是資料結構了，然後就是怎麼找到這些人，這就是演算法。這裡...
演算法資料結構裡面有沒有什麼有趣的內容？
Striker 看到下面已經有回答說了穩定婚姻問題，一般的就是n個男生n個女生，每個男生都會對所有女生有乙個偏好順序，每個女生也會對所有男生有個偏好順序，現在問題是想找乙個穩定匹配，穩定 的意思就是不存在一對男生女生，在這個匹配中他們沒有在一起，但是各自都更喜歡對方勝過自己在這個匹配中的伴侶，或者按...
學習資料結構和演算法之前，需要哪些高等數學知識做基礎？
youngitachi 如果這個高等數學是指微積分，那麼基本不需要。如果是指大學裡面接觸的數學知識，可能涉及到離散數學 矩陣 不過都是涉及非常基礎的東西。不要太在意這些，不需要等到把一堆數學知識學完了才開始學資料結構和演算法。試著直接開始學習資料結構和演算法，如果不懂的再去查資料補充。 堅持30天 ...