Leetcode

Leetcode-Two Sum(Java)

Question:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Thinking:

We can use hash map to store the rest of nums[i], and if we find which number is equal to the rest beofore, their sum will be target.

Solution:

public int[] twoSum(int[] nums, int target){
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    int[] res = new int[2];

    for (int i = 0; i < nums.length; i++){
        if (map.containsKey(nums[i])){
            res[0] = map.get(nums[i]) + 1;
            res[1] = i+1;
            break;
        }
        else{
            map.put(target-nums[i], i);
        }
    }

    return res;
}
Leetcode

Leetcode-Game of Life(Java)

Question:

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.

Follow up:
Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Thinkings:

It’s difficult quesiont, isn’t it? We have to fully understand when cell become live or dead and try to replace them in place. One solution is to present their status using bits, the first bit represents their current status and second bit represents their next status. For example:

current status is live and next status will be dead is 01
current status is dead and next status will be live is 10

And then we can get the current status by:

board[i][j] & 1

Get the finnaly status by:

board[i][j] >>= 1

Solution:

public void gameOfLife(int[][] board) {
    int m = board.length;
    if (m == 0)
        return;
    int n = board[0].length;

    //int[][] temp = new int[m][n];


    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            int count = 0;
            for (int p = -1; p < 2; p++)
                for (int q = -1; q < 2; q++){
                    if (i+p>=0 && i+p<m && j+q>=0 && j+q<n && !(p==0 && q==0)){
                        if ((board[i+p][j+q] & 1) == 1)
                            count++;
                    }
                }

            if ((board[i][j] & 1) == 0 && count == 3){
                //temp[i][j] = 1;
                board[i][j] = 2;
            }
            else if ((board[i][j] & 1) == 1 && count <=3 && count >= 2){
                    board[i][j] = 3;

            }
        }
    }

    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            //board[i][j] = temp[i][j];
            board[i][j] >>= 1;
        }
    }
}
Leetcode

Leetcode-Letter Combinations of a Phone Number(Java)

Question:

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Thinking:

We should get all the possiblities of the comibination so we need use backtracing.

Solution:

import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

public class Solution {
    static private Map<Character, char[]> hmap = new HashMap<Character, char[]>();

    private Character two = new Character('2');
    private char[] twoC = {'a', 'b', 'c'};
    private Character three = new Character('3');
    private char[] threeC = {'d', 'e', 'f'};
    private Character four = new Character('4');
    private char[] fourC = {'g', 'h', 'i'};
    private Character five = new Character('5');
    private char[] fiveC = {'j', 'k', 'l'};
    private Character six = new Character('6');
    private char[] sixC = {'m', 'n', 'o'};
    private Character seven = new Character('7');
    private char[] sevenC = {'p', 'q', 'r', 's'};
    private Character eight = new Character('8');
    private char[] eightC = {'t', 'u', 'v'};
    private Character nine = new Character('9');
    private char[] nineC = {'w', 'x', 'y', 'z'};

    public Solution(){
        hmap.put(two, twoC);
        hmap.put(three, threeC);
        hmap.put(four, fourC);
        hmap.put(five, fiveC);
        hmap.put(six, sixC);
        hmap.put(seven, sevenC);
        hmap.put(eight, eightC);
        hmap.put(nine, nineC);
    }

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<String>();

        backTracing(digits, 0, "", res);

        return res;
    }

    private void backTracing(String digits, int index, String cur, List<String> res){
        int l = digits.length();
        if (l == 0)
            return;
        if (index == l){
            res.add(cur);
            return;
        }


        Character tmpc = new Character(digits.charAt(index));
        if(hmap.containsKey(tmpc)){
            for (char c :hmap.get(tmpc)){
                backTracing(digits, index+1, cur+c, res);
            }
        }

    }
}
Leetcode

Leetcode-Path Sum II(Java)

Question:

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return

[
      [5,4,11,2],
       [5,8,4,5]
]

Thinking:

We should use classic dfs method to solve this problem and record all the results.

Solution:

But my first version of solution is time limit exceeded:

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<Integer> res = new ArrayList<Integer>();

    return dp(root, sum, res);
}

private List<List<Integer>> dp(TreeNode root, int sum, List<Integer> cur){
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if (root == null)
        return null;
    if (root.left == null && root.right == null){
        if (root.val == sum){
            cur.add(root.val);
            res.add(cur);
            return res;
        }
        else{
            return res;
        }
    }
    for (List<Integer> ele: dp(root.left, sum-root.val, cur)){
        if (ele != null){
            ele.add(0, root.val);
            res.add(ele);
        }
    }
    for (List<Integer> ele: dp(root.right, sum-root.val, cur)){
        if (ele != null){
            ele.add(0, root.val);
            res.add(ele);
        }
    }

    return res;
}

Then I have to improve the effiency of this algorithm, and the code is below:

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<Integer> cur = new ArrayList<Integer>();
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    dp(root, sum, cur, res);

    return res;
}

private void dp(TreeNode root, int sum, List<Integer> cur, List<List<Integer>> res){
    if (root == null)
        return;
    //preorder dfs

    sum -= root.val;
    if (root.left == null && root.right == null){
        if (sum == 0){
            cur.add(root.val);
            List<Integer> tempres = new ArrayList<Integer>();
            tempres.addAll(cur);
            res.add(tempres);
            cur.remove(cur.size() - 1);
        }
        return;
    }
    cur.add(root.val);
    if (root.left != null){
        dp(root.left, sum, cur, res);
    }
    if (root.right != null){
        dp(root.right, sum, cur, res);
    }
    cur.remove(cur.size() - 1);
}

It’s very importatn to create a new List while put the current list data to final result, becuase if not we will only copy the address of this variable cur. Then it will be incorrect if we revise cur.