目錄:

• 292.Nim游戲
• 319.燈泡開(kāi)關(guān)
• 777.在LR字符串中叫喚相鄰字符
• 1033.移動(dòng)石子直到連續(xù)
• 1227.飛機(jī)座位分配率
• 1503.所有螞蟻掉下來(lái)前的最后一刻

292.Nim游戲

思路

如果堆中石頭的數(shù)量 nn 不能被 44 整除，那么你總是可以贏得 Nim 游戲的勝利。

推理

讓我們考慮一些小例子。顯而易見(jiàn)的是，如果石頭堆中只有一塊、兩塊、或是三塊石頭，那么在你的回合，你就可以把全部石子拿走，從而在游戲中取勝。而如果就像題目描述那樣，堆中恰好有四塊石頭，你就會(huì)失敗。因?yàn)樵谶@種情況下不管你取走多少石頭，總會(huì)為你的對(duì)手留下幾塊，使得他可以在游戲中打敗你。因此，要想獲勝，在你的回合中，必須避免石頭堆中的石子數(shù)為 4 的情況。

同樣地，如果有五塊、六塊、或是七塊石頭，你可以控制自己拿取的石頭數(shù)，總是恰好給你的對(duì)手留下四塊石頭，使他輸?shù)暨@場(chǎng)比賽。但是如果石頭堆里有八塊石頭，你就不可避免地會(huì)輸?shù)?#xff0c;因?yàn)椴还苣銖囊欢咽^中挑出一塊、兩塊還是三塊，你的對(duì)手都可以選擇三塊、兩塊或一塊，以確保在再一次輪到你的時(shí)候，你會(huì)面對(duì)四塊石頭。

顯然，它以相同的模式不斷重復(fù) n=4,8,12,16,\dotsn=4,8,12,16,…，基本可以看出是 44 的倍數(shù)。

題解C

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

319.燈泡開(kāi)關(guān)

1 分析
1）第j輪的第i個(gè)燈泡的狀態(tài)判斷方法：
將包含本輪在內(nèi)的對(duì)第i個(gè)燈泡的所有操作次數(shù)做和，記為Sij。
若Sij為奇數(shù)，說(shuō)明第i個(gè)燈泡，經(jīng)過(guò)j輪以后，是亮著的，因?yàn)榈?輪一定是關(guān)閉的。
同理，若Sij為偶數(shù)，說(shuō)明第i個(gè)燈泡，經(jīng)過(guò)j輪以后，是關(guān)閉的。

所以問(wèn)題轉(zhuǎn)變?yōu)?#xff1a;
經(jīng)過(guò)n輪，第i個(gè)燈泡被操作了奇數(shù)次還是偶數(shù)次？奇數(shù)次則最后是亮的，偶數(shù)次則最后是關(guān)閉的。

2）觀察：
第j輪操作的燈泡的位置，一定是j的倍數(shù)。咱們反向觀察一下：

第1個(gè)燈泡在什么時(shí)候會(huì)被操作？第1輪
第10個(gè)燈泡在什么時(shí)候會(huì)被操作？第1輪，第2輪，第5輪，第10輪
第20個(gè)燈泡在什么時(shí)候會(huì)被操作？第1輪，第2輪，第4輪，第5輪，第10輪，第20輪

說(shuō)到這里，會(huì)立馬發(fā)現(xiàn)：第 i 個(gè)燈泡只有在第 k 輪會(huì)被操作，而 k 一定是 i 的因數(shù)。并且 n>=k。所以如果一個(gè)數(shù)的因數(shù)的個(gè)數(shù)為奇數(shù)個(gè)，那么它最后一定是亮的，否則是關(guān)閉的。
那么問(wèn)題又轉(zhuǎn)變了：

什么數(shù)的因數(shù)的個(gè)數(shù)是奇數(shù)個(gè)？
答案是完全平方數(shù)。

2 為什么完全平方數(shù)的因數(shù)的個(gè)數(shù)是奇數(shù)個(gè)？
設(shè)P,A,B 為正整數(shù)，如果 P=A*B，則A和B為P的因數(shù)。
P的因數(shù)A和B總是成對(duì)出現(xiàn)。也就是說(shuō)他們總是一起為 P 的因數(shù)個(gè)數(shù)做貢獻(xiàn)。但是如果他們相等呢？這個(gè)時(shí)候他們一起只會(huì)為因數(shù)的個(gè)數(shù)貢獻(xiàn) 1。

其次，P=A*A，這種情況對(duì)于P來(lái)說(shuō)最多只能出現(xiàn)1次，而這種情況只可能出現(xiàn)在完全平方數(shù)中。
所以對(duì)于正整數(shù)而言，只有完全平方數(shù)的因數(shù)的個(gè)數(shù)是奇數(shù)個(gè)。

綜上所述，所以每個(gè)完全平方數(shù)就是答案

還可以這樣推導(dǎo)：
對(duì)于數(shù)k，第i輪被撥一下的條件是k%i==0
所有數(shù)k被撥的次數(shù)是k的約束的個(gè)數(shù)
若k=p_1^x p_2^y p_3^z … , 其中p_i為素?cái)?shù)，則約數(shù)的個(gè)數(shù)f(k)= (1+x)(1+y)(1+z).
第k個(gè)燈亮意味著f(k)為奇數(shù)，根據(jù)推論3可知，其中的x,y,z…都必須為偶數(shù)。
回看，k=p_1^x p_2^y p_3^z … , 說(shuō)明k是個(gè)完全平方數(shù)

題解C

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

777.在LR字符串中叫喚相鄰字符

思路

將 ‘L’，‘R’ 分別理解為一個(gè)隊(duì)伍中面向左和面向右的人，‘X’ 理解為隊(duì)伍中的空擋?？梢詥?wèn)自己一個(gè)問(wèn)題，一次移動(dòng)操作之后有什么是保持不變的？ 這是狀態(tài)轉(zhuǎn)換問(wèn)題中一個(gè)很常見(jiàn)的思路。

算法

這道題的 轉(zhuǎn)換不變性 在于字符串中的 ‘L’ 和 ‘R’ 是不會(huì)互相穿插的，也就是隊(duì)伍中的人在移動(dòng)過(guò)程中是不能穿過(guò)人的。這意味著開(kāi)始和結(jié)束的字符串如果只看 ‘L’ 和 ‘R’ 的話是一模一樣的。

除此之外，第 n 個(gè) ‘L’ 不可能移動(dòng)到初始位置的右邊，第 n 個(gè) ‘R’ 不可能移動(dòng)到初始位置的左邊，我們把這個(gè)特性稱為 “可到達(dá)性“。

根據(jù) 轉(zhuǎn)換不變性 和 可到達(dá)性，在算法中可以分別檢查這兩個(gè)性質(zhì)是否滿足。如果都滿足，則返回 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; //發(fā)現(xiàn)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; //發(fā)現(xiàn)end中R往左移了}return true;} }

1033.移動(dòng)石子直到連續(xù)

思路：
題目看著很繞，其實(shí)很簡(jiǎn)單，首先排序，排序并不會(huì)改變結(jié)果，但是我們寫(xiě)起來(lái)更方便一點(diǎn)，然后重新賦值abc

a最小,c最大，因?yàn)橹荒苣脙蛇叺氖^往中間放，所以最大情況就是一步一步挪，那么就是c-a-2，最小情況多重情況討論即可

三個(gè)緊貼著 c-a=2 返回0
其中有兩個(gè)緊貼著 返回1
其中有兩個(gè)中間空了一格 返回 1
最小移動(dòng)次數(shù)最大是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.飛機(jī)座位分配率

思路
設(shè)dp[i]為第i個(gè)乘客坐在自己的座位上的概率，
初始化dp[1]=1;dp[2]=0.5;

當(dāng)i=3時(shí):
若第一個(gè)人選擇第一個(gè)座位，后邊的人的椅子沒(méi)有被占用，按照正常順序，第3個(gè)人肯定能坐到第3個(gè)位置，這個(gè)概率是1/3；
若第一個(gè)人選擇第二個(gè)位置，第二個(gè)人發(fā)現(xiàn)自己的椅子被占用，他有兩個(gè)位置可選，只有選擇第一個(gè)位置，第三個(gè)人才能坐到自己的位置，根據(jù)概率乘法原則，這個(gè)概率是1/3 × 1/2;
只有這兩種情況，第3個(gè)人才能坐到第三個(gè)位置
所以dp[3]=1/3+1/3×1/2
=1/3×(1+1/2)
=1/3×(dp[1]+dp[2])

以此類推，可以推出來(lái)：
dp[i]=(1/i)×(dp[1]+dp[2]+…+dp[i-1])
這就是狀態(tài)轉(zhuǎn)移方程

所以說(shuō)實(shí)際上只要n>1,那么結(jié)果必是1/2！

題解Java

class Solution {public double nthPersonGetsNthSeat(int n) {if (n == 1) {return 1.0;}double [] dp=new double[n+1];//從下標(biāo)1開(kāi)始使用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.所有螞蟻掉下來(lái)前的最后一刻

思路
兩個(gè)螞蟻相撞之后會(huì)互相調(diào)頭，其實(shí)只要想成如果每只螞蟻都長(zhǎng)得一模一樣，那么是不是螞蟻碰撞的調(diào)頭 就等于 穿透了？

知道了這一點(diǎn)，那么就可以直接讓螞蟻直接穿透爬行就好了

那么題目就變成了求單只最晚落地的螞蟻，與碰撞無(wú)關(guān)

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

總結(jié)

以上是生活随笔為你收集整理的LeetCode_脑筋急转弯的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。