Algorithm
350. 兩個數(shù)組的交集 II
給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集。
示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
說明：
輸出結(jié)果中每個元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個數(shù)組中出現(xiàn)的次數(shù)一致。
我們可以不考慮輸出結(jié)果的順序。
進階:
如果給定的數(shù)組已經(jīng)排好序呢？你將如何優(yōu)化你的算法？
如果 nums1 的大小比 nums2 小很多，哪種方法更優(yōu)？
如果 nums2 的元素存儲在磁盤上，磁盤內(nèi)存是有限的，并且你不能一次加載所有的元素到內(nèi)存中，你該怎么辦？
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int num: nums1) {
if (!map.containsKey(num)) {
map.put(num, 1);
} else {
map.put(num, map.get(num) + 1);
}
}
ArrayList<Integer> list = new ArrayList<>();
for (int num: nums2) {
if (map.containsKey(num)) {
list.add(num);
map.put(num, map.get(num) - 1);
if (map.get(num) == 0) {
map.remove(num);
}
}
}
int[] ret = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
ret[i] = list.get(i);
}
return ret;
}
}
Review
Tip
HTTPS可以有效的防止信息竊聽，身份偽裝等安全問題。
HTTP的缺點
- 通信使用明文，內(nèi)容可能被竊聽
- 不驗證通信方的身份，因此有可能遭遇偽裝
- 無法證明報文的完整性，所以有可能已遭篡改
通信使用明文可能會被竊聽
- 加密處理防止被竊聽
通信的加密
HTTP通過和SSL或TLS的組合使用，加密HTTP的通信內(nèi)容。即使用SSL建立安全通信線路之后，就可以在這條線路上進行HTTP通信了。
內(nèi)容的加密
將報文主體進行加密處理。
不驗證通信的身份就可能遭遇偽裝
- 任何人都可以發(fā)送請求
通信時，不存在確認通信方的處理步驟，任何人都可以發(fā)送請求。另外，服務(wù)器只要接收到請求，不管對方是誰都會返回到實際提出請求的客戶端（僅限于發(fā)送端的IP地址和端口號沒有被Web服務(wù)器設(shè)定限制訪問的前提下）。
由于不確認通信方，會存在如下各種隱患：
目標(biāo)服務(wù)器有可能是已偽裝的Web服務(wù)器
客戶端有可能是已偽裝的Web服務(wù)器
無法確定正在通信的對方是否具備訪問權(quán)限。
即使無意義的請求也會照單全收。無法阻止海量請求下的DoS攻擊
查明對方的證書
SSL還使用了一種被稱為證書的手段，可用于確定對方。
無法證明報文的完整性，可能已遭篡改
- 接收到的內(nèi)容可能有誤
HTTP ＋ 加密 ＋ 認證 ＋ 完整性保護 ＝ HTTPS
通常HTTP直接和TCP進行通信。當(dāng)使用SSL時，則演變成先和SSL通信，再由SSL和TCP通信。
相互交換密鑰的公開密鑰加密技術(shù)
SSL采用一種叫做公開密鑰加密的加密處理方式。
- 共享密鑰的困境
加密和解密用同一個密鑰的方式稱為共享密鑰加密，也被叫做對稱密鑰加密。
但是，以共享密鑰的方式加密時必須將密鑰也發(fā)送給對方，因此，密鑰有可能被監(jiān)聽。
- 使用兩把密鑰的公開密鑰加密
公開密鑰使用一種非對稱的密鑰。一把叫私有密鑰，另一把叫公開密鑰。
發(fā)送密文的一方使用對方的公開密鑰進行加密處理，對方收到被加密的信息后，再使用自己的私有密鑰進行解密。
- HTTPS采用混合加密機制
HTTPS采用共享密鑰加密和公開密鑰加密兩者并用的混合加密機制。
因為公開密鑰加密處理速度比共享密鑰加密要慢很多。因此使用公開密鑰的方式將共享密鑰傳遞過去（此時的共享密鑰只有發(fā)送端和接受端知道），然后后面的通信就使用共享密鑰。
具體過程大概是：
發(fā)送端：你的公開密鑰是？
接收端：我的公開密鑰是??。
發(fā)送端：將共享密鑰使用得到的公開密鑰進行加密后發(fā)送。
接收端：將收到的內(nèi)容使用私鑰進行解密。然后使用解密后得到密鑰保存起來，以后的通信便使用該密鑰進行加密。
證明公開密鑰正確性的證書
公開密鑰在傳輸過程中可能會被調(diào)包。為解決該問題，使用由數(shù)字證書認證機構(gòu)和其他相關(guān)機關(guān)頒發(fā)的公開密鑰證書。
服務(wù)器會將證書和公鑰一起發(fā)送給客戶端。然后客戶端拿到服務(wù)器的公鑰證書后，使用認證機構(gòu)的公開密鑰，向數(shù)字證書認證機構(gòu)驗證公鑰證書上的數(shù)字簽名，以確認服務(wù)器公開密鑰的真實性。
此時，將認證機關(guān)的公開密鑰安全的轉(zhuǎn)交給客戶端是非常重要的事。大多數(shù)瀏覽器開發(fā)商發(fā)布版本時，會事先在內(nèi)部植入常用認證機關(guān)的公開密鑰。
關(guān)于信息過濾
- 大腦中只保存真正需要記憶的內(nèi)容
- 閱讀圖書時可以先瀏覽一遍，用鋼筆在自己感興趣的內(nèi)容頁上打個標(biāo)記，然后第二遍閱讀時可以用不同顏色的熒光筆標(biāo)記（如，暫時沒看懂的部分，新理論等等）然后對做了標(biāo)記的章節(jié)進行第三次閱讀
- 大塊內(nèi)容化整為零
- 養(yǎng)成把信息一分為二的習(xí)慣?？梢灾弥焕淼男畔⒑徒窈罂赡苡龅降男畔?，然后再將第二類信息分為可以借助外在設(shè)備記住的信息和需要記住的信息。最后為了記住某個信息，可以圍繞該信息編個故事或設(shè)定一個目標(biāo)。
- 每周拿出些時間回顧關(guān)鍵信息，每周都抽出一定 的時間，回顧溫習(xí)本周搜集的信息——會議記錄、電子郵件、收藏網(wǎng)頁，如此等等。需要關(guān) 注某個主題的時候，再次回顧溫習(xí)相關(guān)信息，有助于記住這些信息。需要用到信息的時候能 夠輕松記起，就會更加有條不紊，也更容易取得成功。
- 為了實施信息過濾，在閱讀之前或者閱讀過程當(dāng)中，盡量明確圍繞這些信息需要實現(xiàn)的 目標(biāo)。不管是一本書、一篇文章、一個網(wǎng)帖，還是一堆郵件，都應(yīng)對相關(guān)材料進行通讀。根 據(jù)此前設(shè)定的目標(biāo)，立足對信息所做的不同處理，將其分門別類:可以忽略的內(nèi)容，記下來 以備今后復(fù)習(xí)的內(nèi)容，以及需要當(dāng)場記住的內(nèi)容。也可以根據(jù)有關(guān)信息的背景，把需要記住 的信息劃分成更小的類別。
