返回介绍

solution / 1300-1399 / 1363.Largest Multiple of Three / README_EN

发布于 2024-06-17 01:03:20 字数 7237 浏览 0 评论 0 收藏 0

1363. Largest Multiple of Three

中文文档

Description

Given an array of digits digits, return _the largest multiple of three that can be formed by concatenating some of the given digits in any order_. If there is no answer return an empty string.

Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.

 

Example 1:

Input: digits = [8,1,9]
Output: "981"

Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

Input: digits = [1]
Output: ""

 

Constraints:

  • 1 <= digits.length <= 104
  • 0 <= digits[i] <= 9

Solutions

Solution 1: Greedy + Dynamic Programming + Backtracking

We define $f[i][j]$ as the maximum length of selecting several numbers from the first $i$ numbers, so that the sum of the selected numbers modulo $3$ equals $j$. To make the selected numbers as large as possible, we need to select as many numbers as possible, so we need to make $f[i][j]$ as large as possible. We initialize $f[0][0] = 0$, and the rest of $f[0][j] = -\infty$.

Consider how $f[i][j]$ transitions. We can choose not to select the $i$-th number, in which case $f[i][j] = f[i - 1][j]$; we can also choose to select the $i$-th number, in which case $f[i][j] = f[i - 1][(j - x_i \bmod 3 + 3) \bmod 3] + 1$, where $x_i$ represents the value of the $i$-th number. Therefore, we have the following state transition equation:

$$ f[i][j] = \max { f[i - 1][j], f[i - 1][(j - x_i \bmod 3 + 3) \bmod 3] + 1 } $$

If $f[n][0] \le 0$, then we cannot select any number, so the answer string is empty. Otherwise, we can backtrack through the $f$ array to find out the selected numbers.

Define $i = n$, $j = 0$, start backtracking from $f[i][j]$, let $k = (j - x_i \bmod 3 + 3) \bmod 3$, if $f[i - 1][k] + 1 = f[i][j]$, then we have selected the $i$-th number, otherwise we have not selected the $i$-th number. If we have selected the $i$-th number, then we update $j$ to $k$, otherwise we keep $j$ unchanged. To make the number of the same length as large as possible, we should prefer to select larger numbers, so we should sort the array first.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array.

class Solution:
  def largestMultipleOfThree(self, digits: List[int]) -> str:
    digits.sort()
    n = len(digits)
    f = [[-inf] * 3 for _ in range(n + 1)]
    f[0][0] = 0
    for i, x in enumerate(digits, 1):
      for j in range(3):
        f[i][j] = max(f[i - 1][j], f[i - 1][(j - x % 3 + 3) % 3] + 1)
    if f[n][0] <= 0:
      return ""
    arr = []
    j = 0
    for i in range(n, 0, -1):
      k = (j - digits[i - 1] % 3 + 3) % 3
      if f[i - 1][k] + 1 == f[i][j]:
        arr.append(digits[i - 1])
        j = k
    i = 0
    while i < len(arr) - 1 and arr[i] == 0:
      i += 1
    return "".join(map(str, arr[i:]))
class Solution {
  public String largestMultipleOfThree(int[] digits) {
    Arrays.sort(digits);
    int n = digits.length;
    int[][] f = new int[n + 1][3];
    final int inf = 1 << 30;
    for (var g : f) {
      Arrays.fill(g, -inf);
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 3; ++j) {
        f[i][j] = Math.max(f[i - 1][j], f[i - 1][(j - digits[i - 1] % 3 + 3) % 3] + 1);
      }
    }
    if (f[n][0] <= 0) {
      return "";
    }
    StringBuilder sb = new StringBuilder();
    for (int i = n, j = 0; i > 0; --i) {
      int k = (j - digits[i - 1] % 3 + 3) % 3;
      if (f[i - 1][k] + 1 == f[i][j]) {
        sb.append(digits[i - 1]);
        j = k;
      }
    }
    int i = 0;
    while (i < sb.length() - 1 && sb.charAt(i) == '0') {
      ++i;
    }
    return sb.substring(i);
  }
}
class Solution {
public:
  string largestMultipleOfThree(vector<int>& digits) {
    sort(digits.begin(), digits.end());
    int n = digits.size();
    int f[n + 1][3];
    memset(f, -0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 3; ++j) {
        f[i][j] = max(f[i - 1][j], f[i - 1][(j - digits[i - 1] % 3 + 3) % 3] + 1);
      }
    }
    if (f[n][0] <= 0) {
      return "";
    }
    string ans;
    for (int i = n, j = 0; i; --i) {
      int k = (j - digits[i - 1] % 3 + 3) % 3;
      if (f[i - 1][k] + 1 == f[i][j]) {
        ans += digits[i - 1] + '0';
        j = k;
      }
    }
    int i = 0;
    while (i < ans.size() - 1 && ans[i] == '0') {
      ++i;
    }
    return ans.substr(i);
  }
};
func largestMultipleOfThree(digits []int) string {
  sort.Ints(digits)
  n := len(digits)
  const inf = 1 << 30
  f := make([][]int, n+1)
  for i := range f {
    f[i] = make([]int, 3)
    for j := range f[i] {
      f[i][j] = -inf
    }
  }
  f[0][0] = 0
  for i := 1; i <= n; i++ {
    for j := 0; j < 3; j++ {
      f[i][j] = max(f[i-1][j], f[i-1][(j-digits[i-1]%3+3)%3]+1)
    }
  }
  if f[n][0] <= 0 {
    return ""
  }
  ans := []byte{}
  for i, j := n, 0; i > 0; i-- {
    k := (j - digits[i-1]%3 + 3) % 3
    if f[i][j] == f[i-1][k]+1 {
      ans = append(ans, byte('0'+digits[i-1]))
      j = k
    }
  }
  i := 0
  for i < len(ans)-1 && ans[i] == '0' {
    i++
  }
  return string(ans[i:])
}
function largestMultipleOfThree(digits: number[]): string {
  digits.sort((a, b) => a - b);
  const n = digits.length;
  const f: number[][] = new Array(n + 1).fill(0).map(() => new Array(3).fill(-Infinity));
  f[0][0] = 0;
  for (let i = 1; i <= n; ++i) {
    for (let j = 0; j < 3; ++j) {
      f[i][j] = Math.max(f[i - 1][j], f[i - 1][(j - (digits[i - 1] % 3) + 3) % 3] + 1);
    }
  }
  if (f[n][0] <= 0) {
    return '';
  }
  const arr: number[] = [];
  for (let i = n, j = 0; i; --i) {
    const k = (j - (digits[i - 1] % 3) + 3) % 3;
    if (f[i - 1][k] + 1 === f[i][j]) {
      arr.push(digits[i - 1]);
      j = k;
    }
  }
  let i = 0;
  while (i < arr.length - 1 && arr[i] === 0) {
    ++i;
  }
  return arr.slice(i).join('');
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文