Would be great if you could provide a worded explanation of what this does. Say, maintains the invariant that there are the same number of elements in the min_heap
as there are in the max_heap
. (With the caveat that the min_heap
is allowed at most one number more.)
hlin117
@hlin117
Posts made by hlin117

RE: C++ two heaps solution

RE: 1 line python solution
I personally have no idea why people glorify one line solutions. This code could have easily been 5 readable lines instead of that horrific one liner.
counter = collections.Counter() for i in xrange(len(s)  10, 1, 1): subsequence = s[i:i + 10] counter[subsequence] += 1 return [subsequence for (subsequence, freq) in counter.iteritems() if freq > 1]

RE: 44ms Python dp solution
Good solution. it would help if you indicated that this was O(n^2) time and O(n) space.

RE: A clear C++ DP solution easy to understanding
I'm impressed that you're using only O(n) space here. Great job.

RE: 3 lines accepted Java O(n) space DP solution
I'm not sure why people fancy bare minimum line solutions so much. In an interview situation, your interviewer would probably be very discontent about your code.

RE: Share python solution
This solution isn't necessarily a bad solution. It's still O(n log n) anyways.

A recursive solution to add two numbers represented as strings
This code takes advantage of the fact that
182 * 72 = (100 + 80 + 2) * (70 + 2)
in the core "multiply" function. From here, it's just adding numbers by the distributive law.The way I choose to add my integers represented by strings is by using recursion. The recursive function doesn't have any for loops in the base case, but sometimes calls the recursive function in the base case.
class Solution(object): # @param {string} num1 # @param {string} num2 # @return {string} def multiply(self, num1, num2): decimals1 = num1.split() decimals1.reverse() decimals2 = num2.split() decimals2.reverse() total = "" for i, digit1 in enumerate(decimals1): for j, digit2 in enumerate(decimals2): product = str(int(digit1) * int(digit2)) + ('0' * (i + j)) if product == "0": product = "" total = self._add_strings(total, product, "") return "0" if total == "" else total def _add_strings(self, string1, string2, carry): """Adds two numbers represented as strings. Zero is represented by an empty string. """ if len(string1) == 0: # Check if could recurse on other strings if len(string2) != 0 and len(carry) != 0: return self._add_strings(string2, carry, "") # At least one of these needs to be the empty string return string2 if len(carry) == 0 else carry elif len(string2) == 0: if len(string1) != 0 and len(carry) != 0: return self._add_strings(string1, carry, "") return string1 if len(carry) == 0 else carry # Recursive case temp = str(int(string1[1]) + int(string2[1]) + int(carry)) return self._add_strings(string1[:1], string2[:1], temp[:1]) + temp

RE: A Python iterative solution  O(m*n) 556 ms
You could compress this into one line:
return str(sum((int(digit1) * 10 ** i) * (int(digit2) * 10 ** j) for i, digit1 in enumerate(num1[::1]) for j, digit2 in enumerate(num2[::1])))
This is, of course, if you want your code to be extremely unreadable...

RE: Python DP solution
Can you post the recursive version of this code? It'll help people understand what's going on.

RE: This problem is way too ambiguous...
That's true, it's possible lots of clarification questions would have made the problem more straightforward. Though, in leetcode's defense, it did say that it was vague on purpose.