偶然在別人公眾號看到一篇關於猜數字大小的題目，剛好是 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;
}
};複雜度分析：
Ⅰ-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;
}
};複雜度分析：
Ⅰ-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;
}
};複雜度分析：
猜數字大小 Ⅱ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);
}
};複雜度分析：
Ⅱ-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 中直接有，就不用遞歸了，雖然效率變高了，實際上複雜度還是：
上面這2種寫法在 Leetcode 上提交的最後都會因為 超出時間限制 而失敗，無非前一個是在 n=18 後面一個是在 n=115, 時間複雜度並沒有明顯降下來，所以還是需要換個思路
Ⅱ-3最後當然離不開動態規劃，我不太精通這個，但是看到一篇解析的很清楚的文章推薦給大家
https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/solution/dong-tai-gui-hua-c-you-tu-jie-by-zhang-xiao-tong-2/
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];
}
};複雜度分析：