演算法小問題

01-30

收集一些我接觸到的比較有意思的小問題。對演算法的要求不高。但有難度。

- 給定一個大小為n+1的數組，每個元素都是[1,n]的整數，且只有一個數出現兩次或以上。要求O(N)時間O(1)空間找出不允許修改。

-求出二維矩陣中的任意一個極小點（不大於其他四個方向）。要求O(N)時間。

-求出一個序列任意極小點（不大於兩邊）。要求O(logN)時間。

-通信複雜度問題：同一張N個點的圖 Alice有圖的團 Bob有圖的獨立集兩人通過最少多少bits的通信能確定存在有交集（當然必定只有一個點）

hint：有一個確定性的O(log^2N) 想法是減少圖的規模

- 給兩個序列A,B |A|=N且元素為1-M，|B|=M且元素為1-N。各找一段連續子序列使和相同的。

hint:利用鴿巢原理

- 給N個數求最大最小數。要求1.5N次比較

- 給N個數求第K大的數。要求O(N)時間。

- 給一個長度為N的序列，找一個最大的M，使得存在連續子序列恰好是1-M的排列。

- 給N個數，保證存在唯一一個出現奇數次的數，找出來。(加強版，兩個奇數次的數）

- Call/cc問題：構造一個函數(A->B->A)->A

- 在n＊n棋盤每個點權值gcd（i，j）求（x，y）到（1，1）的最短路 q<=10^5 n<=10^9

- 給二元組集合|{(Ai,Bi)}|=n，取出一個最大的子集的任意排列（m為子集大小），使得滿足 $B(i) geq sum_{j=1}^{i-1} A(j) (1 leq i leq m)$

- 實現微信公平分紅包

- 在連連看遊戲中找出一對可行匹配

- 求一大堆數中的Top100

- 判斷一段字元串能否拆分成三個迴文子串

- 用位運算實現a+b problem

- 實現一個銀行報單buffer 假設數據按時間發送要滿足任意連續的1s內的單子數量不超過n 否則捨棄