游卡服务器端笔试 7.29

情况说明

牛客sp专场投的，you+计划，三道笔试全a了，至今没后续消息。

第一题翻转部分链表

输入一个链表，一个整型数left和一个整形数right，将链表首到第left节点翻转，并将第right节点到链表末尾翻转，返回反转后的链表。
解析：用栈来做会超时，只能分段进行翻转，注意头尾的连接。

public ListNode reverseAmong (ListNode head, int left, int right) {
        ListNode p = head;
        ListNode now = p.next;
        p.next = null;
        ListNode t1 = head;
        //第一阶段
        while(left>0){
            ListNode next = now.next;
            now.next = p;
            p = now;
            now = next;
            left--;
            right--;
        }
        ListNode l1 = p.next;
        p.next = now;
        t1.next = p;
        if(right==1){
            //第三阶段，跳过第二阶段
            ListNode t2 = t1;
            p.next = null;
            while(now!=null){
                ListNode next = now.next;
                now.next = p;
                p = now;
                now = next;
            }
            t2.next = p;
        }else {
            //第二阶段
            while (right > 2) {
                p = p.next;
                now = now.next;
                right--;
            }
            //第三阶段
            ListNode t2 = p;
            p.next = null;

            p = now;
            now = now.next;
            p.next = null;

            while (now != null) {
                ListNode next = now.next;
                now.next = p;
                p = now;
                now = next;

            }
            t2.next = p;
        }
        return l1;
    }

第二题连续胜利的博弈

输入一个数组和k，将数组0号元素和1号元素比较，胜者将保留在0号位置，败者将移动至数组末端，当一个元素连续胜利k次时，输出该元素。注：数组长度大于2，k大于等于1.
解析：0号元素永远是最大的元素，比赛失败的元素没有意义，当对比完队列里所有元素时，再和被淘汰的元素比较（一定比它小），那不管对比多久，都还是它最大，直接返回即可。

public int FindWinner (int[] candidates, int k) {
        Deque<Integer> q = new LinkedList<>();
        for(int e:candidates)
            q.addLast(e);
        int cnt = 0;
        while(true){
            int l1 = q.pollFirst();
            if(q.size()==0)
                return l1;
            int l2 = q.pollFirst();
            if(l1>=l2){
                cnt++;
                q.addFirst(l1);
                if(cnt==k)
                    return l1;
            }else{
                if(k==1)
                    return l2;
                cnt = 1;
                q.addFirst(l2);
            }
        }
    }

第三题麻将的最大搭子数

麻将中如[1,2,3]是顺子，[3,3,3]是刻子，顺子和刻字统称为搭子，输入一个数组，每个数表示麻将的数字，求最多组成搭子数（一张牌不能重复用）
解析：贪心，先顺子再刻子，题目没有说输入数在1~9之间，但麻将事实时这样，用例也是如此。

public int maxCompose(int[] a){
     int res = 0;
     int[] f = new int[9];
     for(int e:a){
         f[e-1]++;
     }
     for(int i=0;i<=6;i++){
         if(f[i]>0&&f[i+1]>0&&f[i+2]>0){
             f[i]--;
             f[i+1]--;
             f[i+2]--;
             res++;
         }
     }
     for(int i=0;i<9;i++)
         res += f[i]/3;
     return res;
 }

#笔经##游卡#