gld面试笔试题

1合并两个有序数组到一个数组里

public int[] merge(int[] items1,int a,int[] items2,int b){
    int i = a-1;
    int j = b-1;
    int k = a+b-1;
    
    while(i >= 0&&j >= 0){
        if(items1[i] > items2[j]){
            items1[k] = items1[i];
            i--;
            k--;
        }else{
            items1[k] = items2[j];
            j--;
            k--;
        }
    }
    while(j >= 0){
        items1[k] = items2[j];
    }
    return items1;
}

2.判断一个数是不是Happy Number

//循环平方和是不是等于1

public boolean judgeHappy(int num){
    Set judgeHave = new HashSet();

    while(num != 1){
        sum = 0;
        while(num > 0){
            sum += math.pow(num%10);
            num = num/10;
        }
        num = sum
        if(judgeSet.contains(num)) return false;
        judgeSet.add(sum);
    }
    return true;
}

3.运输船一次能运两个人，最大为limit，问最少次数

public int getTimes(vector<int>& people,int limit){
    int i = 0;
    int j = people.length;
    sort(people.begin(),people.end());
    int count = 0;
    while(j >= i){
        count++;
        if(people[i]+people[j] <= limit) i++;
        j--;
    }
    return count++;
}

4.股票单线程无限次数购买，利润最大值

public int getPrice(int[] prices){
    int price = 0;
    int priceSize = price.length;
    if(priceSize = 0) retrun 0;
    for(int i=0;i<priceSize;i++){
        if(prices[i]<prices(i+1)){//如果有附加费判断条件要根据改变，理论计算也要改变
            price += prices[i+1]-prices[i]
        }
    }
    return price；
}

2019.10.23

14.最长公共前缀

每个字符串挨个查，暴力法

    public String longestCommonPrefix(String[] strs) {
        if(strs.length<1) return "" ;
        if(strs.length==1) return strs[0];
        int len = strs.length;
        StringBuilder sb = new StringBuilder();
        boolean go = true;
        int j = 0;
        while(go && strs[0].length()> j){
            char first = strs[0].charAt(j);
            for(int i=1;i<len;i++){
                if(j >= strs[i].length()|| strs[i].charAt(j) != first){
                    go = false;
                    break;
                }
            }
            if(go){
              sb.append(strs[0].charAt(j));
              j++;  
            }        
        }
        return sb.toString();
    }

有几个判断非常不必要，外层循环按照第一个元素的长度就可以了，substring函数的使用还需要加强。

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    for (int i = 0; i < strs[0].length() ; i++){
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j ++) {
            if (i == strs[j].length() || strs[j].charAt(i) != c)
                return strs[0].substring(0, i);             
        }
    }
    return strs[0];
}