【面试】Liveramp 面试题 面经 猴子过河问题

本文主要是介绍【面试】Liveramp 面试题 面经 猴子过河问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目和青蛙过河有一点不同，A数组值是时间，因为我们需要按时间先后来处理，因此首先想到对值排序，但是复杂度会是nlogn，与题目不和。再看题目要求空间是哦（N+MAX(A)),因此可以新建一个数组，size为maxA，那么直接把值和索引兑换一下，空间换时间，就是On级别了。之后与青蛙过河完全相同。

public int monkeyCross(int D, int[] A, int N){if(-1 + D >= N) return 0;if(A == null || A.length == 0) return -1;int size = 0;for(int i : A){size = Math.max(size, i);}int[] time = new int[size + 1];Arrays.fill(time, -1);for(int i = 0; i < A.length; i++){if(A[i] == -1) continue;time[A[i]] = i;}Set<Integer> reach = new HashSet<>();reach.add(-1);Set<Integer> unreach = new HashSet<>();int max_sofar = -1;for(int i = 0; i < time.length; i++){if(time[i] != -1 && !reach.contains(time[i]) && !unreach.contains(time[i])){if(max_sofar + D >= time[i]){reach.add(time[i]);max_sofar = time[i];for(int j = 1; j <= D; j++){int pos = j + time[i];if(unreach.contains(pos)){max_sofar = Math.max(max_sofar, pos);unreach.remove(pos);reach.add(pos);}}if(max_sofar + D >= N)return i;}else{unreach.add(time[i]);}}}return -1;}

这篇关于【面试】Liveramp 面试题 面经 猴子过河问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---