去哪儿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]);
    }
}


#去哪儿##笔经##java工程师#
全部评论
思路就是,动态规划,dp[0][i]、dp[1][i]、dp[2][i],分别存储当前数组最大的余0,1,2的数 每次更新三个数 余0,凑0+0,1+2,2+1 余1,凑0+1,1+0,2+2 余2,凑0+2,1+1,2+0 大概就这样
点赞 回复 分享
发布于 2021-09-14 19:13
考试时间放其实不太好
点赞 回复 分享
发布于 2021-09-14 19:26
我用俩存2和1的优先队列,写的像个屎山一样,ifelse乱的我都看不下去了(自信点,把像去了)
点赞 回复 分享
发布于 2021-09-14 19:33

相关推荐

12-01 12:34
已编辑
广东工业大学 Java
如题,fw🐭🐭,加上准备的太晚,大三上已找不到日常实习,导致连锁反应,下学期的暑期实习找不到好的实习,导致秋招找不到中大厂,现在是中小厂Java还有考公的选择,由于有些中小厂工作强度比肩大厂,钱还少,感觉不如考公如果🐮u们是我现在这种情况,会怎么选?
负债的混子:关注你一段时间了,突然发现你头像名字都改了,想必是这段时间压力很大。关于就业还是考公的选择,就像很多牛友说的:不要美化自己没走过的路。你现在想往互联网发展,发现这条路很难走,然后想往考公发展,但是你没走过考公这条路,所以你不知道这条路的压力如何。你今年大三了,还有时间给你做选择,我希望你能够尽快的决定自己的方向,然后一条路走到黑,而不是在这里徘徊,每个人的道路是不一样的,你无法复刻别人的路,你能做的就是尽力的完善自己。 最后,我想说的是,加油,陌生人!
点赞 评论 收藏
分享
无敌虾孝子:喜欢爸爸还是喜欢妈妈
点赞 评论 收藏
分享
昨天 19:53
已编辑
湖南文理学院 产品经理
牛客224543458号:他想找牛马,愿意疯狂加班的,因为要证明自己
点赞 评论 收藏
分享
评论
点赞
4
分享
牛客网
牛客企业服务