莉莉丝4.1笔试，好简单。。

第一题链表的另一种顺序返回，要求从头结点开始，后面的依次插入链表尾，链表头，链表尾

记录一个链表数组，找相对位置就行

       public ListNode formatList (ListNode head) {
        // write code here
        int num = 0;
        ListNode p = head;
        while(p != null){
            num++;
            p = p.next;
        }
        ListNode[] listNodes = new ListNode[num];
        int start = (num - 1)/2;
        int end = start+1;
        int glag = -1;
        int cnt = 0;
        p = head;
        while(p!=null){
            if(glag == -1){
                listNodes[start--] = p;
            }else {
                listNodes[end++] = p;
            }
            p = p.next;
            glag*=-1;
        }
        for (int i = 0; i < num - 1; i++) {
            listNodes[i].next = listNodes[i + 1];
        }
        listNodes[num - 1].next = null;
        return  listNodes[0];
    }

第二题简单的二分查找，排序后找，去个重就行

我这边当时直接写完了，其实找到第一个之后不需要再次二分查找，直接双指针向前向后就可以了，当时想的反正排序要nlogn，我这边降到n没有意义

     public long ans (int[] array, int k) {
        // write code here
        Arrays.sort(array);
        int start = 0;
        long res = 0;
        for (int i = 0; i < array.length; i++) {
            if(array[start] > k){
                break;
            }
            int index = partition(array, k - array[start]);//这边index的选取可以用双指针降到n
            if(index > start){
                res += (index - start);
            }
        }
        return  res;
    }
    public  int partition(int[] array, int k){
        int start = 0;
        int end = array.length;
        int res =-1;
        while(start <= end){
            int mid = (start + end)/2;
            if(array[mid] <= k){
                res = mid;
                start = mid + 1;
            }else{
                end = mid -1;
            }
        }
        return  res;
    }

第三题环状数组分两半，求两部分和绝对差值最小

简单的滑动窗口，这边阔以在第二个while start之前设置一个==sum或者sum+1（和为奇数的情况），此时可以直接返回0/1降低了一些运行时间，这边写错了，我在交的代码改的，这里忘记改了

有的代码可能不能ac，我可能在上面改了点

       public long minimum (int[] a) {
        // write code here
        long res = Long.MAX_VALUE;
        long sum = 0;
        for (int i = 0; i < a.length; i++) {
            sum+=a[i];
        }
                long tempsum = sum;
        sum = sum/2;
        long temp = 0;
        int start = 0;
        int end = 0;
        while(end < a.length){
            while(temp < sum && end < a.length){
                temp+=a[end++];
                res = Math.min(Math.abs(tempsum - temp*2), res);
            }
            if(end == a.length - 1){
                break;
            }//这里加个if判断阔以直接返回0/1
            while(temp >= sum && start < a.length){
                temp -= a[start++];
                res = Math.min(Math.abs(tempsum - temp*2), res);
            }
        }
        while(temp > sum ){
            temp -= a[start++];
            res = Math.min(Math.abs(tempsum - temp*2), res);
        }
        return res;
    }

代码贴上来了，仓促之间写的很丑笑死，大家看个思路就行啦,有的代码可能有些许错误我的改动没有在本地改可能是，但是思路应该是这样的

#莉莉丝游戏##笔试题目#