两道算法题-打家劫舍-逆波兰表达式

打家劫舍

一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

 

思路

标签：动态规划
动态规划方程：dp[n] = MAX( dp[n-1], dp[n-2] + num )
由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 房屋可盗窃的最大值，要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值
举例来说：1 号房间可盗窃最大值为 333 即为 dp[1]=3，2 号房间可盗窃最大值为 444 即为 dp[2]=4，3 号房间自身的值为 222 即为 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5，3 号房间可盗窃最大值为 555
    时间复杂度：O(n)O(n)O(n)，nnn 为数组长度

public int rob(int[] nums) {
	int[] dp = new int[nums.length + 1];
	dp[0] = 0;
	dp[1] = nums[0];
	for (int i = 2; i < dp.length; i++) {
		dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
	}
	return dp[nums.length];
}

 

逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

示例

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

public static int evalRPN(String[] tokens) {
	Deque<Integer> stack = new ArrayDeque<>();
	for (String str : tokens) {
		switch (str) {
		case "+":
			stack.push(stack.pop() + stack.pop());
			break;
		case "-":
			Integer pop = stack.pop();
			Integer pop1 = stack.pop();
			stack.push(pop1 - pop);
			break;
		case "*":
			stack.push(stack.pop() * stack.pop());
			break;
		case "/":
			Integer pop3 = stack.pop();
			Integer pop4 = stack.pop();
			stack.push(pop4 / pop3);
			break;
		default:
			stack.push(Integer.parseInt(str));
			break;
		}
	}
	return stack.pop();
}