clueless coding // TODO: be smarter

LeetCode 441. Arranging Coins: C++ Solution



Problem Statement


You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Function Signature (C++):
  int arrangeCoins(int n)

Inputs:
  n = 5

Outputs:
  2

We can create rows like this:
¤
¤ ¤
¤ ¤
There are 2 full rows.

Inputs:
  n = 8

Outputs:
  3

We can create rows like this:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
There are 3 full rows.



TL;DR Code Solution


int arrangeCoins(int n) {

    long left = 1;
    long right = n;

    while (left <= right) {
        long middle = (left + right) / 2;
        long sum = (middle * (middle + 1)) / 2.0;

        if (sum < n) {
            left = middle + 1;
        }
        else if (sum > n) {
            right = middle - 1;
        }
        else {
            return middle;
        }
    }

    return left - 1;

}

LeetCode 441. Arranging Coins: Java Solution



Problem Statement


You have a grand total of n coins that you want to form into a staircase. Every k-th row must have exactly k coins to be “full”.

Given n total coins, find the total number of full staircase rows that can be formed.

You can assume that n is a non-negative integer and also fits within the range of a 32-bit signed integer.

Function Signature (Java):
  int arrangeCoins(int n)

Inputs:
  n = 5

Outputs:
  2

We can create rows like this:
¤
¤ ¤
¤ ¤
There are 2 full rows.

Inputs:
  n = 8

Outputs:
  3

We can create rows like this:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
There are 3 full rows.



TL;DR Code Solution


public int arrangeCoins(int n) {

    int start = 0;
    int end = n;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) >>> 1;
        if ((0.5 * mid * mid + 0.5 * mid ) <= n) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    return start - 1;

}

LeetCode Assign Cookies: Java Solution



Problem Statement


Assume that you are handing out cookies to children.

Assume also that you should give each child at most one cookie.

Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj.

If sj >= gi, we can assign the cookie j to the child i, and the child i will be content.

Maximize the number of your content children and output the maximum number.

Function Signature (Java):
  int findContentChildren(int[] g, int[] s)

Inputs:
  g = [1,2,3]
  s = [1,1]

Outputs:
  1

You have 3 children and 2 cookies.

You can give one cookie to the child with greed factor 1, and he/she will be satisfied.

However, the next cookie is too small; we only have a cookie of size one, and both children left would only be satisfied with size 2 and 3 cookies.

Therefore, we can satisfy only one child.



TL;DR Code Solution


public int findContentChildren(int[] g, int[] s) {

    Arrays.sort(g);
    Arrays.sort(s);

    int gp = 0;
    int sp = 0;

    while (gp < g.length && sp < s.length) {
        if (s[sp] >= g[gp]) {
            gp++;
        }
        sp++;
    }

    return gp;

}

LeetCode 110. Balanced Binary Tree: Java Solution



Problem Statement


Given a binary tree, determine if it is height-balanced.

A “height-balanced” binary tree is defined as a binary tree in which the depth (height) of the two subtrees of every node are never different by more than one.

Function Signature (Java):
  boolean isBalanced(TreeNode root)

Inputs:
    o
   / \
  o   o

Outputs:
  true

Inputs:
    o
     \
      o
       \
        o

Outputs:
  false



TL;DR Code Solution



int helper(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int right = helper(root.right);
    if (right == Integer.MIN_VALUE) return Integer.MIN_VALUE;
    int left = helper(root.left);
    if (left == Integer.MIN_VALUE) return Integer.MIN_VALUE;

    if (Math.abs(right - left) > 1) return Integer.MIN_VALUE;

    return Math.max(right, left) + 1;
}

public boolean isBalanced(TreeNode root) {
   return helper(root) != Integer.MIN_VALUE;
}

LeetCode 419. Battleships in a Board: C++ Solution



Problem Statement


Given an 2D board, count the total number of battleships on it.

Battleships are represented by ‘X’s,

Board slots without a battleship are represented by ‘.’s.

Assume that you have a valid board. Every spot is empty or contains a battleship.

Battleships can only be placed vertically or horizontally.

No two battleships are adjacent. Assume there’s at least one space between each battleship.

Function Signature (C++):
  int countBattleships(vector<vector<char>>& board)

Inputs:
X..X
...X
...X

Outputs:
  2

Inputs:
...X
XXXX
...X

Invalid board - adjacent battleships.



TL;DR Code Solution


bool isTopLeft(vector<vector<char>>& board, int i, int j) {

    bool leftMost = false;
    if (i == 0 || board[i-1][j] == '.') {
        leftMost = true;
    }

    bool topMost = false;
    if (j == 0 || board[i][j-1] == '.') {
        topMost = true;
    }

    return leftMost && topMost;

}

int countBattleships(vector<vector<char>>& board) {

    int result = 0;

    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[0].size(); j++) {
            if (board[i][j] == 'X' && isTopLeft(board, i, j)) {
                result++;
            }
        }
    }

    return result;

}

LeetCode 419. Battleships in a Board: Java Solution



Problem Statement


Given an 2D board, count the total number of battleships on it. Battleships are represented by ‘X’s, and empty board slots are represented by ‘.’s. You can assume the following information:

You receive a valid board - every spot is either an empty space or contains a battleship.

Battleships are placed horizontally or vertically.

No two battleships are ‘touching’ - every battleship has a least on space of separation between them. You will have no adjacent ‘X’s that do not belong to the same battleship.

Function Signature (Java):
  int countBattleships(char[][] board)

Inputs:
X..X.X
...X.X
...X..

Outputs:
  3

Inputs:
.X..
XXXX
.X..

Invalid board - adjacent battleships.



TL;DR Code Solution



public void dfs(char[][]board, int i, int j) {

    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'X') {
        return;
    }
    board[i][j] = 'x';

    dfs(board, i+1, j);
    dfs(board, i-1, j);
    dfs(board, i, j+1);
    dfs(board, i, j-1);

}

public int countBattleships(char[][] board) {

    int result = 0;

    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == 'X') {
                result += 1;
                dfs(board, i, j);
            }    
        }
    }

    return result;

}