第45題：撲克牌順子
難易度：??
題目描述:
LL今天心情特別好,因?yàn)樗ベI了一副撲克牌,發(fā)現(xiàn)里面居然有2個大王,2個小王(一副牌原本是54張^_^)
他隨機(jī)從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票.
“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....
LL不高興了,他想了想,決定大\小 王可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13空另。
上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”。LL決定去買體育彩票啦。
現(xiàn)在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運(yùn)氣如何.
如果牌能組成順子就輸出true澄步，否則就輸出false。為了方便起見,你可以認(rèn)為大小王是0千扶。
思路分析：
我們需要做以下的三件事
- 首先將數(shù)組進(jìn)行排序肆饶，即：排序手中的五張牌
- 統(tǒng)計(jì)數(shù)組中 0 的個數(shù)
- 統(tǒng)計(jì)排序數(shù)組中除去0之外相鄰數(shù)字之間的空缺總數(shù)
除了大王小王，即0之外储玫，任何數(shù)字不能發(fā)生重復(fù)侍筛，因?yàn)閿?shù)字重復(fù)后，就無法構(gòu)成順子撒穷；最后我們只需要判斷數(shù)組中除去0之外相鄰數(shù)字之間的空缺總數(shù)是否小于等于0的個數(shù)即可匣椰。
代碼如下：
import java.util.Arrays;
public class Solution {
public boolean isContinuous(int [] numbers) {
if(numbers == null || numbers.length < 5){
return false;
}
// step1:sort
Arrays.sort(numbers);
// step2:Count the number of 0
int numberOf0 = 0;
int gap = 0;
for(int i = 0;i < numbers.length && numbers[i] == 0;i++){
numberOf0++;
}
// step3:
int index = numberOf0;
while(index < numbers.length - 1){
if(numbers[index] == numbers[index + 1]){
return false;
}
gap += numbers[index + 1] - numbers[index] - 1;
index++;
}
return gap <= numberOf0;
}
}
第46題：圓圈中最后剩下的數(shù)
難易度：??
每年六一兒童節(jié),奧特曼都會準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此。
雷歐作為體術(shù)最強(qiáng)的奧特曼,自然也準(zhǔn)備了一些小游戲端礼。
其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈禽笑。
然后,他隨機(jī)指定一個數(shù)m,讓編號為0的小朋友開始報數(shù)。
每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中
從他的下一個小朋友開始,繼續(xù)0...m-1報數(shù)....
這樣下去....直到剩下最后一個小朋友,可以不用表演,拿到頭等獎
請你試著想下,哪個小朋友會得到這份禮品呢蛤奥？(注：小朋友的編號是從0到n-1)
如果沒有小朋友佳镜，請返回-1
最直白的思路就是，吧本題小朋友圍成的大圈圈模擬成環(huán)凡桥，然后依次從環(huán)中刪除元素蟀伸，可以使用數(shù)組作為環(huán)，思路也比較簡單：
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(m <= 0 || n <= 0){
return -1;
}
int[] help = new int[n];
int fill = 0;
int index = -1;
int mStep = 0;
while(fill != n){
index++;
if(help[index % n] == -1){
continue;
}else{
mStep++;
}
if(mStep == m){
mStep = 0;
help[index % n] = -1;
fill++;
}
}
return index % n;
}
}
本題最優(yōu)解：
使用遞歸的思路
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(m <= 0 || n <= 0){
return -1;
}
if(n == 1){
return 0;
}
return (LastRemaining_Solution(n - 1, m) + m )% n;
}
}
