阿里笔试20210322

Java实习生 笔试

01背包装满问题

花里胡哨讲了一大堆就是问，$n$个物品，限重$m$, 每个物品$w_i$, 从这几个物品中任选几个问是否能恰好装满。
也可说是01换零钱。

全AC，$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]);
}

1563. 石子游戏 V

一排球，每个球都有各自的值，每轮在中间划分两排（保持顺序不变），哪排球的总分值多，哪排球抛弃，剩下的那一排算入游戏总分，如果分值相同任选一个抛弃。
求问能够得到的最高分数。
例子：{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=20 去掉{4}
返回20

第一种方法（笔试时的思路）：二分法+贪心（错误解法🙅） $O(N^2)$

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的时候搞得太麻烦了，什么单调递增递减的，全搜就完事了，也不影响复杂度，真的给一些边缘情况搞得心态爆炸，45分钟的做题时间最后只通了5%，真是作死啊。

第二种方法：暴力递归+Memo $O(N^3)$

class Solution {
    int[][] memo;

    public int stoneGameV(int[] stoneValue) {
        int N = stoneValue.length;
        memo = new int[N][N];
        return ball(stoneValue, 0, N-1);
    }

    public int ball(int[] a, int head, int rear) {
        if (head >= rear) {
            return 0;
        }
        if (memo[head][rear] != 0) {
            return memo[head][rear];
        }
        int total = sum(a, head, rear);
        int leftSum = 0;
        int rightSum = total;
        int points = 0;
        for (int i=head; i < rear; i++) {
            leftSum += a[i];
            rightSum -= a[i];
            if (leftSum < rightSum) {
                points = Math.max(points, leftSum+ball(a, head, i));
            } else if (leftSum > rightSum) {
                points = Math.max(points, rightSum+ball(a, i+1, rear));
            } else {
                points = Math.max(points, leftSum+Math.max(ball(a, head, i), ball(a, i+1, rear)));
            }
        }
        memo[head][rear] = points;
        return points;
    }


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