Single Number, Single Number II, Decode Ways, Triangle

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

O(n) Memory O(n) Time Solution

LTE? With an instantiated Iterator I can pass the OJ…

public int singleNumber(int[] A) {
    HashSet<Integer> set = new HashSet<Integer>();
    for(Integer i:A){
        if(set.contains(i)) set.remove(i);
        else set.add(i);
    }
    return set.iterator().next();
}

XOR Solution

Similar Problem

• n+1 elements in range n, find the duplicate. take XOR between 1 to n, and the given array.

• Here we use the property x^x=0，x^0=x

public int singleNumber(int[] A) {
    int res = 0;
    for(Integer i:A){
        res ^= i;
    }
    return res;
}

---

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution

• count 1 in each bit position among all A numbers.
• if a count can be divided by 3, then it does not contain single number

public int singleNumber(int[] A) {
    int[] count = new int[32];
    int res=0;
    for(int i=0;i<32;i++){
        for(int j=0;j<A.length;j++){
            if((A[j]>>i & 1)==1){
                count[i]+=1; //increment bit bin
            }
        }
        res |= count[i]%3 << i; //recover single number
    }
    return res;
}

---

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).
The number of ways decoding “12” is 2.

Recursive Solution

• quite straight forward…? LTE..
• when at i, we can decode i separately , or decode i,i+1 as a whole
• checking conditions: 1X or <26, then we can return substr(1) + substr(2).
• only when len==2 under this case, s.len would be 0, and return 1

public int numDecodings(String s) {
    if(s.length() == 0 || s.length() == 1 && s.charAt(0) != '0')
        return 1;
    if(s.charAt(0) == '0')
        return 0;
    if(s.charAt(0) == '1' || (s.charAt(0) == '2' && s.charAt(1) <= '6'))
        return numDecodings(s.substring(1)) + numDecodings(s.substring(2));
    return numDecodings(s.substring(1));
}

DP Solution

＋ ways[i] represents the # of decoding from i to end

• given s[i] is not ‘0’, we can always decode s in ways[i+1] ways, viewing s[i] as a separate code, ways[i] = ways[i+1]
• check if i,i+1 forms a valid code, ways[i] = ways[i+1] + ways[i+2]
• if s[i] is ‘0’, ways[i] is set to 0

public int numDecodings(String s) {
    if(s.length() == 0 || s==null || s.charAt(0) == '0')
    return 0;
    int[] ways = new int[s.length()+1];
    ways[s.length()] = 1;
    for(int i=s.length()-1; i>=0;i--){
        if(s.charAt(i) == '0') ways[i]=0;
        else ways[i] = ways[i+1];
        if(i+1<s.length() && (s.charAt(i) == '1' || s.charAt(i) == '2' && s.charAt(i+1) <= '6'))
            ways[i] = ways[i] + ways[i+2];
    }
    return ways[0];
}

DP forward

public int numDecodings(String s) {
    int[] ways = new int[s.length()+1];
    if(s==null || s.length()==0) return 0;
    if(s.charAt(0)=='0') return 0;
    ways[0] = 1;
    ways[1] = 1;
    for(int i=2;i<=s.length();i++){
        if(s.charAt(i-1)=='0'){
            if(s.charAt(i-2)=='1' ||s.charAt(i-2)=='2'){ways[i]=ways[i-2]; }
            else return 0;
        }
        else{
            if(s.charAt(i-1)<='6' && s.charAt(i-2)=='2' || s.charAt(i-2)=='1'){
                ways[i]=ways[i-1]+ways[i-2];
            }   
            else ways[i]=ways[i-1];
        }
    }
    return ways[s.length()];
}

O(1) Space DP

 public int numDecodings(String s) {
    if(s==null || s.length()==0 || s.charAt(0)=='0') return 0;
    int twopre = 1;
    int onepre = 1;
    int cur = 1;
    for(int i=1;i<s.length();i++){
        if(s.charAt(i)=='0'){
            if(s.charAt(i-1)=='1' ||s.charAt(i-1)=='2'){cur = twopre; }
            else return 0;
        }
        else{
            if(s.charAt(i)<='6' && s.charAt(i-1)=='2' || s.charAt(i-1)=='1'){
                cur = twopre + onepre;
            }   
            else cur=onepre;
        }
        twopre=onepre;
        onepre=cur;
    }
    return cur;
}

---

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below
For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Inplace DP Solution

• start from second to end level, change each element to the smaller sum with lower level’s two adjacent elements
• the top one will be the shortest path

public int minimumTotal(List<List<Integer>> triangle) {
    for(int i=triangle.size()-2; i>=0; i--){
        List<Integer> tmp = triangle.get(i);
        for(int j=0;j<tmp.size();j++){
            tmp.set(j, tmp.get(j) + Math.min(triangle.get(i+1).get(j),triangle.get(i+1).get(j+1)));
        }    
    }
    return triangle.get(0).get(0);
}