2주차 2차 1 - LeetCode-Study-Team/solutions GitHub Wiki

322 Coin Change

Summary

i 개 동전으로 n 금액을 만들 수있는 최소 개수를 구하여라

점화식

  • f(n): 동전으로 n금액을 만들 수 있는 최소 개수
  • f(n) = min(f(n), f(n - coins) + 1)

Bottom Up Time: O(N * Amount), Space: O(Amount)

int coinChange(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    int[] ret = new int[amount+1];

    Arrays.fill(ret, -1);
    ret[0] = 0;

    for (int i = 1; i <= amount; i++) {

        for (int j = 0; j < coins.length; j++) {
            if (i - coins[j] >= 0 && ret[i - coins[j]] != -1 ) {
                if (ret[i] == -1) { // initialize
                    ret[i] = ret[i - coins[j]] + 1;
                } else {
                    ret[i] = Math.min(ret[i], ret[i - coins[j]] + 1);
                }
            }
        }
    }

    return ret[amount];        
}

Top Down - BFS

public int coinChange(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }

    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[amount + 1];

    queue.offer(amount);
    visited[amount] = true;
    int currLevel = 1;

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            int curr = queue.poll();

            for (int coin : coins) {
                int child = curr - coin;
                if (child == 0) {
                    return currLevel;
                } else if (child > 0 && !visited[child]) {
                    queue.add(child);
                    visited[child] = true;
                }
            }
        }
        currLevel++;
    }

    return -1;
}

200 Number of Islands

Summary

m x n 메트릭스에서 '1'로 표기되는 영역(land)수 구하기

접근법

  • DFS 로 1개 영역을 찾고, 반복해서 남은 영역 검사.
  • visited 를 별도 만들지 말지 선택

DFS

public int numIslands(char[][] grid) {
    int count=0;
    for(int i=0;i<grid.length;i++)
        for(int j=0;j<grid[0].length;j++){
            if(grid[i][j]=='1'){
                dfsFill(grid,i,j);
                count++;
            }
        }
    return count;
}
private void dfsFill(char[][] grid,int i, int j){
    if(i>=0 && j>=0 && i<grid.length && j<grid[0].length&&grid[i][j]=='1'){
        grid[i][j]='0';
        dfsFill(grid, i + 1, j);
        dfsFill(grid, i - 1, j);
        dfsFill(grid, i, j + 1);
        dfsFill(grid, i, j - 1);
    }
}

BFS

public int numIslands(char[][] grid) {
    int count=0;
    for(int i=0;i<grid.length;i++)
        for(int j=0;j<grid[0].length;j++){
            if(grid[i][j]=='1'){
                bfsFill(grid,i,j);
                count++;
            }
        }
    return count;
}
private void bfsFill(char[][] grid,int x, int y){
    grid[x][y]='0';
    int n = grid.length;
    int m = grid[0].length;
    LinkedList<Integer> queue = new LinkedList<Integer>();
    int code = x*m+y;
    queue.offer(code);
    while(!queue.isEmpty())
    {
        code = queue.poll();
        int i = code/m;
        int j = code%m;
        if(i>0 && grid[i-1][j]=='1')    //search upward and mark adjacent '1's as '0'.
        {
            queue.offer((i-1)*m+j);
            grid[i-1][j]='0';
        }
        if(i<n-1 && grid[i+1][j]=='1')  //down
        {
            queue.offer((i+1)*m+j);
            grid[i+1][j]='0';
        }
        if(j>0 && grid[i][j-1]=='1')  //left
        {
            queue.offer(i*m+j-1);
            grid[i][j-1]='0';
        }
        if(j<m-1 && grid[i][j+1]=='1')  //right
        {
            queue.offer(i*m+j+1);
            grid[i][j+1]='0';
        }
    }
}

DisJoint SET

⚠️ **GitHub.com Fallback** ⚠️