it should be like n^3
bboczeng
@bboczeng
Posts made by bboczeng

RE: 52ms Dynamical Programming Python Code

114ms Python AC code with a global variable
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def maxPathSum(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 global maxpathsum maxpathsum = (1<<31) def getmaxsum(node): if not node: return 0 global maxpathsum maxsum = node.val leftmax = getmaxsum(node.left) rightmax = getmaxsum(node.right) if leftmax > 0: maxsum += leftmax if rightmax > 0: maxsum += rightmax maxpathsum = max(maxpathsum, maxsum) return max(node.val, node.val + leftmax, node.val + rightmax) getmaxsum(root) return maxpathsum

Heapq for python AC code.
# Definition for singlylinked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if not lists: return [] heap = [] firstlists = [] for i in range(len(lists)): firstlists.append(lists[i]) for i in range(len(firstlists)): if firstlists[i]: val = firstlists[i].val firstlists[i] = firstlists[i].next heapq.heappush(heap, (val, i)) result = [] while heap: val, index = heapq.heappop(heap) result.append(val) if firstlists[index]: val = firstlists[index].val firstlists[index] = firstlists[index].next heapq.heappush(heap, (val, index)) return result

52ms Dynamical Programming Python Code
class Solution(object): def diffWaysToCompute(self, input): """ :type input: str :rtype: List[int] """ def calculator(x, y, operator): if operator == '*': return x*y elif operator == '': return x  y elif operator == '+': return x + y else: return 0 def parse_input(input): operators = [] operands = [] lastop = 0 for i in range(len(input)): if input[i] in ('*', '+', ''): operators.append(input[i]) operands.append(int(input[lastop:i])) lastop = i + 1 operands.append(int(input[lastop:])) return operands, operators operands, operators = parse_input(input) size = len(operands) result = [[[] for _ in range(size)] for __ in range(size)] # inclusive if not input: return [] for i in range(size): result[i][i].append(operands[i]) for j in range(2, size + 1): for i in range(size  j + 1): for k in range(i, i + j  1): left = result[i][k] right = result[k + 1][i + j  1] operator = operators[k] temp_result = [calculator(x, y, operator) for x in left for y in right] result[i][i + j  1].extend(temp_result) return sorted(list(result[0][size1]))
we build the final solution from subproblems: the sub operand string starting from i with size j. while k is the different ways to divide this sub operand string with the last pair of parenthesis

AC binary search in Python
# The isBadVersion API is already defined for you. # @param version, an integer # @return a bool # def isBadVersion(version): class Solution(object): def firstBadVersion(self, n): """ :type n: int :rtype: int """ if n <= 1: return n # do a binary search front = 1 end = n while front < end: middle = (front + end)//2 if isBadVersion(middle): end = middle else: front = middle + 1 return front

AC backtracking dfs Python code (the problem needs clarification)
class Solution(object): def combinationSum3(self, k, n): """ :type k: int :type n: int :rtype: List[List[int]] """ results = [] if n < 6: return results def dfs_backtracking(results, temp, remaining): if remaining == 0 and len(temp) == k: results.append(temp[:]) if remaining < 0 or len(temp) > k: return if not temp: start = 1 else: start = temp[1] + 1 for each in range(start, 10): if each > remaining: break temp.append(each) dfs_backtracking(results, temp, remaining  each) temp.pop() dfs_backtracking(results, [], n) return results
I think the problem is saying we need all distinct numbers in the solution

Python AC code for h index calculation
class Solution(object): def hIndex(self, citations): """ :type citations: List[int] :rtype: int """ if not citations: return 0 citations.sort() h_index = 0 size = len(citations) for i in range(size): try_index = size  i if citations[i] >= try_index and (i < 1 or citations[i  1] <= try_index): h_index = max(h_index , try_index) return h_index

A concise Python Solution
Basically, you need to quickly lookup to the left, what is the closest column whose height is smaller than you (so a rectangle with h=your height can not extend beyond that column). This is done using a stack maintaining nondecreasing order, with indices stored. Also, you should look right. But how to do it in just O(n)? because when you pop stuff in the stack, you are actually exactly finding the closest smaller column in the right direction. It is this column that forces you to be poped out of the stack (due to the nondecreasing order), and you can only be poped out once. so it must be the first one in the right direction that force you to do so.
Anyway, you can record ever such rect and find max of them as follows:
class Solution: # @param height, a list of integer # @return an integer def largestRectangleArea(self, height): if not height: return 0 # using a queue to keep track of left, closest element smaller than current one; and right smallest element smaller than a given one (that is when it is poped out). and save max in each iteration stack=[] maxrect=0 for i in range(len(height)): current=height[i] while stack: if stack[1][1]>current: (index,h,left)=stack.pop() maxrect=max(h*(iindex1)+left,maxrect) elif stack[1][1]==current: stack.pop() else: break if stack: stack.append((i,current,current*(i(stack[1])[0]))) else: stack.append((i,current,current*(i+1))) while stack: (index,h,left)=stack.pop() maxrect=max(h*(len(height)index1)+left,maxrect) return maxrect

RE: My solution does not need a table for palindrome, is it right ? It uses only O(n) space.
this is not divide and conquer. This is DP. looking backwards of what he is doing, he is building the right cut K[i] for all i<n. aid K[n] is min(all valid palindrome(j,n) + K[j]). However , he did it in a very elegant , serial way

RE: My solution does not need a table for palindrome, is it right ? It uses only O(n) space.
this is not divide and conquer. This is DP.
looking backwards of what he is doing, he is building the right cut K[i] for all i<n. aid K[n] is min(all valid palindrome(j,n) + K[j]). However , he did it in a very elegant , serial way