Leetcode 75 day8 (N-th Tribonacci Number, Min Cost Climbing Stairs, Single Number)

1차원 DP 문제 둘, 비트연산 문제 하나

1137. N-th Tribonacci Number

피보나치 넘버가 아닌 n 번째 트리보나치 넘버 문제.

The Tribonacci sequence Tn is defined as follows: 
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given n, return the value of Tn.

피보나치는 동적 프로그래밍 단골 예제라 설명할 것도 없다.

class Solution {
    private int[] trib = {0, 1, 1};
    public int tribonacci(int n) {
        if (n < 3) {
            return trib[n];
        }
        int[] ret = new int[n+1];
        ret[0] = trib[0];
        ret[1] = trib[1];
        ret[2] = trib[2];
        for(int i=3; i<=n; i++) {
            ret[i] = ret[i-1] + ret[i-2] + ret[i-3];
        }
        return ret[n];
    }
}

시간 복잡도, 공간 복잡도 O(n).

746. Min Cost Climbing Stairs

i 번째 계단을 디딜 때 코스트가 cost[i] 일 때 한 개 또는 두 개의 스텝을 건널 수 있다. 그리고 시작은 0번째나 1번째 계단에서 시작할 수 있을 때 정상에 올라가는 최소한의 비용을 구하는 문제다.

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.

각 계단을 올라가는 최소한의 비용을 저장한 배열을 sum이라고 할 때, i 번째 계단으로 가는 최소한의 비용은 Math.min(sum[i-2]+cost[i-2], sum[i-1]+cost[i-1])로 정의할 수 있다. 시작을 0번째 또는 1번째 계단에서 할 수 있기 때문에 sum[0]=0, sum[1]=0 으로 초기화할 수 있다. 그러면 문제에서 구하는 답은 sum[cost.length]으로 정의할 수 있다.

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] sum = new int[len+1];
        for(int i=2; i<=len; i++) {
            sum[i] = Math.min(sum[i-2]+cost[i-2], sum[i-1]+cost[i-1]);
        }
        
        return sum[len];
    }
}

시간복잡도 O(n), 공간복잡도 O(n)

136. Single Number

주어진 배열에 정수가 한 개를 제외하고는 두 개씩 들어있다. 이 때 한 개인 정수를 찾아라. 솔루션 코드는 반드시 선형 시간 복잡도이고 상수 공간 복잡도를 가져야 한다.

Given a non-empty array of integers nums, every element appears twice except for one.
Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.

비트 연산이 관련 주제인 것을 알았음에도 불구하고, 비트 연산 기본 지식을 몰라서 조건대로 풀지 못한 문제다...😢

다음과 같은 공식을 활용하면 코드를 조건대로 구현할 수 있다.

A XOR 0 = A

A XOR A = 0

A XOR (B XOR C) = (A XOR B) XOR C

class Solution {
    public int singleNumber(int[] nums) {
        int ans=0;
        for(int n : nums) {
            ans = ans ^ n;
        }
        return ans;
    }
}

시간복잡도 O(n), 공간복잡도 O(1).