C++LeetCode 구현(67.바 이 너 리 추가)

[LeetCode]67.바 이 너 리 바 이 너 리 추가
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Constraints:
  • 1 <= a.length, b.length <= 104
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.
  • 바 이 너 리 수 를 더 하고 string 에 저장 합 니 다.string 과 int 사 이 를 어떻게 바 꾸 는 지 주의 하 셔 야 합 니 다.그리고 각 비트 를 더 할 때 진 위 를 할 수 있 고 그 후에 추 가 된 결과 에 영향 을 줄 수 있 습 니 다.그리고 두 입력 string 의 길이 도 다 를 수 있 습 니 다.이 때 우 리 는 string 을 새로 만들어 야 합 니 다.그것 의 길 이 는 두 개의 입력 string 중 비교적 큰 것 입 니 다.그리고 비교적 짧 은 입력 string 을 시작 에 문자'0'을 추가 하여 비교적 큰 길 이 를 보충 해 야 합 니 다.이 때 각각 두 string 의 끝 에서 문 자 를 꺼 내 고 숫자 로 바 꾸 려 고 합 니 다.2 보다 크 면 진입 표지 carry 를 표시 하고 새 string 에 문자'0'을 추가 하려 고 합 니 다.코드 는 다음 과 같 습 니 다:
    해법 1:
    
    class Solution {
    public:
        string addBinary(string a, string b) {
            string res;
            int na = a.size(), nb = b.size(), n = max(na, nb), carry = 0;
            if (na > nb) {
                for (int i = 0; i < na - nb; ++i) b.insert(b.begin(), '0');
            } else {
                for (int i = 0; i < nb - na; ++i) a.insert(a.begin(), '0');
            }
            for (int i = n - 1; i >= 0; --i) {
                int sum = (a[i] - '0') + (b[i] - '0') + carry;
                res = to_string(sum % 2) + res;
                carry = sum / 2;
            }
            if (carry) res.insert(res.begin(), '1');
            return res;
        }
    };
    아래 의 이런 표기 법 은 교묘 하고 간결 하 다.두 개의 바늘 로 각각 a 와 b 의 끝 을 가리 키 고 매번 에 한 문 자 를 꺼 내 숫자 로 바 꾸 었 다.문 자 를 꺼 내지 못 하면 0 으로 처리 한 다음 에 진 위 캐 리 를 정의 하고 0 으로 초기 화 했다.세 가 지 를 합치 면 2 의 나머지 는 바로 앞 자리 의 숫자 이 고 2 의 취 업 체 는 현재 의 진 위 를 가 진 값 이다.마지막 으로 캐 리 를 판단 해 야 한다.1 이 라면 결과 맨 앞 에 1 을 더 해 야 합 니 다.코드 는 다음 과 같 습 니 다.
    해법 2:
    
    class Solution {
    public:
        string addBinary(string a, string b) {
            string res = "";
            int m = a.size() - 1, n = b.size() - 1, carry = 0;
            while (m >= 0 || n >= 0) {
                int p = m >= 0 ? a[m--] - '0' : 0;
                int q = n >= 0 ? b[n--] - '0' : 0;
                int sum = p + q + carry;
                res = to_string(sum % 2) + res;
                carry = sum / 2;
            }
            return carry == 1 ? "1" + res : res;
        }
    };
    C++구현 LeetCode(67.바 이 너 리 추가)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 바 이 너 리 추가 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!

    좋은 웹페이지 즐겨찾기