114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6
//The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

思路: 用Stack,如果当前节点有右子树,把右子树入栈,左子树放到右子树,如果找到左子树叶子节点,左子树叶子节点接到stack中pop出来的右子树节点。
复杂度: Time O(n), Space O(n)

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
           if (cur.right != null) { // 右子树放到stack
               stack.push(cur.right);
           }
           if (cur.left != null) { // 如果右左子树,左子树变为右子树
               cur.right = cur.left;
               cur.left = null; // 原来左子树为null
           } else if (!stack.isEmpty()) { // 找到左子树的叶子
               TreeNode temp = stack.pop(); 
               cur.right = temp;
           }
           cur = cur.right;
        }
    }
}
Advertisements

419. Battleships in a Board

Given an 2D board, count how many different battleships are in it. The battleships are represented with ‘X’s, empty slots are represented with ‘.’s. You may assume the following rules:

You receive a valid board, made of only battleships or empty slots.
Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
At least one horizontal or vertical cell separates between two battleships – there are no adjacent battleships.
Example:
X..X
…X
…X
In the above board there are 2 battleships.
Invalid Example:
…X
XXXX
…X
This is an invalid board that you will not receive – as battleships will always have a cell separating between them.

思路: 找多少有多少条battleship,这个题目解法跟island题目完全相同。 用BFS或者DFS来遍历, 题目要求不准改动board的值,可以用个boolean的visited数组来解决;

public class Solution {
    private int[] xDir = new int[]{0, -1, 0, 1};
    private int[] yDir = new int[]{1, 0, -1, 0};

    public int countBattleships(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) return 0;
        int row = board.length;
        int col = board[0].length;
        int count = 0;
        boolean[][] visited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (!visited[i][j] && board[i][j] == 'X') {
                    countBattleships(board, visited, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public void countBattleships(char[][] board, boolean[][] visited, int x, int y) {
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) return;
        if (board[x][y] == '.' || visited[x][y]) return;
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int newX = x + xDir[i];
            int newY = y + yDir[i];
            countBattleships(board, visited, newX, newY);
        }
    }
}

Cache的三种pattern:write-through, write-around, write-back

Write-through: data is written simultaneously to the cache and disk storage. But the ack of the write is not sent to the application until the database write successfully completes the write.

Write-around: data is written to the database first, then a copy of that data promoted up to the cache.

Write-back: only update the cache and later the cache will update the database
asynchronously. However, the ack to the applications comes after the data is written to the cache, not to the database, which means ack occurs at the flash speed. But it may suffer data loss when cache fails before data has been flushed to the disk.

Comparing write-through, write-back and write-around caching

152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

思路: 乘积的最大值可能来自于两个正数相乘或者两个负数相乘。所以我们要同时来保存每次乘积的最大值跟最小值.
复杂度: time O(n), space: O(n)

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] maxProds = new int[nums.length];
        int[] minProds = new int[nums.length];
        int res = nums[0];
        maxProds[0] = minProds[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= 0) {
                maxProds[i] = Math.max(nums[i], maxProds[i-1] * nums[i]);
                minProds[i] = Math.min(nums[i], minProds[i-1] * nums[i]);
            } else {
                maxProds[i] = Math.max(nums[i], minProds[i-1] * nums[i]);
                minProds[i] = Math.min(nums[i], maxProds[i-1] * nums[i]);
            }
            res = Math.max(maxProds[i], res);
        }
        return res;
    }
}

53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

思路: DP的思路,用一个curSum跟maxSum来追踪.
复杂度 time O(n) space O(1)

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) 
            return Integer.MIN_VALUE;
        int curSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i &lt; nums.length; i++) {
            curSum = curSum &gt; 0 ? curSum + nums[i]: nums[i];
            maxSum = Math.max(curSum, maxSum);
        }
        return maxSum;
    }
}

150. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:
[“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9
[“4”, “13”, “5”, “/”, “+”] -> (4 + (13 / 5)) -> 6

思路: 用stack来实现, 数字就是入栈,运算符就pop出前两个值,进行计算再入栈。

public class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) return 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < tokens.length; i++) {
            String token = tokens[i];
            if (!isOperator(token)) {
                stack.push(Integer.valueOf(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                int res = calculate(num1, num2, token);
                stack.push(res);
            }
        }
        return stack.peek();
    }

    public boolean isOperator(String op) {
        if (op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/")) return true;
        return false;
    }

    public int calculate(int num1, int num2, String op) {
        if (op.equals("+")) {
            return num1 + num2;
        } else if (op.equals("-")) {
            return num1 - num2;
        } else if (op.equals("*")) {
            return num1 * num2;
        } else if (op.equals("/")) {
            return num1 / num2;
        } else {
            return 0;
        }
    }
}

341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6]
思路: 用一个List来盛放flatten之后的元素,同时用一个index来取当前flatten list的元素。

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List&lt;NestedInteger&gt; getList();
 * }
 */
public class NestedIterator implements Iterator&lt;Integer&gt; {
    List&lt;Integer&gt; flatList;
    int index;

    public NestedIterator(List&lt;NestedInteger&gt; nestedList) {
        flatList = new ArrayList&lt;Integer&gt;();
        index = 0;
        dumpToList(nestedList, flatList);
    }

    public void dumpToList(List&lt;NestedInteger&gt; nestedList, List&lt;Integer&gt; flatList) {
        for (NestedInteger ni : nestedList) {
            if (ni.isInteger()) {
                flatList.add(ni.getInteger());
            } else {
                dumpToList(ni.getList(), flatList);
            }
        }
    }


    @Override
    public Integer next() {
        if (hasNext()) {
            Integer result = flatList.get(index);
            index++;
            return result;
        } 
        return null;
    }

    @Override
    public boolean hasNext() {
        return index &lt; flatList.size();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */