Leetcode–Subsets

The Problem:

Given a set of distinct integers, S, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Notes:

  1. Sort the input list first, and then add each next element to all existing list in result. Remember to add an empty set first.

Java Solution

public class Solution {
    public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result.add(new ArrayList<Integer>());
        if(S.length==0){
            return result;
        }
        Arrays.sort(S);
        for(int i = 0; i < S.length; i++){
            int len = result.size();
            for(int j = 0; j < len; j++){
                ArrayList<Integer> addlist =  new ArrayList<Integer>(result.get(j));
                addlist.add(S[i]);
                result.add(addlist);
            }
        }
        return result;
    }
}

Leetcode–Gray Code

The Problem:

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Notes:

  1. List a few examples then a pattern reveals. The list of n is the list of n-1 appends another list created by reversing the list of n-1 and adding a leading 1 to each element.

Java Solution

public class Solution {
    public List<Integer> grayCode(int n) {
        // combo fo rn is the reverse of combo for n-1, and left append 1
        List<Integer> result = new ArrayList<Integer>();
        
        result.add(0);
        if(n==0) return result;
        result.add(1);
        if(n==1)return result;
        
        for(int j = 2; j <=n; j++){
            List<Integer> append = new ArrayList<Integer>();
            int num = 1<<(j-1);
            for(int i = result.size()-1; i>=0; i--){
                append.add( num+ result.get(i));
            }
            result.addAll(append);
        }
        return result;
    }
    
}

Leetcode–Letter Combinations of a Phone Number

The Problem:

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"].

Notes:

  1. Similar to Combinations, just list every combination.
  2. I tried using StringBuffer instead of String, the speed doesn’t show a big difference, but code gets less concise. Anyway, I think StringBuffer is a better choice and will show advantage when test cases gets bigger.

Java Solution

public class Solution {
    public List<String> letterCombinations(String digits) {
        String[] letters= {" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        List<String> res = new ArrayList<String>();
        if(digits==null || digits.length()==0){
            res.add("");
            return res;
        }
        
        for(int i = 0; i < digits.length(); i++){
            if(letters[digits.charAt(i)-'0'].length()!=0){
                List<String> temp = new ArrayList<String>();
                for(int j = 0; j < letters[digits.charAt(i)-'0'].length(); j++){
                    if(res.size()==0){
                        temp.add(""+letters[digits.charAt(i)-'0'].charAt(j));
                    }
                    else{
                        for(String s: res){
                            temp.add(s+letters[digits.charAt(i)-'0'].charAt(j));
                        }
                    }
                }
                res = temp;
            }
        }
       
        return res;
    }
}

Leetcode–Combination Sum II

The Problem:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Notes:

  1. Similar to Combination Sum, use recursion. But this time we cannot use same number repeatedly, so get a bool array to record the index of those already used.
  2. No duplicates allowed in result. Even we did the same thing of sorting the array, record the index and only examine larger number when appending to list, there is one condition could result in duplicates: the input array contains duplicates, so even the numbers in result refer to different indices in input array, they are still the same numbers. Here I used the same trick as for other duplication check–maintain a hash set of list.toString().

Java Solution

public class Solution {
    List<List<Integer>> result;
    HashSet<String> resSet;
    public List<List<Integer>> combinationSum2(int[] num, int target) {
        result = new ArrayList<List<Integer>>();
        if(num==null || num.length==0) return result;
        Arrays.sort(num);
        resSet = new HashSet<String>();
        findTarget(num, -1, target, new ArrayList<Integer>(), new boolean[num.length]);
        return result;
    }
    
    private void findTarget(int[] num, int index, int tar, List<Integer> onelist, boolean[] used){
        for(int i = index+1; i < num.length; i++){
            if(!used[i]){
                if(tar-num[i]==0){
                    List<Integer> newlist = new ArrayList<Integer>(onelist);
                    newlist.add(num[i]);
                    if(!resSet.contains(newlist.toString())){
                        result.add(newlist);
                        resSet.add(newlist.toString());
                    }
                }
                else if(tar - num[i] > 0){
                    List<Integer> newlist = new ArrayList<Integer>(onelist);
                    newlist.add(num[i]);
                    used[i] = true;
                    findTarget(num, i, tar-num[i], newlist, used);
                    used[i] = false;
                }
            }
        }
    }
}

Leetcode–Combination Sum

The Problem:

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Notes:

  1. As we allow using each number repeatedly,  the problem can be looked as recursive that we are going through the same loop to look for a target (the original target, or it subtract the numbers added to the list).
  2. As we don’t allow duplicates in the final result, the array need to be sort first. The index of element we are looking at should be passed to next recursion call, and only examine the index after, so that an ascending order is enforced in result.

Java Solution

public class Solution {
    public List<List<Integer>> result;
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        result = new ArrayList<List<Integer>>();
        if(candidates== null || candidates.length==0)return result;
        Arrays.sort(candidates);
        
        findTarget(target, candidates, 0, new ArrayList<Integer>());
        return result;
    }
    
    public void findTarget(int tar, int[] candidates, int index, List<Integer> onelist){
        for(int i = index; i < candidates.length; i++){
            if(tar-candidates[i] == 0){
                List<Integer> temp = new ArrayList<Integer>(onelist);
                temp.add(candidates[i]);
                result.add(temp);
            }
            else if(tar - candidates[i] > 0){
                List<Integer> temp = new ArrayList<Integer>(onelist);
                temp.add(candidates[i]);
                findTarget(tar-candidates[i], candidates, i, temp);
            }
        }
    }
    
}

Leetcode–Combinations

The Problem:

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Notes:

  1. In each iteration, choose one number larger than the tail element , and append to the list.

Java Solution

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(k==0) return result;
        for(int i = 1; i <= n-k+1; i++){
            List<Integer> list = new ArrayList<Integer>();
            list.add(i);
            result.add(list);
        }
        k--;
        while(k>0){
            List<List<Integer>> temp = new ArrayList<List<Integer>>();
            for(List<Integer> onelist : result){
                int last = onelist.get(onelist.size()-1);
                for(int j = last+1; j<=n; j++){
                    List<Integer> newone = new ArrayList<Integer>(onelist);
                    newone.add(j);
                    temp.add(newone);
                }
            }
            result = temp;
            k--;
        }
        return result;
    }
}

Leetcode–Permutation Sequence

The Problem:

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Notes:

  1. The key is to use an array or list to record the numbers to be added, then can access that number just according to the index calculated from k. Also I used linkedlist to store the numbers which makes it easier to remove each number after chosen.
  2. input k should be decreased first before treating as index

Java Solution

public class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new LinkedList<Integer>();
        int multiplys = 1;
        for(int i= 0; i<n; i++){
            multiplys= multiplys*(i+1);
            numbers.add(i+1);
        }
        
        k--; //---!! k is not array index
        StringBuilder result  = new StringBuilder();
        for(int i =0; i < n; i++){
            multiplys = multiplys/(n-i);
            int index = k/multiplys;
            result.append(numbers.get(index));
            numbers.remove(index);
            k = k%multiplys;
        }
        return result.toString();
    }
}