Archive for July 21st, 2013
- In: leetcode
- 5 Comments
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
这个算法挺难想到的。让O(n)说明不能sort，那只能用container。但是用container怎么traverse连续的呢？又不能sort key。所以，我们人眼是怎么做这个题的呢，上来是100，我们其实就想找99和101，有的话就接着那个方向，直到找不着了为止。这样算过的数就从set里删掉，既然是别人的连续，那也是自己的连续，所以不用看了。这样过一遍就能把所有连续数列找全，没有元素重复处理的。
public int longestConsecutive(int[] num) {
int res = 0;
Set<Integer> set = new HashSet<Integer>();
for (int i : num)
set.add(i);
for (int i = 0; i < num.length && !set.isEmpty(); i++) {
int len = 0;
//go up
for (int j = num[i] - 1; set.contains(j); j--) {
set.remove(j);
len++;
}
//go down
for (int j = num[i]; set.contains(j); j++) {
set.remove(j);
len++;
}
res = Math.max(res, len);
}
return res;
}
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
The largest rectangle is shown in the shaded area, which has area = 10 unit.
这个也是看别人答案做出来的。感觉很像那道二维直方图盛水的题，可惜那道是短板固定在两边，这题则是短板可以随意在中间任何一个位置。总之，这种题一定能找到一个状态，就是在i之前，i怎么变都是越来越大（小），但是在i处就不一定了，所以对i才进行运算，之前的就不用算了反正都是比算i的小（大）。
算法：
穷举两个边界，但不是完全穷举，这里可以省掉一部分右右边界。对于i，如果A[i] <= A[i + 1]，即当前递增，则无论对于哪个左边界，选i+1作为右边界都比选i作为右边界合适（宽本来就多一个，然后高还更高，所以肯定选右边的面积大）。所以就算i+1作为右边界的所有左边界配对就行，没必要算i作为右边界的了。所以递推下去，只有A[i] > A[i + 1]的时候，在递减，说明拿A[i]和拿A[i + 1]不一定谁大了，这时候算一下A[i]作为右边界的左边界所有可能，就是一个local peak。这题还有一个O(n)的解法，但是暂时懒的看了。下次再看。
public int largestRectangleArea(int[] height) {
int res = 0;
for (int i = height.length - 1; i >= 0; i--) {
if (i == height.length - 1 || height[i] > height[i + 1]) { //A[i] is a local peak
int min = Integer.MAX_VALUE;
for (int j = i; j >= 0; j--) {
min = Math.min(min, height[j]);
res = Math.max(res, (i - j + 1) * min);
}
}
}
return res;
}
[leetcode] Jump Game 2
Posted on: July 21, 2013
这个是要算到达最后一步最少要跳几步。不用非的跳到last index上，越过去也算。
还是，用dp的话有重复，不需要算d[i]跳到每一步用的最小步数，只要算最后一步能不能跳到，最少用几步就行了。这题其实自己还不够理解，下次还得重做。
算法：在每一步i，都已知到当前这一点用的最小step数k（但是不是存在数组里的，而是local variable）。在每层小循环里，都是“走一步能到的这些点中”， 最远能到哪一点，记载为p，那么到p就能最少用k + 1步就能到了。如果p出了数组边界，直接返回k + 1，就做出来了。要是没出界，则小循环之后，继续下一层循环，但是下一层循环和当前循环不重合，因为下一层说明多走了一步，则k++， 那循环的起始部分就是上一个小循环的尾。（每层小循环的意义是：用k步能走到的这些点，都试探一下，看看从他们身上走一步最远能走到哪）。
public int jump(int[] A) {
if (A.length == 0 || A.length == 1)
return 0;
int examingStart = 0;
int currSectionCanReach = 0;
int steps = 0;
while (examingStart <= currSectionCanReach) {
int examingEnd = currSectionCanReach;
int nextSectionCanReach = examingStart;
for (int i = examingStart; i <= examingEnd; i++) {
nextSectionCanReach = Math.max(nextSectionCanReach, i + A[i]);
if (nextSectionCanReach >= A.length - 1)
return steps + 1;
}
examingStart = examingEnd + 1;
currSectionCanReach = nextSectionCanReach;
steps++;
}
return -1;
}
Lexi's Leetcode solutions 