LeetCode 1363. 形成三的最大倍数

Categories:

题目描述
思路分析
1. 解法一：计数 + 贪心（推荐）
相似题目

题目描述

✅ 1363. 形成三的最大倍数

思路分析

解法一：计数 + 贪心（推荐）

核心思路：

统计 0~9 的出现次数并计算数字和。

根据 sum % 3 删除最小的 1 个或 2 个数字，使和能被 3 整除。

最终从大到小构造最大数字，若全为 0 则返回 “0”。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数字个数。

空间复杂度：O(1)，固定 10 位计数数组。

class Solution {
    public String largestMultipleOfThree(int[] digits) {
        int[] count = new int[10];
        int sum = 0;
        for (int d : digits) {
            count[d]++;
            sum += d;
        }

        if (!adjust(count, sum % 3)) {
            return "";
        }

        StringBuilder builder = new StringBuilder();
        for (int d = 9; d >= 0; d--) {
            for (int i = 0; i < count[d]; i++) {
                builder.append(d);
            }
        }

        if (builder.length() == 0) {
            return "";
        }
        if (builder.charAt(0) == '0') {
            return "0";
        }

        return builder.toString();
    }

    private boolean adjust(int[] count, int mod) {
        if (mod == 0) {
            return true;
        }

        int[] mod1 = {1, 4, 7};
        int[] mod2 = {2, 5, 8};
        if (mod == 1) {
            if (removeOne(count, mod1)) {
                return true;
            }
            return removeTwo(count, mod2);
        }

        if (removeOne(count, mod2)) {
            return true;
        }
        return removeTwo(count, mod1);
    }

    private boolean removeOne(int[] count, int[] nums) {
        for (int n : nums) {
            if (count[n] > 0) {
                count[n]--;
                return true;
            }
        }
        return false;
    }

    private boolean removeTwo(int[] count, int[] nums) {
        int removed = 0;
        for (int n : nums) {
            while (count[n] > 0 && removed < 2) {
                count[n]--;
                removed++;
            }
            if (removed == 2) {
                return true;
            }
        }
        return false;
    }
}

func largestMultipleOfThree(digits []int) string {
	count := make([]int, 10)
	sum := 0
	for _, d := range digits {
		count[d]++
		sum += d
	}

	if !adjustCount(count, sum%3) {
		return ""
	}

	res := make([]byte, 0, len(digits))
	for d := 9; d >= 0; d-- {
		for i := 0; i < count[d]; i++ {
			res = append(res, byte('0'+d))
		}
	}

	if len(res) == 0 {
		return ""
	}
	if res[0] == '0' {
		return "0"
	}

	return string(res)
}

func adjustCount(count []int, mod int) bool {
	if mod == 0 {
		return true
	}

	mod1 := []int{1, 4, 7}
	mod2 := []int{2, 5, 8}

	if mod == 1 {
		if removeOne(count, mod1) {
			return true
		}
		return removeTwo(count, mod2)
	}

	if removeOne(count, mod2) {
		return true
	}
	return removeTwo(count, mod1)
}

func removeOne(count []int, candidates []int) bool {
	for _, n := range candidates {
		if count[n] > 0 {
			count[n]--
			return true
		}
	}
	return false
}

func removeTwo(count []int, candidates []int) bool {
	removed := 0
	for _, n := range candidates {
		for count[n] > 0 && removed < 2 {
			count[n]--
			removed++
		}
		if removed == 2 {
			return true
		}
	}
	return false
}

相似题目

题目	难度	考察点
179. 最大数	中等	排序
402. 移掉 K 位数字	中等	单调栈
670. 最大交换	中等	贪心
2384. 最大回文数字	中等	计数
1005. K 次取反后最大化的数组和	简单	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/74903862