首页 > 去哪儿9.14Java第一题被3整除的最大数
头像
wnhyang
发布于 2021-09-14 18:58
+ 关注

去哪儿9.14Java第一题被3整除的最大数

A了,但代码有点多,可以打磨优化一下,有点类似最佳买卖股票时机含冷冻期
public static String getString(int[] d) {
    int n = d.length;
    Arrays.sort(d);
    long[][] dp = new long[3][n + 1];
    dp[1][0] = -1;
    dp[2][0] = -1;
    for (int i = 1; i <= n; i++) {
        int index = n - i;
        if (d[index] % 3 == 0) {
            dp[0][i] = Math.max(dp[0][i - 1], dp[0][i - 1] * 10 + d[index]);
            dp[1][i] = dp[1][i - 1];
            if (dp[1][i - 1] != -1) {
                dp[1][i] = Math.max(dp[1][i - 1], dp[1][i - 1] * 10 + d[index]);
            }
            dp[2][i] = dp[2][i - 1];
            if (dp[2][i - 1] != -1) {
                dp[2][i] = Math.max(dp[2][i - 1], dp[2][i - 1] * 10 + d[index]);
            }
        } else if (d[index] % 3 == 1) {
            dp[0][i] = dp[0][i - 1];
            if (dp[2][i - 1] != -1) {
                dp[0][i] = Math.max(dp[0][i - 1], dp[2][i - 1] * 10 + d[index]);
            }
            dp[1][i] = Math.max(dp[1][i - 1], dp[0][i - 1] * 10 + d[index]);
            dp[2][i] = dp[2][i - 1];
            if (dp[1][i - 1] != -1) {
                dp[2][i] = Math.max(dp[2][i - 1], dp[1][i - 1] * 10 + d[index]);
            }
        } else {
            dp[0][i] = dp[0][i - 1];
            if (dp[1][i - 1] != -1) {
                dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1] * 10 + d[index]);
            }
            dp[1][i] = dp[1][i - 1];
            if (dp[2][i - 1] != -1) {
                dp[1][i] = Math.max(dp[1][i - 1], dp[2][i - 1] * 10 + d[index]);
            }
            dp[2][i] = Math.max(dp[2][i - 1], dp[0][i - 1] * 10 + d[index]);
        }
    }
    if (d[0] == 0) {
        return String.valueOf(dp[0][n]);
    } else {
        return dp[0][n] == 0 ? "" : String.valueOf(dp[0][n]);
    }
}


全部评论

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