飞

Count of Smaller Numbers After Self First I thought start from the end, for each element look right and find the first number which is smaller than it, then c[current] = c[firstsmall]+1, it turns out to be wrong in case [2,0,1], the correct should be move from the end and keep the array on the right of current element to be sorted, My first solution is insertion sort, but it results in time limit exceeds error, the complexity is nlg(n), if we don't consider the time used in copy array, to find the index where current number will be inserted is easy, just use the binary search, since it's already an sorted array class Solution(object): def countSmaller(self, nums): """ :type nums: List[int] :rtype: List[int] """ l = len(nums) i = l-1 self.sorted = [] ret = [] while i>=0: num = nums[i] index = self.getindex(num) self.sorted = self.sorted[:index]+[num]+self.sorted[index:] ret.append(index) i-=1

https://leetcode.com/problems/ugly-number-ii/ The idea is to keep three pointers, each pointer points to a position in the stack each number in the stack will be multiplied by 2,3,5 class Solution(object): def nthUglyNumber(self, n): """ :type n: int :rtype: int """ d = {} stack = [1] p1,p2,p3 = 0,0,0 i = 1 ret = 1 while i<n: u2,u3,u5 = [stack[p1]*2,stack[p2]*3,stack[p3]*5] cmin = min(u2,u3,u5) if cmin == u2: p1 +=1 if cmin == u3: p2+=1 if cmin == u5: p3+=1 i+=1 stack.append(cmin) return stack[-1] The same solution can be used for super ugly number def nthSuperUglyNumber(self, n, primes): stack = [1] l = len(primes) assert(l!=0) pointers = l*[0] while n>1: minnum = stack[pointers[0]]*primes[0] for i,p in enumerate(pointers): minnum = min(stack[p]*primes[i],minnum) for i,p in enumerate(pointers): if minnum == stack[p]*primes[i]:

Nim Game My first impression is to use dp, no need to store all three values just use a,b,c a is if I can win, if I pick one nim, b is if I pick two nim, c is if I pick three nim But this will cause Memory Error in python Then I used a loop and printed all the results within range 10, and found only if it's the multiple of 4 that will return False Runtime:  32 ms class Solution(object): def canWinNim(self, n): """ :type n: int :rtype: bool """ # a,b,c = False,False,False # for x in range(1,n+1): # current = False # if a == False: # current = True # if b == False: # current = True # if c == False: # current = True # a,b,c = current,a,b # return a                return n%4 !=0 s = Solution() for x in xrange(10): print s.canWinNim(x)

I Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. Complexity log(m) + log(n) First search the first column to decide which row using binary search Then, search the row from step one using binary search class Solution:     def searchMatrix(self, matrix, target):         row = len(matrix)         if row ==0:             return False         col = len(matrix[0])         start,end = 0,row-1         while start <end:             mid = (start+end)/2             if matrix[mid][0] > target:                 end = mid-1             elif matrix[mid][0] < target:                 start = mid+1             else:                 return True         row = end if target>=matrix[end][0] else end-1         start,end = 0,col-1         while start <=end:             mid = (start+end)/2             if matrix[row][mid] < target:                 start = mi

Remove Duplicate Letters Runtime:  272 ms https://leetcode.com/problems/remove-duplicate-letters/ Greedy solution, recursive, 1. Loop the string to find the letter(and it's position) which does not have duplicate or it's smallest among all letter in the string; if there are multiple of the smallest letter, use the position of the leftmost one 2.  call the function recursively, partition the string s[pos+1:], where pos is the one we find in step1, and replace all other occurence of the letter at s[pos]  from collections import Counter class Solution(object): def removeDuplicateLetters(self, s): """ :type s: str :rtype: str """ # s = list(s) if len(s) == 0: return "" d = Counter() pos = 0 for i,c in enumerate(s): d[c]+=1 for i,c in enumerate(s): if c < s[pos]: pos = i if d[c] == 1: break d[c] -=1 return s[pos]+self.removeDuplicateLetters(s[pos+1:].replace(s[pos]

https://leetcode.com/problems/rotate-array Rotate an array of  n  elements to the right by  k  steps. For example, with  n  = 7 and  k  = 3, the array  [1,2,3,4,5,6,7]  is rotated to  [5,6,7,1,2,3,4] . Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem. [show hint] Related problem:  Reverse Words in a String II Credits: Special thanks to  @Freezen  for adding this problem and creating all test cases. Subscribe  to see which companies asked this question Solution 1: Runtime:  80 ms Space O(n)  class Solution(object): def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ l = len(nums) k = k%l numscopy = list(nums) numscopy = numscopy[l-k:] + numscopy[:l-k] for i,num in enumerate(numscopy): nums[i] = num Solution 2: [1,2,3,4] is the first

https://leetcode.com/problems/basic-calculator-ii/ class Solution(object): def calculate(self, s): """ :type s: str :rtype: int """ numstack = [] operators = [] l = len(s) i=0 while i<l: if s[i].isdigit(): start = i while i<l and s[i].isdigit(): i+=1 numstack.append(int(s[start:i])) elif s[i] in ["+","-","*","/"]: operators.append(s[i]) i+=1 else: i+=1 # if there is n operator then there is n+1 nums for i,operator in enumerate(operators): if operator in ["*","/"]: num1,num2 = numstack[i],numstack[i+1] if operator == "*": numstack[i],numstack[i+1] = 0,num1*num2 else: numstack[i],numstack[i+1] = 0,num1/num2 operators[i] = operators[i-1] if i-1 >=0 else "+" if len(numstack) == 0: return 0 total = numstack[0] for i,operator in enumerate(oper