首页 > 游卡 服务器端 笔试 7.29
头像
sick白牧
编辑于 2021-08-09 10:18
+ 关注

游卡 服务器端 笔试 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. 麻将中如[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;
     }

全部评论

(3) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐