- Algorithm 74. 搜索二維矩陣
- Review Lambdas不是函數(shù)式編程
- Tip TCP的窗口滑動(dòng)
- Share ConcurrentHashMap1.7實(shí)現(xiàn)
Algorithm 74. 搜索二維矩陣
編寫一個(gè)高效的算法來(lái)判斷 m x n 矩陣中挖滤，是否存在一個(gè)目標(biāo)值糙置。該矩陣具有如下特性：
- 每行中的整數(shù)從左到右按升序排列踱蛀。
- 每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)阱飘。
示例 1:
輸入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
輸出: true
示例 2:
輸入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
輸出: false
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0].length == 0){
return false;
}
//右上角元素開始
int i = 0;
int j = matrix[0].length - 1;
while(i < matrix.length && j >= 0){
if(target == matrix[i][j]){
return true;
}
if(target > matrix[i][j]){
i++;
}else{
j--;
}
}
return false;
}
算法思路：
二維數(shù)組是有序的，從右上角來(lái)看，向左數(shù)字遞減，向下數(shù)字遞增轴踱。
因此從右上角開始查找，
當(dāng)要查找數(shù)字比右上角數(shù)字大時(shí)谚赎，下移淫僻；
當(dāng)要查找數(shù)字比右上角數(shù)字小時(shí)，左移壶唤；
如果出了邊界嘁傀，則說(shuō)明二維數(shù)組中不存在該整數(shù)。
Review Lambdas不是函數(shù)式編程
Lambda表達(dá)式是Java SE 8中包含的一個(gè)新的重要特性。它們提供了一種使用表達(dá)式表示一個(gè)方法接口的簡(jiǎn)潔方法辅斟。Lambda表達(dá)式還改進(jìn)了Collection庫(kù)姐军，使其更容易迭代儒将，過(guò)濾和提取數(shù)據(jù)Collection员舵。此外工扎，新的并發(fā)功能可提高多核環(huán)境的性能泪酱。
Java的土地中沒有人正在進(jìn)行函數(shù)式編程钓觉，這是一件好事茴肥。
Java中的Lambda表達(dá)式只是一種不那么冗長(zhǎng)的創(chuàng)建（略微受限制）對(duì)象的方式，因此在沒有很好地理解核心功能概念的情況下采用Lambda的最可能的結(jié)果是粗糙荡灾，扭曲瓤狐，難以理解，混淆的命令式面向?qū)ο蟮拇a與一個(gè)很簡(jiǎn)潔的語(yǔ)法批幌。是的础锐，我們可以通過(guò)創(chuàng)建單獨(dú)的類和lambda來(lái)以更冗長(zhǎng)的方式編寫完全相同的狡猾代碼。
相反荧缘，即使用Java編寫實(shí)際的功能代碼皆警，我們也可以用簡(jiǎn)潔的lambdas編寫帶有詳細(xì)的類定義和對(duì)象的相同代碼。
懶惰和表現(xiàn)
在所有性能最佳的代碼未執(zhí)行代碼之后截粗，懶惰可以提高性能信姓。
Tip TCP的窗口滑動(dòng)
- 窗口左邊沿向右邊沿靠近為窗口合攏。這種現(xiàn)象發(fā)生在數(shù)據(jù)被發(fā)送和確認(rèn)時(shí)绸罗。
- 當(dāng)窗口右邊沿向右移動(dòng)時(shí)將允許發(fā)送更多的數(shù)據(jù)意推，我們稱之為窗口張開。這種現(xiàn)象發(fā)
生在另一端的接收進(jìn)程讀取已經(jīng)確認(rèn)的數(shù)據(jù)并釋放了 T C P的接收緩存時(shí)珊蟀。 - 當(dāng)右邊沿向左移動(dòng)時(shí)菊值，我們稱之為窗口收縮。 Host Requirements RFC強(qiáng)烈建議不要使
Share ConcurrentHashMap1.7實(shí)現(xiàn)
為什么要使用ConcurrentHashMap系洛？
- 多線程環(huán)境下俊性，HashMap會(huì)處于不安全狀態(tài)。例如put操作可能會(huì)引起程序死循環(huán)描扯，Cpu占有率達(dá)百分百定页，原因是多線程會(huì)導(dǎo)致HashMap的Entry鏈表形成環(huán)形數(shù)據(jù)結(jié)構(gòu)，如此一來(lái)绽诚，他的next結(jié)點(diǎn)將永不為空典徊，就會(huì)產(chǎn)生死循環(huán)獲取Entry。既然不能使用HashMap恩够，在多線程環(huán)境下就給并發(fā)容器有了登場(chǎng)機(jī)會(huì)卒落。具體請(qǐng)參考談?wù)凥ashMap線程不安全的體現(xiàn) .
- Hashtable效率低下。Hashtable相信很多人都知道蜂桶，相比HashMap就增加了線程安全機(jī)制儡毕，在過(guò)去Hashtable就會(huì)被使用，但由于它的實(shí)現(xiàn)是利用synchronized來(lái)保證線程安全的，在線程競(jìng)爭(zhēng)激烈的情況下腰湾，效率就非常低下了雷恃。原因在于當(dāng)有線程訪問Hashtable的同步方法時(shí)，其他線程也來(lái)訪問就會(huì)進(jìn)行阻塞或者輪詢狀態(tài)费坊。因此效率低下倒槐，如今開發(fā)中已經(jīng)鮮有人使用Hashtable了。
- ConcurrentHashMap采用鎖分段技術(shù)可有效提高并發(fā)訪問率附井。
參考文獻(xiàn)：
《TCP-IP詳解》
Lambdas不是函數(shù)式編程
ConcurrentHashMap1.7實(shí)現(xiàn)
