算法题（奇安信面试）

奇安信-8.16

1，老板一共需要给某个员工发奖金n元，可以选择一次发1元，也可以选择一次发2元…老板也可以一次发n元。请问老板给这位员工发放完n元奖金的共有多少种方法？

class Solution { public int waysToStep(int n) { if(n == 1) return 1; if(n == 2) return 2; if(n == 3) return 4; long [] dp = new long[n + 1]; dp[1] = 1; dp[2] = 2; dp[3] = 4; for(int i =4;i <= n;i ++){ dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3])%1000000007; } return (int)dp[n]; } } 

2，撤销/恢复操作具有广泛的用途，比如word文档中输入一个单词，可以点撤销，然后可以再恢复。
编程实现如下功能：从标准的输入读取到一个字符串，字符串可以包含0个或者多个单词，单词以空格或者tab分隔。如果遇到"undo"字符串表示“撤销”操作，前一个字符串被撤销掉；如果遇到"redo"字符串，表示恢复刚才撤销掉的字符串。
例如：输入字符串"hell0 undo redo world"，对字符串中的undo和redo处理后，最终输出的结果是"hello world"

public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] ss = sc.nextLine().trim().split(" "); String ans = res(ss); System.out.println(ans); } public static String res(String[] ss){ int redo = 0; Stack<String> stack = new Stack<>(); StringBuilder sb = new StringBuilder(); for (int i = ss.length-1; i >=0; i--) { if(stack.peek().equals("redo")){ redo++; } else if(stack.peek().equals("undo")){ if(redo>0) redo--; else i--; }else stack.push(ss[i]); } while (!stack.empty()){ sb.append(stack.pop()); sb.append(" "); } return sb.toString().trim(); } 

或者：

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] strs = sc.nextLine().split("\\s+"); System.out.println(Cal(strs)); } public static String Cal (String[] strs) { Stack<String> stack1 = new Stack<String> (); Stack<String> stack2 = new Stack<String> (); for (String str:strs){ if (str.equals("undo")) { if (stack2.size()>0) { stack1.push(stack2.pop()); } } else if (str.equals("redo")) { if (stack1.size()>0) { stack2.push(stack1.pop()); } } else { stack2.push(str); } } String[] s = new String[stack2.size()]; int i = stack2.size()-1; while (stack2.size()>0) { s[i] = stack2.pop(); --i; } StringBuilder sb = new StringBuilder(); for (int j = 0; j<s.length; ++j) { sb.append(s[j]); if (j < s.length-1) { sb.append(" "); } } return sb.toString(); } } 

本文地址：https://blog.csdn.net/chen772209/article/details/108039480