MaxProfit 100% Solution in python
Question
My Solution
def solution(A): # calculate the difference everyday diff = [0] * len(A) for i in range(1, len(A)): diff[i] = A[i]-A[i-1] # print(diff) # find the max slice maxEnding = 0 maxSlice = 0 for i in range(len(A)): # print(maxEnding) maxEnding = max(0, maxEnding+diff[i]) maxSlice = max(maxSlice, maxEnding) # print(maxSlice) return maxSlice
Note
The reading material is worth reading:
EquiLeader 100% Solution in python
Question
My Solution
def solution(A): # check if A has a dominator length = len(A) stack = [0]*length size = 0 for i in range(length): if size == 0: stack[size] = A[i] size += 1 elif stack[size-1] != A[i]: size -=1 else: stack[size] = A[i] size += 1 count = 0 for i in range(length): if A[i] == stack[size-1]: count += 1 hasDominator = 0 if count > length/2: hasDominator = 1 else: return 0 # print(hasDominator) # if A has a dominator -> prefix sum each index of doiminator numbers prefixSum = [0]*length curSum = 0 for i in range(length): if A[i] == stack[size-1]: curSum += 1 prefixSum[i] = curSum # print(prefixSum) # final step find all the cuts points that makes equiDominator happen ans = 0 for i in range(length): # print(prefixSum[i], " ", (i+1)/2) # print(prefixSum[length-1]-prefixSum[i], " ", (length-i-1)/2) if prefixSum[i] > (i+1)/2 and prefixSum[length-1]-prefixSum[i] > (length-i-1)/2: ans += 1 return ans
Dominator 100% Solution in python
Question
My Solution
def solution(A): stack = [0]*len(A) size = 0 index = -1 count = 0 for i in range(len(A)): if size == 0: stack[size] = A[i] size += 1 else: if stack[size-1] != A[i]: size -= 1 else: stack[size] = A[i] size += 1 # now dominents are remained in the stack for i in range(len(A)): if A[i] == stack[size-1]: index = i count += 1 if count > len(A)/2: return index else: return -1
Note
codility.com is worth reading!
StoneWall 100% Solution in python
Question
My Solution
def solution(H): block = 0 stack = [0]*len(H) size = 0 for i in range(len(H)): while size > 0 and stack[size-1] > H[i]: size -= 1 if size > 0 and stack[size-1] == H[i]: pass else: block += 1 stack[size] = H[i] size += 1 return block
Note
I read this official tutorial at first and followed this:
https://codility.com/media/train/solution-stone-wall.pdfcodility.com
Nesting 100% Solution in python
Question
My Solution
def solution(S): stack = [0]*len(S) size = 0 for i in range(len(S)): if S[i] is "(": stack[size] = S[i] size += 1 else: if size is 0: return 0 else: size -= 1 if size is 0: return 1 return 0
Brackets 100% Solution in python
Question
My Solution
def solution(S): stack = [0]*len(S) size = 0 for i in range(len(S)): if S[i] is "(" or S[i] is "{" or S[i] is "[": stack[size] = S[i] size += 1 else: if size is 0: return 0 elif S[i] is ")" and stack[size-1] is "(": size -=1 elif S[i] is "}" and stack[size-1] is "{": size -=1 elif S[i] is "]" and stack[size-1] is "[": size -=1 if size is 0: return 1 return 0
Note
Classic brackets pairing usually comes up with stack solution.
Fish 100% Solution in Python
Notice
Recently I got some codility challenges from companies and they don't allow me to use javascript. As a results, I learn the basic coding style in python from the very beginning on YouTube Python Programming Tutorial - 1 - Installing Python - YouTube and start to write codility in python.
Question
My Solution
def solution(A, B): downStack = [0] * len(A) downSize = 0 upAlive = 0 for i in range(-1, -1*(len(A)+1), -1): # push to downstream stack if B[i] is 0: downStack[downSize] = A[i] downSize += 1 else: # there's no downstream fish ahead of a upstream fish if downSize is 0: upAlive += 1 else: # eats all the smaller downstream fish ahead while A[i] > downStack[downSize-1]: downSize -= 1 if downSize is 0: break # it is alive if it eat them all if downSize is 0: upAlive += 1 return downSize+upAlive
Note
It took me a while to come up with this solution. Here's my concept behind the code:
I start trace the array from top to bottom, pushing all the downstream fishes to the stack. Whenever I meet an upstream fish. I popped up all the downstream fish ahead and smaller than this fish. If this stack is totally empty, it also means that this upstream fish survive, if not, this upstream fish is dead and all the remaining downstream survives.
