莉莉丝8/11后台开发笔试题

第三题咋搞啊xdm，死活通不过啊。前两题都通过了，大家可以参考下。

第一题

public ListNode formatList (ListNode head) {
        // write code here
        ListNode trail = head.next;
        ListNode newHead = trail.next;
        while(trail != null && newHead != null){
            trail.next = newHead.next;
            newHead.next = head;
            trail = trail.next;
            head = newHead;
            if(trail != null) { newHead = trail.next; }
        }
        return head;
    }

第二题

public long ans (int[] array, int k) {
        // write code here
        long count = 0;
        int len = array.length;
        Arrays.sort(array);
        for(int i = 0;i < len;i++){
            if(array[i] >= k){ break; }
            for(int j = i+1;j < len;j++){
                if(array[i] + array[j] <= k){ count++; }
                else{ break; }
            }
        }
        return count;
    }

第三题

public static long minimum (int[] a) {
        // write code here
        long sum = 0;
        for(int num : a){ sum+= num; }
        if(sum % 2 == 0){ return 0; }
        long avg = sum / 2;
        int len = a.length;
        long[] dp = new long[(int)avg+1];
        for(int i = 1;i <= len;i++){
            for(int j = (int)avg;j >= 1;j++){
                if(j >= a[i-1]){ dp[j] = Math.max(dp[j],dp[j-a[i-1]]+a[i-1]); }
            }
        }

        return sum - 2*dp[(int)avg];
    }