演算法面試題(四)
1. 問題:有一對兔子,從出生第3個月起每個月都生一對兔子,小兔子長到第三個月後每個月也生一對兔子,假如兔子都不死,問每個月兔子的總數是多少?這個一個菲波拉契數列問題。
package test; /** * @author cz * @date 2018年7月29日 */ public class Test10 { //月123456789101112 //對1123581321345589144 public static void main(String[] args) { System.out.println("第1個月:"+1+"對"); System.out.println("第2個月:"+1+"對"); //記錄月 int M=24; // int f1=1,f2=1; int f; for(int i=3;i<=M;i++){ f=f2; f2=f1+f2; f1=f; System.out.println("第"+i+"個月:"+f2+"對"); } } }
2.已知有一個數列,f(0)=1,f(1)=4,f(n+2)=2*f(n+1)+f(n);求f(10).(提示:遞迴只能往已知方向走)
package test; /** * @author cz * @date 2018年7月29日 */ public class Test11 { public static void main(String[] args) { System.out.println(func(10)); } public static int func(int n){ if(n==0) return 1; else if(n==1) return 4; else{ return 2*func(n-1) + func(n-2); //return func(n+2)-2*func(n+1); } } }
3.求1-10之間整數的階乘
package test; import java.util.HashMap; public class Test12 { public static void main(String[] args) { for(long i=1;i<=10;i++){ System.out.println(i+"!="+fact(i)); } } //階乘方法 public static long fact(long n){ if(n==0 || n==1) return 1; else if(n<0) return 1; else { return n*fact(n-1); } } }
4.輸入一個只包含加減乖除和括號的合法表示式,求表示式的值。其中除表示整除。
輸入格式 輸入一行,包含一個表示式。 輸出格式 輸出這個表示式的值。 樣例輸入 1-2+3*(4-5) 樣例輸出 -4 資料規模和約定 表示式長度不超過100,表示式運算合法且運算過程都在int內進行。
解題思路:
1,初始化兩個棧:運算子棧S1和儲存中間結果的棧S2; 2,從左至右掃描中綴表示式; 3,遇到運算元時,將其壓入S2,這裡由於運算數可能大於10,所以如果數字後面一個符號是運算子,則將‘#’入S2棧充當分割線; 4, 遇到運算子時有三種情況: (4-1) 三種情況下直接入S1棧①S1為空②運算子為‘(’③運算子優先順序比S1棧頂運算子的高; (4-2)如果右括號“)”,則依次彈出S1棧頂的運算子,並壓入S2,直到遇到左括號為止,此時將這一對括號丟棄; (4-3) 若運算子優先順序小於或等於S1棧頂運算子的優先順序,則依次彈出S1棧頂元素,直到運算子的優先順序大於S1棧頂運算子優先順序; 5, 重複步驟(2)至(5),直到表示式的最右邊; 6,將S1中剩餘的運算子依次彈出並壓入S2; 7,依次彈出S2中的元素並輸出,結果的逆序即為中綴表示式對應的字尾表示式
解題
import java.util.Scanner; import java.util.Stack; public class Main{ public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); Stack<Integer> nums = new Stack<Integer>(); // 儲存數字 Stack<Character> opes = new Stack<Character>(); // 儲存操作符 String string = scanner.nextLine(); int n = 0; // 儲存每一個數字 char[] cs = string.toCharArray(); for (int i = 0; i < cs.length; i++) { char temp = cs[i]; if (Character.isDigit(cs[i])) { n = 10 * n + Integer.parseInt(String.valueOf(cs[i])); // 大於10的數字儲存 } else { if (n != 0) { nums.push(n); n = 0; } if (temp == '(') { opes.push(temp); } else if (temp == ')') { while (opes.peek() != '(') { // 括號裡面運算完 int t = cal(nums.pop(), nums.pop(), opes.pop()); nums.push(t); } opes.pop(); } else if (isType(temp) > 0) { if (opes.isEmpty()) { // 棧為空直接入棧 opes.push(temp); } else { // 若棧頂元素優先順序大於或等於要入棧的元素,將棧頂元素彈出並計算,然後入棧 if (isType(opes.peek()) >= isType(temp)) { int t = cal(nums.pop(), nums.pop(), opes.pop()); nums.push(t); } opes.push(temp); } } } } // 最後一個字元若是數字,未入棧 if (n != 0) { nums.push(n); } while (!opes.isEmpty()) { int t = cal(nums.pop(), nums.pop(), opes.pop()); nums.push(t); } System.out.println(nums.pop()); } // 返回的是運算子的優先順序,數字和()不需要考慮 public static int isType(char c) { if (c == '+' || c == '-') { return 1; } else if (c == '*' || c == '/') { return 2; } else { return 0; } } // 運算次序是反的,跟入棧出棧次序有關 public static int cal(int m, int n, char c) { int sum = -987654321; if (c == '+') { sum = n + m; } else if (c == '-') { sum = n - m; } else if (c == '*') { sum = n * m; } else if (c == '/') { sum = n / m; } return sum; } }
5.用兩個棧實現一個佇列,完成佇列的push和pop,佇列中的元素為int型別。
import java.util.Stack; //使用棧記得引用java.util,Stack包 public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); //入棧函式 public void push(int num) { stack1.push(num);//要往棧中壓入什麼就直接用棧的push方法就好了 } //出棧函式 public int pop() { Integer re=null; if(!stack2.empty()){// 如果棧2不是空的,那麼把最上面那個取出來 re=stack2.pop(); }else{ //如果棧2是空的,就把棧1裡的數一個個取出來,放到棧2裡 while(!stack1.empty()){ re=stack1.pop(); stack2.push(re); } //棧2裡有數之後,再次把裡面的數取出來 if(!stack2.empty()){ re=stack2.pop(); } } return re; } }
原文釋出時間為:2018-09-18
本文作者:IT技術之道