Leetcode 75 day6 (Counting Bits, Reverse Vowels of a String, Guess Number Higher or Lower)

6번째 날에는 비트연산, 문자열, 이진 검색 패턴의 문제를 풀어봤다.

338. Counting Bits

정수 n이 주어졌을 때 0부터 n까지 n+1개 숫자의 이진 표현에서 1의 개수를 저장한 배열을 리턴한다.

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

각 숫자별로 시프팅을 하면서 1과 논리 연산을 해서 1의 개수를 카운트하여 리턴해준다.

class Solution {
    public int[] countBits(int n) {
        int[] ret = new int[n+1];
        for(int i=1; i<=n; i++) {
            ret[i] = bits(i);
        }
        return ret;
    }

    private int bits(int n) {
        int cnt=0;
        while(n > 0) {
            if ((n & 1) == 1) {
                cnt++;
            }
            n = n >> 1;
        }
        return cnt;
    }
}

bits 함수를 호출하는데 O(logn), n개에 대해서 bits 함수를 호출하기 때문에 시간 복잡도는 O(nlogn)이고, 공간 복잡도는 배열을 리턴하기 위해서 O(n)이다.

345. Reverse Vowels of a String

문자열에서 모음끼리만 순서를 뒤집은 문자열을 반환해야 한다.

Given a string s, reverse only all the vowels in the string and return it.
The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

문자열은 in place 수정이 불가능하기 때문에 StringBuilder 객체를 생성하고 모음을 문자열 양쪽 끝에서부터 찾아서 swap 해주었다.

class Solution {
    public String reverseVowels(String s) {
        StringBuilder sb = new StringBuilder(s);
        int l=0;
        int r = s.length()-1;
        while(l < r) {
            while(l < r && !isVowel(s.charAt(l))) {
                l++;
            }
            while(l < r && !isVowel(s.charAt(r))) {
                r--;
            }
            if (l < r) {
                char tmp = s.charAt(l);
                sb.setCharAt(l, s.charAt(r));
                sb.setCharAt(r, tmp);
                l++;
                r--;
            }
        }
        return sb.toString();
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
        c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
    }
}

문자열의 길이를 n이라고 했을 때 시간 복잡도는 O(n), 공간 복잡도는 StringBuilder 객체에 문자열을 복사하기 때문에 O(n)이다.

374. Guess Number Higher or Lower

인자를 n으로 받아서 1부터 n 사이에서 선택한 값을 추측하여 맞히는 문제. guess 함수를 호출했을 때 선택된 값이 내 추측보다 크다면 1, 작다면 -1, 맞추면 0을 리턴한다.

We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num), which returns three possible results:
-1: Your guess is higher than the number I picked (i.e. num > pick).1: Your guess is lower than the number I picked (i.e. num < pick).0: your guess is equal to the number I picked (i.e. num == pick).
Return the number that I picked.

주어진 숫자 범위 내에서 이진 검색으로 선택된 값을 찾으면 된다. 

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        return guessNumber(0, n);
    }

    private int guessNumber(int left, int right) {
        int mid = left + (right-left)/2;
        int res = guess(mid);
        if (res == 0) { // num == pick
            return mid;
        }
        if (res == -1) { // num > pick
            return guessNumber(left, mid);
        }
        // num < pick
        return guessNumber(mid+1, right);
    }
}

시간 복잡도는 O(logn), 공간 복잡도는 O(1)이다.