class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        ListNode dummy = new ListNode(1), ptr = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int l1Val = 0, l2Val = 0, sum = 0;
            if (l1 != null) {
                l1Val = l1.val;
            }
            if (l2 != null) {
                l2Val = l2.val;
            }
            sum = l1Val + l2Val + carry;
            int currDigit = sum % 10;
            carry = sum / 10;
            ptr.next = new ListNode(currDigit);
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
            ptr = ptr.next;
        }
        return reverse(dummy.next);
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

class Solution {
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        StringBuilder lastSay = new StringBuilder("1");
        for (int i = 2; i <= n; i++) {
            lastSay = getCurrSay(lastSay);
        }
        return lastSay.toString();
    }

    private StringBuilder getCurrSay(StringBuilder lastSay) {
        int count = 1;
        lastSay.append('*');
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < lastSay.length() - 1; i++) {
            if (lastSay.charAt(i) == lastSay.charAt(i + 1)) {
                count += 1;
            } else {
                sb.append(count).append(lastSay.charAt(i));
                count = 1;
            }
        }
        return sb;
    }
}

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        helper(ans, new ArrayList<>(), 1, k, n);
        return ans;
    }

    private void helper(List<List<Integer>> ans, List<Integer> curr, int pos, int k, int remain) {
        if (curr.size() == k) {
            if (remain == 0) {
                ans.add(new ArrayList<>(curr));
            }
            return;
        }
        if (remain < 0) {
            return;
        }
        for (int i = pos; i < 10; i++) {
            curr.add(i);
            helper(ans, curr, i + 1, k, remain - i);
            curr.remove(curr.size() - 1);
        }
    }
}

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i < j * j) {
                    break;
                }
                dp[i] = Math.min(dp[i], dp[i - (j * j)] + 1);
            }
        }
        return dp[n];
    }
}

class Solution {
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> findLeaves(TreeNode root) {
        TreeNode dummy = new TreeNode(0, root, null);
        while (dummy.left != null || dummy.right != null) {
            ans.add(new ArrayList<>());
            dfs(dummy);
        }
        return ans;
    }

    private boolean dfs(TreeNode node) {
        if (node == null) {
            return false;
        }
        if (node.left == null && node.right == null) {
            ans.get(ans.size() - 1).add(node.val);
            return true;
        }
        boolean isLeftLeaf = dfs(node.left);
        if (isLeftLeaf) {
            node.left = null;
        }
        boolean isRightLeaf = dfs(node.right);
        if (isRightLeaf) {
            node.right = null;
        }
        return false;
    }
}

class Solution {
    private final static int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public int countSubIslands(int[][] grid1, int[][] grid2) {
        boolean[][] visited = new boolean[grid2.length][grid2[0].length];
        int ans = 0;
        for (int i = 0; i < grid2.length; i++) {
            for (int j = 0; j < grid2[0].length; j++) {
                if (grid2[i][j] == 1 && !visited[i][j]) {
                    if (dfs(grid1, grid2, i, j, visited)) {
                        ans += 1;
                    }
                }
            }
        }
        return ans;
    }

    private boolean dfs(int[][] grid1, int[][] grid2, int row, int col, boolean[][] visited) {
        boolean coverAll = true;
        if (grid1[row][col] != 1) {
            coverAll = false;
        }
        visited[row][col] = true;
        for (int[] direction : DIRECTIONS) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if (!isOutOfBound(grid2, newRow, newCol) && grid2[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                if (!dfs(grid1, grid2, newRow, newCol, visited)) {
                    coverAll = false;
                }
            }
        }
        return coverAll;
    }

    private boolean isOutOfBound(int[][] grid2, int row, int col) {
        return row < 0 || col < 0 || row >= grid2.length || col >= grid2[0].length;
    }
}

class Solution {
    Map<TreeNode, Integer[]> memo = new HashMap<>();

    public int rob(TreeNode root) {
        return Math.max(dfs(root, 0), dfs(root, 1));
    }

    private int dfs(TreeNode node, int canRob) {
        if (node == null) {
            return 0;
        }
        if (memo.containsKey(node) && memo.get(node)[canRob] != null) {
            return memo.get(node)[canRob];
        }
        int max = Integer.MIN_VALUE;
        if (canRob == 1) {
            max = Math.max(max, dfs(node.left, 0) + dfs(node.right, 0) + node.val);
        }
        max = Math.max(max, dfs(node.left, 1) + dfs(node.right, 1));
        memo.putIfAbsent(node, new Integer[2]);
        memo.get(node)[canRob] = max;
        return max;
    }
}

class Solution {
    public int minCost(int[][] costs) {
        Integer[][] cache = new Integer[costs.length][3];
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < costs[0].length; i++) {
            ans = Math.min(ans, dfs(costs, 1, i, cache) + costs[0][i]);
        }
        return ans;
    }

    private int dfs(int[][] costs, int pos, int last, Integer[][] cache) {
        if (pos == costs.length) {
            return 0;
        }
        if (cache[pos][last] != null) {
            return cache[pos][last];
        }
        int minimum = Integer.MAX_VALUE;
        for (int i = 0; i < costs[pos].length; i++) {
            if (i == last) {
                continue;
            }
            minimum = Math.min(minimum, dfs(costs, pos + 1, i, cache) + costs[pos][i]);
        }
        return cache[pos][last] = minimum;
    }
}

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int firstMax = 0, secondMax = 0, ans = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            int currMax = Math.max(firstMax + nums[i], secondMax);
            firstMax = secondMax;
            secondMax = currMax;
        }
        ans = secondMax;
        firstMax = 0;
        secondMax = 0;
        for (int i = 1; i < nums.length; i++) {
            int currMax = Math.max(firstMax + nums[i], secondMax);
            firstMax = secondMax;
            secondMax = currMax;
        }
        ans = Math.max(ans, secondMax);
        return ans;
    }
}

class Solution {
    public boolean reorderedPowerOf2(int n) {
        int currNum = 1;
        int[] nCountArray = countDigits(n);
        for (int pow = 0; pow < 30; pow++) {
            if (Arrays.equals(nCountArray, countDigits(currNum))) {
                return true;
            }
            currNum <<= 1;
        }
        return false;
    }

    private int[] countDigits(int num) {
        int[] digitArray = new int[10];
        while (num != 0) {
            digitArray[num % 10] += 1;
            num /= 10;
        }
        return digitArray;
    }

}