微软18预科生笔试题

1.经典约瑟夫环问题 2.没看懂到底是删哪个，不过大致意思懂了（我理解是删右边的数），链表处理然后每遍跑的时候如果产生了单调递减的序列就加一个其头指向尾的标记。（我算不出复杂度，应该不会退化到n方吧） 3.预处理一个前i最大和后i最小然后二分答案（或者对每个位置都二分出后置比它小的最大位置）不知道有没有O(n)算法 4.dp，f[i,0] f[i,1] f[i,2]表示第i天不工作、hard、easy的总最大薪资，可从i-1转移过来

第四题还有一个条件，每天difficult的薪水比Easy的高

前三个题纯模拟或者暴力都能过， 感觉微软的测试用例有点水。。

就过了前两题100%，后面的为0，是不是凉了。。

不是不能泄露题目嘛、、

要是有数据规模就好了

你收到微软的通知了吗？

这已经是第三套题了吧 (ÒωÓױ)！！！

int max_salary(int **List, int len) {  int result_1 = 0, result_2 = 0, result = 0;  if (len <= 0)   return result;  result_1 = max_salary(List, len - 1) + *(*(List + len - 1) + 0);  result_2 = max_salary(List, len - 2) + 0 + *(*(List + len - 1) + 1);  if (result_1 >= result_2) {   result = result_1;  }  else {   result = result_2;  } } int main() { #define MAXNUMLENGTH 5 #define MAXLENGTH 100  char input_num[5] = { 0 };  char input[MAXLENGTH] = { 0 };  int in_count = 0;  int count = 0;  int num_len = 0;  int len = 0;  int num_of_days = 0;  //输入第一行  char c = getchar();  while (c != '\n') {   input_num[count] = c;   c = getchar();   count++;  }  num_len = count;  count = 0;  for (int i = num_len - 1; i >= 0; i--) {   num_of_days += (int)((input_num[i] - '0')*pow(10, in_count));   in_count++;  }  in_count = 0;  //输入第二行  c = getchar();  while (c != '\n') {   input[count] = c;   c = getchar();   count++;  }  len = count;  count = 0;    //申请内存  int **salary_list = (int **)(malloc(sizeof(int*) * num_of_days));  for (int i = 0; i < num_of_days; i++) {   *(salary_list + i) = (int*)(malloc(sizeof(int) * 2));   memset(*(salary_list + i), 0, 2);  }  int first_num = 0, second_num = 0;  for (int i = num_of_days - 1; i >= 0; i--) {   count += 2;   second_num = 0;   while (input[len - count - 1] != ',') {    second_num += (int)((input[len - count - 1] - '0')*pow(10, in_count));    in_count++;    count++;   }   in_count = 0;   count++;   *(*(salary_list + i) + 1) = second_num;      first_num = 0;   while (input[len - count - 1] != '[') {    first_num += (int)((input[len - count - 1] - '0')*pow(10, in_count));    in_count++;    count++;   }   in_count = 0;   count++;   *(*(salary_list + i) + 0) = first_num;  }  /*  for (int i = 0; i < num_of_days; i++) {   for (int j = 0; j < 2; j++) {    cout << *(*(salary_list + i) + j) << endl;   }  }  */  //int salary_list[4][2] = { {1, 5},{2, 3},{2, 9},{1, 3} };  cout << max_salary(salary_list, num_of_days) << endl;  //释放内存  for (int i = 0; i < num_of_days; i++) {   free(*(salary_list + i));   *(salary_list + i) = NULL;  }  free(salary_list);  salary_list = NULL;    return 0; }

本人github： https://github.com/cld378632668 cld378632668 (系统领域学术研究的一定要加好友多交流) 微软预科生讨论微信群 加微信号 little_dong_dong 备注 微软和学校_想去微软哪个地区_技术方向 哈，已经有95个人了