微信公衆号： bigsai
01二維數組的查找
題目描述
在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。
思路：
標明一個次元(行或列)先找到需要查找的元素所在的
行
(列)，再從該
行
(列)找到該元素的該元素具體的列(行)位置。複雜度O(n)。
優化：因為數列是遞增有序的，可以進行二分查找進行優化，但是本題可以不進行二分也可以過。因為大家有興趣可以去查一查程式設計語言數組可以開多大。然後單個查找在這個範圍内即使不優化也不會逾時。有興趣的可以自己寫一寫二分！複雜度O(logn)
代碼：
public class Solution {
public boolean Find(int target, int [][] array) {
if(array.length==0||array[0].length==0)return false;
for(int i=array.length-1;i>=0;i--)
{
if(array[i][0]>target) {continue;}
for(int j=0;j<array[0].length;j++)
{
if(array[i][j]==target)
{return true;}
}
}
return false;
}
}
02替換空格
請實作一個函數，将一個字元串中的每個空格替換成“%20”。例如，當字元串為We Are Happy.則經過替換之後的字元串為We%20Are%20Happy。
水題，字元串周遊重構即可。遇到為
的字元直接在新的字元添加一個
%20
即可。當然，在java中直接使用replaceAll即可。複雜度O(n);
ps: replaceall效率較低，建議使用StringBuider之類完成
參考讨論區
：
在讨論區看到了一些不一樣的聲音，大緻就是 有讨論是在原字元串上進行移動還是建立字元串的問題。當然建立字元串會更簡單些，但是如果遇到要求在原字元串基礎上進行移動的，因為String的底層實作是數組，那就要首先周遊一次知道有多少空格，然後擴充空間。至于周遊完空格的移動方式：從後往前移動的方式更好，因為最終移動的位置是相同的，但是從前往後每次遇到空格都會拖家帶口後面一串都要跟着移動。(好比國旗下講話排隊往後挫，要挫很多次整體慢慢騰騰移動)，而從後往前插就相當于很明确一個個明确移動到哪。
雖然兩者最終已經總距離一樣的，但是從前往後每個單詞要經過(1-n)次才能移動到最後，而從後往前每個單詞隻1次就移動到目标位置！
public class Solution {
public static String replaceSpace(StringBuffer str) {
String team=str.toString();
return team.replaceAll(" ", "%20");
}
public static String replaceSpace(StringBuffer str) {//方法二
StringBuffer str2 = new StringBuffer();
char demo = ' ';
for (int i = 0; i < str.length(); i++) {
demo = str.charAt(i);
if (demo == ' ') {
str2.append("%20");
} else {
str2.append(demo);
}
}
return str2.toString();
}
}
03從尾到頭列印連結清單
輸入一個連結清單，按連結清單從尾到頭的順序傳回一個ArrayList。
題目給我們一個連結清單讓我們傳回一個序列數字。而這個序列要求我們将連結清單從後向前的順序傳回。當然，這樣的話處理方法就比較多了。
比如
先從前往後存到一個數組中，然後數組再從後往前往List中塞。
當然
Arraylist本身也是一個線性表(順序表)，可以進行頭插。将連結清單每次向後周遊的數插在首位，最後傳回即可。
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer>list=new ArrayList<Integer>();
while (listNode!=null) {
list.add(0, listNode.val);
listNode=listNode.next;
}
return list;
}
}
參考讨論區
這題參考了讨論區，發現了一些其他比較優秀的解法，
比如
可以用遞歸函數進行插入，當next為null的時候停止，當然
還有
就是利用棧的結構儲存然後抛出啦。這些思想都可實作！
04重建二叉樹★
輸入某二叉樹的前序周遊和中序周遊的結果，請重建出該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建二叉樹并傳回。
說實話這題還是有難度的，以前手動模拟的時候也沒掌握方法隻是瞎畫。以前再力扣也曾經遇到這題當時不會停滞下來。不過這次憑借思考還是克服了。
我們都知道一個中序序列帶着一個前序或者後序序列都能确定一棵完整的二叉樹。首先分析這種問題。二叉樹的問題大部分有可重複性，經常會使用遞歸。是以大部分人應該能夠想到使用遞歸，但是可能不清楚該怎麼遞歸。其實遞歸的使用不需要你考慮全篇，需要你謹慎完整的考慮其中一個過程。現在我們看看前序周遊序列
{1,2,4,7,3,5,6,8}
和中序周遊序列
{4,7,2,1,5,3,8,6}
，的構造過程！
- 對于前序，我們知道從根還是，是以可以确定第一個是根。然而中序是
左中右
- 然而很重要的一點是：在中序左側右側的在前序序列中的：根
左右
- 是以，如果用代碼實作的話，比較麻煩的就是要考率數組的區間問題，要記錄進行複原的兩數組的左右區間。具體了解還是要靠大家。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode node=new TreeNode(in[0]);//根節點
int preleft=0,preright=pre.length-1;
int inleft=0,inright=pre.length-1;
return creat(pre, in, preleft, preright,inleft,inright);
}
private TreeNode creat(int[] pre, int[] in, int preleft, int preright, int inleft, int inright) {
if(preleft>preright||inleft>inright)return null;
TreeNode node=new TreeNode(pre[preleft]);
int mid=0;
for(int i=inleft;i<=inright;i++)
{
if(pre[preleft]==in[i])
{
mid=i;
}
}
node.left=creat(pre, in, preleft+1, preleft+(mid-inleft), inleft, mid-1);
node.right=creat(pre, in, preleft+(mid-inleft)+1, preright, mid+1, inright);
return node;
}
}
05 用兩個棧實作隊列
用兩個棧來實作一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為int類型
首先要了解隊列，隊列是一種先進先出(排隊)的結構，而棧是一種後進先出的結構。如果基本概念不清可以看我以前寫的哈。要求完成push和pop兩種操作。push就是加入隊尾(tail)類似enqueue，而pop是傳回并抛出隊頭(front)類似dequeue。我們假設stack1是用作傳回，而stack2用作中轉。可以先看看下面的圖。假設
7、3、5、6
在隊列中，待加入8（push
8
）.stack1用作傳回，那麼棧頂肯定是隊頭(才能傳回)，在不發生變化的狀态甚至是pop傳回的狀态是這樣的：
- 對于push加入的操作，兩個棧，處理思路就是先用棧2倒置棧1，然後加入要加入的元素到棧2，再用棧1倒置棧2。
實作代碼為：
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
stack2.push(node);
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
stack2.clear();
}
public int pop() {
return stack1.pop();
}
}
06旋轉數組的最小數字
把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。
輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。
例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。
NOTE：給出的所有元素都大于0，若數組大小為0，請傳回0。
就是要求我們在這麼一組序列中找到最小的一個數字，非遞減的旋轉，也就是這麼一串有兩段非遞減的連續串串。找到第二個非遞減的串串頭就是結果。
然而，我們隻需第一次查找到最小即可結束。不會逾時還是因為數組大小有限制。無法提供更大量輸入資料。複雜度為O(n)；
public int minNumberInRotateArray(int [] array) {
if(array.length==0)return 0;
int min=array[0];
for(int i=0;i<array.length;i++)
{
if(array[i]<min)
{
min=array[i];
break;
}
}
return min;
}
參考題解
之前提過二分，但是這題很多讨論區的方案并非完善，漏了非遞減比如101111這種情況。而二分也隻是壓縮搜尋空間，如歸一個非遞減串被分成左側非遞減和右側非遞減，右側的最大要小于等于左側最小的。就跟就行分類讨論，下面分享一個講的不錯的題解(原文連結)：
07 斐波那契數列
大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0）。
n<=39
思路：斐波那契的公式為：
F(0)=0;F(1)=1;
F(n)=F(n-1)+F(n-2); （n>=2）
你可以使用遞歸，但是遞歸效率極低！因為遞歸的一項會産生新的兩項遞歸函數。它的複雜度是O(2^n^)指數級别的。具體原因可以參考以前的一篇文章的動态圖遞歸詳解。這裡不做累述。因為遞歸浪費太多資源，進行很多沒必要的運算。是以我們采用數組從前往後計算。兩種方法都附上代碼。
代碼為(推薦法2)：
public int Fibonacci(int n) {
if (n == 1 || n == 0) {
return n;
} else {
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
/*
* 法二，打表法
*/
public int Fibonacci2(int n) {
int Fibo[]=new int [40];
Fibo[0]=0;
Fibo[1]=1;
for(int i=2;i<=n;i++)
{
Fibo[i]=Fibo[i-1]+Fibo[i-2];
}
return Fibo[n];
}
參考讨論區：
其他的其實沒有多少差別的，主要是動态規劃從前往後計算不需要整個數組。隻需要兩個變量就夠了，這樣空間能夠節省一些。
08 跳台階
一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法（先後次序不同算不同的結果）。
可以遞歸或者dp吧，因為目前台階F(n)可能是1步跳來的，也可能是2步跳來的。是以F(n)=F(n-1)+F(n-2).(初始情況單獨考慮)。這題遞歸和正向dp時間複雜度差不多，差別不大。
代碼為：
public int JumpFloor(int target) {
int dp[]=new int[target+1];
dp[0]=1;
dp[1]=1;
for(int i=2;i<=target;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[target];
}
參考評論區：
本題評論區的有些遞歸方案感覺感覺不太好，隻有優化和斐波那契差不多，可以用兩個數進行計算就可以了，節省部分空間。
09 變态跳台階★
一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。
這種複雜的就别想着用遞歸了，從正面考慮吧。對于n位置的跳法，可能從n-1跳，可能從n-2跳-------可能從1跳，也可能直接從開始跳。是以
F(n）
=
1
(直接跳)+
sum(F(k))
(k屬于1到n-1)。我們肯定需要一個數組儲存F[n]；但是我們不能每次都要相加。是以用一個sum[]數組儲存前n個跳法的合即可！
public class Solution {
public int JumpFloorII(int target) {
int a[]=new int[target+1];//存儲結果
int sum[]=new int[target+1];//儲存和
a[1]=1;
sum[1]=1;
for(int i=2;i<=target;i++)
{
a[i]=1+sum[i-1];
sum[i]=a[i]+sum[i-1];
}
return a[target];
}
}
參考評論區：
這題，個人分析方法是基于正常算法的，看了讨論區有個非常非常牛的用數學推理方法，類似等差等比數列的推理，做題的時候沒想到直接這麼推哈哈，大家可以學習一波！
10 矩陣覆寫
我們可以用2 * 1 的小矩形橫着或者豎着去覆寫更大的矩形。請問用n個2 * 1的小矩形無重疊地覆寫一個2*n的大矩形，總共有多少種方法？
遞歸或dp。每個矩形的大小都是2*1；同樣第F(n)=F(n-1)+F(n-2).（第n-1個橫鋪一塊，第n-2豎直兩塊）考慮下初始即可
/*
* dp
*/
public int RectCover(int target) {
if(target==0)return 0;
int dp[]=new int[target+1];
dp[0]=1;
dp[1]=1;
for(int i=2;i<=target;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[target];
}
/*
* 遞歸
*/
// public int RectCover(int target) {
// if(target==0)return 0;
// if(target==1)return 1;
// if(target==2)return 2;
// else {
// return RectCover(target-1)+RectCover(target-2);
// }
// }
歡迎關注、交流，微信公衆号：
bigsai
！