2019獨角獸企業重金招聘Python工程師標準>>>

博文視點答題
1. 二維數組中的查找
1.1. 問題描述
??? 在一個二維整數數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。
???? 例如下面的二維數組就是每行、每列都遞增排序。如果在這個數組中查找數字7，則返回true；如果查找數字5，由于數組不含有該數字，則返回false。
圖1-1
1.2. 問題分析
??? 由于數組M是一個m*n階矩陣。矩陣M的可能情況如下：

矩陣M的特點是：
(1) 圖中“ 紅色元素”是以第一個元素為頂點的最大正方形對角線上的元素，這條對角線上的紅色元素把矩陣的每行和每列都切割成了兩部分。
(2) 行和列都是遞增數列，“紅色元素”所在行的左側都比它小，右側都比它大；所在列的上側都比它小，下側都比它大。
(3)矩陣M的第一個元素最小，最后一個元素最大。

算法描述：
??? (1)將key分別與矩陣的最大元素和最小元素比較，如果key比矩陣的最大元素大或者比最小元素小，則無須繼續查找，不存在這樣的key。
??? (2)以“紅色元素”為分割點，對于行數大于等于列數的矩陣采用 列二分搜索(如圖1-2和圖1-4所示矩陣)。如果key等于“紅色元素”返回true；比“紅色元素”大在列下側搜索；比“紅色元素”小，則key只可能在圖中紅色箭頭圍成的區域中，把這樣的區域稱為“ 最小區域”。發現“最小區域”后，直接進入最小區域搜索。
??? (3)對于行數小于列數的矩陣采用 行二分搜索(如圖1-3所示矩陣)。

1.3. 算法實現
1.3.1. 行搜索算法
boolean rowSearch(int [][] matrix,int key) {int row = matrix.length-1,col = matrix[0].length-1;int low = 0 , high = 0,mid = 0,midVal = 0,fixMin=-1;for (int i = 0; i <= row ; i++) {if(fixMin != -1) {low = 0;high = fixMin;} else {if(key > matrix[i][i]) {low = i+1;high = col; } else if(key < matrix[i][i]) {low = 0;high = i-1;fixMin = high;//發現最小區域} else {return true;} }while(low <= high) {mid = (low + high)>>1;midVal = matrix[i][mid];if(key < midVal) {high = mid -1;} else if (key > midVal) {low = mid + 1;} else {return true;//發現key}} }return false;//沒有發現key }
1.3.2. 列搜索算法
boolean colSearch(int [][] matrix,int key) {int row = matrix.length-1,col = matrix[0].length-1;int low = 0 , high = 0,mid = 0,midVal = 0,fixMin=-1;for (int i = 0; i <= col ; i++) {if(fixMin != -1) {low = 0;high = fixMin;} else {if(key > matrix[i][i]) {low = i+1;high = row; } else if(key < matrix[i][i]) {low = 0;high = i-1;fixMin = high;//發現最小區域} else {return true;} }while(low <= high) {mid = (low + high)>>1;midVal = matrix[mid][i];if(key < midVal) {high = mid -1;} else if (key > midVal) {low = mid + 1;} else {return true;//發現key}} }return false;//沒有發現key }
1.3.3. 搜索主算法
boolean search(int [][] matrix,int key) {//比最小值小if(key<matrix[0][0]) {return false ;}int row = matrix.length-1,col = matrix[0].length-1;//比最大值大if(key > matrix[row][col]) {return false ;}if( row < col) {//行數小于列數采用行搜索return rowSearch(matrix, key);} else {//行數大于等于列數采用列搜索return colSearch(matrix, key);} }
2. 青蛙跳臺階問題
2.1. 問題描述
??? (1) 一只青蛙一次可以跳上 1 級臺階，也可以跳上2 級。求該青蛙跳上一個n 級的臺階總共有多少種跳法？(2)一只青蛙一次可以跳上1級臺階，也可以跳上2 級……它也可以跳上n 級，此時該青蛙跳上一個n級的臺階總共有多少種跳法？

2.2. 問題分析
??? 對于n步臺階，記青蛙的跳法為F(n),n=S1+S2(其中Si表示一次連跳i步的次數.
當n=1時,(1,0) →F(n) = 1;
當n=2時,(0,1),(2,0) →F(n) = 2;
當n=3時,(1,1)[2], (3,0) →F(n) = 3;
???? 青蛙可以先跳一步，再跳一次兩連步；或者先跳一次兩連步，再跳一次一步，故共計3次。
當n=4時,(0,2),(2,1)[3], (4,0) →F(n) = 5;
由上面的推到可知：
F(1) = 1; F(2) = 2;
F(3) = F(1) + F(2) = 1+2 = 3;
F(4) = F(2) + F(3) = 2+3 = 5;
.......
假設青蛙最后一次跳1步，則青蛙的跳法與只有n-1步臺階時跳法數一致，即有F(n-1) 種跳法；
假設最后一次跳2步，則青蛙的跳法與只有n-2步臺階時跳法數一致，即有
F(n-2) 種跳法。這里實際存在 對偶關系：m+(n-m) = n ,則F(m)= F(n-m)。所以，F(n)= F(n-1) + F(n-2)。
則：

由此可見青蛙的跳法是一個 斐波那契數列。
??? 如果青蛙有m種跳法，即青蛙可以一次連跳1,2,3,4,5,...m階臺階。由上面的推理過程得到:F(n)= F(n-1) + F(n-2)+...+ F(n-m).
如果 n-m < 0, F(n-m) = 0,青蛙一次能夠跳躍的步數m大于臺階數n時，這樣的跳法實際不存在。所以當n<m時，讓m等于n。
n-m = 0, F(n-m) = 1, 即 F(0) = 1，表示青蛙一次能夠跳n步臺階。
n-m = 1, F(n-m) = 1, 即 F(1) = 1。表示青蛙先跳一次再連跳m次。
對n >= 2時，對F(n)進行簡化如下：
F(n-1)= F(n-2) + F(n-3)+...+ F(n-1-m).
F(n)- F(n-1) =? F(n-1)- F(n-1-m).
則F(n)=2 F(n-1) -? F(n-1-m).
當n <= m時，n – 1 – m < 0,F(n-1-m) = 0,則F(n)=2 F(n-1)。
F(1) = 1; F(2) = 2; F(3) = 4;…;F(n)=2^(n-1)。則：

2.3. 算法實現
2.3.1.1. 問題一的遞歸算法
int jump2(int n) {if(n == 1 || n == 2) {return n;}return jump2(n-1)+jump2(n-2); }
2.3.1.2. 問題一的非遞歸算法
int jump2(int n) {if(n == 1 || n == 2) {return n;}int n1 = 1,n2 = 2;int r = 0;for (int i = 3; i <= n; i++) {r = n1 + n2 ;n1 = n2;n2 = r ;}return r; }
2.3.2.1. 問題二的遞歸算法
int jumpm0(int n,int m) {if(n == 0) {return 1;}if(n <= m) {return 1<<(n-1);}return 2*jumpm0(n-1,m)-jumpm0(n-1-m,m); }
2.3.3.2. 問題二的非遞歸算法
int jumpm(int n,int m) {if(n <= m) {return 1<<(n-1);}int [] f = new int [1 + m];f[0] = 1;//求f[1]...f[m]for (int i = 0; i < m; ) {f[++i] = 1<<i;}//求fnint r = f[m];for (int i = m+1; i < n;i++) {r = 2 * f[m] - f[0];f = poll(f);f[m] = r;}r = 2 * f[m] - f[0];return r; }int [] poll( int [] m) {int len = m.length-1;for (int i = 0; i < len ;) {m[i] = m[++i];}return m; }

圖2-1
???? 非遞歸算法通過增加輔助存儲空間來存儲F(n-1-m),.., F(n-2), F(n-1)。首先通過公式F(n)= F(n-1) + F(n-2)+...+ F(n-m)。求出F(0),…, F(1), F(m)。然后通過迭代求F(n)。迭代過程中通過公式F(n)=2 F(n-1) -? F(n-1-m)，求F(n)。每次迭代都需要像圖2-1那樣移動元素。

2.3.3.3. 問題二的非遞歸算法的改進
??? 問題二的非遞歸算法中，求F(n)的迭代過程中用到了poll函數，這樣每迭代一次數組f都需要整體向做移動一次，效率比較低。如果把數組f中的元素存到一個隊列中，每次迭代實際上只與第一個元素和最后一個元素有關。迭代過程中移除首元素之后取出其值和最后一個元素的值計算出F(i)。再將F(i)插入到隊尾。這樣減少了數組的移動，提高了效率。但需要消耗一定的空間創建對象實例。以空間換取效率。改進后的 存儲模型如下：

圖2-2
??? 改進后的java代碼如下：
int jumpmm(int n,int m) {if(n <= m) {return 1<<(n-1);}//將f[0]...f[m]存放到隊列中Deque<Integer> fq = new LinkedList<Integer>();fq.add(Integer.valueOf(1));for (int i = 0; i < m; i++) {fq.add(Integer.valueOf(1<<i));}//求fnint r = 0;for (int i = m+1; i < n;i++) {r = 2 * fq.peekLast() - fq.pollFirst();fq.add(Integer.valueOf(r));}r = 2 * fq.peekLast() - fq.pollFirst();return r; }
2.3.3.4. 問題二的運行結果

圖2-3

3. 總結
??? 通過本文可以了解 二分查找算法的實現； 遞歸算法向 迭代轉化的方法；問題的 分析和推演方法；同時還可以了解java中隊列的使用方法。在實際問題中 針對問題本身的特征對問題進行分析是一條很重要的法則，仔細閱讀本文就可以看到本文的分析與算法都是基于問題本身的特征的。

4. 附件
??? 附件中有本文的word，pdf詳細文檔和java代碼。
??? 附件《ch02.pdf》有第一題的一種巧妙解法。供大家學習參考。在pdf的第19頁。

轉載于:https://my.oschina.net/91jason/blog/300129

總結

以上是生活随笔為你收集整理的博文视点答题1的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。