Lexi's Leetcode solutions

Posts Tagged ‘array

这题八月轻松过,现在十月看看就彻底不会了。感觉跟array有关的自己想算法的题就能把我吓个好歹。多做多总结!

Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2,1].(length之后的都不管了)。

算法:

  1. i从1开始,遇见和上一个不一样的,就放在j指的位置里,j++
  2. 要是arr[i] == arr[i – 1],i继续往后走
public int removeDuplicates(int[] A) {
  if (A.length == 0)
    return 0;
  int j = 1;
  for (int i = 1; i < A.length; i++) {
    if (A[i] != A[i - 1]) {
      A[j] = A[i];
      j++;
    }
  }
  return j;
}

bit好久没看真是全尼玛忘了。那些最基本的:

  • 显现a的第i位: a & 1 << i
  • 把a的第i位置零:a &= ~(1 << i)
  • 把result给populate回来:result |= 1 << i

创建一个长度为32的数组a,a[i]表示所有数字在i位出现的次数。假如a[i]是3的整数倍,则忽略;否则就把该位取出来组成答案。空间复杂度O(1).

public int singleNumber(int[] A) {
    int[] bv = new int[32];
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < 32; j++) {
            bv[j] += (A[i] & (1 << j)) == 0 ? 0 : 1;
        }
    }
    int res = 0;
    for (int i = 0; i < 32; i++) {
        if (bv[i] % 3 != 0) {
            res |= 1 << i;
        }
    }
    return res;
}
Tags: , ,

DP是O(n2)的解法。新开一个数列B,B[i]表示以A[i]结尾的LIS的最大长度。每次在i处往前看,若j<i,则以i结尾的就只少>=B[j] + 1。

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

这题不好想,还是看了答案才明白。中心思路是:每个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);
 }

Blog Stats

  • 221,455 hits
June 2020
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
2930