扑克牌的顺子
一副牌里随机抽5张牌,大小王看作任意的数字,判断是不是顺子。
方法一:先快速排序,然后比较大小和是否相等,最后判断。
public boolean isContinuous(int[] n){
if(n==null||n.length==0)
return false;
Arrays.sort(n);
int numberOfZero=0;
int numberOfGap=0;
for(int i=0;i<n.length&&n[i]==0;i++)
++numberOfZero;
int small=numberOfZero;
int big=small+1;
while(big<n.length){
if(n[small]==n[big])
return false;
numberOfGap+=n[big]-n[small]-1;
small=big;
++big;
}
return numberOfGap>numberOfZero?false:true;
}
方法二: 新建数组,O(N)时间完成排序。
public boolean isContinuous(int [] a) {
if(a==null||a.length==0)
return false;
int []d=new int[14];
int max=-1,min=14;
for(int i=0;i<a.length;i++){
d[a[i]]++;
if(a[i]==0)
continue;
if(d[a[i]]>1)
return false;
if(a[i]>max)
max=a[i];
if(a[i]<min)
min=a[i];
}
if(Math.abs(max-min)<5)
return true;
return false;
}
约瑟夫环问题
0,1,...,n-1这n个数字排成一个圆圈,从数字0开始每次删除圆圈第m个数字。求剩下的最后一个数字。
public static int lastRemaining(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
List<Integer> list = new LinkedList<>();
for (int i = 0; i < n; i++) {
list.add(i);
}
// 要删除元素的位置
int idx = 0;
while (list.size() > 1) {
idx = (idx +m- 1) % list.size(); //
list.remove(idx);
}
return list.get(0);
}
数学方法。先做记录。
public static int lastRemaining2(int n, int m) {
if(n<1||m<1)
return -1;
int last=0;
for(int i=2;i<=n;i++)
last=(last+m)%i;
return last;
}
二进制中1的个数
只需要循环1出现的次数,而不需要全部遍历。如果是负数情况下,计算机用补码形式存储。补码=负数反码(除符号位全取反)+1,此时求得的是补码的1的个数。
比如-10求得补码中1个数为30。每一次循环都去掉了n的二进制中最后一位1。
int numberOf1(int n){
int count=0;
while(n!=0){
++count;
n=(n-1)&n;
}
return count;
}
方法二:每次向右位移一位,注意如果用>> ,负数会陷入无限循环,所以用>>>表示无符号位移。
static int numberof1(int n){
int count=0;
while(n!=0){
if((n&1)==1)
count++;
n=n>>>1;
}
return count;
}
方法三:同样,也可以对1进行左移
static int numberof1(int n){
int count=0;
int flag=1;
while(flag!=0){
if((n&flag)!=0)
count++;
flag=flag<<1;
}
return count;
}
网友评论