扑克牌顺子 / 约瑟夫环问题 / 二进制1的个数

扑克牌的顺子

一副牌里随机抽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;
    }