一个月刷完cc150

16.15
Problem:
The Game of Master Mind is played as follows:
The computer has four slots, and each slot will contain a ball that is red (R), yellow (Y), green (G) or blue (B). For example, the computer might have RGGB (Slot #1 is red, Slots #2 and #3 are green, Slot #4 is blue).
You, the user, are trying to guess the solution. You might, for example, guess YRGB.
When you guess the correct color for the correct slot, you get a "hit:' If you guess a color that exists but is in the wrong slot, you get a "pseudo-hit:' Note that a slot that is a hit can never count as a pseudo-hit.
For example, if the actual solution is RGBY and you guess GGRR , you have one hit and one pseudo- hit
Write a method that, given a guess and a solution, returns the number of hits and pseudo-hits.

Analysis:
We can go through the solution string and count hits and pseudo-candidate color frequencies on the way. Then go through guess string and reduce frequencies when count one pseudo-hit.

Code:
public Class Result{
    int hit;
    int peudoHit;
    public void print(){
        System.out.println(“hit = “+hit+”, psudo hit = “+pseudoHit);
    }
}

int code(char c){
    switch(c){
        case ‘B’:
            return 0;
        case ‘G’:
            return 1;
        case ‘R’:
            return 2;
        case ‘Y’:
            return 3;
        default:
            return -1;
    }
}

public Result calcResult(String solution,String guess){
    int MAX_COLOR=4;
    if(solution==null || guess==null || solution.length()!=guess.length()){
        return null;
    }
    Result res=new Result();
    int[] frequencies=new int[MAX_COLOR];

    //count hits
    for(int i=0;i<solution.length();i++){
        if(solution.charAt(i)==guess.charAt(i)){
            res.hit++;
        } else {
            int code=code(solution.charAt(i));
            frequencies[code]++;
        }
    }

    //count pseudo-hits
    for(int i=0;i<guess.length();i++){
        int code=code(guess.charAt(i));
        if(code>-1 && frequencies[code]!=0 && guess.charAt(i)!=solution.charAt(i)){
            res.pseudoHit++;
            frequencies[code]—;
        }
    }

    return res;
}

16.16
Problem:
Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n , the entire array would be sorted. Minimize n such sequence).
EXAMPLE
Input:1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19
Output: (3, 9)

Analysis:
We can find the leftmost sorted array and rightmost sorted array, so basically we need to sort the middle array, which is the required sequence. But the left array shouldn’t have values larger than middle array’s maximum, and the right array shouldn’t have values lower than middle’s minimum.
left < middle+right
left+middle < right
The maximum of left should be smaller than the minimum of (middle+right). The minimum of right should be larger than the maximum of (left+middle). In this way we can find boundary of middle array.

Code:
public void minSequence(int[] nums){
    if(nums.length==0){ System.out.println(“Invalid input array!"); }
    //find left,middle,right
    int lo=findLow(nums);
    int hi=findHigh(nums);

    //find minimum of middle+right
    int min=findMin(nums,lo);
    //find maximum of left+middle
    int max=findMax(nums,hi);

    //find m and n by shrinking left and right
    int m,n;
    for(int i=lo;i>=0;i—){
        if(nums[i]<=min){
            m=i;
            break;
        }
    }
    for(int i=hi;i<nums.length;i++){
        if(nums[i]>=max){
            n=i;
            break;
        }
    }

    System.out.println(“m = “+m+”, n = “+n);
}

public int findLow(nums[]){
    for(int i=1;i<nums.length;i++){
        if(nums[i]<nums[i-1]){
            return i-1;
        }
    }
}

public int findHigh(nums[]){
    for(int i=nums.length-2;i>=0;i—){
        if(nums[i]>nums[i+1]){
            return i+1;
        }
    }
}

public int findMin(int nums[],int lo){
    int min=Integer.MAX_VALUE;
    for(int i=lo+1;ii<nums.length;i++){
        if(nums[i]<min){
            min=nums[i];
        }
    }
    return min;
}

public int findMax(int nums[],int hi){
    int max=Integer.MAX_VALUE;
    for(int i=0;i<hi;i++){
        if(nums[i]>max){
            max=nums[i];
        }
    }
    return max;
}

16.17
Problem:
You are given an array of integers (both positive and negative). Find the contiguous sequence with the largest sum. Return the sum.
EXAMPLE
Input: 2, -8, 3, -2, 4, -10 Output:5 (i.e., {3, -2, 4})

Analysis:
As adding negative number will only make the sum smaller, when previous sum is negative, we won’t add the previous sequence, but start the new sequence. We can save the current sum and the current max sum as we go through the array.
This problem can also be approached with dynamic programming, by caching the current max sum when going through array, f[x] = max(f[x], f[x]+f[x-1]).

Code:
public int findMaxSubsequenceSum(int nums[]){
    int sum=0;
    int maxSum=0;
    for(int num:nums){
        if(sum<0){
            sum=num;
        }else{
            sum+=num;
        }
        if(sum>max){
            max=sum;
        }
    }
    return max;
}

16.19
Problem:
You have an integer matrix representing a plot of land, where the value at that location represents the height above sea level. A value of zero indicates water. A pond is a region of water connected vertically, horizontally, or diagonally. The size of the pond is the total number of connected water cells. Write a method to compute the sizes of all ponds in the matrix.
EXAMPLE
Input:
0210
0101
1101
0101
Output: 2, 4, 1 (in any order)

Analysis:
We can use breadth-first-search for pond when we find a water spot, and mark the spot visited. If we don’t want to modify the original matrix, we can use a new visited matrix.

Code:
public List<Integer> solution(int[][] land){
    List<Integer> sizes = new ArrayList<>();
    boolean[][] visited=new boolean[land.length][land[0].length];

    for(int i=0;i<land.length;i++){
        for(int j=0;j<land[0].length;j++){
            if(land[i][j]==0){
                int size=computSize(i,j,land,visited,0);
                sizes.add(size);
            }
        }
    }
    return sizes;
}

public int computSize(int i,int j,int[][] land,boolean[][] visited){
    if(i>=land.length || j>= land[0].length || i<0 || j<0 || land[i][i] != 0 || visited[i][j]){
        return 0;
    }
    int size=1;
    visited[i][j]=true;
    for(int m=i-1;m<i+2;m++){
        for(int n=j-1;n<j+2;n++){
            size+=computSize(m,n,land,visited);
        }
    }
    return size;
}

Trie
Note: As there are 26 letters, we can use char[26] as Map.
```
class TrieNode{
    Map<Character,TrieNode> children;
    char c;
    boolean isEnd;
    TrieNode(){
        children=new HashMap<Character,TrieNode>();
    }  
    TrieNode(char c){
        children=new HashMap<Character,TrieNode>();
        this.c=c;
    }  
}
class Trie{
    TrieNode root;
     
    Trie(){
        root=new TrieNode();
    }
    void insert(String word){
        Map<Character,TrieNode> children=root.children;
        
        for(int i=0;i<word.length();i++){
            TrieNode node;
            char letter=word.charAt(i);
            if(!children.containsKey(letter)){
                node=new TrieNode(letter);
                children.put(letter,node);
            }
            node=children.get(letter);
            children=node.children;
            if(i==node.length()-1){
                node.isEnd=true;
            }
        }
    }

    boolean containsWord(String word){
        TrieNode node=findWord(word);
        if(node==null || !node.isEnd){
            return false;
        }else{
            return true;
        }
    }

    boolean startWith(String word){
        TrieNode node=findNode(word);
        if(node==null){
            return false;
        }else{
            return true;
        }
    }

    TrieNode findNode(String word){
        Map<Character,TrieNode> children=root.children;
        TrieNode node;
        for(char letter:word){
            if(children==null || !children.containsKey(letter)){
                return null;
            }else{
                node=children.get(letter);
                children=node.children;
            }
        }
        return node;
    }
}
```

Problem:
On old cell phones, users typed on a numeric keypad and the phone would provide a list of words that matched these numbers. Each digit mapped to a set of 0-4 letters. Implement an algorithm to return a list of matching words, given a sequence of digits. You are provided a list of valid words (provided in whatever data structure you'd like). The mapping is shown in the diagram below:
1    2    3 
    abc def
4    5    6 
ghi jkl mno
7    8    9 
pqrs tuv wxyz
      0
EXAMPLE
Input: 8733 Output: tree, used

Analysis:
Solution 1: We can iterate through letter combinations and use Trie to store dictionary. Because Trie has quick search with prefix, and we can skip the combination if the prefix is not contained in dictionary.
Solution 2: We can get all number mapping of the words in dictionary, and return on lookup.

Code:
Solution 1:
```
public List<String> getWords(String number, TrieNode root){
    List<String> words=helper(number,root,0,new ArrayList<String>(),new StringBuilder());
    return words;
}

public List<String> words(String number,TrieNode node,int index,List<String> words,StringBuilder sb){
    if(node.isEnd && index==number.length()-1){
        words.add(sb.toString());
        return;
    }

    char[] letters=numberToChars(number.charAt(index));
    if(letters==null){return;}
    for(char letter:letters){
        if(node.children.containsKey(letter)){
            sb.append(letter);
            words(number,node.children.get(letter), index+1, words, sb);
        }
    }    
}

public char[] numberToChars(char number){
    if(number=='0'){return null;}
    return keypad[number-'0'-1];
}

public char[][] keypad=new char[][]{
    {}, {a,b,c}, {d,e,f},
    {g,h,i}, {j,k,l}, {m,n,o},
    {p,q,r,s}, {t,u,v}, {w,x,y,z},
    {}
};
```

Solution 2:
```
public List<String> getWords(String number,String[] words){
    Map<String,List<String>> mapping=getMapping(words);
    return mapping.get(number);
}

Map<String,List<String>> getMapping(String[] words){
    Map<String,List<String>> mapping=new HashMap<String,List<String>>();
    char[] letterToDigit=new char[26];
    createLetterToDigit(letterToDigit);

    for(String word:words){
        StringBuilder sb=new StringBuilder();
        for(char letter:word){
            sb.append(letterToDigit[letter-'a']);
        }
        if(!mapping.containsKey(sb.toString())){
            mapping.put(sb.toString(),new ArrayList<String>());
        }
        mapping.get(sb.toString()).add(word);
    }
    return mapping;
}

char createLetterToDigit(char[] letterToDigit){
    for(int i=0;i<keypad.length;i++){
        if(keypad[i]!=null){
            for(char letter:keypad[i]){
                letterToDigit[letter-'a']=i+1;
            }
        }
    }
}

public char[][] keypad=new char[][]{
    {}, {a,b,c}, {d,e,f},
    {g,h,i}, {j,k,l}, {m,n,o},
    {p,q,r,s}, {t,u,v}, {w,x,y,z},
    {}
};
```

Problem:
Given two arrays of integers, find a pair of values (one value from each array) that you can swap to give the two arrays the same sum.
EXAMPLE
lnput:{4, 1, 2, 1, 1, 2}and{3, 6, 3, 3}
Output: {1, 3}

Analysis:
To think this problem in Math perspective, it requires sumA - moveA + moveB = sumB - moveB + moveA. This is simplified as moveA - moveB = (sumA - sumB)/2.
So this question is simplified as finding 2 numbers whose difference is fix value.
Solution 1: Sort 2 arrays, and use 2 pointers, if difference is too large, move deduct-or; if difference is too small, move deducted.
Solution 2: To find fix difference is to find (fix difference - a) in arrayB, so use iterate through arrayA and store (difference-a) in a set, then iterate through arrayB for matched value in set.

Code:
Solution 1:
```
public int[] findPair(int[] arrayA,int[] arrayB){
    Arrays.sort(arrayA);
    Arrays.sort(arrayB);
    int diff=(sum(arrayA)-sum(arrayB))/2;
    int deductor=0;
    int deducted=0;
    while(deductor<arrayA.length && deducted<arrayB.length){
        if(arrayA[deductor]-arrayB[deducted]==diff){
            return new int[]{arrayA[deductor],arrayB[deducted]}；
        }else if(arrayA[deductor]-arrayB[deducted]<diff){
            deductor++;
        }else{
            deducted++;
        }
    }
    return null;
}

int sum(int[] numbers){
    int sum=0;
    for(int number:numbers){
        sum+=number;
    }
    return sum;
}
```

Solution 2:
```
public findPair(int[] arrayA,int[] arrayB){
    Set<Integer> match=new HashSet<Integer>();
    int diff=(sum(arrayA)-sum(arrayB))/2;
    for(int a:arrayA){
        match.add(diff-a);
    }
    for(int b:arrayB){
        if(set.contains(b)){
            return new int[]{diff-b,b};
        }
    }
    return null;
}

int sum(int[] numbers){
    int sum=0;
    for(int number:numbers){
        sum+=number;
    }
    return sum;
}
```