BYR Achieve · 镜像论坛

微软笔试题

b1196027787

2018/4/2镜像同步82 回复

关于第一题：有童鞋说暴力过了，也有童鞋说暴力可能超时。不过我知道当时那个代码错在了哪儿了。但是目前还只是暴力的。用空间换时间的做法。@zn950213 童鞋已经做出来了。[点这里](https://bbs.byr.cn/#!article/ACM_ICPC/95466) 下面贴出来的是修改之前过不了的代码。就是用一个变量t标记一趟不需要拔掉的树。 ``` int numOfDays(int numOfPlants, int plantsHeights[]){ bool quit = false; int ret = 0; int pre = 1; int t = 1; while(!quit){ quit = true; ret++; for(int i = 1; i < numOfPlants;i++){ if(plantsHeights[i] <= plantsHeights[i-1]){ plantsHeights[t++] = plantsHeights[i]; quit = false; } } if(pre == t){ quit = true; } pre = t; t = 1; numOfPlants = t; } return ret; } ``` 第二题：按照@yuanfang 说的《算法设计》Kleinberg, Tardos的，屈婉玲教授有翻译。同时b站上也有北大的算法公开课。[下载这本书](https://download.csdn.net/download/lilynothing/10326145)，[答案](https://download.csdn.net/download/lilynothing/10327515) 在这本书的动态规划的课后练习题的第2题就是这道题。我根据答案提示，写了如下的代码，但是很有可能还是18/19，因为已经有童鞋这么做了。关于第一天能不能选择hard的task，我觉得这是需要和第二天一起考虑的。 ``` int maxOfSalary(int numOfDays,vector< vector<int> > tasklist){ if (numOfDays == 0){ return 0; } //int x = taskList[0][1], ans = taskList[0][1], y = 0; int dp[numOfDays]; dp[0]= tasklist[0][0]; dp[1]=max(tasklist[1][1], tasklist[0][0]+tasklist[1][0]); for (int i = 2; i<numOfDays; i++){ dp[i]=max(dp[i-2]+tasklist[i][1], dp[i-1]+tasklist[i][0]); } return dp[numOfDays-1]; } ``` --------------------------我是分割线-------------------------------------------------------------- 今天晚上做微软的题目，有一道题目硬是过不了，想求大佬指教。题目一：题意：有一组数组，每次遍历一次数组，遇到一个比它左边的数大的数就标记，然后遍历一遍之后，删除那些标记的值。然后不断重复，问需要多少次能结束这样的操作，也就是是一个非递增数组？。 example： input：〔3,6,9,8〕 output：2 解释：第一趟，标记6（因为6大于3）和9（9大于6）。然后删除6.9剩下3.8，只需要一趟就可以标记8，然后删除，最后剩下3一个数。我做了当时给出的这个例子过了，但是其它的是0/18。题目二：题意：一个实习生一天可以选择easy，ghard两个任务中的一个做，也可以一个也不做，两种任务每天的报酬不一样。同时需要注意的是如果想要连续两天以及两天以上都选择hard的话，那么选择hard的前一天必须一个任务也没做。（原句 he choose a hard work on days when and only when he didnot do any work on the previous day.）要求怎么样选择任务能拿到最大报酬。 example： input：days：4, tasklist: [[1.2].〔4.10〕,[20.21],[2.23]] output:33 解释：第二天和第四天选择hard。通过『我邮2.0』发布原书答案：

订阅后，新回复会通过你的通知中心匿名送达。