偶然在别人公众号看到一篇关于猜数字大小的题目，刚好是 LeetCode 上的题目，在 LeetCode 上又刚好看到一道很接近的扩展题，放一起整理一下
猜数字大小 Ⅰ
LeetCode 374 题
猜数字游戏的规则如下：
- 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
- 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
-1：我选出的数字比你猜的数字小pick<num1：我选出的数字比你猜的数字大pick>num0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
示例 1：
# 1 <= n <= 2^31 - 1
# 1 <= pick <= n
输入：n = 10, pick = 6
输出：6
Ⅰ-1
提供了一个 int guess(int num) 的接口来判断猜测结果，所以下意识的想到的是暴力
class Solution {
public:
int guessNumber(int n) {
for (int i = 1; i < n; i++)
if (guess(i) == 0)
return i;
return n;
}
};
复杂度分析：
- 时间复杂度：
O(n) - 空间复杂度：
O(1)
Ⅰ-2
但是从头开始一个个试肯定不是最优解，其次很容易想到的方法就是 二分查找
class Solution {
public:
int guessNumber(int n) {
int low = 1;
int high = n;
while (low <= high) {
int mid = low + (high - low) / 2;
int res = guess(mid);
if (res == 0)
return mid;
else if (res < 0)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
};
复杂度分析：
- 时间复杂度：
O( log2(n) ) - 空间复杂度：
O(1)
Ⅰ-3
看了一下答案，官方还给了一个 三分查找 的方法
在二分查找中，我们选择中间元素作为分隔点。而在三分查找中，我们选择两个分隔点（比方记作
m1和m2），那么给定范围会被分成3个相等长度的部分。如果答案num比m1小，那么我们对m1左边的区间做三分查找。如果num比m2大，那么我们在m2右边的区域进行三分查找。否则我们在m1和m2中间区域进行三分查找。
class Solution {
public:
int guessNumber(int n) {
int low = 1;
int high = n;
while (low <= high) {
int mid1 = low + (high - low) / 3;
int mid2 = high - (high - low) / 3;
int res1 = guess(mid1);
int res2 = guess(mid2);
if (res1 == 0)
return mid1;
if (res2 == 0)
return mid2;
else if (res1 < 0)
high = mid1 - 1;
else if (res2 > 0)
low = mid2 + 1;
else {
low = mid1 + 1;
high = mid2 - 1;
}
}
return -1;
}
};
复杂度分析：
- 时间复杂度：
O( log3(n) ) - 空间复杂度：
O(1)
猜数字大小 Ⅱ
LeetCode 375 题
我们正在玩一个猜数游戏，游戏规则如下：
我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。
每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。
然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。
示例:
n = 10, 我选择了8.
第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。
游戏结束。8 就是我选的数字。
你最终要支付 5 + 7 + 9 = 21 块钱。
给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
仔细体会一下这道题，这道题 不是找出如何最快猜出选中的数的方法，而是一个策略的权衡，在最坏的情况下最便宜猜出选中的数
比方说：
n=5
1 2 3 4 5
# 假设答案是 5
根据二分法，如果我们一开始猜 3 ，那么我们下一次肯定猜 4 ，最终总代价为 4+3=7。
而实际上，我们只要先猜 4， 对了和小了的总代价就是 4，猜大了，在猜 2，这时候不管大了小了还是对了，都定位出真正的数字，此时的总代价是 6， 而为了保证赢，最小的总代价就是 6
结合上面的介绍，实际上就是在 (1,n) 范围内考虑猜中数字的最坏情况下的最小代价
当我们从 (1,n) 中随机取个数字 x, 如果没有猜中，则根据结果，在 (1,x-1) 或者 (x+1,n) 的范围继续猜数字，考虑到最坏情况，所以总体最小代价是：
cost(1,n) = x + max( cost(1,x-1), cost(x+1,n) )
Ⅱ-1
根据这个逻辑，直接暴力递归
class Solution {
public:
int cost(int left, int right) {
if (left >= right)
return 0;
int res = INT_MAX;
for (int i = left; i<=right; i++) {
int tmp = i + max( cost(left, i-1), cost(i+1, right) );
res = min(tmp, res) ;
}
return res;
}
int getMoneyAmount(int n) {
return cost(1,n);
}
};
复杂度分析：
- 时间复杂度：
O(n!) - 空间复杂度：
O(n)
Ⅱ-2
暴力递归确实可以解决这个问题，但是递归会导致出现很多重复的计算，所以我们需要对结果进行保存，防止重复计算
#include <map>
#include <algorithm>
using namespace std;
class Solution {
public:
int cost(map<string, int> &record, int left, int right) {
if (left >= right)
return 0;
string key = to_string(left) + "-" +to_string(right);
map<string, int>::iterator find_res = record.find(key);
if ( find_res != record.end())
return find_res->second;
int res = INT_MAX;
for (int i = left; i<=right; i++) {
int tmp = i + max( cost(record, left, i-1), cost(record, i+1, right) );
res = min(tmp, res) ;
}
record[key] = res;
return res;
}
int getMoneyAmount(int n) {
map<string, int> record = {};
return cost(record, 1, n);
}
};
我用 map 存了计算的结果, 在计算的时候，如果 map 中直接有，就不用递归了，虽然效率变高了，实际上复杂度还是：
- 时间复杂度：
O(n!) - 空间复杂度：
O(n)
上面这2种写法在 Leetcode 上提交的最后都会因为 超出时间限制 而失败，无非前一个是在 n=18 后面一个是在 n=115, 时间复杂度并没有明显降下来，所以还是需要换个思路
Ⅱ-3
最后当然离不开动态规划，我不太精通这个，但是看到一篇解析的很清楚的文章推荐给大家
建议直接参考别人的解题思路~
class Solution {
public:
int getMoneyAmount(int n) {
if(n==1)
return 0;
int dp[n+1][n+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
dp[i][j]=INT_MAX;
}
}
for(int i=0;i<=n;i++){
dp[i][i]=0;
}
for(int j=2;j<=n;j++){
for(int i=j-1;i>=1;i--){
for(int k=i+1;k<=j-1;k++){
dp[i][j]=min(k+max(dp[i][k-1],dp[k+1][j]),dp[i][j]);
}
dp[i][j]=min(dp[i][j],i+dp[i+1][j]);
dp[i][j]=min(dp[i][j],j+dp[i][j-1]);
}
}
return dp[1][n];
}
};
复杂度分析：
- 时间复杂度：
O(n^3) - 空间复杂度：
O(n^2)