1.如何僅用遞歸函數和棧操作逆序一個棧
一個棧依次壓入1、2、3、4、5，那么從棧頂到棧底分別是5、4、3、2、1.將這個棧轉置后，從棧頂到棧底為1、2、3、4、5，也就是實現棧中元素的逆序，但是只能用遞歸函數來實現，不用其他數據結構

首先，思考如何使用遞歸方法不使用輔助存儲得到棧底元素：

public static int getAndRemoveLast(Stack<Integer> stack){int result = stack.pop();if(stack.isEmpty()){return result;}else{int last = getAndRemoveLast(Stack);stack.push(result);return last;} }接下來即水到渠成了：
public static void reverse(Stack<Integer> stack){if(stack.isEmpty()){return;}int i = getAndRemoveLast(stack);reverse(stack);stack.push; }

2.給定一個字符串str，str表示一個表達式，其中只可能有整數、加減乘除符號和左右括號，返回公式的計算結果，例如：str = "48*((70-65)-43)+8*1",返回-1816；str="3+1*4",返回7；str="3+(1*4)",返回7
說明：可以認為給定的字符串一定是正確的表達式，即不需要對str做公式有效性的檢查；如果是負數，就需要用括號括起來，比如"4*(-3)",但如果負數作為公式的開頭或括號部分的開頭，則可以沒有括號，比如"-3*4"和"（-3*4）"都是合法的；不考慮計算過程發生溢出的情況
public static int getNum(LinkedList<String> que){int res = 0;boolean add = true;String cur = null;int num = 0;while(!que.isEmpty()){cur = que.pollFirst();if(cur.equals("+")){add = true;}else if(cur.equals("-")){add = false;}else{num = Integer.valueOf(cur);res += add ? num : (-num);}}return res; } public static int getValue(String str){return value(str.toCharArray(), 0)[0]; } public static void addNum(LinkedList<String> que, int num){if(!que.isEmpty()){int cur = 0;String top = que.pollLast();if(top.equals("+") || top.equals("-")){que.addLast(top);}else{cur = Integer.valueOf(que.pollLast);num = top.equals("*") ? (cur * num) : (cur/num);}}que.addLast(String.valueOf(num)); } public static int[] value(char[] str, int i){LinkedList<String> que = new LinkedList<String>();int pre = 0;int[] bra = null;while(i < str.length && str[i] != ')'){if(str[i] >= '0' && str[i] <= '9'){pre = pre * 10 + str[i++] - '0';}else if（str[i] != '('）{addNum(que, pre);que.addLast(String.valueOf(str[i++]));pre = 0;}else{//遞歸小括號bra = value(str, i + 1);pre = bra[0];i = bra[i] + 1;}}addNum(que,pre);return new int[] {getNum(que), i}; }

3.生成窗口最大值數組
有一個整型數組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}

public static int[] getMaxWindow(int[] arr,int w){if(arr == null || w < 1 || arr.length < w){return null;}LinkedList<Integer> qmax = new LinkedList<Integer>();int[] res = new int[arr.length - w + 1];int index = 0;for(int i = 0; i < arr.length; i++){while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){qmax.pollLast();}qmax.addLast(i);if(qmax.peekFirst() == i - w){qmax.pollFirst();}if(i >= w - i){res[index++] = arr[qmax.peekFirst()];}}return res; }

總結

以上是生活随笔為你收集整理的有关递归的三道算法题总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。