Lintcode简答题篇章

language:java

1. A + B 问题
   DES:给出两个整数a和b, 求他们的和, 但不能使用+等数学运算符。
   code:

public class Solution {
    /*
     * @param : An integer
     * @param : An integer
     * @return: The sum of a and b
     */
    public int aplusb(int a, int b) {
        // write your code here
        // int c = a & b;
        // int d = a ^ c;
        // int e = a ^ b;
        // int f = d | e;
        // c = c << 1;
        // int h = f & c;
        // if(h != 0) {
        //     return aplusb(f,c);
        // }else{
        //     return f | c;
        // }
        
    int sum = a;  
      
    /*直到进位的结果为0*/  
    while(b != 0)  
    {  
        sum = a ^ b; /*不考虑进位的和*/  
        b = (a & b) << 1; /*只考虑进位的产生值*/  
        a = sum;  
    }//while  
        return sum; 
    }
};

2. 尾部的零
   DES:设计一个算法，计算出n阶乘中尾部零的个数
   code:

public class Solution {
    /*
     * @param n: An integer
     * @return: An integer, denote the number of trailing zeros in n!
     */
    public long trailingZeros(long n) {
        // write your code here, try to do it without arithmetic operators.
        long count = 0;
        while(n >= 5){
            n /= 5;
            count += n;
        }
        return count;
    }
}

6. 合并排序数组
   DES:合并两个排序的整数数组A和B变成一个新的数组。
   code:

public class Solution {
    /*
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */
    public int[] mergeSortedArray(int[] A, int[] B) {
        // write your code here
        int indexA = 0;
        int indexB = 0;
        int index = 0;
        int[] arr = new int[A.length + B.length];
        while(index < A.length + B.length){
            if(indexA < A.length && indexB < B.length && A[indexA] <= B[indexB]){
                arr[index] = A[indexA];
                indexA ++;
            }else {
                if(indexB < B.length){
                    arr[index] = B[indexB];
                    indexB ++;
                }else {
                    arr[index] = A[indexA];
                    indexA ++;
                }
            }
            index ++;
        }
        return arr;
    }
}

9. Fizz Buzz 问题
   DES:给你一个整数n. 从 1 到 n 按照下面的规则打印每个数：
   如果这个数被3整除，打印fizz.
   如果这个数被5整除，打印buzz.
   如果这个数能同时被3和5整除，打印fizz buzz.

code:

public class Solution {
    /*
     * @param n: An integer
     * @return: A list of strings.
     */
    public List<String> fizzBuzz(int n) {
        // write your code here
        ArrayList<String> results = new ArrayList<String>();
        for (int i = 1; i <= n; i++) {
            if (i % 15 == 0) {
                results.add("fizz buzz");
            } else if (i % 5 == 0) {
                results.add("buzz");
            } else if (i % 3 == 0) {
                results.add("fizz");
            } else {
                results.add(String.valueOf(i));
            }
        }
        return results;
    }
}

156.合并区间
DES:给出若干闭合区间，合并所有重叠的部分
code:

 Definition of Interval:
 public classs Interval {
     int start, end;
     Interval(int start, int end) {
         this.start = start;
         this.end = end;
     }
 }
public class Solution {
    /**
     * @param intervals: interval list.
     * @return: A new interval list.
     */
   public List<Interval> merge(List<Interval> intervals) {
        // write your code here
        if(intervals.size() <= 1){
            return intervals;
        }
        
        for(int i = intervals.size() - 1;i >= 0;i--){
            for(int j = 0; j < i ;j++) {
                Interval cu = intervals.get(j);
                Interval next = intervals.get(j+1);
                if(cu.start > next.start){
                    intervals.set(j,next);
                    intervals.set(j+1,cu);
                }
            }
        }
        
        Interval start = intervals.get(0);
        ArrayList<Interval> endList = new ArrayList<Interval>();
        for (int index = 1;index < intervals.size();index ++) {
            Interval cuInterval = intervals.get(index);
            if (cuInterval.start <= start.end && cuInterval.end > start.end) {
                start.end = cuInterval.end;
            } else if(cuInterval.start > start.end) {
                endList.add(start);
                start = cuInterval;
            }
            if(index == intervals.size() - 1){
                endList.add(start);
            }
        }
        return endList;
    }
}