Lexi's Leetcode solutions

Posts Tagged ‘math

Point:

  • randN() 表示能生成0~N-1这N个数。
  • 一般除呀余呀之类的都是从0开始最好,如果题中不是从0开始,自己-1最后再+1。
  • a % b就是(0, 1, …, b – 1),一共b个。

Example 1: 用randK()来实现randN() (K < N,用小的生产大的)

  1. 比如rand5() -> rand7()
  2. 想要生成0 – 20 evenly distributed
  3. int a = 5 * rand5() + rand5() = 5 * (0 … 4) + (0…4) = (0, 5, 10, 15, 20) + (0…4) = (0..24)
  4. 然后如果a < 3 * 7,, return a % 7
  5. if a >= 3 * 7, do it again

Example 2:  用randN()来实现randK()(用大的生成小的)

  1. 用rand10() -> rand4()
  2. 已经有(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
  3. 想生成(0, 1, 2, 3)
  4. 10 % 4 = 2, 说明%1, %2的几率由于最后两个数的出现比%别的的几率都大了。所以要想办法除掉最后两个数
  5. 所以rand10结果是8, 9的时候,扔掉重算
  6. rand10结果<8的时候,就可以用这个数%K,就是结果了。
Tags:

subset 1:  array本身都是distinct number,所以往里一个一个插不用担心重复。{}, 放第一个,放第二个。。

//inintialize a {}, keep inserting, mark as used (distinct nums)
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
    Arrays.sort(S);
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    result.add(new ArrayList<Integer>());
    for (int i = 0; i < S.length; i++) {
        ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
        for (ArrayList<Integer> prevSubset : result) {
            ArrayList<Integer> newSubset = new ArrayList<Integer>();
            newSubset.addAll(prevSubset);
            newSubset.add(S[i]);
            temp.add(newSubset);
        }
        result.addAll(temp);
    }
    return result;
}

subset 2————————————-
先sort,然后往后加。重点是怎么保证不重复?比如array[] = {1, 2, 2}

  1. {}
  2. {}, {1}
  3. {}, {1}, {2}, {12}
  4. {}, {1}, {2}, {12} 这时要是还往{}和{1}里面插2就会产生重复。所以要想办法把他们skip过去。skip到哪为止呢?毕竟还是想往{2}和{12}里插的。
  5. 所以是arr[i] == arr[i + 1]的时候,不要往arr[i]之前那一层插了。要往i这一层新插的里面插。
public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
  Arrays.sort(num);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    result.add(new ArrayList<Integer>());
  int start = 0;
  for (int i = 0; i < num.length; i++) {
    int prevSize = result.size();
    //上一层的size,是数字可以用来循环,避免modification exception
    for (int j = start; j < prevSize; j++) {
      ArrayList<Integer> newSubset = new ArrayList<Integer>();
      newSubset.addAll(result.get(j));
      newSubset.add(num[i]);
      result.add(newSubset);
    }
    if (i + 1 < num.length && num[i] == num[i + 1])
      start = prevSize;
      //i + 1那层越过i - 1这层的所有subsets,因为第i层已经往i - 1层的所有subsets里插过了
    else
      start = 0;
  }
  return result;
}

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: , ,

这题真是做了挺久,尼玛还是二分法不熟悉。。怎么终止还是想了很久。

二分法永远是(p, mid – 1)和(mid + 1, q), 不要想什么(p, mid)之类的,那样范围永远没法缩小,最后肯定死循环。

二分的模板终止条件永远是p > q,不要去想p == q + 1, p == q这些,这些都可以经过下一次recurse再分解成p > q的形式。

最后p > q说明没找到,比如foo(5, 4),即那么x应该是在4,5之间,这个时候p的值是5,q的值是4,说明小的那个是q,大的那个是p。所以二分法找x应该在的index那题返回p(返回较大的),这题应该返回q(返回较小的)。别去考虑p==q之类的的情况,那种再走一遍就会又形成p > q。若是找到了,更会在mid==x这个catch里直接接住,不用在终止条件处考虑。

还有一个要注意的地方:代码中间有mid * mid这种式子,这个就很可能overflow,所以要在出现这个之前接住overflow的情况。因为整数的乘法可能导致溢出,而溢出的监测和整数加法直接判断是否小于0是不同的(整数加法溢出时和会<0因为第一位bit被从0顶到1了),因为整数的乘法有可能多次溢出,当奇书次溢出时是负数,当偶数次溢出时时整数。网上看的巧妙的解决办法是干脆不要乘,而是用x/mid和mid比较。

public int sqrt(int x) {
    return sqrt(x, 1, x);
}
private int sqrt(int x, int p, int q) {
    if (p > q)
        return q;
    int mid = (p + q) / 2;
    if (x / mid == mid)
        return mid;
    else if (x / mid < mid )
        return sqrt(x, p, mid - 1);
    else
        return sqrt(x, mid + 1, q);
}

这个和regex的 .*不一样。这个是平时cd src*这种;?可以match任意一个字符,*可以match任意一个字符串,可以是空。

算法:下面这个算法超时,不过能写出来就不错了。每次两个字符串的第一个字母比较,若p的第一个字母是*,则一点点的chop s和p除了*剩下的recursive比较。p的那个*可以占用s的0个字符,1个字符,2个字符。。

一点优化:出现连续的*,取最右边那个就行。

public boolean isMatch(String s, String p) {
  if (s.length() == 0 && p.length() == 0)
    return true;
  if (p.length() == 0)
    return false;
  char c = p.charAt(0);
  if (s.length() != 0 && (c == '?' || c == s.charAt(0)))
    return isMatch(s.substring(1), p.substring(1));
  if (c == '*') {
    for (int i = 0; i <= s.length(); i++) { 
      // i is "* is taking up how many chars in s"
      String sLeft = "";
      if (s.length() != 0)
        sLeft = s.substring(i);
      if (isMatch(sLeft, p.substring(1)))
        return true;
     }
  }
  return false;
}
Tags:

这题正经做了一段时间;首先自己想的算法不好,不够数学;另外这个题的testcase很多情况,自己没想清楚,全是用oj来查出错误了。

数学的做法:每个zigzag(|/形状是n + n – 2的长度;除非n < 2, 则就是n本身的长度),这样可以直接在string上跳着取出应该append的index。这个有两种情况:

ABCDEFGHIJKL n = 4
-------------
A     G 
B   F H   L 
C E   I K  
D     J
  1. 第一行和最后一行每个zigzag段只要append一个就行了
  2. 中间那些行每次要append两个字母;

两个变量,想了半天。分别是“在当前段里的offset”和”在哪个zigzag段里“,但是要保证以”在那个段里“外层循环。

注意:想不明白边界条件的时候,不妨直接用if(边界在string range里),这样就能把所有出界全接住了。

public String convert(String s, int nRows) {
  if (s == null)
    return null;
  int len = nRows <= 1 ? nRows : (2 * nRows - 2);
  StringBuilder sb = new StringBuilder();
  for (int offset = 0; offset < nRows; offset++) {
    for (int zigIndex = 0; zigIndex * len < s.length(); zigIndex++) {
      int firstIndex = zigIndex * len + offset;
      if (firstIndex >= 0 && firstIndex < s.length())
        sb.append(s.charAt(firstIndex));
      if (offset > 0 && offset < nRows - 1) {
        int reverseIndex = (zigIndex + 1) * len - offset;
        if (reverseIndex >= 0 && reverseIndex < s.length())
          sb.append(s.charAt(reverseIndex));
      }
    }
  }
  return sb.toString();
}
Tags: , ,

单链表只让过一次,所以不能先把size找出来再rand(size)。

解法:reservoir  sampling

  1. 每次在curr处,假设curr的之前这段list的random element已经找到了,此时决定curr要不要把之前找到的result替换掉?在第i个node上,选中第i个node为result的概率是1/i。所以以1/i的概率用curr来替换已经找好的previous random result.
  2. 这样interative的linked list往后一个个移动,直到最后一个也做完,说明result就是list所有元素都consider了的random结果。
ListNode getRandom(ListNode head) {
  int count = 1;
  ListNode result = head;
  ListNode curr = head;
  while (curr != null) {
    int rand = generateRandBetween(1, count);
    if (rand % count == 1) //this condition will happen with prob of 1/count
      result = curr;
    curr = curr.next;
    count++;
  }
  return result;
}

蓄水池抽样的原理:

从很大(不知道有多大)的水池里取k滴水。假设在i – i处已经取了k滴水了,现在决定要不要拿i来替换已有的某个k中的元素。同样,替换的概率是1/i,但是替换k中的哪一滴水呢?所以整体概率应该是(1/i) * k。

rand = generateRandBetween(1, i);
if (rand % i <= k) //should replace something in result with arr[i]
   result[rand%i] = arr[i];

 

Tags:

Blog Stats

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