一个月刷完cc150

16.6
Problem:
Given two arrays of integers, compute the pair of values (one value in each array) with the smallest (non-negative) difference. Return the difference.
EXAMPLE
Input: {l, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
Output: 3. That is, the pair (11, 8).

Analysis:
We could firstly sort the arrays, then use 2 pointers starting from smallest(first item). Store the current difference, then move the smaller one pointer, (because if we move the larger one the difference will only get bigger). Update difference on each move.

Code:
public int smallestDiff(int[] nums1,int[] nums2){
    if(nums1.length==0||nums2.length==0){return -1;}
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int p1=0,p2=0,dif=Integer.MAX_VALUE;
    while(p1<nums1.length&&p2<nums2.length){
        dif=Math.min(dif, Math.abs(nums1[p1]-nums2[p2]) );
        if(nums1[p1]<nums2[p2]){p1++;}
        else {p2++;}
    }
    return dif;
}

16.7
Problem:
Write a method that finds the maximum of two numbers. You should not use if-else or any other comparison operator.

Analysis:
We cannot use if-statement, so the returned value will be multiplication of factors. So the max’s factor could be 1, and min’s factor could be 0. The sign of (a-b) is 1 if a max, 0 if b max. But (a-b) could overflow when b is negative, so we could only safely use (a-b) when a and b are same signs. When different signs we can always use sign of a. (if a positive sign is 1, when a negative sign is 0)

Code:
public int getMax(int a,int b){
    int signA=sign(a);
    int signB=sign(b);
   
    int sameSign=flip(signA) ^ signB;
    int diffSign=flip(sameSign);

    int sameK=sameSign*signA;
    int ansSame=sameK*a+flip(sameK)*b;

    int diffK=sign(a-b);
    int ansDiff=diffK*a+flip(diffK)*b;

    return --
}

public int sign(int n){
    return (n>>31) & 0x1;
}

public int flip(int n){
    return 1^n;
}

16.8
Problem:
Given any integer, print an English phrase that describes the integer (e.g., "One Thousand, Two Hundred Thirty Four”).

Analysis:
To transfer a number into english, we can divide the number to parts of 3-digit, which are segmented by “thousands”/“million”/“billion”. Then transfer each part into english not larger than hundreds. Make sure to take care of scenarios when number is 1) larger than 20; 2) larger than one hundred.
Edge scenario: 1) zero; 2) negative.

Code:
public String transferToEnglish(int num){
    String[] segment=new String[]{“”, “thousand”, “million”, “billion”, “trillion”};
    String zero=“Zero”;
    String negative=“Negative”;
    if(num==0){return zero;}
    if(num<0){
        return negative+” “+transferToEnglish(-1*num);
    }
    List<String> str=new LinkedList<>();

    int segCoung=0;
    while(num>0){
        if(num%1000!=0){
            str.addFirst(segment[segCount]);
            str.addFirst(convert(num%1000).trim());
        }
        num%=1000;
        segCount++;
    }

    return listToString(str).trim();
}

public String convert(int num){
    String[] smaller=new String[]{“”,”One”,”Two”,”Three”,”Four”,”Five”,”Six”,”Seven”,”Eight”,”Nine”,”Ten”,”Eleven”,”Twelve”,”Thirteen”,”Fourteen”,”Fifteen”,”Sixteen”,”Seventeen”,”Eighteen”,”Nineteen”};
    String[] tens=new String[]{“”,,””,“Twenty”,”Thirsty”,”Forty”,”Fifty”,”Sixty”,”Seventy”,”Eighty”,”Ninety”};
    String hundred=“Hundred”;
    List<String> words=new LinkedList<>();
   
    //larger than hundred
    if(num>99){
        words.add(smaller[num/100]);
        words.add(hundred);
        num%=100;
    }

    //larger than 20
    if(num>19){
        words.add(tens[num/10]);
        num%=10;
    }

    //not zero
    if(num>0){
        words.add(smaller[num]);
    }
   
    return listToString(words);
}

public String listToString(List<String> list){
    StringBuilder sb=new StringBuilder();

    for(String s:list){
        sb.append(s);
        sb.append(“ “);
    }
   
    return sb.toString();
}

16.9
Problem:
Write methods to implement the multiply, subtract, and divide operations for integers. The results of all of these are integers. Use only the add operator.

Analysis:
We can think multiplication as adding several times; subtract as adding negate value; divide as subtract multiplications. So we need to implement negation, which could be done by add -1 several times.
To improve negate efficiency, we can add -1 in exponential. Resolve to -1 when beyond 0.

Code:
public int negate(int num){
    int sign=num>0?-1:1;
    int amount=sign;
    int negate=0;

    while(num>0){
        if((num+amount<0) == (sign<0) && (num+amount!=0)){
            amount=sign;
        }
        negate+=amount;
        num+=amount;
        amount+=amount;
    }
    return negate;
}

public int subtract(int a,int b){
    return a+negate(b);
}

public int multiply(int a,int b){
    if(a==0||b==0){return 0;}
    int sign=(a>0&&b>0) || (a<0&&b<0)?1:-1;
    a=abs(a);
    b=abs(b);
    if(a>b){return multiply(b,a);}
    int sum=0;

    for(int i=0;i<b;i++){
        sum+=a;
    }

    return sign>0? sum: negate(sum);
}

public int abs(int num){
    if(num<0){return negate(num);}
    else return num;
}

public int divide(int a,int b){
    int sign=(a>0&&b>0) || (a<0&&b<0) ?1:-1;
    a=abs(a);
    b=abs(b);
    int ans=0;
    int product=0;

    while(product+b<a){
        product+=b;
        ans++;
    }

    return sign>0?ans:negate(ans);
}

16.10
Problem:
Given a list of people with their birth and death years, implement a method to compute the year with the most number of people alive. You may assume that all people were born between 1900 and 2000 (inclusive). If a person was alive during any portion of that year, they should be included in that year's count. For example, Person (birth= 1908, death= 1909) is included in the counts for both 1908 and 1909.

Analysis:
First we need to decide the data structure to store people, so we use Person class with birthDate and deathDate as variables. Then we can think of birth date as people+1 and death date as people-1, and create an array of population fluctuation to iterate through the period and fluctuation array.

Code:
public class Person{
    int birthYear,deathYear;
    public Person(int birth,int death){
        birthYear=birth;
        deathYear=death;
    }
}
public int denseYear(Person[] people){
    int[] fluctuation= new int[2000-1900+1];
    for(Person person:people){
        fluctuation[person.birthYear-1900]++;
        if(person.deathYear!=2000){
            fluctuation[person.deathYear+1-1900]—;
        }
    }

    int currentCount=0;
    int maxCount=currentCount;
    int maxYear=0;
    for(int i=0;i<fluctuation.length;i++){
        currentCount+=i;
        if(currentCount>maxCount){
            maxCount=currentCount;
            maxYear=i;
        }
    }

    return 1900+maxYear;
}

16.11
Problem:
You are building a diving board by placing a bunch of planks of wood end-to-end. There are two types of planks, one of length shorter and one of length longer. You must use exactly K planks of wood. Write a method to generate all possible lengths for the diving board.

Analysis:
The number of long boards is (K-i) if we decide to use i short boards, because we need to use exactly K boards. So we have K lengths.

Code:
public int possibleLength(int k,int short,int long){
    if(short==long){
        return Arrays.asList(Integer[]{k*short});
    }
    List<Integer> lengths=new ArrayList<>();
   
    for(int i=0;i<=k;i++){
        lengths.add(i*short + (k-i)*long);
    }
    return lengths;
}

16.12
Problem:
Since XML is very verbose, you are given a way of encoding it where each tag gets mapped to a pre-defined integer value. The language/grammar is as follows:
Element --> Tag Attributes END Children END
Attribute --> Tag Value
END --> 0
Tag --> some predefined mapping to int
Value --> string value
For example, the following XML might be converted into the compressed string below (assuming a mapping of family -> 1, person -> 2, firstName -> 3, lastName -> 4, state -> 5).
<family lastName="McDowell" state="CA">
    <person firstName="Gayle">Some Message</person>
</family>
Becomes:
1 4 McDowell 5 CA 0 2 3 Gayle 0 Some Message 0 0
Write code to print the encoded version of an XML element (passed in Element and Attribute objects).

Analysis:
As xml is in tree structure, we can implement the encoding with recursion.

Code:
public String encode(Element root){
    StringBuilder sb=new StringBuilder();
    helper(root,sb);
    return sb.toString();
}

public void helper(Element root,StringBuilder sb){
    String end=“0”;

    encodeString(root.getNameCode(),sb);
    for(Attribute attribute:root.attributes){
        sb.appendAttribute(attribute,sb);
    }
    encodeString(end,sb);

    if(root.value!=null && root.value!=“”){
        encodeString(root.value,sb);
    }
    else{
        for(Element child:root.children){
            helper(child,sb);
        }
    }
    encodeString(end,sb);
}

public void encodeString(String s,StringBuilder sb){
    sb.append(s).append(“ “);
}

public void encodeAttribute(Attribute a,StringBuilder sb){
    encodeString(a.getTagName(),sb);
    encodeString(a.value,sb);
}

16.13
Problem:
Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis.

Analysis:
The line must go through the 2 middles of the 2 squares. So we can easily get the slope. Take care of the infinity slope scenario.

Code:
public Class Square{
    public Point middle(){
        return new Point((this.leftUp.x+this.rightUp.x)/2, (this.leftDown.y+this.leftUp.y)/2);
    }
}

public Line solution(Square s1,Square s2){
    Point mid1=s1.middle();
    Point mid2=s2.middle();
    //slope is infinity
    if(mid1.x==mid2.x){
        return new Line(new Point(mid1.x,s1.leftDown.y), new Point(mid1.x,s1.leftUp));
    }

    int slope=(mid1.y-mid2.y) / (mid1.x-mid2.x);
    int b=mid1.y-slope*mid1.x;
    return new Line(new Point(s1.leftDown.x, slope*s1.leftDown.x+b), new Point(s1.rightDown.x, slope*s1.rightDown+b));
}

16.14
Problem:
Given a two-dimensional graph with points on it, find a line which passes the most number of points.

Analysis:
We can collect all lines, and then count the most occurrence.

Code:
public Line findLine(Point[] points){
    Map<String,Integer> lines=getLines(points);
    return getBestLine(lines);
}

public Map<String,Integer> getLines(Point[] points){
    int INF=-1;
    Map<String,Integer> lines=new HashMap<>();
    for(int i=0;i<points.length;i++){
        for(int j=i+1;j<points.length;j++){
            Point p1=points[i];
            Point p2=points[j];
            int slope=(p1.x==p2.x)?INF:(p1.y-p2.y)/(p1.x-p2.x);
            int intersect=p1.y-slope*p1.x;
            StringBuilder sb=new StringBuilder();
            sb.append(slope).append(“ “).append(intersect);
            String line=sb.toString();
            lines.put(line,lines.getOrDefault(line,0)+1);
        }
    }
    return lines;
}

public Line getLines(Map<String,Integer>  lines){
    int maxFreq=0;
    Line bestLine;
    String line=“";
   
    for(int l:lines.keySet()){
        int count=lines.get(l);
        if(count>maxFreq){
            maxFreq=count;
            line=l;
        }
    }
    int spaceIndex=line.getIndex(“ “);
    int slope=Integer.valueOf(line.substring(0,spaceIndex));
    int intersect=Integer.valueOf(line.substring(spaceIndex+1));
    bestLine=new Line(slope,intersect);
    return bestLine;
}

16.14
Problem:
Given a two-dimensional graph with points on it, find a line which passes the most number of points.

Analysis:
We can collect all lines, and then count the most occurrence.

Code:
public Line findLine(Point[] points){
    Map<String,Integer> lines=getLines(points);
    return getBestLine(lines);
}

public Map<String,Integer> getLines(Point[] points){
    int INF=-1;
    Map<String,Integer> lines=new HashMap<>();
    for(int i=0;i<points.length;i++){
        for(int j=i+1;j<points.length;j++){
            Point p1=points[i];
            Point p2=points[j];
            int slope=(p1.x==p2.x)?INF:(p1.y-p2.y)/(p1.x-p2.x);
            int intersect=p1.y-slope*p1.x;
            StringBuilder sb=new StringBuilder();
            sb.append(slope).append(“ “).append(intersect);
            String line=sb.toString();
            lines.put(line,lines.getOrDefault(line,0)+1);
        }
    }
    return lines;
}

public Line getLines(Map<String,Integer>  lines){
    int maxFreq=0;
    Line bestLine;
    String line=“";
   
    for(int l:lines.keySet()){
        int count=lines.get(l);
        if(count>maxFreq){
            maxFreq=count;
            line=l;
        }
    }
    int spaceIndex=line.getIndex(“ “);
    int slope=Integer.valueOf(line.substring(0,spaceIndex));
    int intersect=Integer.valueOf(line.substring(spaceIndex+1));
    bestLine=new Line(slope,intersect);
    return bestLine;
}