有哪些令人拍案叫絕的演算法?
相關問題:
有哪些令人拍案叫絕的代碼優化? - 計算機 - 知乎
在Matrix67的blog 上看的一道題:
有一個黑匣子,黑匣子里有一個關於 x 的多項式 p(x) 。我們不知道它有多少項,但已知所有的係數都是正整數。每一次,你可以給黑匣子輸入一個整數,黑匣子將返回把這個整數代入多項式後的值。那麼,最少需要多少次, 我們可以得到這個多項式每項的係數呢?
答案是兩次。
/*-------------------------------------答案分界線------------------------------*/
第一次,輸入 1 ,於是便得到整個多項式的所有係數之和。記作 S 。
第二次,輸入 S + 1 ,於是黑匣子返回的是
的值。
我們要得到 ,只需要把這個值換成 S+1 進位, 然後依次讀出每一位上的數。
P.S. 第一次得到S是為了保證對於任意係數
---------------------------------------------------------------------------------------
其實最大係數不超過N的多項式,本來就是N進位的本質
上大學的時候,有一次列印課程設計,要列印兩份,打出來一摞是「1122334455...」排序的,於是我就在店門口左一張右一張的開始分成兩摞。然後列印店老闆過來看了一眼,一臉鄙視的從我手裡接過一摞列印稿,左邊兩張,右邊兩張的分了起來...
這樣[1,12,23,34,45...]一次兩張也能分成有序的兩摞,這是在生活中第一次讓我感覺到演算法好厲害。
--------------------------------
這不是「怎麼快速列印兩份文檔」的演算法,這是「不小心設置錯了怎麼努力補救更快一點」的演算法啊!
我作為一個程序員因為這種答案上了日報,會不會很影響職業道路...
HR:「同學,你就是那個連印表機都不會用的小傻瓜么...」
前三個是zero knowledge proof的幾個簡單例子,第四個比較有趣。
1. 有n&>2個交易員,他們想知道他們平均的薪水,但是又不想任何人知道自己的薪水。
第一個交易員random選一個數,加在自己的薪水上,然後告訴第二個交易員,然後第二個再把自己薪水加上去告訴第三個交易員,。。。。,第n個把自己的薪水加上去告訴第一個交易員,第一個交易員把自己最初選的隨機數減掉,然後把結果/n告訴大家。
比如三個人分別為1 2 3,第一個人選隨機數100,告訴第二個人101,第二個人告訴第三個人103,第三個人告訴第一個人106,第一個人減去100,告訴大家平均數是6/3=2
2. Alice是色盲,她有兩個球,外觀完全一樣,Bob告訴她這兩個球顏色不同,問Bob怎麼向Alice證明這倆球顏色不同。
把兩個球分別稱為A球B球,Alice放在背後,每次拿出來一個讓Bob判斷是哪個,重複足夠多次,say100000次,如果Bob每次都說對,那麼兩個球顏色不同的概率&>1-(1/2)^100000,但是Alice仍然不知道兩個球的顏色。
3. 判斷兩個圖G和H是同構的是NP的,只要給出一組頂點的對應關係就可以多項式時間檢驗,Alice要給Bob證明這兩個圖是同構的但又不給出這組對應關係。
每一次,Alice都生成一個G的同構圖G",然後由Bob提出由Alice給出G和G"的頂點對應關係,還是H和G"的頂點對應關係,然後bob去驗證。重複足夠多次,如果alice每次都說對,那麼G和H同構的概率就非常大。
4. 有個list,已知存在majority element,就是出現次數多餘一半的元素,怎麼把它找出來。比如 abaacbbacaa 中的a。
如果不知道list裡面是不是有majority element,如果有就把它找出來,沒有的話return none呢?
方法很多,我知道的最漂亮的是用O(n)時間和constant memory。
演算法很簡單,開始記錄0
遍歷第i個元素時
------如果當前記錄的是0,那麼記錄(第i個元素,1)
------如果當前記錄是(x,y)
------------如果當前元素是x,那麼記錄(x,y+1)
------------否則記錄(x,y-1)(如果y-1=0,記為0)
在這個例子當中, abaacbbacaa,根據看到的元素我們記錄
0-&>a-&>(a,1)-&>b-&>0
-&>a-&>(a,1)-&>a-&>(a,2)-&>c-&>(a,1)-&>b-&>0
-&>b-&>(b,1)-&>a-&>0
-&>c-&>(c,1)-&>a-&>0
-&>a-&>(a,1)
大概證明思路就是,按每次記錄0劃分成sub list,也就是ab,aacb,ba,ca,a,在除去最後一個的sub list的sub list當中,都沒有majority element,(因為其中第一個元素剛好出現一半次數),又因為已知整個list存在majority element,那肯定就是最後一個sub list中的majority element,在這個例子就是a。
通過證明我們知道,如果不知道是否有majority element的話沒啥區別,就是遍歷兩遍,第一遍一樣,找出來唯一可能的candidate,第二遍count一下出現次數,判斷是否真的是majority。
一道很有意思的題目,曾經在面試騰訊關鍵時刻出現過,感恩。
問:
有一種玻璃杯質量確定但未知,需要檢測。
有一棟100層的大樓,該種玻璃杯從某一層樓扔下,剛好會碎。
現給你兩個杯子,問怎樣檢測出這個杯子的質量,即找到在哪一層樓剛好會碎?
------- 一條分割線的時間思考 ---------
分析:
首先理解題意,將這個杯子從某一層樓扔下,如果沒碎,我還可以再利用它測試。
如果碎了的話,就不能再繼續用了。
如果我從x樓扔下,沒碎,在x+1樓扔下,碎掉了,即證明找到了x+1是剛好碎掉的樓層。
問題的關鍵是,怎麼快速找到這個樓層呢?這是一個查找問題。
我們需要一個策略方法來快速地找到它,就看誰的方法比較優秀拉。
而優秀的方法其評價標準顯而易見:各種情況下都能快速地找到目標樓層。
------- 再一條分割線的時間思考 ---------
思考路徑:
如果只有一個杯子的話,應該怎麼做呢?
稍微想一下也可以知道,必定只能一層一層地扔,1樓沒碎扔2樓,2樓沒碎扔3樓,直到碎掉。
現在我有兩個杯子。
學習過演算法和程序的人應該都知道二分法,很容易想到這樣去做,因為面對的是一個搜索問題。
所以可能會給出這樣的策略:
從50樓扔下,沒碎的話,再扔75樓,再沒碎我扔88樓,依次下去很快就可以鎖定樓層?
很快你會意識到問題所在,萬一第一次從50層樓扔下去,碎了咋整,難道又一層一層地扔?
杯子的質量是剛好在49層碎掉的話。最差的情況我需要扔50次,這方法不行。
再一個比較常見的方法是,先分區間的扔,再慢慢地一層一層地扔,隱含著分段查找的策略。
具體操作方式是:
先從第10樓扔,再從第20樓扔,依次下去,如果到某一層碎掉,比如50層碎掉了,我再從41樓開始扔,這樣的話應該算是比較快了把?
這個方法是要快一點不過如果我杯子的質量比較好,在99樓才會剛好碎掉。
這樣,最差的情況下,需要扔19次才能找到目標樓層,還是不能讓面試官滿意。
我們需要的方法是無論杯子的質量如何,不論是在1樓碎,49樓碎,99樓碎都要能快速鎖定的方法。
繼續思考剛才方法的缺陷,當杯子質量比較差的時候,此方法還是比較快速的找到的。比如杯子是在19樓剛好碎,我只需要扔11次,比99樓剛好碎的情況要少很多次。
所以我們的願望是:
杯子的質量無論分布在哪個查找區間,都可以快速地找到。所以我想到的是可以「勻」一下剛才的方法。即最開始我需要大膽地扔,然後再慢慢小心地扔。
具體方法設計:
每次扔的區間減少一層,這樣做可以保證每個區間查找的最差次數是一樣的。
假定第一步在15樓扔,沒碎的話則下一步在29樓扔,沒碎下一步在42樓扔....碎掉之後則在上一次沒碎的樓層開始向上扔。那麼最開始在哪一層開始扔呢??
這裡我們需要拿支筆算一下:
x+(x-1)+(x-2)+...+2 &>=100
求解出答案為14。
即最終給出的解決方案是:
最開始從14樓開始扔,沒碎的話在27樓扔,再沒碎的話在39樓扔.....一旦碎掉,則從上一次沒碎的樓層逐層往上扔,即可快速確認杯子在哪一層剛好會碎掉。
這樣的方法可以保證在最差的情況下也能在14次內找到樓層,平均需要的次數不到10次。
(列式子算了下期望是9次多)
【2017.11.3更新】:另一個令人拍案叫絕的數據結構(也可以算作演算法吧)
阮行止:你認為最優美的數據結構是什麼?
快速傅里葉變換(FFT)。
考慮多項式。現在要計算這兩個多項式的乘積。
普通的多項式乘法,總是係數相乘,走不出的複雜度。
於是就有了FFT的令人拍案叫絕之處:用點值來表達一個多項式。 選定個取值點,求出這些點上的值。我們拿到這些值,就可以還原出整個多項式。 有什麼用呢?詳見我的博客:FFT入門 · blue"s Blog。 FFT令人拍案叫絕的地方,就是想到了用點值來表達多項式,並在點值上計算乘積。 與之類似,快速數論變換(NTT)也是令人拍案叫絕的演算法。但是由於與FFT思路相似,不再贅述。 --------------------------------------------2016.11.15---------------------------------- 由於常數很小,python的大整數乘法甚至比C++的FFT還要快(整數長度很小的情況下)。 但是由於分治乘法比較容易想到,還是不太容易令人拍案叫絕。 比對一下運行效率:(10000位整數乘法)for(i=0;i&
我們知道,給定兩個點就可以求出一個一次函數的解析式,給定三個點就能求出一個二次函數的解析式……這啟示我們,可以將多項式以點值的形式表示。
例如:,選定取值點,於是我們得到這個多項式的點值表達:
憑藉對單位複數根的靈活應用,多項式乘法的複雜度被降到了。
noip2016 RP++.
有朋友提到分治乘法。
Python2
C++, FFT
--------------------------------------------2016.11.21----------------------------------
感謝知友給的RP。noip好像沒掛太慘。
莫隊演算法也是令人拍案叫絕的演算法呢…………有時間的時候來寫一寫吧。
隨便聊幾個,有大有小,玩過OI的人可能都聽說過,一笑而過就好。
1. 很多稱得上「拍案叫絕」的演算法都涉及到巧妙的模型/問題轉換,把看似毫不想乾的兩個領域聯繫起來。曾經有這麼一個OI題:你在製作一個遊戲,關卡設計員幫你設計了很多個(n個)關卡,每個關卡有各自的難度(1-m的整數)和精彩度(1-m的整數),假如最終的遊戲要求從中挑選若干個遊戲組成一個序列,每關的難度和精彩度都分別不小於上一關。如果n很大但m相對較小,最多可以做多少關?
================劇透====================
m較小是問題的突破口,另一個突破口是如果有兩關(ai, bi) == (aj, bj),那麼兩關一定是要麼都選,要麼都不選想清楚這一點之後,準備一張m*m的表,其中x_ij表示難度為i,精彩度為j的關卡有多少個。然後呢?
就是那個經典的動態規劃問題了:從左上角走到右下角,路徑最大值是多少?
2. 對隨機化演算法的利用也是非常巧妙的,最經典的比如Miller-Rabin Test等。下面也是某個OI題:給出n*n矩陣A, B, C,判斷是否有A*B=C?
================劇透====================
直接採用矩陣乘法的話,即使是Strassen演算法也需要O(n^2.84)的時間,雖然還有更好的分治演算法但實現難度變得越來越大,而且常數也變得越來越大。
官方給出的答案是:隨機生成若干個n*1向量X,計算A(BX) = CX是否成立。注意到這樣的測試只需要O(n^2)的時間。只要任何一個X沒有通過測試,A*B就不等於C。否則,在大量測試之後,我們可以非常確信A*B=C的概率極高。
3. 我做過幾年圖形學和計算幾何,為了追求高效,通用和誤差低,有很多非常實用的小技巧,其中很多我認為已經超越了技巧的範疇,值得稱其為一個演算法。相信很多人都聽說過John Carmack的神奇的開平方演算法了,再舉一個:
圖形學一個基礎核心的問題是:如何判斷給定直線和給定多邊形相交。一個簡化版的問題是:給定平面上一個三角形ABC和平面上的一個點X,判斷X與ABC的關係(內部/外部/邊上/頂點?)
================劇透====================
注意到任何嘗試求解點與某條邊關係的演算法,都難以避免地會遇到大量除0,重合,平行等一系列特殊情況。應用最廣泛的演算法,說起來很簡單:計算三角形XAB, XBC, XCA的2倍有向面積,然後:
(1) 三個同號:X在其內部;
(2) 兩個同號,另一個異號:X在其外部;
(3) 一個為0,兩個不為0且同號:X在三角形邊上;
(4) 一個為0,兩個不為0且異號:X在三角形某條邊的延長線上;
(5) 兩個為0:X在三角形頂點上;
(6) 三個為0:三角形ABC是退化的。
如果更詳細的分析三個有相面積哪個為正哪個為負,還可以得到更多細節比如X在哪條邊上,在三條直線劃分的哪個區域里,等等。有向面積的計算方法是:
(x1, y1), (x2, y2), (x3, y3)圍成的三角形的2倍有向面積為x1y2+x2y3+x3y1-y1x2-y2x3-y3x1。
這個演算法的好處在於:除了最後一步給出結論,中間計算不需要任何if-else。只用乘法和加減法,儘可能減小了誤差。
思考題:用2和3中的思想,分別解決下列問題:給定平面上不自交的封閉多邊形(可能為凹)和平面上的一個點,判斷點是否在多邊形內。
4. 並查集的Union-Find演算法看起來並沒有什麼拍案叫絕的地方,無非是查找祖先的時候順便做一下路徑壓縮。可是這個大巧無工的小優化,極大地改善了演算法的均攤複雜度。
(大致介紹一下就是,如何設計一個數據結構,使其支持如下三種操作:插入一個包含單獨一個新元素的集合,將兩個元素所在的集合合併,以及查詢兩個元素是否在同一個集合中。該數據結構在Kruskal等一系列重要演算法中有應用。)
這個演算法真正拍案叫絕的地方在於複雜度分析,自1964年路徑壓縮發明之後十幾年之內竟然沒有人能準確的分析出每個操作的均攤複雜度。直到1973年才由Hopcroft和Ullman給出第一個有意義的複雜度:O(log*n),其中log*的意思是:至少需要多少層log,才能使log(log(log(....log(n)...))) &< 0。這個證明已經很複雜了,有興趣的朋友可以參見https://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find
到了1975年,Tarjan證明了一個更好的複雜度上界:O(alpha(n)),其中alpha(n)是Ackermann函數的反函數。這個alpha(n)有多小呢?對於我們現在所能處理的數據規模,這個數不會超過4。我甚至大膽揣測,在我的有生之年,我們不需要這個數等於5的情形……
再後來,就是直到1989年,才最終證明了alpha(n)是並查集均攤複雜度的下界。這就是為什麼我認為這個演算法拍案叫絕:這是我見過的演算法里,
不是常數複雜度的,
有實際意義的演算法中,
復.雜.度.最.他.媽.低.的.一.個!
寫一個簡單,嚴格來說不算演算法的例子
初中數學老師最開始講到歐幾里得的幾何原本時提到的
因為覺得極度巧妙和簡單而終生難忘
問題就是,怎麼證明等腰三角形兩底角相等(不允許做輔助線)
----------------------------------------------------------------------------------
三角形ABC與三角形ACB全等
刷leetcode時碰到的,題目為Single Number | LeetCode OJ和Single Number III | LeetCode OJ。
這個題目是說,有一個n個元素的數組,除了一個元素只出現一次外,其他元素都出現兩次,讓你找出這個只出現一次的元素是幾,要求時間複雜度為O(n)且不再開闢新的內存空間。
——————————答案分割線—————————
解法是將所有元素做異或運算,即a[1] XOR a[2] XOR a[3] XOR…XOR a[n],所得的結果就是那個只出現一次的數字,時間複雜度為O(n)。
當時看了答案後就一拍腦瓜,感嘆這個技巧真不錯。然而直到我遇見了這道題的進階版,當時真是恍然大悟拍案叫絕。
進階版:有一個n個元素的數組,除了兩個數只出現一次外,其餘元素都出現兩次,讓你找出這兩個只出現一次的數分別是幾,要求時間複雜度為O(n)且再開闢的內存空間固定(與n無關)。
——————————答案分割線————————
首先,仿照前面的演算法,把所有元素異或,得到的結果就是那兩個只出現一次的元素異或的結果。
然後,重點來了,因為這兩個只出現一次的元素一定是不相同的,所以這兩個元素的二進位形式肯定至少有某一位是不同的,即一個為0,另一個為1,找到這一位。
可以根據前面異或得到的數字找到這一位,怎麼找呢?稍加分析就可以知道,異或得到這個數字二進位形式中任意一個為1的位都是我們要找的那一位,找到這一位就可以了(這很容易)。
再然後,以這一位是1還是0為標準,將數組的n個元素分成了兩部分,將這一位為0的所有元素做異或,得出的數就是只出現一次的數中的一個;將這一位為1的所有元素做異或,得出的數就是只出現一次的數中的另一個。從而解出題目。忽略尋找不同位的過程,總共遍曆數組兩次,時間複雜度為O(n)。一些螞蟻在樹枝上向其中一端爬,爬到末端就掉下去,如果相遇則向反方向爬,螞蟻速度相同,給定位置和方向,求所有螞蟻從樹枝上落下來的時間
想了半天好像沒啥特別驚艷的,最近的一個覺得很好的應該是google的那個jump一致性hash演算法吧,利用了偽隨機數列的均勻性和同seed的一致性
今天突然想起小時候學演算法看到的一個段子,說有一個老太拿了一個漁網,跟程序員出了道題,說這個漁網縱橫交錯,看成一個地圖,從左下到右上最短路徑是什麼呢,程序員說用dijkstra,老太微微一笑,說兩手捏住起點終點拉伸,拉直的這條線就是了
現實中解決問題,有時候物理碾壓數學:)
有哪些「上帝演算法」? - 冒泡的回答 - 知乎
我想很多OIer/ACMer看到這個問題下的大多數回答的感覺都是「這TM都能拍案叫絕?」
說一個簡單並在生活中經常用到的,那就是經典的「二分法」。
有這麼一個例子,同學A的自行車鎖在宿舍樓下,第二天發現被盜了,無奈只能去學校保安科調出監控攝像頭,但是那一天的監控視頻有24個小時的時長,為了找到自行車被偷的那個時刻,同學A還真打算把長達24小時的視頻一分一秒的看下去。
這時候聰明的同學可能會想到快進了,間隔若干分鐘快進一次。但是,我對A說,你不知道二分法么,從整個視頻的中間第12h開始,如果那個時刻自行車不在了,那麼被偷的時刻在[0,12]區間內,如果自行車還在,那麼被偷的時刻在[12-24]區間內,接著再進行二分直到找到為止。比如,被偷的時刻在第15h,那麼二分查找次數是12-18-15,只需要少數次查找,便可以立刻最大限度地縮小查找範圍。平均時間複雜度為logn。
同學A聽完後,這才恍然大悟。自從學了演算法之後,Leetcode見的多了,各種演算法接觸的多了,我的內心對於神奇演算法基本已經毫無波動。
講一個雖然幼稚,但是在小學時候,也曾經驚艷過我的演算法。題目:甲乙兩個人相向而行,相距L,出發同時甲的狗也出發在甲乙之間往返。已知甲,乙,狗速度分別為A,B,C且有 C&>A&>B。
求兩人相遇時狗跑過的距離。
在小時候我怎麼都做不出來,因為算出來 我列出了一個無數項求和的式子。在當時的我根本求不出來。
結果當我問了我爹後= =我爹直接就寫下了答案
===我是奧術(劃掉)奧數的分割線===
答案:
L/(A+B)*C。
演算法:
先求出甲乙相遇時間,再乘以狗的速度=。=
當時這個演算法震撼了我幼小的心靈,原來同樣問題換個演算法複雜度會下降這麼多!
===我是高數的分割線===
後來當接觸到收斂概念的時候。
第一反應就是:
媽的,小時候寫的那個無限級數是收斂的,其實能算出來!
有奧數童年的小伙們求贊~(≧▽≦)/~
難道不是RSA
給出一個數組a,求,n5W。log是要求取整的。
想了很久不會做啊。
後來沒有看題解看討論區說這個題代碼不長而且很妙一下子會做了。
先把所有的元素存到一個01字母樹里。記Q(i,j,s)表示i節點為根的子樹里的數和節點j為根的子樹里的數xor和小於等於s的方案數。
可以發現假如節點i深度很深而S很大的話直接退出就行了。
抱著試試看的想法敲了個暴力一樣的東西,或者就直接返回答案否則左右子樹下去做。
然後過了。
Ural 1318
雞兔同籠 抬腿法
26個腳8個頭,雞兔同籠
現在不排方程上軍訓教官:
1,2,3所有雞和兔子抬一條腿!
26-8=18條腿站著
1,2,3所有雞兔再抬一條腿!
18-8=10,雞全掉地上了,剩的腿都是兔子的,一共10/2 5隻,三隻雞5隻兔子
5×4+3×2 = 26腿,切題。
雞表示算個題我摔個屁股著地,兔子表示老子都站起來了
一道看起來很恐怖的題:如何對n個短整型數據進行排序,要求時間複雜度為O(n),空間複雜度為O(1)。
~~~~~~~答案分界線~~~~~~~~
一個短整型表示範圍為-32768~+32767,設定一個數組int count[655356]並全初始化為0,則所需空間與n無關,為O(1)。掃描一遍待排序列A[n],count[A[i]+32768]++ ;再掃描一遍count[],當count[i]&>0時,將count[i]個
(i-32768)輸入到A[n]中。總的時間複雜度為O(n)。
有1,5,2,1,4,2,1,3,5,4排序
數的範圍為0~5,設一個數組count[6]並初始化為0。掃描序列十個數,
1-count[1]=0+1=1;
5-count[5]=0+1=1;
2-count[2]=0+1=1;
1-count[1]=1+1=2;
4-count[4]=0+1=1;
2-count[2]=1+1=2;
1-count[1]=2+1=3;
3-count[3]=0+1=1;
5-count[5]=1+1=2;
4-count[4]=1+1=2;
結束後
___i 0 1 2 3 4 5
count[i] 0 3 2 1 2 2
count[]中分別保存了各個數出現的次數。
然後遍歷一遍count,輸出count[i]個i,即
1,1,1,2,2,3,4,4,5,5
然後也許有人要問了,那要有負數怎麼辦呢,這種情況下我們可以給所有整數加上一個偏移量,使之都變成正整數(上面那題我們都加了一個32768,使可能的最小數變為0),然後再使用上述辦法。
看了一個小演算法,被深深的震撼了,原來編程中被我們認為理所當然應該這樣做的東西,實際上還有很多優化的空間。
在一個文件中有很多行這樣的數據
134|32|35|2|43234|......|12"
"
25|5|286|16|58|......|614"
"
8731|8|98|22|4823|......|62"
"
......
......代表還有很多列,很多行,我的實驗里一共15列,600萬行
需求是求所有第二列數字的和,在這個例子里是32+5+8=45
1.最簡單的方法就是用C++中的getline讀一行數據,然後逐個字元判斷,如果是第二個』|『,就把第一個和第二個『|』中間的數字取出來就可以了,然後處理下一行。
這種方法時間是:0.8秒
2.第1種方法用getline,它幫我們讀取文件的時候,實際上是要逐個字元比較"
"的,才能取出來這一行,然後我們查找"|"的時候,又遍歷了一下這一行的其中一部分。實際上我們只要遍歷一次就可以了,於是可以用mmap函數把整個文件映射進內存,然後逐個字元判斷是"|"還是"
"來取得我們想要的結果。
這種方法時間是:0.65秒
如果我們不是每次只處理一個字元,而是一次處理多個字元呢?
查找第二列的時候還是和2中方法相同,關鍵是找"
"的時候
這種方法的時間是:0.45秒
//char *current = 文件初始位置, safeLimit是文件結尾(有些細節就先不處理了)
while (current&
//單獨拿出來一個字元看,1000,0000,實際上是8個這樣的
constexpr uint64_t highBits=0x8080808080808080ull;
//0111,1111
constexpr uint64_t lowBits=~highBits;
//0000,1010,這個是"
"(Ascii碼)
constexpr uint64_t pattern=0x0A0A0A0A0A0A0A0Aull;
//這塊有點神奇,你自己用一個例子試一下
uint64_t lowChars=(~block)highBits;
uint64_t found0A=~((((blocklowBits)^pattern)+lowBits)highBits);
uint64_t match=found0AlowChars;
//如果match是1000,0000,就說明遇到"
"了
//如果這8個位元組里沒有"
",直接進入下8個位元組
if (!match) {
current+=8;
continue;
}
//把match的位元組前後交換一下位置
match=__builtin_bswap64(match);
//找到了"
",current直接移動到下一行
current+=(__builtin_clzll(match)/8);
}
說一個在某競賽書第一單元看到的,交換 A 和 B 的最簡單的做法:
scanf("%d %d",a,b);
printf("%d %d",b,a);
媽的好機智!
這個確實不能叫演算法,不過真的很拍案叫絕啊哈哈哈
無限循環小數化分數的方法
推薦閱讀:
※大公司筆試面試有哪些經典演算法題目?
※ACM 中常用的演算法有哪些?
※如何在三角形(比如正三角形)里隨機取點?
※手機的九宮格圖案解鎖總共能繪出多少種圖案?
※什麼是動態規劃?動態規劃的意義是什麼?