劍指offer(01-15題)優化題解
- 2020 年 2 月 19 日
- 筆記
聲明：如果有效率太低的或者錯誤還請指正！ 如果有數據結構問題，可以參考筆者寫的系列數據結構文章也可以加我交流哈！
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（push8）.
- 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); // } // }
11 二進位種1的個數★
題目描述
輸入一個整數，輸出該數二進位表示中1的個數。其中負數用補碼錶示。。
思路： 這題感覺應該還會有很多思路和解法，單身筆者自身只寫了兩個方法吧，後面討論看題解會進行補充。
法一：直接轉成二進位字元串。然後進行比較裡面的1的個數。
法二：大家知道每個類型的數據它的背後實際都是二進位操作。大家知道int的數據類型的範圍是(-2^31^,2^31^-1)。並且int有32位。但是並非32位全部用來表示數據。真正用來表示數據大小的也是31位。最高位用來表示正負。
首先大家要知道：
1<<0=1 =00000000000000000000000000000001 1<<1=2 =00000000000000000000000000000010 1<<2=4 =00000000000000000000000000000100 1<<3=8 =00000000000000000000000000001000 . . . . . . 1<<30=2^30^ =01000000000000000000000000000000 1<<31=-2^31^ =10000000000000000000000000000000
其次還要知道位運算&與。兩個十進位與運算.每一位同1為1。所以我們用2的正數次冪與知道的數分別進行與。如果結果不為0，那麼就說明這位為1.(前面31個都是大於0的最後一個與結果是負數但是如果該位為1那麼結果肯定不為0)
程式碼：
public int NumberOf1(int n) { int va=0; String num=Integer.toBinaryString(n); for(int i=0;i<num.length();i++) { if(num.charAt(i)=='1') { va++; } } return va; } public int NumberOf2(int n) { int va=0; for(int i=0;i<32;i++) { if((n&(1<<i))!=0) { va++; } } return va; } public int NumberOf3(int n) {//上面的差不多，可能慢一點 int va=0; int num=1; for(int i=0;i<32;i++) { if((n&num)!=0) { va++; } num*=2; } return va; }
評論區參考： 看了評論區，發現前面的方法很多人採用，但是也有些有差別的：我那個是用這個數分別和2,4,8,16等進行位運算計算，還有事用位運算右移每次和1進行位運算比較。其實本質一樣的，就是選的靜止參照物不同而已。
而還有一種非常棒的方法，確實沒想到，就是運用n&(n-1)。n如果不為0，那麼n-1就是二進位第一個為1的變為0，後面全為1.這樣的n&(n-1)一次運算就相當於把最後一個1變成0.這樣一直到運算的數為0停止計算次數就好了。
實現程式碼為：
public class Solution { public int NumberOf1(int n) { int count=0; while (n!=0) { n=n&(n-1); count++; } return count; } }
12 數值的正數次方
題目描述
給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。 保證base和exponent不同時為0
思路： 法1：直接利用數學包求。或者直接進行exponent次相乘。複雜度為O(n);
法2：快速冪求法。首先快速冪思想可以參考以前寫的一個記錄快速冪模板。但是這題有點不同就是不需要求余。也就是說數值不會越界，數值可能較小。 還有一點快速冪適合正數次冪這裡可能為負數次冪。假設a,b大於0.但是a^-b^可以轉化為(1/a)^b^然後進行快速冪！時間複雜度為O(logn).
程式碼：
public double Power(double base, int exponent) { return Math.pow(base, exponent); } public double Power(double base, int exponent) { if(base==0)return 0; if(exponent<0) {exponent=-exponent;base=1/base;} if(exponent==0)return 1; else if (exponent % 2 == 0) { return Power(base*base, exponent/ 2) ; } else return base*Power(base*base, (exponent-1)/ 2); }
13 調整數組順序使奇數位於偶數前面
題目描述
輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有的奇數位於數組的前半部分，所有的偶數位於數組的後半部分，並保證奇數和奇數，偶數和偶數之間的相對位置不變。
思路： 題目要求1、奇數位於偶數前面2、奇數之間相對位置不變。 注意事項： void函數，注意對象克隆，深淺拷貝。如果是java最好先了解java函數調用參數(指針)問題。
- 需要新開數組team複製(克隆)array數組。
- 進行兩次遍歷team，一次從左向右找奇數從左向右賦值給array對應位置。
- 一次從右向左遍歷team將數值從右往左賦值給array對應位置。
public class Solution { public void reOrderArray(int [] array) { int team[]=array.clone(); int index=0; for(int i=0;i<team.length;i++) { if((team[i]&1)==1)//如果為奇數 array[index++]=team[i]; } index=team.length-1; for(int i=team.length-1;i>=0;i--) { if((team[i]&1)==0) array[index--]=team[i]; } } }
參考討論區： 我是基於開闢新空間數組跑兩遍實現的，但是有的討論區不開闢新空間的話那就只能考慮一些排序(插入排序)。當然，在vx打卡交流群中有個小姐姐曾經用兩個隊列跑一遍儲存感覺思想也很棒！還沒想到用隊列呢！
14 鏈表中倒數第K個節點
題目描述
輸入一個鏈表，輸出該鏈表中倒數第k個結點。
思路： 感覺這題可以搞得實現方式比較多吧。 比如你可以藉助一個Arraylist之類集合將鏈表遍歷加入。根據集合大小和K直接取值(自行ac)。
比如你還可以不藉助外部集合，第一次遍歷到尾獲得鏈表長度l。根據長度l和倒數第k個節點獲得正數的序號。再遍歷一次取該節點的值即可！
程式碼：
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindKthToTail(ListNode head, int k) { int count = 0; ListNode team = head; while (team != null) { count++; team = team.next; } int value = count - k; int index = 0; while (head!= null) { if (index == value) { return head; } index++; head = head.next; } return head; } }
參考討論區 這題參考了討論區發現了一些其他也很不錯的解法： 比如遞歸先到頭，返回的時候對整型數值疊加符合題意返回，判斷處理即可！ 還有就是定義快慢指針。這個思想就像兩輛車中間拖個繩子，前車走的如果超過繩子長度就拉著後車保持繩子長度跑。如果繩子沒拉直那就肯定不符合題意噠！
15 反轉鏈表
題目描述
輸入一個鏈表，反轉鏈表後，輸出新鏈表的表頭。
思路： 法一：最簡單的想法是遍歷整個鏈表，head用來遍歷。team用來作為新鏈表返回。每次遍歷時候新建一個listNode指向前面的team。
實現程式碼：
public static class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } public ListNode ReverseList(ListNode head) { if (head == null) return head; ListNode team = new ListNode(head.val);// head的第一個當作team的最後一個 while (head != null) { head = head.next; if (head != null) { ListNode listNode = new ListNode(head.val); listNode.next = team;// 將它指向lsitNode team = listNode;// team指向listnode } } return team; }
法二(參考)：參考了評論區一個遞歸的方案，感覺很巧妙，至於理解就像圖所畫。
實現程式碼為：
public static ListNode ReverseList(ListNode head) { if (head == null||head.next==null) return head; else { ListNode node=ReverseList(head.next); head.next.next = head; head.next = null; return node; }
理解為：
記得收藏、關注、再看哈。如果有數據結構問題，可以參考寫的系列數據結構文章也可以加我交流哈！附上超越妹妹美圖一張！
