Forrest

摘要： 面向對象： 需求變換是必然的，那么盡管無法預測會發生什么，但通常可以預測哪里會發生變化，面向對象的優點之一是可以封裝這些變化的區域，從而更容易的將代碼與變化產生的影響隔離開。代碼可以逐步演進，新代碼可以影響較少的加入。經典的設計模式是可以復用的面向對象設計方法。 書的配套code分析，回頭補上 1. 閱讀全文

摘要： 1. 動態規劃的適用場景 動態規劃常常適用于有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少于樸素解法。 2. 動態規劃的基本思想 動態規劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。通常許多子問題非常相似， 閱讀全文

摘要： 操作： 單點更新，區間求和 區間求和：如sum [3,10) 需要對19，5，12，26節點求和即可。 觀察可知，左端點為右子節點(奇數)時直接相加，右端點為左子節點(偶數)時直接相加，兩邊向中間移動并求其父節點。 Refer: Codeforces blog 樹狀數組解法 所有的奇數位置的數字和原 閱讀全文

摘要： 隨機性問題 水塘抽樣算法可保證每個樣本被抽到的概率相等 使用場景：從包含n個項目的集合S中選取k個樣本，其中n為一很大或未知的數量，尤其適用于不能把所有n個項目都存放到主內存的情況 Knuth洗牌算法 拿起第i張牌時，只從它前面的牌隨機選出j，或從它后面的牌隨機選出j交換即可 閱讀全文

摘要： 1、使用場景 IO多路復用是指內核一旦發現進程指定的一個或者多個IO條件準備讀取，它就通知該進程。IO多路復用適用如下場合： （1）當客戶處理多個描述字時（一般是交互式輸入和網絡套接字），必須使用I/O復用。 （2）當一個客戶同時處理多個套接口時，而這種情況是可能的，但很少出現。 （3）如果一個TC 閱讀全文

摘要： 表鎖: MySQL服務器端會使用讀寫鎖實現表鎖，忽略存儲引擎的鎖機制 行鎖: 在存儲引擎使用的鎖機制，并發效果更好 事務：一組原子性的SQL查詢，要么全部執行成功，要么全部執行失敗 ACID：原子性，一致性，隔離性，持久性 隔離級別：未提交讀(用的少)，提交讀(不可重復讀)，可重復讀(出現幻讀)，可 閱讀全文

摘要： 天際線問題，參考自: 百草園 天際線為當前線段的最高高度，所以用最大堆處理，當遍歷到線段右端點時需要刪除該線段的高度，priority_queue不提供刪除的操作，要用unordered_map來標記要刪除的元素。從heap中pop的時候先看有沒有被標記過，如果標記過，就一直pop直到空或都找到沒被 閱讀全文

摘要： 線程有join和detach兩種結束方式，join:主線程等待該線程結束，detach:主線程不等待該線程結束，讓其在后臺運行。join需要注意選擇適當的位置，在線程啟動后可能會拋出異常，在try/catch中也應該考慮join(一種方式是使用“資源獲取即初始化方式”(RAII，Resource A 閱讀全文

摘要： CAS( compare and swap) 原子操作，保證了如果需要更新的地址沒有被其他進程(線程)改動過，那么它可以安全的寫入。而這也是我們對于某個數據或者數據結構加鎖要保護的內容，保證讀寫的一致性，不出現dirty data。可在循環中不斷執行CAS，如果共享變量沒有改變，那么swap，在當前 閱讀全文

摘要： 給定一棵二叉樹，找到兩個節點的最近公共父節點(LCA)。最近公共祖先是兩個節點的公共的祖先節點且具有最大深度。假設給出的兩個節點都在樹中存在。 dfs遞歸寫法 查找兩個node的最近公共祖先，分三種情況： 深度優先遍歷二叉樹，一旦找到了兩個節點其中的一個，就將這個幾點返回給上一層，上一層節點通過判斷 閱讀全文