Lexi's Leetcode solutions

Posts Tagged ‘math

这就是典型的try and fail,尼玛谁知道什么算是数什么不算啊?让我用眼睛看我也不知道啊!总之,试出来的规则是这样的:

  • AeB代表A * 10 ^ B
  • A可以是小数也可以是整数,可以带正负号
  • .35, 00.神马的都算valid小数;就”.”单独一个不算
  • B必须是整数,可以带正负号
  • 有e的话,A,B就必须同时存在

算法就是按e把字符串split了,前面按A的法则做,后面按B做。

public boolean isNumber(String s) {
    s = s.trim(); 
    if (s.length() > 0 && s.charAt(s.length() - 1) == 'e')
        return false; //avoid "3e" which is false
    String[] t = s.split("e");
    if (t.length == 0 || t.length > 2)
        return false;
    boolean res = valid(t[0], false);
    if (t.length > 1)
        res = res && valid(t[1], true);
    return res;
}
private boolean valid(String s, boolean hasDot) {
    if (s.length() > 0 && (s.charAt(0) == '+' || s.charAt(0) == '-')) //avoid "1+", "+", "+."
    s = s.substring(1);
    char[] arr = s.toCharArray();
    if (arr.length == 0 || s.equals("."))
        return false;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == '.') {
            if (hasDot)
                return false;
            hasDot = true;
        } else if (!('0' <= arr[i] && arr[i] <= '9')) {
            return false;
        }
    }
    return true;
}
Tags:

这题太经典了,在amz wiki上见过解法,才知道可以把指数分一半,从O(n)改成O(logn)。有几个要注意的地方:

  1. 初中数学不会了。(-2)^(-3) = 1 / (-2)^3。所以正负号还是和指数是否是偶数有关。
  2. 不要分四种情况讨论,简洁的代码是如果n<0,则直接/x,因为前面算好half的也是1/something的!
  3. 要特别讨论x == 0的情况,因为后面要1/x,不想挂在这吧。
public double pow(double x, int n) {
    if (x == 0)
        return 0;
    return power(x, n);
}
private double power(double x, int n) {
    if (n == 0)
        return 1;
    double left = power(x, n / 2);
    if (n % 2 == 0) {
        return left * left;
    } else if (n < 0) {
        return left * left / x;
    } else {
        return left * left * x;
    }
}
Tags:

Hands down,这是我leetcode做的最难的题top 5。别的都是可以用算法说得通的,这题就是纯数学。我这辈子最怕的就是数学,要死要活。

几个要点:

  1. 找没用过的里面的第(k – 1) / (n – 1)!个数字,放第一位上
  2. k = (k – 1) % (n – 1)!,第一个数字确定了,剩下这些里面重新找第k个。
  3. n每次-1,比如第一位确定后有(n-1)!种后面数字的排法,第二位也确定了后面的数字排法就又少了一位(n – 1 – 1)!

还是不是很清楚,今晚睡觉接着想。

public String getPermutation(int n, int k) {
    boolean[] used = new boolean[n];
    // used[i] means the digit i + 1 is used, e.g. used[0] means digit '1' is used
    StringBuilder sb = new StringBuilder();
    int factorial = getFactorial(n - 1);
    int originalN = n;
    while (k > 0) {
        int index = (k - 1) / factorial;
        int count = 0;
        for (int i = 0; i < originalN; i++) {
            if (used[i] == false)
                count++;
            if (index == count - 1) {
                sb.append(i + 1);
                used[i] = true;
                break;
            }
        }
        n--;
        k = (k - 1) % factorial + 1;
        if (n == 0)
            break;
        factorial /= n;
    }
    return sb.toString();
}
private int getFactorial(int n) {
    if (n == 1 || n == 0)
        return 1;
    return n * getFactorial(n - 1);
}
Tags: ,

这个题第二遍做code就写的挺完美的,高兴~~几个要点:

  • 直接乘会溢出,所以每次都要两个single digit相乘,最大81,不会溢出。
  • 比如385 * 97, 就是个位=5 * 7,十位=8 * 7 + 5 * 9 ,百位=3 * 7 + 8 * 9 …
    可以每一位用一个Int表示,存在一个int[]里面。
  • 这个数组最大长度是num1.len + num2.len,比如99 * 99,最大不会超过10000,所以4位就够了。
  • 这种个位在后面的,不好做(10的0次方,可惜对应位的数组index不是0而是n-1),
    所以干脆先把string reverse了代码就清晰好多。
  • 最后结果前面的0要清掉。
public String multiply(String num1, String num2) {
    num1 = new StringBuilder(num1).reverse().toString();
    num2 = new StringBuilder(num2).reverse().toString();
    // even 99 * 99 is < 10000, so maximaly 4 digits
    int[] d = new int[num1.length() + num2.length()];
    for (int i = 0; i < num1.length(); i++) {
        int a = num1.charAt(i) - '0';
        for (int j = 0; j < num2.length(); j++) {
            int b = num2.charAt(j) - '0';
            d[i + j] += a * b;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < d.length; i++) {
        int digit = d[i] % 10;
        int carry = d[i] / 10;
        sb.insert(0, digit);
        if (i < d.length - 1)
            d[i + 1] += carry;
        }
    //trim starting zeros
    while (sb.length() > 0 && sb.charAt(0) == '0') {
        sb.deleteCharAt(0);
    }
    return sb.length() == 0 ? "0" : sb.toString();
}
Tags:

这个题是非常常见的面试题,自己试着implement了两种方法,一个O(logn),一个O(n),但是写起来都不是很简洁。

O(n)的方法:binary search by start,找到一个要insert的位置(start1<start<=start2),取那个大的start2(因为它肯定会被start给replace掉,start1则不一定)。插入这个新interval,然后从头到尾检查overlap(两个参数无论谁前谁后都能用这个helper查出来),有就merge,不断吞噬overlap的。代码写起来有点长,不过思路非常清晰,不用考虑任何边界条件(什么a.start <= b.end…那些都烦死人了)。interview的时候可以写这种,因为binary search那段可能都不让你写。

还有一个trick是用iterator可以直接修改正在iterate的list,不会报modification exception,第一次用,很方便。

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    int insertPosition = insertByStart(intervals, newInterval.start, 0, intervals.size() - 1);
    intervals.add(insertPosition, newInterval);
    Iterator<Interval> it = intervals.iterator();
    Interval prev = it.next();
    while (it.hasNext()) {
        Interval curr = it.next();
        if (overlap(prev, curr)) {
            prev.start = Math.min(prev.start, curr.start);
            prev.end = Math.max(prev.end, curr.end);
            it.remove();
        } else {
            prev = curr;
        }
    }
    return intervals;
}
private int insertByStart(ArrayList<Interval> intervals, int x, int p, int q) {
    if (p > q)
        return p;
    int mid = (p + q) / 2;
    if (intervals.get(mid).start < x) {
        return insertByStart(intervals, x, mid + 1, q);
    } else {
        return insertByStart(intervals, x, p, mid - 1);
    }
}
private boolean overlap(Interval a, Interval b) {
    return within(a.start, b) || within(a.end, b) || within(b.start, a) || within(b.end, a);
}
private boolean within(int v, Interval b) {
    return v >= b.start && v <= b.end;
}

另一种方法是binary search,找出要start属于的位置,end属于的位置。但是很不好写,需要判断那些this.start >=that.end之类的,就更长了。回头看看能不能写简洁点。

Tags: , ,

这题上来没法下手,咬牙看了半天用dfs写出了个差不多的,最后卡在两个list merge上。实在看不出规律(后来发现是自己例子都写错了!!),上网一查,大神回复:

假设有n-1的答案为:G0, G1, …, Gn,想得到n的答案,只需要在G0…Gn左边加上一个0,再把G0…Gn颠倒顺序,在左边加上一个1即可。比如n=3(在分界线上倒映):

000
001
011
010
---
110
111
101
100

用dfs可以每次求出左边是0,然后求出左边是1的,合一起就是了。两个教训:

  1. 这种数学题找规律,千万别自己把例子写错了。那样打死也看不出规律的。
  2. 拿到一题往死里想个10分钟总能想出点眉目的,别放弃。
public ArrayList<Integer> grayCode(int n) {
    if (n == 0) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(0);
        return list;
    }
    return getGrayCode(n - 1);
}
private ArrayList<Integer> getGrayCode(int pos) {
    if (pos == 0) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(0);
        list.add(1);
        return list;
    }
    ArrayList<Integer> result = new ArrayList<Integer>();
    ArrayList<Integer> startsWithZero = getGrayCode(pos - 1);
    ArrayList<Integer> startsWithOne = new ArrayList<Integer>();
    for (int i = startsWithZero.size() - 1; i >= 0; i--) {
        startsWithOne.add(startsWithZero.get(i) + (1 << pos));
    }
    result.addAll(startsWithZero);
    result.addAll(startsWithOne);
    return result;
}

不让用*, /, %号做整数除法。基本只能bit了。但是bit操作都是跟2有关的,所以到最后还得不断缩小范围,好能贴近结果。

算法:a / b

  1. a本来是想一直-b,然后减到<0了,算counter。但是这样慢,所以类似c++ vector的思路,每次发现还没减没,那减数就翻倍(b <<= 1)
  2. 然后到了一定程度,b实在太大了,大于a剩余的部分了,那么就停止。然后剩下的a再一点点开始减,b回归成最开始的值,重做这两步。

重点是一旦超过,b应该不要一下回到原始值,而是应该一点一点/2这样做。最刁钻的地方是test case全是各种Integer.MINVALUE之类的,搞得各种溢出,然后才发现Math.abs(MIN_VALUE)其实还是-2147483648(坑爹呢吧abs还是负数),而不是2147483648。

下面的解法是能跑过的。因为测试数据出现了-2147483648,还不能把它转成正的(2147483648就溢出了),所以直接全转换成long(64位),跑一遍就过了。

public int divide(int dividend, int divisor) {
    if (dividend == 0)
        return 0;
    if (divisor == 1)
        return dividend; //纯粹是为了防止超时
    boolean positive = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0);
    long absDividend = dividend < 0 ? 0 - (long) dividend : (long) dividend;
    long absDivisor = divisor < 0 ? 0 - (long) divisor : (long) divisor;
    int result = dividePositive(absDividend, absDivisor, absDivisor);
    return positive ? result : 0 - result;
}
private int dividePositive(long p, long q, long originalDivisor) { // p / q
    if (p < q)
        return 0; //这个十分必要,否则会因为p > 0而直接下一层递归,pq永远不变,死循环了就。
    int result = 0;
    int e = 0;
    while (p >= q) { //等于应该也进去。
        result += 1 << e;
        p -= q;
        q = q << 1;
        e++;
    }
    return p > 0 ? result + dividePositive(p, originalDivisor, originalDivisor) : result;
 }
Tags: , ,

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

Blog Stats

  • 221,688 hits
September 2020
M T W T F S S
 123456
78910111213
14151617181920
21222324252627
282930