兩道算法題-打家劫舍-逆波蘭表達式

打家劫舍

一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之内能夠偷竊到的最高金額。

示例

輸入：[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();
}