2018-12 在职刷题保持状态， 每天1题+ML insights

Day19.

Solved 725.

Day20,

Headed back to Bay Area yesterday being exhausted. Unable to solve more problems. Will make this up today.

Merry Xmas!

Solved 746, 252, 682

Day21.

Solved 353.
Solved 738 with Binary Search.

Solved 652.

加油，祝楼主天天有进步

拿到offer请回地里报喜

dizhufengzhi 发表于 2018-12-27 13:33
加油，祝楼主天天有进步

Thanks!!

dizhufengzhi 发表于 2018-12-27 13:34
拿到offer请回地里报喜

一定一定！

Day22

Solved 762 and learned bit masking.
Solved 771.

Solved 775 with O(n) by keeping a record of largest and second largest number so far.  Note that all local inversions are also global inversions. So check if non-local inversion exists.

If current A is the largest so far, continue. if A[i] is smaller than second largest so far, return False as there are at least one non-local inversion exists.

If second < A[i] < largest -> check if A[i-1] is the largest. Otherwise, at least one non-local inversion exists.
[/i][/i][/i]
[i][i][i]A more general solution can be built with Divide and Conquer in O(nlogn) that counts the global inversions and make no assumption of the member of the array.[/i][/i]