美文网首页程序员
扑克牌顺子 / 约瑟夫环问题 / 二进制1的个数

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

作者: icecrea | 来源:发表于2017-10-03 16:35 被阅读131次

    扑克牌的顺子

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

    相关文章

      网友评论

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

        本文链接:https://www.haomeiwen.com/subject/crkfyxtx.html