LeetCode_脑筋急转弯

小咪咪 2023-02-27 13:48 34阅读 0赞

### 目录: ###

*  292.Nim游戏
 *  319.灯泡开关
 *  777.在LR字符串中叫唤相邻字符
 *  1033.移动石子直到连续
 *  1227.飞机座位分配率
 *  1503.所有蚂蚁掉下来前的最后一刻

# 292.Nim游戏 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]

**思路**

如果堆中石头的数量 nn 不能被 44 整除，那么你总是可以赢得 Nim 游戏的胜利。

**推理**

让我们考虑一些小例子。显而易见的是，如果石头堆中只有一块、两块、或是三块石头，那么在你的回合，你就可以把全部石子拿走，从而在游戏中取胜。而如果就像题目描述那样，堆中恰好有四块石头，你就会失败。因为在这种情况下不管你取走多少石头，总会为你的对手留下几块，使得他可以在游戏中打败你。因此，要想获胜，在你的回合中，必须避免石头堆中的石子数为 4 的情况。

同样地，如果有五块、六块、或是七块石头，你可以控制自己拿取的石头数，总是恰好给你的对手留下四块石头，使他输掉这场比赛。但是如果石头堆里有八块石头，你就不可避免地会输掉，因为不管你从一堆石头中挑出一块、两块还是三块，你的对手都可以选择三块、两块或一块，以确保在再一次轮到你的时候，你会面对四块石头。

显然，它以相同的模式不断重复 n=4,8,12,16,\\dotsn=4,8,12,16,…，基本可以看出是 44 的倍数。

**题解C**

bool canWinNim(int n){
        
        return (n/4==0);
    }

# 319.灯泡开关 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]  
**1 分析**  
1）第j轮的第i个灯泡的状态判断方法：  
将包含本轮在内的对第i个灯泡的所有操作次数做和，记为Sij。  
若Sij为奇数，说明第i个灯泡，经过j轮以后，是亮着的，因为第0轮一定是关闭的。  
同理，若Sij为偶数，说明第i个灯泡，经过j轮以后，是关闭的。

所以问题转变为：  
经过n轮，第i个灯泡被操作了奇数次还是偶数次？奇数次则最后是亮的，偶数次则最后是关闭的。

**2）观察：**  
第j轮操作的灯泡的位置，一定是j的倍数。咱们反向观察一下：

第1个灯泡在什么时候会被操作？第1轮  
第10个灯泡在什么时候会被操作？第1轮，第2轮，第5轮，第10轮  
第20个灯泡在什么时候会被操作？第1轮，第2轮，第4轮，第5轮，第10轮，第20轮

说到这里，会立马发现：第 i 个灯泡只有在第 k 轮会被操作，而 k 一定是 i 的因数。并且 n>=k。所以如果一个数的因数的个数为奇数个，那么它最后一定是亮的，否则是关闭的。  
那么问题又转变了：

什么数的因数的个数是奇数个？  
答案是完全平方数。

2 为什么完全平方数的因数的个数是奇数个？  
设P,A,B 为正整数，如果 P=A\*B，则A和B为P的因数。  
P的因数A和B总是成对出现。也就是说他们总是一起为 P 的因数个数做贡献。但是如果他们相等呢？这个时候他们一起只会为因数的个数贡献 1。

其次，P=A\*A，这种情况对于P来说最多只能出现1次，而这种情况只可能出现在完全平方数中。  
所以对于正整数而言，只有完全平方数的因数的个数是奇数个。

综上所述，所以每个完全平方数就是答案

**还可以这样推导：**  
对于数k，第i轮被拨一下的条件是k%i==0  
所有数k被拨的次数是k的约束的个数  
若k=p\_1^x p\_2^y p\_3^z … , 其中p\_i为素数，则约数的个数f(k)= (1+x)(1+y)(1+z).  
第k个灯亮意味着f(k)为奇数，根据推论3可知，其中的x,y,z…都必须为偶数。  
回看，k=p\_1^x p\_2^y p\_3^z … , 说明k是个完全平方数

**题解C**

int bulbSwitch(int n){
        
        return (int)sqrt(n);
    }

# 777.在LR字符串中叫唤相邻字符 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 2]  
**思路**

将 ‘L’，‘R’ 分别理解为一个队伍中面向左和面向右的人，‘X’ 理解为队伍中的空挡。可以问自己一个问题，一次移动操作之后有什么是保持不变的？ 这是状态转换问题中一个很常见的思路。

**算法**

这道题的 转换不变性 在于字符串中的 ‘L’ 和 ‘R’ 是不会互相穿插的，也就是队伍中的人在移动过程中是不能穿过人的。这意味着开始和结束的字符串如果只看 ‘L’ 和 ‘R’ 的话是一模一样的。

除此之外，第 n 个 ‘L’ 不可能移动到初始位置的右边，第 n 个 ‘R’ 不可能移动到初始位置的左边，我们把这个特性称为 “可到达性“。

根据 转换不变性 和 可到达性，在算法中可以分别检查这两个性质是否满足。如果都满足，则返回 True，否则返回 False。

**题解Java**

class Solution {
        
        public boolean canTransform(String start, String end) {
        
            if (!start.replace("X", "").equals(end.replace("X", "")))
                return false;
    
            int t = 0;
            for (int i = 0; i < start.length(); ++i)
                if (start.charAt(i) == 'L') {
        
                    while (end.charAt(t) != 'L') t++;
                    if (i < t++) return false; //发现end中L往右移了
                }
    
            t = 0;
            for (int i = 0; i < start.length(); ++i)
                if (start.charAt(i) == 'R') {
        
                    while (end.charAt(t) != 'R') t++;
                    if (i > t++) return false; //发现end中R往左移了
                }
    
            return true;
        }
    }

# 1033.移动石子直到连续 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 3]  
思路：  
题目看着很绕，其实很简单，首先排序，排序并不会改变结果，但是我们写起来更方便一点，然后重新赋值abc

a最小,c最大，因为只能拿两边的石头往中间放，所以最大情况就是一步一步挪，那么就是c-a-2，最小情况多重情况讨论即可

三个紧贴着 c-a=2 返回0  
其中有两个紧贴着 返回1  
其中有两个中间空了一格 返回 1  
最小移动次数最大是2 就是两边分别往中间放

**题解Java**

class Solution {
        
        public int[] numMovesStones(int a, int b, int c) {
        
            int[] arr = new int[]{
        a, b, c};
            Arrays.sort(arr);
            a=arr[0];
            b=arr[1];
            c=arr[2];
            
            int min = 0;
            if (c - a == 2) min = 0;
            else if (b - a == 1 || c - b == 1) min = 1;
            else if (b - a == 2 || c - b == 2) min = 1;
            else min = 2;
            return new int[]{
        min, c - a - 2};
        }
    }

# 1227.飞机座位分配率 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 4]  
**思路**  
设dp\[i\]为第i个乘客坐在自己的座位上的概率，  
初始化dp\[1\]=1;dp\[2\]=0.5;

当i=3时:  
若第一个人选择第一个座位，后边的人的椅子没有被占用，按照正常顺序，第3个人肯定能坐到第3个位置，这个概率是1/3；  
若第一个人选择第二个位置，第二个人发现自己的椅子被占用，他有两个位置可选，只有选择第一个位置，第三个人才能坐到自己的位置，根据概率乘法原则，这个概率是1/3 × 1/2;  
只有这两种情况，第3个人才能坐到第三个位置  
所以dp\[3\]=1/3+1/3×1/2  
=1/3×(1+1/2)  
=1/3×(dp\[1\]+dp\[2\])

以此类推，可以推出来：  
dp\[i\]=(1/i)×(dp\[1\]+dp\[2\]+…+dp\[i-1\])  
这就是状态转移方程

所以说实际上只要n>1,那么结果必是1/2！

**题解Java**

class Solution {
        
        public double nthPersonGetsNthSeat(int n) {
        
             if (n == 1) {
        
                 return 1.0;
             }
    
            double [] dp=new double[n+1];//从下标1开始使用
            dp[2]=0.5;
    
            double sum_dp=1.5;
            for(int i=3;i<=n;i++){
        
                dp[i]=(1.0/(double)i)*sum_dp;
                sum_dp+=dp[i];
            }
    
            return dp[n];
        }
    }

# 1503.所有蚂蚁掉下来前的最后一刻 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 5]

**思路**  
两个蚂蚁相撞之后会互相调头，其实只要想成如果每只蚂蚁都长得一模一样，那么是不是蚂蚁碰撞的调头 就等于 穿透了？

知道了这一点，那么就可以直接让蚂蚁直接穿透爬行就好了

那么题目就变成了求单只最晚落地的蚂蚁，与碰撞无关

**题解Java\_1**

class Solution {
        
        public int getLastMoment(int n, int[] left, int[] right) {
        
            int max = -1;
            for(int i = 0; i < left.length;i++){
        
                max = Math.max(max,left[i]);
            }
            for(int i = 0; i < right.length;i++){
        
                max = Math.max(max,n-right[i]);
            }
            return max;
        }
    }

**题解Java\_2**

class Solution {
        
        public int getLastMoment(int n, int[] left, int[] right) {
        
            int leftMax = Integer.MIN_VALUE;
            int rightMin = Integer.MAX_VALUE;
            
            // 往右走的取最小值
            for (int item : right) {
        
                if (rightMin > item) {
        
                    rightMin = item;
                }
            }
    
            // 往左走的取最大值
            for (int item : left) {
        
                if (leftMax < item) {
        
                    leftMax = item;
                }
            }
            return Math.max(leftMax, n - rightMin);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]: /images/20230209/8c4db0065d1e47619aec2c2c2d48d6aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]: /images/20230209/e6f0f0d2569d4987af3cfd0f27dee689.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 2]: /images/20230209/e92fb431952346aa861f6a34939ee909.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200718103925271.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200718153044449.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200718160924811.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2,size_16,color_FFFFFF,t_70