(Leetcode) 190 - Reverse Bits
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/reverse-bits/description/
내가 작성한 풀이
public class Solution {
int MASK = 0x7FFFFFFF;
// you need treat n as an unsigned value
public int reverseBits(int n) {
char[] bits = Integer.toBinaryString(n).toCharArray();
StringBuilder reversedBits = new StringBuilder();
for(char bit : bits) {
reversedBits.insert(0, bit);
}
while(reversedBits.length() < 32) {
reversedBits.append(0);
}
short signbit = Short.parseShort(String.valueOf(reversedBits.charAt(0)));
int lastbits = Integer.valueOf(reversedBits.substring(1), 2);
if (signbit == 1) {
return (lastbits^MASK + 1);
}
return lastbits;
}
}
binary string을 charArray로 변환한 후, 역순으로 다시 string 화 해서 처리하였다.
더 좋은 풀이 방법
public class Solution {
public int reverseBits(int n) {
int ans = 0;
for (int i = 0; i < 32; i++) {
ans <<= 1;
ans |= (n & 1);
n >>= 1;
}
return ans;
}
}
for 문 안의 블록을 설명해보면 다음과 같다. n에서 한자리씩 ans로 옮기는 것이라고 생각하면 된다.
ans <<= 1: ans 변수를 좌측으로 1만큼 시프트한다.ans |= (n & 1): n의 가장 오른쪽 비트를 ans에 추가한다.(n & 1)은 n의 가장 오른쪽 비트를 추출하는 연산이며 이를 ans에 추가하기 위해 비트 OR 연산자|를 사용한다.n >>= 1n 변수를 오른쪽으로 1만큼 시프트한다. ans에 추가된 비트는 제거한다.
TC, SC
두 코드의 시간 복잡도는 O(32) → O(1)이고, 공간 복잡도는 O(32) → O(1)이다.