leetcode刷題45——猜數字大小系列

1.猜數字大小

猜數字遊戲的規則如下：

每輪遊戲，我都會從 1 到 n 随機選擇一個數字。 請你猜選出的是哪個數字。

如果你猜錯了，我會告訴你，你猜測的數字比我選出的數字是大了還是小了。你可以通過調用一個預先定義好的接口 int guess(int num) 來擷取猜測結果，傳回值一共有 3 種可能的情況（-1，1 或 0）：

-1：我選出的數字比你猜的數字小 pick < num

1：我選出的數字比你猜的數字大 pick > num

0：我選出的數字和你猜的數字一樣。恭喜！你猜對了！pick == num

傳回我選出的數字。

考察知識點：二分查找

class Solution {
public:
    int guessNumber(int n) {
        int l=1,h=n;
        while(l<h)
        {
            int m=l+(h-l)/2;
            if(guess(m)==0) return m;
            else if(guess(m)==-1)   h=m-1;
            else l=m+1;
        }
        return l;
    }
};
           

2.猜數字大小 II

我們正在玩一個猜數遊戲，遊戲規則如下：

我從 1 到 n 之間選擇一個數字，你來猜我選了哪個數字。每次你猜錯了，我都會告訴你，我選的數字比你的大了或者小了。然而，當你猜了數字 x 并且猜錯了的時候，你需要支付金額為 x 的現金。直到你猜到我選的數字，你才算赢得了這個遊戲。

考察知識點：動态規劃

解題思路：dp[i][j]:在[i,j]之間猜數最少花費

枚舉先猜k，則花費k，剩下區間[i,k-1]和[k+1,j]，因為會告訴你大了或小了，是以肯定隻選擇一個，又因為我們要保證猜對，是以取max{dp[i][k-1],dp[k+1][j]} ，即有：

dp[i][j]=min(dp[i][j], k+max(dp[i][k-1],dp[k+1][j]));

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n+2,vector<int>(n+2)); //*
        for(int j=1;j<=n;++j)
        {
            for(int i=j-1;i>=1;--i)
            {
                dp[i][j]=n*n; //*
                for(int k=i;k<=j;++k)
                {
                    dp[i][j]=min(dp[i][j],k+max(dp[i][k-1],dp[k+1][j]));
                }
            }
        }
        return dp[1][n];
    }
};