算法面试题（四）

1. 问题：有一对兔子，从出生第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月也生一对兔子，假如兔子都不死，问每个月兔子的总数是多少？这个一个菲波拉契数列问题。

package test; /** * @author cz * @date 2018年7月29日 */ public class Test10 { //月 1 2 3 4 5 6 7 8 9 10 11 12 //对 1 1 2 3 5 8 13 21 34 55 89 144 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; } }