【数据结构练习习题】java实现版(一)
練習目錄
- 僅用遞歸函數和棧操作逆序一個棧 不能用其他數據結構
- 一個棧中元素的類型為整型,現在想將該棧從頂到底按從大到小的順序排序,只許申請一個棧。
- 數組
- 在o(N)時間復雜度內查找數組中前三名
- 一個數組中求三個數使得三個數乘積最大
- 求一個無序數組中的兩個數,之和為給定的target
- 更改上面的題目條件:改為升序數組
- 旋轉z數組的最小元素
- 刪除排序數組的重復元素
- 尋找數組中心下標
- 生成窗口最大值數組
- 樹
- 把一個有序的整數數組放到二叉樹中
- 求最大子樹和
- 輸入一棵二元查找樹,將該二元查找樹轉換成一個排序的雙向鏈表。
- 輸入一個整數數組,判斷該數組是否是某二元查找樹的后序遍歷的結果
- 求x的平方根整數部分
- 斐波那契數列的三種解法
- 排列硬幣
僅用遞歸函數和棧操作逆序一個棧 不能用其他數據結構
思路:設計兩個遞歸函數,其中一個用于得到棧底的元素,另一個用于依次逆序棧,最后可得到一個新棧
//先設計一個遞歸函數將棧的棧底元素返回并移除public static int getAndRemoveLast(Stack<Integer>stack){int result = stack.pop();if(stack.empty()) return result;else{int last=getAndRemoveLast(stack);stack.push(result);return last;}}//遞歸函數2public static void reverse(Stack<Integer>stack){if(stack.empty())return;else{int i = getAndRemoveLast(stack);reverse(stack);stack.push(i);}}函數一過程:
注意遞歸函數中遞歸和push的順序,函數二先調用取棧底的函數,再調用自身
函數二過程:
一個棧中元素的類型為整型,現在想將該棧從頂到底按從大到小的順序排序,只許申請一個棧。
除此之外,可以申請新的變量,但不能申請額外的數據結構。如何完成排序?
【難度】 士 ★☆☆☆
【解答】 將要排序的棧記為stack,申請的輔助棧記為help。在stack上執行pop操作,彈出的元素記為cur。 如果cur小于或等于help的棧頂元素,則將cur直接壓入help;如果cur大于help的棧頂元素,則將help的元素逐一彈出,逐一壓入stack,直到cur小于或等于help的棧頂元素,再將cur壓入help。 一直執行以上操作,直到stack中的全部元素都壓入到help。最后將help中的所有元素逐一壓入stack,即完成排序。
(自己寫的):
Stack<Integer>help=new Stack<Integer>();while(!stack.empty()){if(help.empty())help.push(a);else if(help.peek()>=a)help.push(a);else {while(!help.empty()){int b=help.pop();stack.push(b);if(b >=a ||help.empty()) {help.push(a);break;}}}題解的:(簡潔很多)
public static void sortStack(Stack<Integer>stack){Stack<Integer>help=new Stack<Integer>();while(!stack.empty()){int a =stack.pop();while(!help.empty() && help.peek()<a)stack.push(help.pop());help.push(a);//其他情況都推入helpwhile(!help.empty())stack.push(help.pop());//最后把help的元素都推入原stack}}數組
在o(N)時間復雜度內查找數組中前三名
如果沒有時間復雜度的要求,可以首先對整個數組進行排序,然后根據數組下標就可以非常容易地找出最大的三個數,即前三名。由于這種方法的效率高低取決于排序算法的效率高低,因此,這種方法在最好的情況下時間復雜度都為O(NlogN)。 通過分析發現,最大的三個數比數組中其他的數都大。因此,可以采用類似求最大值的方法來求前三名。具體實現思路:初始化前三名(r1:第一名,r2:第二名,r3:第三名)為最小的整數。然后開始遍歷數組:
1)如果當前值tmp大于r1:r3=r2,r2=r1,r1=tmp;
2)如果當前值tmp大于r2且不等于r1:r3=r2,r2=tmp;
3)如果當前值tmp大于r3且不等于r2:r3=tmp。
一個數組中求三個數使得三個數乘積最大
public static int sort(int[]nums) {int min1 = Integer.MAX_VALUE,min2 = Integer.MAX_VALUE;int max1 = Integer.MIN_VALUE;int max2 = max1,max3 = max1;for(int x:nums){if(x < min1){//如果x比最小的還小min2 = min1;min1 = x;//原來最小的變成第二小的,x變成最小的}else if(x < min2)min2 = x;if(x > max1){max3 = max2;max2 = max1;max1 = x;}else if(x > max2){max3 = max2;max2 = x;}else if(x > max3)max3 = x;System.out.println(min1+","+min2+","+max1+" "+max2+" "+max3); } return Math.max(min1*min2*max1,max1*max2*max3);//考慮有正數也有負數,如果是兩個最小的負數和一正數乘積可能比三個正數大//其余情況都是三個最大值乘積最大 }public static void main(String[] args) {int []nums = {-10,-2,-3,-10,-5,9,5};System.out.println(sort(nums));}求一個無序數組中的兩個數,之和為給定的target
返回一個數組,數組中存放兩數的下標
給定初始數組和target整數,從數組中找出兩個數滿足相加之和為target 假定每個輸入只對應唯一的答案,且不重復使用相同的元素
常規:暴力法,雙重for循環,時間復雜度高
優化法:用一個map存儲下標和對應的元素,時間復雜度變為o(N)
更改上面的題目條件:改為升序數組
其他條件不變,找和為目標的兩數下標
方法一:二分法
法2 雙指針法(時間復雜度更優)是最優解
public static int[] towpoints(int[] nums,int target){int low = 0,high = nums.length - 1;while(low < high){int sum = nums[low] + nums[high];if(sum == target) return new int[]{low,high};else if(sum < target) low++;else high--;}return new int[0];}時間復雜度為o(n)
旋轉z數組的最小元素
把一個有序數組最開始的若干個元素搬到數組
的末尾,稱之為數組的旋轉。輸入一個排好序的數組的一個旋轉,輸出旋轉數組的最小元素。例如,數組{3, 4, 5, 1, 2}為數組{1, 2, 3, 4, 5}的一個旋轉,該數組的最小值為1。 分析與解答: 其實這是一個非常基本和常用的數組操作,它的描述如下: 有一個數組X[0…n-1],現在把它分為兩個子數組:x1[0…m]和x2[m+1…n-1],交換這兩個子數組,使數組x由x1x2變成x2x1,例如x={1,2,3,4,5,6,7,8,9},x1={1,2,3, 4,5},x2={6,7,8,9},交換后,x={6,7,8,9,1,2,3,4,5}。 對于本題的解決方案,最容易想到的,也是最簡單的方法就是直接遍歷法。但是這種方法顯然沒有用到題目中旋轉數組的特性,因此,它的效率比較低。下面介紹一種比較高效的二分查找法。 通過數組的特性可以發現,數組元素首先是遞增的,然后突然下降到最小值,然后再遞增。雖然如此,但是還有下面三種特殊情況需要注意:
1)數組本身是沒有發生過旋轉的,是一個有序的數組,如序列{1,2,3,4,5,6}。
2)數組中元素值全部相等,如序列{1,1,1,1,1,1}。
3)數組中元素值大部分都相等,如序列{1,0,1,1,1,1}。
通過旋轉數組的定義可知,經過旋轉之后的數組實際上可以劃分為兩個有序的子數組,前面的子數組的元素值都大于或者等于后面子數組的元素值。可以根據數組元素的這個特點,采用二分查找的思想不斷縮小查找范圍,最終找出問題的解決方案。 按照二分查找的思想,給定數組arr,首先定義兩個變量low和high,分別表示數組的第一個元素和最后一個元素的下標。按照題目中對旋轉規則的定義,第一個元素應該是大于或者等于最后一個元素的(當旋轉個數為0,即沒有旋轉時,要單獨處理,直接返回數組第一個元素)。接著遍歷數組中間的元素arr[mid],其中mid=(high+low)/2。
1)如果arr[mid]<arr[mid-1],則arr[mid]一定是最小值;
2)如果arr[mid+1]<arr[mid],則arr[mid+1]一定是最小值;
3)如果arr[high]>arr[mid],則最小值一定在數組左半部分;
4)如果arr[mid]>arr[low],則最小值一定在數組右半部分;
5)如果arr[low]==arr[mid] 且 arr[high]==arr[mid],則此時無法區分最小值是在數組的左半部分還是右半部分(例如,{2,2,2,2,1,2},{2,1,2,2,2,2,2})。在這種情況下,只能分別在數組的左右兩部分找最小值minL與minR,最后求出minL與minR的最小值。
public class findMin {public static int getMin(int[]arr,int low,int high){if(low > high) return arr[0];//如果選擇個數為0,即沒有旋轉,單獨處理,返回頭元素if(low == high) return arr[low];int mid = low+((high - low) >>1);//這樣運算防止溢出if(arr[mid-1] >arr[mid])return arr[mid];else if(arr[mid] > arr[mid+1]) return arr[mid+1];else if(arr[mid] <arr[high] ) return getMin(arr,low,mid-1);else if(arr[mid]>arr[low]) return getMin(arr,mid+1,high);else return Math.min(getMin(arr,low,mid-1),getMin(arr,mid+1,high));//arr[low]==arr[mid] 且 arr[high]==arr[mid]}public static int getMin(int[]arr){if(arr == null){System.out.println("參數不合法!");return -1;}return getMin(arr,0,arr.length-1);}public static void main(String[] args) {int arr[] = {2,2,2,2,2,1,2};int mii = getMin(arr);System.out.println(mii);} }一般而言,二分查找的時間復雜度為O(logN),對于這道題而言,大部分情況下時間復雜度為O(logN),只有每次都滿足上述條件5)的時候才需要對數組中所有元素都進行遍歷,因此,這種方法在最壞的情況下的時間復雜度為O(N)。
難點:考慮到不同的多種情況
考慮特殊情況
在不同情況下遞歸時的參數是多少(最小值到底是在左半部分還是右半部分容易弄錯,可以自己模擬一個數組判斷
刪除排序數組的重復元素
一個有序數組,刪除重復出現的元素,使得每個元素只出現一次,返回刪除后數組的新長度,不能使用額外的空間,必須在原地修改輸入數組
考察:雙指針法
用一個快慢指針(數組中的下標模擬指針),初始指針j在i的前面,當沒有重復元素時i指針都遞增,并且將nums[i]的元素變為nums[j](如果有重復元素,j繼續加一,i不變)最后i的位置即長度
尋找數組中心下標
中心下標是一個下標值,它左邊的所有元素相加之和等于右側所有元素相加之和。如果不存在,返回-1,如果有多個,返回最左邊的
public static int privotIndex(int[]nums) { int sum = Arrays.stream(num).sum(); int total = 0; for(int i = 0;i < nums.length;i++) { total += nums[i]; if(total == sum) return i; sum -= nums[i];//注意這個if和sum-=的順序,是類似于total占領的元素與sum占領的元素相等時,二者重合的那個元素下標就是需要返回的下標} return -1; }生成窗口最大值數組
有一個整型數組arr和一個大小為w的窗口從數組的最左邊滑到最右邊,窗口每次向右邊滑一個位置。 例如,數組為[4,3,5,4,3,3,6,7],窗口大小為3時: [4 3 5] 4 3 3 6 7 窗口中最大值為5
4 [3 5 4] 3 3 6 7 窗口中最大值為5
4 3 [5 4 3] 3 6 7 窗口中最大值為5
4 3 5 [4 3 3] 6 7 窗口中最大值為4
4 3 5 4 [3 3 6] 7 窗口中最大值為6
4 3 5 4 3 [3 6 7] 窗口中最大值為7
如果數組長度為n,窗口大小為w,則一共產生n-w+1個窗口的最大值。 請實現一個函數。 輸入:整型數組arr,窗口大小為w。 輸出:一個長度為n-w+1的數組res,res[i]表示每一種窗口狀態下的最大值。 以本題為例,結果應該返回{5,5,5,4,6,7}。
【難度】 尉 ★★☆☆
【解答】 如果數組長度為N,窗口大小為w,如果做出時間復雜度O(N×w)的解法是不能讓面試官滿意的,本題要求面試者想出時間復雜度O(N)的實現。 本題的關鍵在于利用雙端隊列來實現窗口最大值的更新。首先生成雙端隊列qmax,qmax中存放數組arr中的下標。
一定要注意qmax中存放的是索引,如果在比較時要與arr[qmax.peekfirst()]比較
public static int[] getMaxWindow(int[]arr,int w){if(arr == null || w < 1||arr.length < w) return null;LinkedList<Integer> qmax = new LinkedList<>();int index = 0;int[]res = new int[arr.length - w + 1];for (int i = 0; i < arr.length; i++) {while (!qmax.isEmpty() && arr[i] > arr[qmax.peekFirst()])qmax.pollLast();qmax.addLast(i);if(qmax.peekFirst() == i - w)//如果過期qmax.pollFirst();if(i >= w -1)//注意i是從0開始,i為0表示第一個元素res[index++] = arr[qmax.peekFirst()];//注意qmax中存放的是索引而不是具體的元素值}return res;}public static void main(String[] args) {int[]arr = getMaxWindow(new int[]{4,3,5,4,3,3,6,7},3);for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}樹
把一個有序的整數數組放到二叉樹中
//把一個有序的整數數組放到二叉樹中
//思路:取數組中間元素作為根節點,數組分為左右兩部分,對兩部分用遞歸的方法分別構建左右子樹
求最大子樹和
在上圖中,首先遍歷結點-1,這個子樹的最大值為-1。同理,當遍歷到結點 9 時,子樹的最大值為9,當遍歷到結點3時,這個結點與其左右孩子結點值的和(3-1+9=11)大于最大值(9)。因此,此時最大的子樹為以3為根結點的子樹,依此類推,直到遍歷完整棵樹為止。實現代碼如下:
class Btnode{int data;Btnode lchild,rchild;private static int maxSum = Integer.MIN_VALUE;/*求最大子樹*/public static int findMaxSubTree(Btnode root,Btnode maxRoot){if(root == null) return 0;int lmax = findMaxSubTree(root.lchild,maxRoot);int rmax = findMaxSubTree(root.rchild,maxRoot);int sum = rmax + lmax + root.data;if(sum > maxSum){maxSum = sum;maxRoot.data = root.data;//用于確定取得最大子樹的根節點編號}return sum;//返回以root為結點的子樹和} public static Btnode buildTree() {Btnode root = new Btnode();Btnode node1 = new Btnode();Btnode node2 = new Btnode();Btnode node3 = new Btnode();Btnode node4 = new Btnode();root.data = 6;node1.data = 3;node2.data = -7;node3.data = -1;node4.data = 9;root.lchild = node1;root.rchild = node2;node1.lchild = node3;node1.rchild = node4;node2.lchild = node2.rchild = node3.rchild = node3.lchild = node4.rchild = node4.lchild = null;return root; }public static void main(String[] args) {Btnode btnode = new Btnode();Btnode maxNode = new Btnode();btnode = Btnode.buildTree();Btnode.findMaxSubTree(btnode,maxNode);System.out.println("最大子樹和"+maxSum);System.out.println("樹的根節點:"+maxNode.data);} }輸入一棵二元查找樹,將該二元查找樹轉換成一個排序的雙向鏈表。
要求不能創建任何新的結點,只能調整結點的指向,例如下圖。
由于轉換后的雙向鏈表中結點的順序與二叉樹的中序遍歷的順序相同,因此,可以對二叉樹的中序遍歷算法進行修改。通過在中序遍歷的過程中修改結點的指向來轉換成一個排序的雙向鏈表。實現思路如下圖所示:假設當前遍歷的結點為root,root的左子樹已經被轉換為雙向鏈表,如下圖(1)所示。使用兩個變量pHead與pEnd分別指向鏈表的頭結點與尾結點。那么在遍歷root結點時,只需要將root結點的lchild指向pEnd,把pEnd的rchild(右)指向root;此時root結點就被加入到雙向鏈表里了。因此,root變成了雙向鏈表的尾結點。對于所有的結點都可以通過同樣的方法來修改結點的指向。因此,可以采用遞歸的方法來求解,在求解時需要特別注意遞歸的結束條件和邊界情況(例如雙向鏈表為空的時候)。
時間復雜度o(n) 只用了兩個額外變量pHead pEnd來記錄雙向鏈表首尾結點,空間復雜度o(1)
輸入一個整數數組,判斷該數組是否是某二元查找樹的后序遍歷的結果
如果是,那么返回true,否則返回false。例如,數組{1,3,2,5,7,6,4}就是下圖中二叉樹的后序遍歷序列。
二元查找樹的特點:對于任意一個結點,它的左子樹上所有結點的值都小于這個結點的值,它的右子樹上所有結點的值都大于這個結點的值。根據這個特點及二元查找樹后序遍歷的特點可以看出,這個序列的最后一個元素一定是樹的根結點(上圖中的結點4),然后在數組中找到第一個大于根結點4的值5,那么結點5之前的序列(1,3,2)對應的結點一定位于結點4的左子樹上,結點5(包含這個結點)后面的序列一定位于結點4的右子樹上(也就是說,結點5后面的所有值都應該大于或等于4)。對于結點4的左子樹遍歷的序列{1,3,2},以及右子樹的遍歷序列{5,7,6}可以采用同樣的方法來分析,因此,可以通過遞歸方法來實現。
public static boolean IsAfterOrder(int[]arr,int start,int end) {if(arr == null) return false;int root = arr[end];int i,j;for(i = start;i < end;i++)if(arr[i] > root)break;for(j = i;j < end;j++)if(arr[j] < root)return false;boolean isLeft = true;boolean isRight = true;if(i > start)//判斷小于Root的序列是否為查找樹的后序遍歷isLeft = IsAfterOrder(arr,start,i-1);if(j < end)//判斷大于Root的序列是否為查找樹的后序遍歷isRight = IsAfterOrder(arr,i,end);return isLeft && isRight; }public static void main(String[] args) {int arr[] = {1,3,2,5,7,6,4};boolean reasult = IsAfterOrder(arr,0,arr.length-1);if(reasult == true) System.out.println("是");else System.out.println("不是");}}輸出“是”
求x的平方根整數部分
考察:二分法
//題目:求x的平方根整數部分//二分查找public static int binarySearch(int x){int index = -1, l =0,r = x;while (l <= r){System.out.println("l:"+l+"r:"+r);int mid = l + (r - l)/2;if(mid * mid == x){ index=mid;return index;}//也可以用if (mid * mid <= x) {index = mid;l = mid + 1;}其中index = mid;不能少else if(mid * mid < x){ index = mid;l = mid + 1;}else{r = mid - 1;}}return index;}public static void main(String[] args) {for (int i = 1;i < 26;i ++) {System.out.println(binarySearch(i));}}斐波那契數列的三種解法
第一種:暴力遞歸
第二種:去重遞歸(用一個數組保存之前求出來的值)
第三種:雙指針迭代
排列硬幣
總共有n個硬幣,要求第k行必須有k個硬幣,給定一個整數,求可形成的完整階梯行的總行數
如1 2 3 4,數字10可形成的完整階梯行的總行數是4,數字11也是4
法一:
法二:二分法
public static int arrange2(int n){ int low = 0,high = n; while(low <= high){ int mid = (high - low)/2 + low; int cont = ((mid+1)*mid)/2' if(cont == n)return mid; else if(cont > n) high = mid -1; else low = mid+1; } return high; }總結
以上是生活随笔為你收集整理的【数据结构练习习题】java实现版(一)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 【练习】树(Tree, UVa 548)
- 下一篇: 【算法学习笔记】二叉树的基本操作实现和应