【更新】微软笔试题拔树题遍历一次出结果的解法

2018/4/4镜像同步6 回复

有一组数组，每次遍历一次数组，遇到一个比它左边的数大的数就标记，然后遍历一遍之后，删除那些标记的值。然后不断重复，问需要多少次能结束这样的操作思路比较奇葩，看是否还有漏洞，谢谢@zhouliyan111帮我找到漏洞[ema3] 目前看来是On的正确解法，通过样例如下[ema1] int[] a = {3,6,9,8}; int[] b = {3,2,1,2,3,2,1,5,4,3,2,1,5,4}; int[] c ={2,1}; int[] d = {1,5,4,3,5,4,5,3}; int[] e = {1, 7, 6, 5, 2, 6, 5, 4, 6, 5, 6, 3}; int[] f = {1,7,6,5,4,5,6,3,5,6,3,6,5,4}; public class Pulltree { public static int getTimes(int[] trees) { if (trees == null || trees.length < 2) return 0; int minOfMin = 0; //遍历过的下坡的最小值点 int lastMin = 0; //上一个下坡的极小值点 int minOfMax = 0; //取得Max的下坡的极小值点 int curCount = 0; int Max = 0; boolean isUp = false; if (trees[0] >= trees[1]) { while (lastMin < trees.length -1 && trees[lastMin] >= trees[lastMin+1]) ++lastMin; minOfMin = lastMin; } for (int i = lastMin + 1; i <trees.length; ++i) { if (trees[i-1] < trees[i]) { //上坡 if (!isUp) { //上坡的起点 isUp = true; curCount = 0; lastMin = i-1; minOfMin = trees[minOfMin] < trees[lastMin] ? minOfMin : lastMin; } }else { //下坡或平 if (trees[i] > trees[lastMin]) { //会因为比上一个下坡最低点高被拔掉 if (isUp) { isUp = false; ++curCount;// 下坡的起点，计数要算上坡顶 } ++curCount; if (curCount >= Max) { //注意这个等号 Max = curCount; minOfMax = i; } }else if (trees[i] > trees[minOfMin] && trees[i] <= trees[minOfMax]) { ++Max; minOfMax = i; //用例f，两个3让++max，后面654的4比3大所有没有++max } } } return Max; } public static void main(String[] args) { int[] a = {3,6,9,8}; int[] b = {3,2,1,2,3,2,1,5,4,3,2,1,5,4}; int[] c ={2,1}; int[] d = {1,5,4,3,5,4,5,3}; int[] e = {1, 7, 6, 5, 2, 6, 5, 4, 6, 5, 6, 3}; int[] f = {1,7,6,5,4,5,6,3,5,6,3,6,5,4}; System.out.println(getTimes(f)); } }

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

6 条回复

w1252675615机器人#1 · 2018/4/4

感觉对数据结构还不太熟，代码也写的很丑

zhouliyan111机器人#2 · 2018/4/4

{1, 7, 6, 5, 2, 6, 5, 4, 6, 5, 6, 3}; 应该是4，你是5 3的去除与4有关，有lastMinOfMax的2无关，你的思路和我之前是一样的，但许多极小值点的信息都是有用的，所以我改用数组存储下来了，以便查找，只记录上一个和当前最大的依然信息缺失

w1252675615机器人#3 · 2018/4/4

【在 zhouliyan111 的大作中提到: 】 : {1, 7, 6, 5, 2, 6, 5, 4, 6, 5, 6, 3}; 应该是4，你是5 : 3的去除与4有关，有lastMinOfMax的2无关， : 你的思路和我之前是一样的，但许多极小值点的信息都是有用的， : ................... 又改了下，还有没有测试用例[ema1]

zhouliyan111机器人#4 · 2018/4/4

【在 w1252675615 的大作中提到: 】 : : 又改了下，还有没有测试用例 {0, 4, 3, 2, 1, 6, 5, 6, 4, 6, 3, 6, 2}; 应该是5，你答案是4 struct record { int num; int count; void set(int num, int count) { record::num = num; record::count = count; } }; int fun(int array[], int n) { if (n <= 1) return 0; record *min = new record[n / 2 + 1]; int cursor = 0; min[cursor].set(array[0], 0); int ans = 0; for (int i = 1; i < n; i++) { for (; i < n && array[i] > array[i - 1]; i++); // 连续上升 int tmp = 1; int k = cursor; while (i < n && array[i] <= array[i - 1]) { // 连续下降 if (array[i] <= min[k].num) { if (tmp < min[k].count) { tmp = min[k].count; } k--; } else { tmp++; i++; } } if (ans < tmp) { ans = tmp; } cursor++; min[cursor].set(array[i - 1], tmp); } return ans; }

w1252675615机器人#5 · 2018/4/4

【在 zhouliyan111 的大作中提到: 】 : : {0, 4, 3, 2, 1, 6, 5, 6, 4, 6, 3, 6, 2}; : 应该是5，你答案是4 : ................... 懒得想了[ema36]

Hogwarts机器人#6 · 2018/4/4

【在 w1252675615 (你没有们) 的大作中提到: 】 : 懒得想了[ema36]