文章目錄

• • 34 第一個只出現(xiàn)一次的字符
  • 35 數(shù)組中的逆序數(shù)
  • 36 兩個鏈表的第一個公共節(jié)點
  • 37 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
  • 38 二叉樹的深度
  • 39 平衡二叉樹
  • 40 數(shù)組中只出現(xiàn)一次的數(shù)字

歡迎關(guān)注個人數(shù)據(jù)結(jié)構(gòu)專欄哈
劍指offer系列：
劍指offer(1-10題)詳解
劍指offer(11-25題)詳解
劍指offer(26-33題)詳解
劍指offer(34-40題)詳解
劍指offer(51-59題)詳解
劍指offer(34-40題)詳解
微信公眾號：bigsai

聲明：大部分題基本未參考題解，基本為個人想法，如果由效率太低的或者錯誤還請指正！，如果有誤導(dǎo)，還請指正！

34 第一個只出現(xiàn)一次的字符

題目描述

在一個字符串(0<=字符串長度<=10000，全部由字母組成)中找到第一個只出現(xiàn)一次的字符,并返回它的位置, 如果沒有則返回 -1（需要區(qū)分大小寫）

思路：
用hashmap儲存記錄每個字母出現(xiàn)的次數(shù)。然后再進(jìn)行遍歷查找第一個出現(xiàn)一次的字母返回位置。

實現(xiàn)代碼：

import java.util.HashMap; public class Solution {public int FirstNotRepeatingChar(String str) {HashMap<String, Integer>map=new HashMap<String, Integer>();String team="";for(int i=0;i<str.length();i++){team=str.charAt(i)+""; if(map.containsKey(team)){map.put(team, 2);}else {map.put(team, 1);}}int index=-1;for(int i=0;i<str.length();i++){team=str.charAt(i)+"";if(map.get(team)==1){index=i;break;}}return index;} }

35 數(shù)組中的逆序數(shù)

題目描述

在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)Α］斎胍粋€數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對1000000007取模的結(jié)果輸出。 即輸出P%1000000007
輸入描述:
題目保證輸入的數(shù)組中沒有的相同的數(shù)字

數(shù)據(jù)范圍：

對于%50的數(shù)據(jù),size<=10^4對于%75的數(shù)據(jù),size<=10^5對于%100的數(shù)據(jù),size<=2*10^5

示例1

輸入
1,2,3,4,5,6,7,0
輸出
7

思路：
至于逆序數(shù)，一般有三種方法求解，首當(dāng)其中的就是暴力的O(n²)的方法，但是這種方法復(fù)雜度過高一看這個數(shù)據(jù)范圍肯定是過不了的。18年夏天遇到過逆序數(shù)記錄下來，但是寫的不夠好，從寫了一下！

今天剛寫的歸并排序和逆序數(shù)各位一定好好看看，進(jìn)行了詳細(xì)分析。

然后可以采用樹狀數(shù)組或者歸并排序求解逆序數(shù)。當(dāng)然，筆者這里采用的是歸并排序。

實現(xiàn)代碼為：

public class Solution {static int value=0;public static int InversePairs(int [] array) { mergesort(array,0,array.length-1);return value;} private static void mergesort(int[] array, int l, int r) {int mid=(l+r)/2;if(l<r){mergesort(array, l, mid);mergesort(array, mid+1, r);merge(array, l,mid, r);}}private static void merge(int[] array, int l, int mid, int r) {int lindex=l;int rindex=mid+1;int team[]=new int[r-l+1];int teamindex=0;while (lindex<=mid&&rindex<=r) {if(array[lindex]<=array[rindex]){team[teamindex++]=array[lindex++];}else { team[teamindex++]=array[rindex++];value+=mid-lindex+1;value%=1000000007;}}while(lindex<=mid){team[teamindex++]=array[lindex++];}while(rindex<=r){team[teamindex++]=array[rindex++];} for(int i=0;i<teamindex;i++){array[l+i]=team[i];} } }

36 兩個鏈表的第一個公共節(jié)點

題目描述

輸入兩個鏈表，找出它們的第一個公共結(jié)點

思路：
這題的吧不要用暴力匹配的O(n²)的方法。大家直到鏈表是一條直的對吧？然后一個鏈表節(jié)點相同也就是后面都相同是吧？ 所以如果有相同節(jié)點的話那么一定從那個節(jié)點到最后都是相同的。并且肯定在短的后面才可能匹配。

至于實現(xiàn)方式其實還是蠻多的，比如你可以先遍歷一次分別把兩個長度求出來然后把長的節(jié)點往后移到相同長度，然后一個個比較就好。當(dāng)然這樣可能跑2次但是影響確實不大。你也可以借助外部空間然后將遍歷一次的存下來。然后從后往前找到第一個不一樣的那個后面就是了。 當(dāng)然筆者采用上面一個方法并沒有采用外部空間。

實現(xiàn)代碼為：

/* public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;} }*/ public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {int lp1=getlen(pHead1); int lp2=getlen(pHead2);while (lp1>lp2) {pHead1=pHead1.next;lp1--;}while (lp1<lp2) {pHead2=pHead2.next;lp2--;}while (pHead1!=pHead2) {pHead1=pHead1.next;pHead2=pHead2.next;}return pHead1;}private int getlen(ListNode pHead1) {int len=0;ListNode team=pHead1;while (team!=null) {team=team.next;len++;}return len;} }

37 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

題目描述

統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

思路：
數(shù)組問題，一般枚舉能過但是不夠優(yōu)雅。有序的數(shù)組、序列當(dāng)然可以使用二分法哈！先二分找到其中任意一個數(shù)字所在的序號，然后根據(jù)這個坐標(biāo)左右試探就可以直到多少個啦！

實現(xiàn)代碼為：

public class Solution {public int GetNumberOfK(int [] array , int k) {int l=0,r=array.length;int mid=(l+r)/2;while (l<r) {if(array[mid]==k){return search(array,mid);}else if (array[mid]<k) {l=mid+1;mid=(l+r)/2;}else {r=mid;mid=(l+r)/2;}}return 0;}private int search(int[] array, int mid) {int l=mid-1,r=mid+1;int value=0;while (l>=0&&array[l]==array[mid]) {value++;l--;}while (r<array.length&&array[r]==array[mid]) {value++;r++;}return value+1;} }

38 二叉樹的深度

題目描述

輸入一棵二叉樹，求該樹的深度。從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點（含根、葉結(jié)點）形成樹的一條路徑，最長路徑的長度為樹的深度

思路：
因為二叉樹有 左右子節(jié)點，左右節(jié)點的問題。每個孩子都要比自己更深一層，對于這個問題，你可以自己定義一個包含次數(shù)的結(jié)構(gòu)體或者類用隊列或者棧進(jìn)行遍歷找到最大的。但是這題可以直接使用遞歸進(jìn)行求解。父節(jié)點和子節(jié)點之間的關(guān)系就是deep(parent)=max(parent.left,parent.right)+1。當(dāng)然，這里的left和right節(jié)點也要判空之類的處理。

實現(xiàn)代碼為：

/** public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;} } */ public class Solution {public int TreeDepth(TreeNode root) {if(root==null)return 0;return Math.max(TreeDepth(root.left), TreeDepth(root.right))+1; } }

39 平衡二叉樹

題目描述

輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。

思路：
至于平衡二叉樹(avl)，之所以平衡，是因為它的任意一個左右節(jié)點的高度相差都小于等于1. 如果有不了解的可以參考以前寫的一篇avl二叉平衡樹 。但是這個跟文中寫的的其實不太一樣，是因為之前我創(chuàng)造二叉樹的時候有個height值每次插入的時候動態(tài)維護(hù)，判斷是否平衡。但是顯然這題什么都沒有，需要自己完成所有。

好吧，來就來，不就是判斷每個節(jié)點都要滿足左右高度都要相差在1之內(nèi)嘛！上面那題，不就是求高度的嘛？！！我用個隊列把所有點存下來，然后一個個判斷可還行？雖然可能效率不一定高。但是還是能過的。

實現(xiàn)代碼為：

import java.util.ArrayDeque; import java.util.Queue; public class Solution {public boolean IsBalanced_Solution(TreeNode root) {if(root==null)return true;Queue<TreeNode>q1=new ArrayDeque<TreeNode>();q1.add(root);while (!q1.isEmpty()) {TreeNode team=q1.poll();if(Math.abs(TreeDepth(team.left)-TreeDepth(team.right))<=1){if(team.left!=null)q1.add(team.left);if(team.right!=null)q1.add(team.right);}else {return false;} }return true;}public int TreeDepth(TreeNode root) {if(root==null)return 0;return Math.max(TreeDepth(root.left), TreeDepth(root.right))+1; } }

40 數(shù)組中只出現(xiàn)一次的數(shù)字

題目描述

一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。

思路：
這題只能用普通方法過，但是還是有技巧的。感覺可以用位運(yùn)算但是奈何自己沒想出來。兩個相同的數(shù)進(jìn)行異或^運(yùn)算等于0.而0和任何數(shù)異或等于它自己。如果只求1個數(shù)那可能好搞一些，但是后面會研究討論區(qū)大佬的位運(yùn)算方案。

對于普通思路，可能大部分人會用hashmap先添加，最后遍歷兩個次數(shù)等于1個的兩個數(shù)返回。但是其實可以使用hash進(jìn)行減。如果存在這個元素，就減去這個元素。如果不存在那就加入hash中，那么最終剩的2個元素其實就是我們出現(xiàn)一次的元素。由于java底層用hashmap維護(hù)hashset我就用hashmap了差不了太大。

實現(xiàn)代碼為：

import java.util.HashMap; //num1,num2分別為長度為1的數(shù)組。傳出參數(shù) //將num1[0],num2[0]設(shè)置為返回結(jié)果 public class Solution {public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {HashMap<Integer, Integer>map=new HashMap<Integer, Integer>();for(int i=0;i<array.length;i++){if(map.containsKey(array[i])) {map.remove(array[i]);}else {map.put(array[i],1);}}int count=0;for(Integer va:map.keySet()){if(count++==0)num1[0]=va;else {num2[0]=va;}}} }

參考討論區(qū)：
這題的討論區(qū)很妙，用^來解決問題。至于討論區(qū)的題解稍微解釋一下：大概就是將數(shù)組一分為2份！
就是說先異或到最后得到一個數(shù)，肯定是a^b的值。這個數(shù)位位1的那個肯定就是兩個位不同的。比如10100.第三位就是a和b不同的，然后我們就再次遍歷所有數(shù)，用兩個數(shù)進(jìn)行異或，如果第三位為1xx那么和a1異或，如果為0xx那么和a2異或。就相當(dāng)于把這個數(shù)邏輯一分為2.因為所有數(shù)除了這兩都出現(xiàn)兩次，所以是可以消下去的！

實現(xiàn)代碼為：

鏈接：https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811?f=discussion 來源：牛客網(wǎng)public class Solution {public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2) {int length = array.length;if(length == 2){num1[0] = array[0];num2[0] = array[1];return;}int bitResult = 0;for(int i = 0; i < length; ++i){bitResult ^= array[i];}int index = findFirst1(bitResult);for(int i = 0; i < length; ++i){if(isBit1(array[i], index)){num1[0] ^= array[i];}else{num2[0] ^= array[i];}}}private int findFirst1(int bitResult){int index = 0;while(((bitResult & 1) == 0) && index < 32){bitResult >>= 1;index++;}return index;}private boolean isBit1(int target, int index){return ((target >> index) & 1) == 1;} }

歡迎關(guān)注公眾號：bigsai 長期奮戰(zhàn)輸出！

總結(jié)

以上是生活随笔為你收集整理的剑指offer(34-40题)详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。