今天下午接到某公司笔试的通知，面试官发过来一个链接，打开之后，发现是两道笔试题，看似简单，但是打完之后，
面试官直接关了页面，结果可想而知，这里分享一下这两道题，后面想想更好的解决方案。

1. 查找整数
   输入：一个有序数组array，一个整数n
   输出：如果n在array里，输出n的位置；如果n不在array中输出n可以插入的位置，插入后的数组仍然有序
   例如：

*[1,3,5,6], 5 → 2
*[1,3,5,6], 2 → 1
*[1,3,5,6], 7 → 4
*[1,3,5,6], 0 → 0

我的答案：

// 默认升序，如果降序需要反过来
public int findPosition(int arr[], int n){
 int min = 0;
    int max = arr.length - 1;
  
   if(null == arr || arr.length == 0){
     return -1; 
    }
  
   if(n > arr[max]){
     return max + 1;
    }
   
   if(n == arr[max]){
     return max;
     }
  
   if(n <= arr[min]){
     return min;
    }
  
   while(max - min > 1){
     int newIndex = (max + min) / 2;
       if(arr[newIndex] > n){
         //取小区间
           max = newIndex;
        } else if(arr[newIndex] < n){
         //取大区间
           min = newIndex;
        } else{
         //相等，找到了
           return newIndex;
        }
    }
   if(arr[max] == n){
     return max;
    } else if(arr[min] == n){
     return min;
    } else {
     // 可以插入位置在min后
     return min + 1;
    }
}

分析：
上面只是做了一个简单的二分查找，有没有更优的解决方案，后面还需要再研究下。

2. 字符串查找
   输入: 字符串str1， 字符串str2
   输出: 字符串str2在字符串str1中第一次出现的位置。如果没有返回-1.
   例如： str1=“www.taobao.com” str2=”taobao” -> 4
   其它要求：不能使用String类的indexOf方法

我的答案：

public class Solution {
    public int strStr(String str1, String str2) {
     if(null == str1 || null == str2 || str1.length()<str2.length()){
         return -1;
        }
    
     int i = 0; // str1 p1
        while(i<str1.length()){
         int j = 0; // str2 p2
         while( str1.length() >= (i + j) 
             && str1.charAt(i + j) == str2.charAt(j)){
                j++;
                if(j == str2.length()){
                 return i;
                }
            } 
            i++;
        }
      return -1;
    }
}    
    
    

    }
}

分析：
我的答案只是传统的字符串匹配方式，大学里面学的KMP早已忘记，很尴尬，😅。