Lexi's Leetcode solutions

Posts Tagged ‘array

这题不好想,还是看了答案才明白。中心思路是:每个bar头顶能接多少水,取决于它两边有木有比自己高的两个木板,有的话自己上方就被trap住了,trap的volumn是(两边比自己高的那两个模板中的短板-自己的高度)×1。
然后就要考虑怎么求在每个木板i,他的左边最高板和右边最高板的值呢?用dp一试就出来了。这个就是因为很熟练LIS了,所以一下就做出来了。这种接水题也是,现在觉得难,多做几道思路就清晰了吧。

public int trap(int[] A) {
    int[] left = new int[A.length];
    int[] right = new int[A.length];
    for (int i = 0; i < A.length; i++) {
        left[i] = i > 0 ? Math.max(left[i - 1], A[i]) : A[i];
    }
    for (int i = A.length - 1; i >= 0; i--) {
        right[i] = i < A.length - 1 ? Math.max(right[i + 1], A[i]) : A[i];
    }
    int res = 0;
    for (int i = 1; i < A.length - 1; i++) { //two edges can't trap nothin'
        int lowBar = Math.min(left[i - 1], right[i + 1]);
        if (lowBar > A[i])
            res += lowBar - A[i];
    }
    return res;
}

比如{1, 2, 4, 5},3的supposed index就应该是2(把4的位置顶替了)。

facts:

  • because in the end, when p’s next is q, the mid will == p, and new left section will be [q, p](q is mid – 1 and p stays); new right section will be [q, p] (p is mid + 1 and q stays), which ever, we want to return the p because we didn’t find x!
  •  is there a possibility where in the end p’s next is not q? like p q somehow points to the same element, then it’s the same, we want to return p.
  • that’s all the possible combinations. There’s no way [p, somethinglese, q] in the end, that will always transform to scenario 1 or scenario 2.
int findSupposedIndex(int[] arr, int x, int p, int q) {
  if (p > q)
    return p;
  int mid = (p + q) / 2;
  if (arr[mid] == x)
      return mid;
  else if (arr[mid] > x)
      return findSupposedIndex(arr, x, p, mid - 1);
  else
      return findSupposedIndex(arr, x, mid + 1, q);

http://www.mitbbs.com/article_t1/JobHunting/32184907_0_1.html

思路(这个没怎么测试,不知道对不对,也想不明白time)。。

从头开始顺着摸,摸到摸过的,说明有loop。

什么时候结束?摸到下一个index out of boundry了,说明当前绳子结束。但是可能数组里中间还剩一大堆元素没动呢,所以要keep一个currRopeHead variable (当前绳子的头);从这个头的下一个开始往右找(左边不用找了,既然当前绳子在这开头,说明左边的小绳结早就处理过了),找到第一个没visited过的绳头,接着做。

test: {2, -1, 1, 4, 5, 0}这算是loop吗?感觉应该不算,所以一个visited array还不行,得用Map<Index, HashSet<ropeIndex>>才行。顺着当前绳子摸到的节点若在当前绳子上visit过才叫visit过。所以每次新生成绳子的时候,要把ropeIndex++。卧槽这越来越复杂了。

boolean hasCycle(int[] arr) {
  int[] visited = new int[arr.length]; 
  int i = 0; 
  int currRopeHead = i; 
  while (i < arr.length) { 
    if (visited[i])
    return true;
    visited[i] = true;
    int next = arr[i];
    if (next < 0 || next >= arr.length) {
      //rope is broken, will start a new one
      //find the first unvisited rope start
      boolean foundRopeHead;
      for (int j = currRopeHead + 1; j < arr.length; j++) {
        if (!visited[j]) {
          i = j;
          foundRopeHead = true;
          currRopehead = i;
          break;
        }
      }
      if (!foundRopeHead)
        return false;
    } else {
      i = next;
    }
  }
  return false;
}

太复杂了,还是用runner technique吧。两个runner用来看当前绳字有木有loop,外加一个set代表所有没vsit过的“绳头”。

这样的话,其实并不慢,原因是runner fast跑到绳子尽头为止,不多往后跑(如果没loop的话);如果有loop,那肯定在当前绳结跑两次之前也能追上slow而停止,所以还是O(k + k)的速度(k是当前绳结的长度)。然后这个绳子跑完了,上面所有经过的节点都从set里remove掉了,set就可以接着随便找一个当绳头,接着recursion。有一个怀疑就是然后从set里面random拿的一个节点不是绳头,而是绳子中间某个部分怎么办;后来想想那就相当于把一个长绳子分两半做,要是有loop怎么都分不开,要是没loop那分成的两半也各自没loop,时间还是一样的。

boolean hasLoop(int[] arr) {
  Set<Integer> unvisitedIndexSet = new HashSet<Integer>();
  for (int i = 0; i < arr.length; i++) {
    unvisitedIndexSet.add(i);
  }
  return hasLoop(arr, unvisitedIndexSet);
}
boolean hasLoop(int[] arr, Set<Integer> set) {
  if (set.isEmpty())
    return false;
  int randomHead = getRandomElement(set);
  int fast = randomHead;
  int slow = randomHead;
  set.remove(fast);
  while (fast != -1) {
    fast = arr[fast];
    set.remove(fast);
    if (fast == -1)
    break;
  else {
    fast = arr[fast];
    set.remove(fast);
  }
  slow = arr[slow];
  if (fast == slow)
    return true;
  }
  return hasLoop(arr, set);
}
Tags: ,

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

熟悉了二分法的pq终止条件,再做这个题就可厉害了!!先用二分法找左边的7(就算找到了8,就当没看见,因为想找7,8之间的一个数);再找右边的10。注意:最后如果两个boundry连起来了,说明之间啥也没有,就是没找到8,就全赋成-1.

public int[] searchRange(int[] A, int target) {
  int[] result = new int[2];
  int prevIndex = findPrevIndex(A, 0, A.length - 1, target);
  int nextIndex = findNextIndex(A, 0, A.length - 1, target);
  if (prevIndex + 1 == nextIndex) {
    result[0] = result[1] = -1;
  } else {
    result[0] = prevIndex + 1;
    result[1] = nextIndex - 1;
  }
  return result;
}
private int findPrevIndex(int[] A, int p, int q, int x) {
  if (p > q)
    return q;
  int mid = (p + q) / 2;
  if (A[mid] < x) //abandon left half
    return findPrevIndex(A, mid + 1, q, x);
  else //when A[mid] ==x, treat x as if it's really big because we want to find left boundry
    return findPrevIndex(A, p, mid - 1, x);
}
private int findNextIndex(int[] A, int p, int q, int x) {
  if (p > q)
    return p;
  int mid = (p + q) / 2;
  if (A[mid] <= x)
    return findNextIndex(A, mid + 1, q, x);
  else
    return findNextIndex(A, p, mid - 1, x);
 }

今天又被assign了不归我的活,怒了。干脆上班不工作了,直接刷题。

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [2,6],[1,3],[8,10],[15,18],
return [1,6],[8,10],[15,18].

思路:先sort by start,然后不断判断当前的interval能不能吞噬下一个(curr.end >= next.start,说明这两个能连起来)。做的过程中发现几个问题:

  1. 本来是想直接循环list,然后不断吞噬,删掉被吞噬的。但是这样就一边iterate一边modify array了,会挂。所以还得用另一个list,然后决定是不断删list2里的东西,还是不断往list2里加东西。这个要拿例子试试哪种好使。
  2. 一开始写的是if (curr.end >= next.start) then curr.end = next.end。然后挂了几个test case,才注意到忘记了curr本身包括了next的情况。应该是curr.next = Math.max(curr.end, next.end)
  3. 第一次写java inline的comparator!
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
  Collections.sort(intervals, new Comparator<Interval>() {
    public int compare(Interval a, Interval b) {
      return a.start - b.start;
    }
  });
  ArrayList<Interval> result = new ArrayList<Interval>();
  for (int i = 0; i < intervals.size(); i++) {
    Interval curr = intervals.get(i);
    while (i < intervals.size() - 1 && curr.end >= intervals.get(i + 1).start) {
      curr.end = Math.max(curr.end, intervals.get(i + 1).end);
      i++;
    }//while出来说明curr已经吃饱了,可以加入result了。
    result.add(curr);
  }
  return result;
}
Tags: , ,

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;
}
Tags:

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;
}

这个是要算到达最后一步最少要跳几步。不用非的跳到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;
}

这个好做,是build up的一维DP。还是,把状态d一定义,关系就自然出来了。d[i]表示能不能跳到i处,要是能跳,则再把从i处能跳到的别的地方全set up了。这样过一遍数组,就出来了。

public boolean canJump(int[] A) {
 boolean d[] = new boolean[A.length];
 d[0] = true;
 for (int i = 0; i < A.length; i++) {
   if (d[i] == true) {
     for (int j = 1; j <= A[i]; j++) {
       if (i + j < A.length)
         d[i + j] = true;
     }
   }
 }
 return d[A.length - 1];
}

然后大的就挂了有木有!!卧槽dp原来也不一定是最优解啊!!你的dp是个两层循环,有很多重复(比如到j,从i已经跳到它过了,但是i+1也能跳到它,所以重设了一遍true)。没必要把每个i能不能走到都算出来,只要算出最后一跳能不能>=n就行了。

算法:keep一个var,表示目前看来最远能走到哪。比如现在在i上,已知之前算的从0~i-1上最远就能跳到m处,那么如果i <= m,就说明i这个位置是能跳到的。为什么这就说明了呢?因为你的m是在0~i-1中的某个index上算出的,比如i0,那么说明从i0一直到m全能跳到(一步一步跳),而i还>i0,所以i到m之间当然也能一步一步跳到了。

public boolean canJump(int[] A) {
  int farIndex = 0;
  for (int i = 0; i < A.length; i++) {
    if (i <= farIndex){
      farIndex = Math.max(farIndex, A[i] + i);
    }
  }
  return farIndex >= A.length - 1;
}
Tags: ,

给一个无序int array,有正有负,找第一个missing正整数。比如[3,4,-1,1] return 2.要求O(n)时间,O(1)空间。

思路:

  • 要求这么高,还不让用空间换时间,说明不是dp,所以基本只让过一两遍数组,一边过一遍直接in place的改动数组(不让生成新数组啊)
  • 既然是大部分不missing,所以可以用index来直接和元素产生关系。
  • 试图让A[i]这个值x的index是x – 1,即每个index身上的元素都是index本身+1。所以{1 2 3}就是理想中的新数组,{1 5 3}就说明缺2。

算法:

  1. 如果A[i]不在自己该在的地方,就想办法把他换到该在的地方。如果A[i]是<=0或者A[i]比数组长度还大,说明没有它该在的地方,那就skip他,弄下一个(不用担心当前位置被它占了,如果后面有想在这个位置的正整数,它会被换走的)
  2. A[i]和A[A[i] – 1]换,然后继续回到i,接着换,直到第一种情况满足。但是如果这俩数一样,换也没用,就别原地打转了。
  3. 最后过一遍shift过的array,第一个不在原位的就是。
public int firstMissingPositive(int[] A) {
  for (int i = 0; i < A.length; i++) {
    //if it's not in its supposed to be place (the index of value x should be x - 1)
    if (i != A[i] - 1){
      if (A[i] <= 0 || A[i] > A.length || A[i] == A[A[i] - 1])
        continue;
      else {
        //put A[i] to A[A[i] - 1]
        swap(A, i, A[i] - 1);
        i--; //回到刚才这位接着做
      }
    }
  }
  for (int i = 0; i < A.length; i++) {
    if (i != A[i] - 1)
      return i + 1;
  }
  return A.length + 1;
}

看了http://www.cnblogs.com/AnnieKim/archive/2013/04/21/3034631.html的答案才会的。

Tags:

Blog Stats

  • 222,235 hits
September 2021
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
27282930