美团笔试

用Hashtable实现栈：用一个size记录当前hashtable的大小，然后将size+1作为key,将要放入栈的值当着value,就实现了入栈，然后出栈时候用当前size作为key值，查找出对应的value即可。 最大连续自数组：查找前i最长的连续子数组，记录下最长的连续子数组长度及起始下标index 求数组中位次：先进行快排(大到小)，然后用二分查找找出对应下标，然后用数组大小减去对应下标就得到对应位次。

1.用一个count记录size，用size来记录key 2、最长上升子序列改下判断条件，如果降序也可以，那么求2次比较最大就行 3、直接遍历求大于等于它的？（开始还想着维护一个最大堆），当然如果b不在数组中，就加条件判断一下

谢谢楼主

#include<iostream> using namespace std; void GetLong(int *arry, const int &len, int &start, int &end); void main() { int start = 0; int end = 0; int arry[] = {1,2,4,3,4,7,5,6,5,7,9,10}; GetLong(arry, sizeof(arry)/sizeof(arry[0]), start, end); while(start<=end) { cout<<arry[start]<<" "; start++; } cout<<endl; } void GetLong(int *arry, const int &len, int &start, int &end) { if(arry == NULL || len<=0) return; int i = 1; int *tempspace = new int[len]; tempspace[0] = 1; while(i<len) { if(arry[i] == (arry[i-1]+1)) tempspace[i] = tempspace[i-1]+1; else tempspace[i] = 1; i++; } int max = 0; int maxpos = 0; i=0; while(i<len) { if(tempspace[i]>max) { max = tempspace[i]; maxpos = i; } i++; } end = maxpos; start = end-max+1; } 这是第二题最长连续子数组的答案，时间复杂度为O(n)，空间复杂度为O(n)

#include <stdio.h> #include <stdlib.h> typedef unsigned int size_t; void *subarray(const int *array, size_t count) { size_t i, j; size_t numb, max = 0; const int *tmp; int *res; for (i = 0; i < count - 1; ++i) { /* code */ tmp = array + i; numb = 0; for (j = 0; j < count - i; ++j) { /* code */ if (*(tmp + (j + 1)) - *(tmp + j) != 1) { /* code */ break; } numb++; } if (numb > max) { /* code */ max = numb; res = tmp; } } printf("The longest subarray is: "); for (i = 0; i < max + 1; ++i) { /* code */ printf("%d ", *(res + i)); } } int main(int argc, char const *argv[]) { /* code */ int array[] = {1, 3, 4, 5, 6, 9, 10}; subarray(array, 7); return 0; }

#include <stdio.h> #include <stdlib.h> typedef unsigned int size_t; int find_target(const int *array, const int target, size_t count) { size_t i; for (i = 0; i < count; ++i) { /* code */ if (*(array + i) == target) { /* code */ return i } } return -1; }

主要是哪方面的

这是提前批的笔试吗？

//位次 public static int getNumPosition( int [] nums, int target) { int index = 0 ; for ( int i = 0 ; i < nums. length ; i++) { if (nums[i] > target) { int t = nums[i]; nums[i] = nums[index]; nums[index] = t; index += 1 ; } } return index; }

美团什么时候笔试的啊

回复里贴的不能换行，写在下面。。。。 7题DP代码，不知道有没有复杂度更低的，有的话希望告诉我，谢谢 public static void dp(int[] a) { int[] dp = new int[20]; for (int i = 0 ; i < 19 ;++i) { dp[i] = 0x3f3f3f3f; } dp[0] = 1; int len = a.length; // System.out.println(len); for(int i = 0;i < len; ++i) { for (int j = i+1; j <= i+a[i] && j < len; j++ ) { dp[j] = Math.min(dp[j], dp[i] + 1); } } System.out.println(dp[len-1]-1); }

public class JumpNext { public static int[] a = {4, 6, 2, 5, 1, 3, 0, 4, 8, 1, 5, 3, 6}; public static int min = 0; public static void main (String[] args) { minJump(a, 0, 0); System.out.println(min); //3 } public static void minJump (int[] a, int pos, int count) { if (pos >= a.length - 1) { if (min == 0) { min = count; }else if (count < min) { min = count; } return; }else if (a[pos] == 0) { return; }else { for (int i = 1; i <= a[pos]; i ++) { int p = i + pos; int c = count; c ++; minJump(a, p, c); } } } } 感觉写的有点笨，希望高手上传更好的。

请问楼主这是什么时候的笔试题目啊

第三题：求数的位次 思路：遍历数组，找出数组中比指定值b大的数的个数，记为count。在遍历过程中，得判断是否真存在这个数，如果不存在，则最后返回0，否则，返回count+1。 int maxOrder(int *a, int length,int val){ if(a == NULL || length < 1) return 0; int count = 0; bool flag = false; for(int i = 0; i < length; i++) { if(!flag && val == a[i])//判断该数是否存在 flag = true; if(val < a[i]) count++; } if(flag) count++; else return 0; return count; }