【LeetCode】 374. 猜数字大小骚气的猴子算法打死都找不着系列 JAVA

淩亂°似流年 2021-06-10 20:38 333阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 猴子排序 ###

猴子排序是一种什么样子的排序呢？

猴子排序引用了无限猴子定理：`即一只猴子随机不停的敲击键盘，如果时间足够长，那么它总有可能会打出特定的文本，比如莎士比亚全集？，算法通过不停的随机排列数组，直到数组有序`

这个真实的含义就是把一个无序的数组进行乱排序，然后看其是否会有序，这是个概率性事件，有可能一次之后就有序了，也有可能很多次后依然无序。

实现方法如下：

1.  定义数组
2.  数组随机
3.  检验数组是否有序，无序继续，有序了就停止

### 猴子算法 ###

当然这个算法也可能不存在哈，我给它起的名字，就叫猴子算法，也是随机寻找的意思

所以我想的就是，随机数找这个数字，这样就完事儿了

虽然超出时间限制，但是也很好玩

### 骚气的猴子算法代码 ###

/* 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 num = 0;
            Random random = new Random();
            while(guess(num) != 0){ 
                num = random.nextInt(n) + 1;
            }
            return num;
        }
    }

### 正儿八经的二分查找代码 ###

/* 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 res = 0;
            int left = 1;
            int right = n;
            while(left <= right){ 
                res = left + (right - left) / 2;
                int flag = guess(res);
                if(flag == 0) return res;
                if(flag == -1) right = res - 1;
                if(flag == 1) left = res + 1;
            }
            return res;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/guess-number-higher-or-lower/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/c32703467f784d9a9d36052cca73c255.png