이진 형식의 숫자 s가 있다고 가정합니다. 이 규칙에 따라 1로 줄이기 위한 단계 수를 찾아야 합니다. -
-
현재 숫자가 짝수이면 2로 나누어야 합니다.
-
현재 숫자가 홀수이면 1을 더해야 합니다.
따라서 입력이 "1101"과 같으면 "1101"이 13이므로 출력은 6이 됩니다. 따라서 13은 홀수이고 1을 더하고 14를 얻습니다. 그런 다음 14는 짝수이고 2로 나누고 7을 얻습니다. 7이 홀수이면 1을 더하고 8을 얻습니다.
그런 다음 8은 다시 2로 나누고 4를 얻습니다. 다시 4는 짝수이고 2로 나누어 2를 얻고 마지막으로 2는 짝수이고 2로 나누어 1을 얻습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
addStrings() 함수를 정의하면 배열 num1, 배열 num2,
가 사용됩니다. -
ret 배열 정의
-
캐리 :=0, 합계 :=0
-
num1 및 num2 반전
-
i :=0, j :=0
-
동안 (i
-
i
-
합계 :=캐리 + (num1[i] + num2[j])
-
ret 끝에 sum mod 2 삽입
-
캐리 :=합계 / 2
-
(i를 1씩 증가)
-
(j를 1씩 증가)
-
-
그렇지 않으면 i
-
합계 :=캐리 + (num1[i])
-
ret 끝에 sum mod 2 삽입
-
캐리 :=합계 / 2
-
(i를 1씩 증가)
-
-
그렇지 않으면
-
합계 :=캐리 + (num2[j])
-
ret 끝에 sum mod 2 삽입
-
캐리 :=합계 / 2
-
(j를 1씩 증가)
-
-
-
캐리가 0이 아니면 -
-
ret 끝에 캐리 삽입
-
-
i :=ret의 크기
-
ans :=빈 문자열
-
i>=0인 경우 업데이트(i를 1만큼 감소), 수행 -
-
ans :=ans + (ret[i] + '0'의 ASCII)
-
-
반환(as의 크기가 0과 같으면 "0", 그렇지 않으면 as)
-
addBinary() 함수를 정의하면 배열 a, 배열 b,
를 취합니다. -
addStrings(a, b)를 반환
-
배열 makeVector를 정의하고 v
에서 복사-
ret 배열 정의
-
initialize i :=0의 경우 i
-
v[i] 삽입 - ret의 끝에 '0'의 ASCII
-
-
리턴 렛
-
-
기본 방법에서 다음을 수행합니다.
-
ret :=0
-
배열 정의 x =s
의 makeVector -
x의 크기가 1인 동안 −
-
(ret 1 증가)
-
x의 마지막 요소가 0과 같으면 -
-
x에서 마지막 요소 삭제
-
-
그렇지 않으면
-
크기가 1인 어레이 온도 정의
-
온도[0] :=1
-
x :=makeVector(addBinary(x, 임시))
-
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string addStrings(vector<int> num1, vector<int> num2){
vector<int> ret;
int carry = 0;
int sum = 0;
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int i = 0;
int j = 0;
while (i < num1.size() || j < num2.size()) {
if (i < num1.size() && j < num2.size()) {
sum = carry + (num1[i]) + (num2[j]);
ret.push_back(sum % 2);
carry = sum / 2;
i++;
j++;
}
else if (i < num1.size()) {
sum = carry + (num1[i]);
ret.push_back(sum % 2);
carry = sum / 2;
i++;
}
else {
sum = carry + (num2[j]);
ret.push_back(sum % 2);
carry = sum / 2;
j++;
}
}
if (carry)
ret.push_back(carry);
i = ret.size() - 1;
string ans = "";
for (; i >= 0; i--)
ans += (ret[i] + '0');
return ans.size() == 0 ? "0" : ans;
}
string addBinary(vector<int>& a, vector<int>& b){
return addStrings(a, b);
}
vector<int> makeVector(string v){
vector<int> ret;
for (int i = 0; i < v.size(); i++)
ret.push_back(v[i] - '0');
return ret;
}
int numSteps(string s){
int ret = 0;
vector<int> x = makeVector(s);
while (x.size() > 1) {
ret++;
if (x.back() == 0) {
x.pop_back();
}
else {
vector<int> temp(1);
temp[0] = 1;
x = makeVector(addBinary(x, temp));
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.numSteps("1101"));
} 입력
"1101"
출력
6