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];
    }
};