专栏首页算法码上来每日算法系列【LeetCode 1363】形成三的最大倍数

每日算法系列【LeetCode 1363】形成三的最大倍数

题目描述

给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。

由于答案可能不在整数数据类型范围内,请以字符串形式返回答案。

如果无法得到答案,请返回一个空字符串。

示例1

输入:
digits = [8,1,9]
输出:
"981"

示例2

输入:
digits = [8,6,7,1,0]
输出:
"8760"

示例3

输入:
digits = [1]
输出:
""

示例4

输入:
digits = [0,0,0,0,0,0]
输出:
"0"

提示

  • 1 <= digits.length <= 10^4
  • 0 <= digits[i] <= 9
  • 返回的结果不应包含不必要的前导零。

题解

首先要知道一个小学生都知道的定理:如果一个数可以被 整除,那么它的每一位上的数之和也可以被 整除,反之也成立。

那么问题就转化为了挑选出最多的数,使得和是 的倍数。我们可以先求出所有数之和,记为 ,然后有如下三种情况:

  • 如果 ,那么所有数都选中就行了。
  • 如果 ,那么必须删掉一个模 余 的数(按照从小到大顺序删除 1、4、7)。如果这三个数都没有,那就要删除两个模 余 的数(按照从小到大顺序删除 2、5、8,删除两次)。
  • 如果 ,那么必须删掉一个模 余 的数(按照从小到大顺序删除 2、5、8)。如果这三个数都没有,那就要删除两个模 余 的数(按照从小到大顺序删除 1、4、7,删除两次)。

最终将剩下的数按照从小到大顺序排序,拼接在一起就行了。

注意如果有前导 ,就说明答案就是 。

时间复杂度为 。

代码

c++

class Solution {
public:
    int del(vector<int>& cnt, int q) {
        for (int i = 0; i <= 9; ++i) {
            if (i%3 == q && cnt[i]) {
                return --cnt[i];
            }
        }
        return -1;
    }

    string largestMultipleOfThree(vector<int>& digits) {
        vector<int> cnt(10, 0);
        int sum = 0;
        for (auto x : digits) {
            cnt[x]++;
            sum += x;
        }
        int q = sum % 3;
        if (q && del(cnt, q) < 0) {
            del(cnt, 3-q);
            del(cnt, 3-q);
        }
        string res = "";
        for (int i = 9; i >= 0; --i) {
            while (cnt[i]--) {
                res += i+'0';
            }
        }
        if (res.size() && res[0] == '0') return "0";
        return res;
    }
};

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日算法系列【LeetCode 829】连续整数求和

    遍历所有的连续数字区间 (i, j) ,然后求和看等不等于 N 。这种方法时间复杂度是 ,显然不可行。

    godweiyang
  • 【每日算法Day 109】五大解法,带你深入了解完全背包方案数

    给定数量不限的硬币,币值为 25 分、10 分、5 分和 1 分,编写代码计算 n 分有几种表示法。(结果可能会很大,你需要将结果模上 1000000007)

    godweiyang
  • 【每日算法Day 97】经典面试题:求两个数组最小差

    给定两个整数数组 a 和 b,计算具有最小差绝对值的一对数值(每个数组中取一个值),并返回该对数值的差。

    godweiyang
  • 算法篇:树之树的层次遍历

    树的层次遍历是树的基本操作之一,包括二叉树的层次遍历,多叉树的层次遍历,以及二叉树层次遍历的变形题目,层次遍历+每一层的节点的翻转等操作。

    灰子学技术
  • LeetCode 168. Excel Sheet Column Title

    ShenduCC
  • SpringMVC教程1[原理分析及注解方式的使用]

    用户4919348
  • spring-boot 速成(6) 整合disconf

    spring-boot虽然不推荐使用xml文件做为配置文件,但是并没有把路堵死,所以与disconf的整合,仍旧可以沿用之前的xml方式来处理。 一、在Appl...

    菩提树下的杨过
  • 图书管理系统(四)图书管理系统实战(2)

    前一篇文章 图书管理系统实战(一)[1] 中,我们已经编写了 pojo、dao 层以及配置 dao 层对应的 mapper,从现在开始,我们开始编写 servi...

    村雨遥
  • RecyclerView实现混合布局

    PS:好长时间不写博客了,起初是不知道写些什么,后来接触了到了很多东西,原本看似简单的东西,背后都隐藏着巨大的秘密,想handler的使用,一般情况下会引起内存...

    cMusketeer
  • 如何使用git rm 删除文件名里带空格的文件名

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券