淘先锋技术网

首页 1 2 3 4 5 6 7

292.Nim游戏

在这里插入图片描述

思路

如果堆中石头的数量 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.灯泡开关

在这里插入图片描述
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字符串中叫唤相邻字符

在这里插入图片描述
思路

将 ‘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.移动石子直到连续

在这里插入图片描述
思路:
题目看着很绕,其实很简单,首先排序,排序并不会改变结果,但是我们写起来更方便一点,然后重新赋值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.飞机座位分配率

在这里插入图片描述
思路
设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.所有蚂蚁掉下来前的最后一刻

在这里插入图片描述

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

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

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

题解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);
    }
}