劍指offer51到60題總覽:
- 構(gòu)建乘積數(shù)組
- 正則表達式匹配
- 表示數(shù)值的字符串
- 字符流中第一個不重復(fù)的字符
- 鏈表中環(huán)的入口結(jié)點
- 刪除鏈表中重復(fù)的結(jié)點
- 二叉樹的下一個結(jié)點
- 對稱的二叉樹
- 按之字形打印二叉樹
- 把二叉樹打印成多行
51、構(gòu)建乘積數(shù)組
題目描述
給定一個數(shù)組A[0,1,...,n-1],請構(gòu)建一個數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
解題思路

兩次遍歷,第一次計算下三角,第二次計算上三角。比如計算下三角,設(shè)置一個temp,temp=A[0],將temp賦值給B[1];temp=temp*A[1],將temp賦值給B[2]。
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int[] B = new int[A.length];
if(A.length == 0){return B;}
if(A.length == 1){
B[0] = 1;
return B;
}
B[0] = 1;//先將B[0]賦值為1,計算下三角時用不到B[0]
int temp = 1;//用來保存當前乘積
for(int i=1; i<A.length; i++){//計算下三角
temp = temp * A[i-1];
B[i] = temp;
}
temp = 1;//計算上三角前將temp置為0
for(int i=A.length-2; i>=0; i--){//計算上三角
temp = temp * A[i+1];
B[i] *= temp;//B[i]應(yīng)該在計算完下三角的基礎(chǔ)上乘temp
}
return B;
}
}
52、正則表達式匹配
題目描述
請實現(xiàn)一個函數(shù)用來匹配包括'.'和'*'的正則表達式。模式中的字符'.'表示任意一個字符,而'*'表示它前面的字符可以出現(xiàn)任意次(包含0次)。 在本題中,匹配是指字符串的所有字符匹配整個模式。例如,字符串"aaa"與模式"a.a"和"ab*ac*a"匹配,但是與"aa.a"和"ab*a"均不匹配。
解題思路
考慮各種情況:
- 如果strIndex和patternIndex都到尾了,則匹配成功。
- 如果strIndex沒有到尾,但patternIndex已經(jīng)到尾了,str還有最后一部分沒有匹配完,則匹配失敗。
- 如果遇到pattern當前字符的下一個字符是*,有幾種情況:
- pattern當前字符是.,則可視作匹配0個字符,strIndex+0,patternIndex+2,繼續(xù)遞歸;可視作匹配1個字符,strIndex+1,patternIndex+2,繼續(xù)遞歸;可視作暫時匹配1個字符,patternIndex不移動,后面可再選擇匹配0個或1個或再暫時匹配一個字符,strIndex+1,patternIndex+0,繼續(xù)遞歸。
- pattern當前字符不是.而是一個字母或者其他,則要看pattern當前字符和str當前字符是否一樣:不一樣,則匹配失敗;一樣,則和pattern當前字符是.一樣,可以選擇匹配0個或1個或暫時匹配一個字符,繼續(xù)遞歸。
3.1
public class Solution {
public boolean match_1(char[] str, char[] pattern) {
if (str == null || pattern == null) {
return false;
}
int strIndex = 0;
int patternIndex = 0;
return matchCore(str, strIndex, pattern, patternIndex);
}
public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
//有效性檢驗:str到尾,pattern到尾,匹配成功
if (strIndex == str.length && patternIndex == pattern.length) {
return true;
}
//pattern先到尾,匹配失敗
if (strIndex != str.length && patternIndex == pattern.length) {
return false;
}
//模式第2個是*,則分兩種情況,一種是*前面是.一種是*是一般字符。
//如果是一般字符,則又可分為pattern當前字符與str當前字符匹配成功和不匹配兩種情況
//而*前面是.和pattern當前字符與str當前字符匹配成功的情況可以寫到一起。
if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
|| (strIndex != str.length && pattern[patternIndex] == '.')) {
//*前面是.,或*前面的一般字符是與str的當前字符匹配成功
return matchCore(str, strIndex, pattern, patternIndex + 2) //模式后移2,視為x*匹配0個字符
|| matchCore(str, strIndex + 1, pattern, patternIndex + 2) //視為模式匹配1個字符,模式向后移動兩位
|| matchCore(str, strIndex + 1, pattern, patternIndex); //當前只匹配1個,模式?jīng)]有移動,再遞歸可匹配str中的下一個或匹配0個
} else {
//*前面的字符與當前字符不匹配,模式向后移動兩位
return matchCore(str, strIndex, pattern, patternIndex + 2);
}
}
//模式第2個不是*,且字符串第1個跟模式第1個匹配,則都后移1位,否則直接返回false
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
|| (strIndex != str.length && pattern[patternIndex] == '.')) {
return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
}
return false;
}
}
53、表示數(shù)值的字符串
題目描述
請實現(xiàn)一個函數(shù)用來判斷字符串是否表示數(shù)值(包括整數(shù)和小數(shù))。例如,字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數(shù)值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
解題思路
用正則表達式。
public class Solution {
public boolean isNumeric(char[] str) {
String s = String.valueOf(str);
return s.matches("[\\+-]?[0-9]*(\\.[0-9]*)?([eE][\\+-]?[0-9]+)?");
}
}
54、字符流中第一個不重復(fù)的字符
題目描述
請實現(xiàn)一個函數(shù)用來找出字符流中第一個只出現(xiàn)一次的字符。例如,當從字符流中只讀出前兩個字符"go"時,第一個只出現(xiàn)一次的字符是"g"。當從該字符流中讀出前六個字符“google"時,第一個只出現(xiàn)一次的字符是"l"。
輸出描述:
如果當前字符流沒有存在出現(xiàn)一次的字符,返回#字符。
public class Solution {
int arr[] = new int[256];//建立所有可能字符的數(shù)組
int index;
public Solution(){
for(int i=0; i<arr.length; i++){//將數(shù)組所有值賦值為-1
arr[i] = -1;
}
index = 0;//index為當前插入的字符的個數(shù)
}
//Insert one char from stringstream
public void Insert(char ch)//因為要頻繁插入,所以不建議在insert方法中設(shè)置循環(huán)
{
if(arr[ch] == -1){//-1表示之前沒有出現(xiàn)過,現(xiàn)在出現(xiàn)了
arr[ch] = index;//將對應(yīng)字符的位賦值為字符流的index
}else if(arr[ch] >= 0){//>=0表示之前出現(xiàn)過一次,而且是唯一一次,而此時出現(xiàn)了第二次
arr[ch] = -2;//出現(xiàn)了第二次,將對應(yīng)字符的位賦值為-2,>=0的情況只保存當前只出現(xiàn)了一次,并記錄在字符流中的index
}
index++;//插入了一個字符,index+1
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
int result_index = index;//給返回結(jié)果一個初始值
for(int i=0; i<arr.length; i++){//遍歷數(shù)組
if(arr[i] >= 0){//遇到一個只出現(xiàn)一次的字符
if(result_index == index){result_index = i;}//如果是第一個只出現(xiàn)一次的字符,則將result_index更新
else{
if(arr[i] < arr[result_index]){//找到了新的只出現(xiàn)一次的字符,且其保存的字符流的位置更靠前,更新result_index。
result_index = i;
}
}
}
}
if(result_index == index){return '#';}//如果整個遍歷沒有找到只出現(xiàn)一次的字符,返回#
else{return (char)result_index;}//將int類型的下標轉(zhuǎn)化為char類型
}
}
55、鏈表中環(huán)的入口結(jié)點
題目描述
給一個鏈表,若其中包含環(huán),請找出該鏈表的環(huán)的入口結(jié)點,否則,輸出null。
解題思路
方法很多,記錄兩種,都是快慢指針的思想。設(shè)置一個慢指針slow,一次走一步;設(shè)置一個快指針fast,一次走兩步。如果存在環(huán),則快慢指針一定會在環(huán)內(nèi)相遇。如果不存在環(huán),則fast會率先走到鏈表尾,則返回null。在環(huán)內(nèi)相遇之后,有兩種方法尋找入環(huán)結(jié)點:
- 從快慢指針相遇的結(jié)點開始,fast結(jié)點不走,slow再走一圈,得到環(huán)內(nèi)包含的結(jié)點數(shù)c。然后令p1=pHead,p1先走c步(此時已經(jīng)知道有環(huán),不用擔心會走到空結(jié)點),令p2=pHead,然后p1和p2一起走,每次都走一步(p1始終超前p2 c步)。則他們第一次相等的時候指向的節(jié)點,就是入環(huán)結(jié)點。
- 從快慢指針相遇的結(jié)點開始,我們有以下推導(dǎo):
參考鏈接:https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4
劍指offer|55題鏈表中環(huán)的入口結(jié)點
假設(shè)x為環(huán)前面的路程(黑色路程),a為環(huán)入口到相遇點的路程(藍色路程,假設(shè)順時針走), c為環(huán)的長度(藍色+橙色路程)
當快慢指針相遇的時候:
此時慢指針走的路程為,
為慢指針在環(huán)內(nèi)轉(zhuǎn)的圈數(shù),這個圈數(shù)并不重要。
快指針走的路程為,
為快指針在環(huán)內(nèi)轉(zhuǎn)的圈數(shù)。
我們設(shè)置快指針一次走兩步,慢指針一次走一步,則相遇時他們的路程有如下關(guān)系:
則有:
從而可以推導(dǎo)出:
上式第二步中,我們提出一個,則
可以表示相遇點后,環(huán)后面部分的路程。(橙色路程)
所以,我們可以讓一個指針p從起點A開始走,讓slow指針從相遇點B開始繼續(xù)往后走,p和slow指針速度一樣,每次只走一步,則當指針p走到環(huán)入口點的時候(此時剛好走了x)slow指針也一定剛好到達環(huán)入口點。p和slow恰好相遇在環(huán)的入口點。返回p或slow即可。這種方法需要一點推導(dǎo)所以可能想不到,但是推出來之后寫代碼就變得更簡單了。
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
if(pHead==null || pHead.next==null || pHead.next.next==null){return null;}
ListNode slow = pHead.next;//slow先走一步
ListNode fast = pHead.next.next;//fast先走兩步
while(slow != fast){//當還沒有相遇的時候
if(fast.next!=null && fast.next.next!=null){//沒有走到鏈表尾
slow = slow.next;//slow和fast繼續(xù)走
fast = fast.next.next;
}else{//如果走到了鏈表尾,則一定沒有環(huán),直接返回null
return null;
}
}//循環(huán)出來了一定是slow和fast相遇了
ListNode p = pHead;//p指向鏈表頭,與slow一起走,p和slow一次都只走一步
while(p!=slow){//p和slow一起走,此時有環(huán)則他們一定會在入環(huán)結(jié)點相遇。
p = p.next;
slow = slow.next;
}
return p;
}
}
56、刪除鏈表中重復(fù)的結(jié)點
題目描述
在一個排序的鏈表中,存在重復(fù)的結(jié)點,請刪除該鏈表中重復(fù)的結(jié)點,重復(fù)的結(jié)點不保留,返回鏈表頭指針。 例如,鏈表1->2->3->3->4->4->5 處理后為 1->2->5
解題思路
如果鏈表最前面就有重復(fù)的,則將鏈表頭前面的重復(fù)結(jié)點全部跳過,讓pHead指向第一個不重復(fù)的結(jié)點,返回新的頭結(jié)點。如果鏈表最前面不是重復(fù)的,則找到最后一個不重復(fù)結(jié)點,遞歸刪除后面的重復(fù)結(jié)點。這里不加速找到最后一個不重復(fù)的結(jié)點也可以,如果頭結(jié)點不是重復(fù)結(jié)點,則遞歸頭結(jié)點后面的結(jié)點,直到遞歸到頭結(jié)點就是重復(fù)結(jié)點。
public class Solution {
public ListNode deleteDuplication(ListNode pHead){
if(pHead == null){return null;}
if(pHead.next == null){return pHead;}
ListNode p = pHead;
if(p.val == p.next.val){//如果p點與p后面的結(jié)點重復(fù)
while(p.next!=null && p.val == p.next.val){//跳過所有的重復(fù)結(jié)點,直到p結(jié)點不重復(fù),或者p為最后一個結(jié)點。
p = p.next;//如果p為重復(fù)結(jié)點,且p后面還有結(jié)點,則p后移一位
}
pHead = deleteDuplication(p.next);//如果是p和p后面的結(jié)點不重復(fù)了,則遞歸p.next;或者p為最后一個結(jié)點了,但是p結(jié)點是重復(fù)結(jié)點,依舊遞歸p.next,這時遞歸返回null
}else{//如果p不是重復(fù)結(jié)點,則看p的后面的結(jié)點是不是重復(fù)結(jié)點
while(p.next.next!=null && p.next.val != p.next.next.val){//向后找重復(fù)結(jié)點,p指向最后一個不重復(fù)結(jié)點
p = p.next;
}//這里的循環(huán)不要也可以,直接p.next = deleteDuplication(p.next);也行
p.next = deleteDuplication(p.next);//遞歸刪除p結(jié)點后面的重復(fù)結(jié)點,并將刪除后返回的頭結(jié)點連接到p的后面
}
return pHead;
}
}
57、二叉樹的下一個結(jié)點
題目描述
給定一個二叉樹和其中的一個結(jié)點,請找出中序遍歷順序的下一個結(jié)點并且返回。注意,樹中的結(jié)點不僅包含左右子結(jié)點,同時包含指向父結(jié)點的指針。
解題思路
畫圖,可知各種情況的下一個結(jié)點。
- 如果pNode為空,則返回null。
- 如果pNode不為空,判斷pNode是否有右子樹,如果有右子樹,則返回右子樹中最左邊的結(jié)點。如果沒有右子樹,則向上找pNode的父結(jié)點。
- 如果沒有父結(jié)點,則pNode是根節(jié)點,中序遍歷已經(jīng)遍歷完,返回null;如果有父結(jié)點,且如果它是父結(jié)點的左結(jié)點,直接返回pNode的父結(jié)點;如果有父結(jié)點,且如果它是父結(jié)點的右結(jié)點,則要看pNode的祖父結(jié)點。
- 如果沒有祖父結(jié)點,則中序遍歷已經(jīng)遍歷完,返回null;如果pNode的父結(jié)點是祖父結(jié)點的左結(jié)點,則返回祖父結(jié)點;如果有父結(jié)點,且如果pNode的父結(jié)點是祖父結(jié)點的右結(jié)點,則中序遍歷已經(jīng)遍歷完,返回null。
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode){
if(pNode == null){return null;}//如果結(jié)點為空,則返回null
if(pNode.right!=null){//如果結(jié)點有右子樹,則找到子樹的最左的結(jié)點
pNode = pNode.right;
while(pNode.left!=null){//找到最左的結(jié)點
pNode = pNode.left;
}
return pNode;
}else{//如果改結(jié)點沒有右子樹,就只能往上找其父結(jié)點
if(pNode.next!=null && pNode.next.left==pNode){//有父結(jié)點,且是父結(jié)點的左結(jié)點,則直接返回pNode的父結(jié)點
return pNode.next;
}else if(pNode.next!=null && pNode.next.right==pNode){//有父結(jié)點,且是父極點的右結(jié)點
if(pNode.next.next!=null && pNode.next.next.left==pNode.next){
//如果祖父結(jié)點存在,且其父結(jié)點是祖父結(jié)點的左結(jié)點,則返回其祖父結(jié)點
return pNode.next.next;
}else if(pNode.next.next!=null && pNode.next.next.right==pNode.next){
//如果祖父結(jié)點存在,且其父結(jié)點是祖父結(jié)點的右結(jié)點,則返回null,中序遍歷后面沒有結(jié)點了
return null;
}else{//如果祖父結(jié)點不存在,也就是其父結(jié)點就是根結(jié)點,中序遍歷后面已經(jīng)沒有結(jié)點了,返回null
return null;
}
}else{//如果他沒有父結(jié)點,則它是根節(jié)點
return null;//這種情況就是根節(jié)點只有左子樹,右邊全為空,根節(jié)點就是最后一個結(jié)點,返回null
}
}
}
}
58、對稱的二叉樹
題目描述
請實現(xiàn)一個函數(shù),用來判斷一顆二叉樹是不是對稱的。注意,如果一個二叉樹同此二叉樹的鏡像是同樣的,定義其為對稱的。
解題思路
根節(jié)點只有一個,不用管其對稱性,拋開根節(jié)點,看根節(jié)點的左右子樹。
如果左右兩顆子樹是鏡像的,則這兩顆子樹的根節(jié)點的值是一樣的,且其left.left與right.right是鏡像的;其left.right與right.left是鏡像的。
public class Solution {
boolean isSymmetrical(TreeNode pRoot){
if(pRoot==null){return true;}//如果根節(jié)點為空,則返回true
return isSym(pRoot.left, pRoot.right);//看根節(jié)點的左右子樹是否是鏡像的
}
boolean isSym(TreeNode left, TreeNode right){
if(left==null && right==null){return true;}//如果兩顆樹都為空,則返回true
if(left!=null && right==null){return false;}//如果左不空,右空,則不是鏡像的
if(left==null && right!=null){return false;}//如果左空,右不空,則不是鏡像的
if(left.val != right.val){return false;}//如果左右都不空,但是左右子樹的根節(jié)點的值不一樣,則不是鏡像的
//左右都不空,則查看left.left與right.right是否鏡像,其left.right與right.left是否鏡像
return isSym(left.left, right.right) && isSym(left.right, right.left);
}
}
59、按之字形打印二叉樹
題目描述
請實現(xiàn)一個函數(shù)按照之字形打印二叉樹,即第一行按照從左到右的順序打印,第二層按照從右至左的順序打印,第三行按照從左到右的順序打印,其他行以此類推。
解題思路
設(shè)置一個boolean left2right來判斷是應(yīng)該從左往右還是從右往左。
有一種方法是用兩個棧,一個是奇數(shù)層棧,一個是偶數(shù)層棧??蓞⒖寂?途W(wǎng)。
層次遍歷一棵樹容易想到用隊列,可以簡單地在將結(jié)點的value插到list的最前面,但是這種方法肯定不能用于海量數(shù)據(jù)。java中的LinkedList可以用來實現(xiàn)隊列,這個隊列的實現(xiàn)是雙向鏈表,是可以正向迭代和反向迭代的。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Iterator;
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> final_list = new ArrayList<>();
if(pRoot==null){return final_list;}
boolean left2right = true;
ArrayList<Integer> list = new ArrayList<>();
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(null);//分隔符在一層結(jié)點的前面比較方便
queue.offer(pRoot);
while(queue.size()!=1){//到最后只剩下一個null的時候結(jié)束循環(huán)
TreeNode node = queue.poll();//隊頭結(jié)點出隊列
if(node == null){//遇到分界符號
Iterator<TreeNode> iter = null;//對隊列中的結(jié)點進行迭代,但不出隊列
if(left2right){
iter = queue.iterator();//正向迭代器
}else{
iter = queue.descendingIterator();//反向迭代器
}
left2right = !left2right;//將迭代方向反向
while(iter.hasNext()){
TreeNode temp = (TreeNode)iter.next();//迭代隊中的每個元素,加入list
list.add(temp.val);
}//一般遍歷樹時我們將結(jié)點出隊,并將val加入list,但是這里只對隊中的元素迭代,并不出隊。另外,此時遍歷時,隊中只有結(jié)點,沒有null
final_list.add(new ArrayList<Integer>(list));//拷貝一個list加入final_list
list.clear();//清空list
queue.offer(null);//隊中元素迭代完了之后加入null
}else{
if(node.left!=null){queue.offer(node.left);}//我們將元素迭代完了之后再將元素遍歷一遍,此時只需要將這里元素的左右結(jié)點加入隊即可
if(node.right!=null){queue.offer(node.right);}
}
}
return final_list;
}
}
60、把二叉樹打印成多行
題目描述
從上到下按層打印二叉樹,同一層結(jié)點從左至右輸出。每一層輸出一行。
解題思路
層次遍歷很容易想到用隊列。??驮u論區(qū)還有利用遞歸方法的,遞歸是深度優(yōu)先,但是他通過對方法傳入深度值來指定將結(jié)點加入哪一個list,從而使返回結(jié)果看起來像層次遍歷。
隊列版本:
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> final_list = new ArrayList<>();
if(pRoot==null){return final_list;}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(pRoot);
queue.offer(null);//分界符號
final_list.add(new ArrayList<Integer>());//新建一個list加入fianl_list
while(queue.size()!=1){//如果隊列只剩下一個元素,則這個元素一定是分界符號
TreeNode node = queue.poll();//取隊頭元素
if(node!=null){//如果隊頭不是分界符號
final_list.get(final_list.size()-1).add(node.val);//將val加入相應(yīng)list
if(node.left!=null){queue.offer(node.left);}//如果左子樹非空,則將左子樹的根節(jié)點加入隊列
if(node.right!=null){queue.offer(node.right);}//如果右子樹非空,則將右子樹的根節(jié)點加入隊列
}else{//如果遇到了分界符號,則分界符號前面的層已經(jīng)遍歷完
final_list.add(new ArrayList<Integer>());//新建一個list,為下一層的遍歷做準備
queue.offer(null);//下一層已經(jīng)全部入隊列,最后加入分界符號
}
}
return final_list;
}
}
遞歸版本:
import java.util.ArrayList;
public class Solution {
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> final_list = new ArrayList<>();
if(pRoot==null){return final_list;}
return depth(pRoot, 1, final_list);
}
ArrayList<ArrayList<Integer>> depth(TreeNode p, int depth, ArrayList<ArrayList<Integer>> final_list){
if(depth > final_list.size()){//當前要遍歷新層
final_list.add(new ArrayList<Integer>());//建一個新層對應(yīng)的list加入final_list
final_list.get(depth-1).add(p.val);//將當前結(jié)點加入對應(yīng)的list
}else{//當前層對應(yīng)的list已經(jīng)建立,則將當前結(jié)點的val加入對應(yīng)list
final_list.get(depth-1).add(p.val);
}
if(p.left!=null){depth(p.left, depth+1, final_list);}//左不為空則遞歸左
if(p.right!=null){depth(p.right, depth+1, final_list);}//右不為空則遞歸右
return final_list;
}
}
結(jié)尾
如果您發(fā)現(xiàn)我的文章有任何錯誤,或?qū)ξ业奈恼掠惺裁春玫慕ㄗh,請聯(lián)系我!如果您喜歡我的文章,請點喜歡~*我是藍白絳,感謝你的閱讀!
