솔루션: 최소 10진수 이진수로 분할

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #1689(중간): 십진수 이진수의 최소 개수로 분할

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.

Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.

예:

Example 1:
Input:	n = "32"
Output:	3
Explanation:	10 + 11 + 11 = 32

Example 2:
Input:	n = "82734"
Output:	8

Example 3:
Input:	n = "27346209830709182346"
Output:	9

제약:

• 1 <= n.length <= 10^5
• n consists of only digits.
• n does not contain any leading zeros and represents a positive integer.

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

각 10진법 숫자가 각 위치에서 1보다 높지 않은 경우 주어진 n 위치에서 x를 달성하려면 적어도 x개의 숫자가 필요합니다. 이는 n의 임의 위치에서 가장 큰 문자가 n을 얻기 위해 함께 더해야 하는 10진수 숫자의 수를 결정함을 의미합니다.

시각적 증명을 위해 n을 숫자 그래프로 생각할 수 있습니다.

그런 다음 그래프를 추가할 숫자의 스택으로 생각할 수 있습니다.

그러면 이 스택은 필연적으로 n에서 가장 큰 한 자릿수만큼 커야 합니다.

n의 문자를 아주 쉽게 분리하고 최대값을 찾은 다음 해당 숫자를 반환할 수 있습니다.

시간 복잡도: O(N) 여기서 N은 입력 문자열 n의 길이임

공간 복잡성: n을 먼저 배열로 분할하는지 여부에 따라 O(N) 또는 O(1)

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

const minPartitions = n => Math.max(...n.split(''))

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def minPartitions(self, n: str) -> int:
        return max(n)

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    public int minPartitions(String n) {
        char best = '0';
        for (char c : n.toCharArray())
            if (c > best) best = c;
        return best - '0';
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
public:
    int minPartitions(string n) {
        char best = '0';
        for (auto& c : n)
            if (c > best) best = c;
        return best - '0';
    }
};