Question

1317. 将整数转换为两个无零整数的和

English Version

题目描述

「无零整数」是十进制表示中 不含任何 0 的正整数。

给你一个整数 n，请你返回一个 由两个整数组成的列表 [A, B]，满足：

• A 和 B 都是无零整数
• A + B = n

题目数据保证至少有一个有效的解决方案。

如果存在多个有效解决方案，你可以返回其中任意一个。

 

示例 1：

输入：n = 2
输出：[1,1]
解释：A = 1, B = 1. A + B = n 并且 A 和 B 的十进制表示形式都不包含任何 0 。

示例 2：

输入：n = 11
输出：[2,9]

示例 3：

输入：n = 10000
输出：[1,9999]

示例 4：

输入：n = 69
输出：[1,68]

示例 5：

输入：n = 1010
输出：[11,999]

 

提示：

• 2 <= n <= 10^4

解法

方法一：直接枚举

从 $1$ 开始枚举 $a$，判断 $a$ 和 $n - a$ 是否满足条件，如果满足则返回。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(1)$。其中 $n$ 为题目给定的整数。

class Solution:
  def getNoZeroIntegers(self, n: int) -> List[int]:
    for a in range(1, n):
      b = n - a
      if "0" not in str(a) + str(b):
        return [a, b]

class Solution {
  public int[] getNoZeroIntegers(int n) {
    for (int a = 1;; ++a) {
      int b = n - a;
      if (!(a + "" + b).contains("0")) {
        return new int[] {a, b};
      }
    }
  }
}

class Solution {
public:
  vector<int> getNoZeroIntegers(int n) {
    for (int a = 1;; ++a) {
      int b = n - a;
      if ((to_string(a) + to_string(b)).find('0') == -1) {
        return {a, b};
      }
    }
  }
};

func getNoZeroIntegers(n int) []int {
  for a := 1; ; a++ {
    b := n - a
    if !strings.Contains(strconv.Itoa(a)+strconv.Itoa(b), "0") {
      return []int{a, b}
    }
  }
}

方法二

class Solution:
  def getNoZeroIntegers(self, n: int) -> List[int]:
    def f(x):
      while x:
        if x % 10 == 0:
          return False
        x //= 10
      return True

    for a in range(1, n):
      b = n - a
      if f(a) and f(b):
        return [a, b]

class Solution {
  public int[] getNoZeroIntegers(int n) {
    for (int a = 1;; ++a) {
      int b = n - a;
      if (f(a) && f(b)) {
        return new int[] {a, b};
      }
    }
  }

  private boolean f(int x) {
    for (; x > 0; x /= 10) {
      if (x % 10 == 0) {
        return false;
      }
    }
    return true;
  }
}

class Solution {
public:
  vector<int> getNoZeroIntegers(int n) {
    auto f = [](int x) {
      for (; x; x /= 10) {
        if (x % 10 == 0) {
          return false;
        }
      }
      return true;
    };
    for (int a = 1;; ++a) {
      int b = n - a;
      if (f(a) && f(b)) {
        return {a, b};
      }
    }
  }
};

func getNoZeroIntegers(n int) []int {
  f := func(x int) bool {
    for ; x > 0; x /= 10 {
      if x%10 == 0 {
        return false
      }
    }
    return true
  }
  for a := 1; ; a++ {
    b := n - a
    if f(a) && f(b) {
      return []int{a, b}
    }
  }
}