Sunday, November 18, 2018

374. Guess Number Higher or Lower, 375. Guess Number Higher or Lower II

374Guess Number Higher or Lower
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
----------------------

/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            int rt = guess(mid);
            if (rt == 0) return mid;
            if (rt > 0) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

375Guess Number Higher or Lower II
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
-----------------------------
题意有点绕:找一个花费最小的通解
brute force的算法是枚举所有的可能性,找出最小(最优)的解。
给定[start, end], 猜i点之后的cost是cost[i] = i + Math.max(cost[start, i - end], cost[i + 1, end]), 取2者中间最大是因为不能确定最终结果在左还是在右
ref: https://leetcode.com/problems/guess-number-higher-or-lower-ii/solution/

Solution #1 DP 是对brute force的优化
重点:这题的2维DP是按对角线来填充,因为[len]是基于[len - i]...[len - 1]
以后写dp要理解其本身的通项公式
O(n^3)
class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];
        
        for (int len = 2; len <= n; len++) {
            for (int start = 1; start < n - len + 2; start++) {
                int min = Integer.MAX_VALUE;
                for (int i = start; i <= start + len - 1; i++) {
                    
                    int v = 0;
                    if (i == start + len - 1) {
                        v = i + dp[start][i - 1];
                    }else 
                        v = i + Math.max(dp[start][i - 1], dp[i + 1][start + len - 1]);
                    
                    min = Math.min(min, v);
                }
                dp[start][start + len - 1] = min;
            }
        }
        
        return dp[1][n];
    }
}
进一步优化: [start, (start + end) / 2] 永远比 [(start + end) / 2, end]小,所以只需计算后半部分。BigO不变

No comments:

Post a Comment