Java实习生 笔试

1. 01背包问题

花里胡哨讲了一大堆就是问，个物品，限重, 每个物品, 从这几个物品中任选几个问是否能恰好装满。

也可说是01换零钱。

100%，O(mn)

public static void knapsack(int m, int n, int[] weights) {
    boolean[] dp = new boolean[m+1];
    dp[0] = true;
    for (int i=0; i < n; i++) {
        for (int v=m; v >= weights[i]; v--) {
            dp[v] = dp[v] || dp[v-weights[i]];
        }
    }
    System.out.println(dp[m]);
}

2. 游戏

一排球，每个球都有各自的值，每轮在中间划分两排（保持顺序不变），哪排球的总分值多，哪排球抛弃，剩下的那一排算入游戏总分，如果分值相同任选一个抛弃。

求问能够得到的最高分数。

例子：{6,2,4,4,5,5}

第一轮：{6,2,4};{4,5,5} 总分=6+2+4=12 去掉{4,5,5}

第二轮：{6};{2,4} 总分=12+2+4=18 去掉{6}

第三轮：{2};{4} 总分=18+2 去掉{4}

二分法+贪心（有可能不对）

平均O(N)

public static int ball(int[] a, int head, int rear) {
    if (head >= rear) {
        return 0;
    }
    int index = head;
    int total = sum(a, head, rear);
    int rightSum = total;
    int leftSum = 0;
    int minDelta = total;
    int points;
    for (int i=index; i < rear; i++) {
        leftSum += a[i];
        rightSum -= a[i];
        int delta = Math.abs(rightSum-leftSum);
        if (delta < minDelta) {
            minDelta = delta;
            index=i;
        }
    }
    leftSum = sum(a, head, index);
    rightSum = sum(a, index+1, rear);

    if (leftSum > rightSum) {
        points = rightSum + ball(a, index+1, rear);
    } else if (leftSum < rightSum) {
        points = leftSum + ball(a, head, index);
    } else { //  等于情况取高值
        points = leftSum + Math.max(ball(a, head, index), ball(a, index+1, rear));
    }
    return points;
}

public static int sum(int[] nums, int head, int rear) {
    int ret = 0;
    for (int i=head; i <= rear; i++) {
        ret += nums[i];
    }
    return ret;
}

考的时候没想好，找leftSum和rightSum差最小的index的时候搞得太麻烦了，本来是想差值递减特性消失提前break的，结果调了半天死递归，真是全遍历就完事了，也不影响复杂度，真的给一些边缘情况搞得心态爆炸，第一题做完剩45分钟的做题时间最后只通了5%，真是不甘心啊。

想问下老铁们，第二题的写法对不对，考完后写的，思路是找左边和与右边和的差的绝对值的最小时的索引，然后取小的那一边当这一轮的分数，如果相等就两边都递归。