HENNG

我遇到的 “笔试+面试” 题目

我觉得还是有必要记录自己笔试和面试中遇到的题目。虽然很多声明最好不要泄露题目，但自己记录下来，重新思考过的才有收获，不然做了题目也没有什么帮助。因此这个帖子会不定时更新。

昨天的美团笔试，共8道必答编程题，其余的是分岗位的选答题。90分钟，我的确做不完。做了3道半的样子，第4题都还没做完。做了 Android开发 的选择题，“什么是 Service 以及 Service 的生命周期、启动方式等等”，比较简单。以下是回忆版。

1.有一个字符串数组 array，存在空字符串，且字符串是按照字母表顺序排列的，例如 {“array”, “”, “”, “boy”, “cost”, “hello”, “next”, “yep”}. 要查找某个字符串 s （例如 “hello”） 出现的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private static int findString(String[] array, String s) {
	//s为空直接返回
	if ( s.equals("") || s == null) {
		System.out.println("s不能为空");
		return -1;
	}
	
	for (int i = 0; i < array.length; ) {
		if ( !array[i].equals("") ) {
           	//由于是字母表顺序排列的，那么如果s的第一个字母比array[i]的
               //第一个字母小，则肯定不存在，立即返回
			if ( s.charAt(0) < array[i].charAt(0) ) {
				return -1;
			}else if (s.charAt(0) == array[i].charAt(0)) {
				//相等的情况则继续判断字符串是否相等
                   if (s.equals(array[i])) {
					return i;//相等：返回位置
				}else {
					i++;//不等：继续下一个
				}
			}else {//如果s的第一个字母比array[i]的
               //第一个字母大，继续比较下一个
				i++;
			}
		}else { //跳过为空的字符串
			i++;
		}
	}
	return -1;
}

   
   public static void main(String[] args) {
	String[] strings = {"array", "", "", "boy", "hello", "next", "yep"};
	int i = findString(strings, "hello");
	if (i == -1) {
		System.out.println("not found!");
	}else
		System.out.println("the index is: " +i);
}

2.有一个长度为 n 的整数数组，找出数组的下标 l, r 且 l, r 可以把数组等分为三部分。例如整数数组为 求出 l 和 r 使得这三部分相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
private static void OneOfThree(int[] array) {
	int sum = 0;//整个数组的总和
	int l = 0, r = 0;//初始化
	for (int i = 0; i < array.length; i++) {
		sum += array[i];
	}
	
	//由于是整数数组，如果总和不是3的倍数，那么肯定不存在
	if ( sum%3 != 0 ) {
		System.out.println("no that l & r index");
		return;
	}
	
	int s1 = array[0];//s1表示第一部分的和
	for (int i = 0; i < array.length; i++) {
		if (s1 < sum/3) {//比 (sum/3) 小，则继续累加
			s1 += array[i+1];
		}else if (s1 == sum/3) {
			l = i;//相等了，把值交给l，一定要退出循环
			break;
		}else {//大于了，肯定不存在这样的 l 了
			l = -1;
			break;
		}
	}
	
	//同理处理，但s2表示的是第三部分的和，从最后一个数，往前累加比较
	int s2 = array[array.length - 1];
	for (int i = array.length-1; i > 0; i--) {
		if (s2 < sum/3) {
			s2 += array[i-1];
		}else if (s2 == sum/3) {
			r = i-1;
			break;
		}else {
			r = -1;
			break;
		}
	}
			
	if ( (l == -1) || (r == -1) ) {
		System.out.println("no that l & r index");
	}
	if ( l>0 && r>0 && l < r && r < array.length-1 ) {
		System.out.println("l = " + l);
		System.out.println("r = " + r);
	}
}
   
   
   public static void main(String[] args) {
	int[] b = {1,5,6,0,4,2};
	OneOfThree(b);
}

3.长度为 n 的整数数组，对数组进行整理，使得所有的奇数都在数组的前面，而所有的偶数都在数组的后面。例如数组为 {1,2,3,4,5,6}. 整理后为 {1,3,5,2,4,6}.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

//判断前后两个元素是否需要交换
private static boolean isNeedSwap(int a, int b) {
	if (a%2 != 0 && b%2 == 0) {//奇数在前，偶数在后，不需要交换
		return false;
	}
	if (a%2 == 0 && b%2 != 0) {//偶数在前，奇数在后，需要交换
		return true;
	}
       
       /*
	 * 如果声明排序后原来的相对位置不能变，则 return a==b
	 * 如果需要升序排列，则 return a<b
	 * 如需要降序排列，则 return a>b
	 */
       
	return a==b;//同奇同偶，顺序不变
       
}

//交换函数的实现函数
   private static void Swap(int[] array, int a, int b) {
	int temp;
	temp = array[a];
	array[a] = array[b];
	array[b] = temp;
}
   
   //利用插入排序来实现，也可以用其他排序方法
   private static void InsertSort(int[] array) {
	for (int i = 1; i < array.length; i++) {
		for (int j = i; j > 0; j--) {
			if ( isNeedSwap(array[j-1], array[j]) ) {
				Swap(array, j, j-1);
			}
		}
	}
}
   
   public static void main(String[] args) {
	
	int[] a = {1,3,4,6,0,8,9,12,14,23};
	InsertSort(a);
	for (int i = 0; i < a.length; i++) {
		System.out.print(a[i]+" ");
	}
   }

4.升序排列的 1号 整数数组，例如 {1,2,3,4,5,6}. 判断 1号 数组中是否包含 2号 数组，例如{1,5}.
PS: 2号 数组可能存在相同的元素，如{1,5,5}. 也判断为存在，但{1,5,5,7} 则判断为不存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

private static void findArray(int[] array1, int[] array2) {
	
	boolean flag = false;//是否找到相等的数
	
	for (int i = 0, j = 0; i < array1.length && j < array2.length; ) {
		
		//由于是升序，如果2号数组的元素比1号数组的元素小，则肯定不存在
		if (array2[j] < array1[i]) {
			flag = false;
			break;
		}
		//相等，则找到一个匹配的，2号数组继续往后面移，1号数组又从第一个元素开始比较
		else if (array2[j] == array1[i]) {
			j++;
			i = 0;//如果2号数组也是升序的，则不必i=0从头开始
			flag = true;
		}
		//大于，则1号数组需要往后面移再比较
		else {
			i++;
			flag = false;
		}
		
	}
	
	if (flag) {
		System.out.println("exists");
	}else {
		System.out.println("not exists");
	}

}


public static void main(String[] args) {
	int[] c = {1,2,3,4,5,6};
	int[] d = {1,5,5,4,3};
	findArray(c, d);
}