Python – Page 4 – Code Says

Solution to Binary Tree Right Side View by LeetCode

18 Jun

Question: https://leetcode.com/problems/binary-tree-right-side-view/ Question Name: Binary Tree Right Side View A variant of level order tree traversal.

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param {TreeNode} root

# @return {integer[]}

def rightSideView(self, root):

current_layer = [root] if root != None else []

result = []

while len(current_layer) != 0:

result.append(current_layer[-1].val)

next_layer = []

for node in current_layer:

if node.left != None: next_layer.append(node.left)

if node.right != None: next_layer.append(node.right)

current_layer = next_layer

return result

Solution to House Robber by LeetCode

18 Jun

Question: https://leetcode.com/problems/house-robber/ Question Name: House Robber Simple DP problem. If you want, you could improve the space complexity to O(1) with bookkeeping (the second previous house, the previous house, and the current house).

class Solution:

# @param {integer[]} nums

# @return {integer}

def rob(self, nums):

if len(nums) == 0: return 0

if len(nums) <= 2: return max(nums)

max_money = [0] * len(nums)

max_money[0] = nums[0]

max_money[1] = max(nums[0], nums[1])

for house in xrange(2, len(nums)):

max_money[house] = max(max_money[house-1], max_money[house-2]+nums[house])

return max_money[-1]

Solution to Number of 1 Bits by LeetCode

1 Jun

Question: https://leetcode.com/problems/number-of-1-bits/ Question Name: Number of 1 Bits The key is how to find and remove the last 1-bit.

class Solution:

# @param n, an integer

# @return an integer

def hammingWeight(self, n):

count = 0

while n != 0:

count += 1

n = n & (n - 1) # Remove the last 1-bit.

return count

Solution to Reverse Bits by LeetCode

1 Jun

Question: https://leetcode.com/problems/reverse-bits/ Question Name: Reverse Bits Exactly same challege from Elements of Programming Interviews.

class Solution:

# @param n, an integer

# @return an integer

def reverseBits(self, n):

transfer_table = {0b0000 : 0b0000, 0b0001 : 0b1000, 0b0010 : 0b0100, 0b0011 : 0b1100,

0b0100 : 0b0010, 0b0101 : 0b1010, 0b0110 : 0b0110, 0b0111 : 0b1110,

0b1000 : 0b0001, 0b1001 : 0b1001, 0b1010 : 0b0101, 0b1011 : 0b1101,

0b1100 : 0b0011, 0b1101 : 0b1011, 0b1110 : 0b0111, 0b1111 : 0b1111}

result = 0

for shift in xrange(0, 32, 4):

# Process 4 bits in each round

result = (result << 4) | transfer_table[(n >> shift) & 0x0F]

return result

Solution to Rotate Array by LeetCode

28 May

Question: https://leetcode.com/problems/rotate-array/ Question Name: Rotate Array Classic Doug McIlroy’s Handwaving. It is very similar with some previous question.

class Solution:

# @param {integer[]} nums

# @param {integer} begin, inclusive

# @param {integer} end, exclusive

# @return {void} Do not return anything, reverse array in-place.

def reverse(self, nums, begin, end):

for index in xrange((end - begin) // 2):

front = begin + index

back = end - index - 1

nums[begin + index] ^= nums[end - index - 1]

nums[end - index - 1] ^= nums[begin + index]

nums[begin + index] ^= nums[end - index - 1]

return

# @param {integer[]} nums

# @param {integer} k

# @return {void} Do not return anything, modify nums in-place instead.

def rotate(self, nums, k):

k = len(nums) - (k % len(nums))

if k != len(nums):

self.reverse(nums, 0, k)

self.reverse(nums, k, len(nums))

self.reverse(nums, 0, len(nums))

return

Solution to Best Time to Buy and Sell Stock IV by LeetCode

25 May

Question: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/ Question Name: Best Time to Buy and Sell Stock IV Thanks to genius solution from @yishiluo.

import heapq

class TopN:

def __init__(self, n):

assert(n > 0)

self.maximum = n

self.content = []

def add(self, value):

if len(self.content) < self.maximum:

heapq.heappush(self.content, value)

elif self.content[0] < value:

heapq.heappushpop(self.content, value)

def result(self):

return self.content

def debug_info(self):

print "Content(max:", self.maximum,"):", self.content

class Solution:

# @param {integer} k

# @param {integer[]} prices

# @return {integer}

def maxProfit(self, k, prices):

if len(prices) < 2 or k < 1: return 0

stack = []

profitable = TopN(k)

valley = 0

peak = -1

while valley < len(prices):

# Find the next profitable transaction.

while valley < len(prices) - 1 and prices[valley] >= prices[valley + 1]:

valley += 1

if valley == len(prices) - 1: break

peak = valley + 1

while peak < len(prices) -1 and prices[peak] < prices[peak + 1]:

peak += 1

# Try to finalize or combine with previous transactions.

valley_price = prices[valley]

peak_price = prices[peak]

while len(stack) != 0 and stack[-1][0] >= valley_price:

transaction = stack.pop()

profitable.add(transaction[1] - transaction[0])

while len(stack) != 0 and stack[-1][1] <= peak_price:

transaction = stack.pop()

profitable.add(transaction[1] - valley_price)

valley_price = transaction[0]

# Finish processing current transaction.

stack.append([valley_price, peak_price])

valley = peak + 1

# Finalize all the remaining transactions.

for transaction in stack:

profitable.add(transaction[1] - transaction[0])

return sum(profitable.result())

Solution to Repeated DNA Sequences by LeetCode

29 Apr

Question: https://leetcode.com/problems/repeated-dna-sequences/ Question Name: Repeated DNA Sequences Simple brute force solution works.

class Solution:

# @param {string} s

# @return {string[]}

def findRepeatedDnaSequences(self, s):

occurrence = {}

for startIndex in xrange(len(s)-9):

piece = s[startIndex : startIndex + 10]

occurrence[piece] = occurrence.get(piece, 0) + 1

return [dna for dna in occurrence.keys() if occurrence[dna] > 1]

Solution to Largest Number by LeetCode

29 Apr

Question: https://leetcode.com/problems/largest-number/ Question Name: Largest Number Conver the input numbers into strings. And then sort the strings according to special rule.

class Solution:

# @param {integer[]} nums

# @return {string}

def largestNumber(self, nums):

temp = [str(i) for i in nums]

temp.sort(cmp = lambda x, y: cmp(x+y, y+x), reverse = True)

result = "".join(temp)

if result[0] == "0": return "0" # All "0"s

else: return result

However, if you prefer a Python3 solution:

from functools import cmp_to_key

class Solution:

def largestNumber(self, nums: List[int]) -> str:

temp = [str(i) for i in nums]

temp.sort(key=cmp_to_key(lambda x, y: 1 if x+y < y+x else -1))

result = "".join(temp)

if result[0] == "0": return "0" # All "0"s

else: return result

Solution to Dungeon Game by LeetCode

27 Apr

Question: https://leetcode.com/problems/dungeon-game/ Question Name: Dungeon Game The challenge is a DP question. Let minHPFromHere be a 2D matrix with the size of input dungeon game. minHPFromHere[i][j] is the minimum HP to rescue the princess, if the input[i][j] is the initial … Read More »

Solution to Binary Search Tree Iterator by LeetCode

24 Apr

Question: https://leetcode.com/problems/binary-search-tree-iterator/ Question Name: Binary Search Tree Iterator The challenge is a variant of the iterative in-order traversal of BST. However, yield in python is much much better in implementing iterator, right?

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class BSTIterator:

# @param root, a binary search tree's root node

def __init__(self, root):

self.stack = []

current = root

while current != None:

self.stack.append(current)

current = current.left

return

# @return a boolean, whether we have a next smallest number

def hasNext(self):

return len(self.stack) != 0

# @return an integer, the next smallest number

def next(self):

next_node = self.stack.pop()

current = next_node.right

while current != None:

self.stack.append(current)

current = current.left

return next_node.val

# Your BSTIterator will be called like this:

# i, v = BSTIterator(root), []

# while i.hasNext(): v.append(i.next())

tl;dr: Please put your code into a <pre>YOUR CODE</pre> section.

Hello everyone!

If you want to ask a question about the solution. DO READ the post and comments firstly.

If you had some troubles in debugging your solution, please try to ask for help on StackOverflow, instead of here.

If you want to post some comments with code or symbol, here is the guidline.

1. To post your code, please add the code inside a <pre> </pre> section (preferred), or <code> </code>. And inside the pre or code section, you do not need to escape < > and &, e.g. no need to use < instead of <.

2. To use special symbols < and > outside the pre block, please use "<" and ">" instead.

3. If you have a comment with lots of < and >, you could add the major part of your comment into a <pre class="decode:true crayon-inline "> YOUR COMMENTS </pre> section.

Finally, if you are posting the first comment here, it usually needs moderation. Please be patient and stay tuned. Thanks!

CodeSays.com Admin

Ovi February 12, 2024 at 11:14 pm on Solution to Min-Perimeter-Rectangle by codilityExactly my question too. I tried something very similar to Sheng's solution, importing the math module and using sqrt(). Codility marked it only as 80%,...
Doron Ben Ari February 11, 2024 at 4:10 am on Solution to Min-Avg-Two-Slice by codilityInspired by Sheng's great solution, I wrote the following proof: Assume you found the slice with minimal average. Assume the first two consecutive elements of...
Ovi February 4, 2024 at 9:03 am on Solution to sigma2012 (Stone-Wall) by codility def solution(H): heights = H # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles...
Ovidiu Oprea February 2, 2024 at 11:06 am on Solution to Fish by codilityIt's the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying...
Ovi January 15, 2024 at 2:40 pm on Solution to Brackets by codilityThanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build...
parikshit verma July 5, 2023 at 8:26 am on Solution to Missing-Integer by codility def missingnum(a): st=min(a) en=max(a) b=set(range(1,en+2)) if (en<1 or st>1) : return 1 else: return min(b-set(a))
Pavankumar Nandeshwar June 26, 2023 at 8:07 am on Solution to Dwarfs-Rafting by codilityOk fixed it. gives 100%: int solution(int N, string &S, string &T) { int q = N / 2 * N / 2; int lf...
Pavankumar Nandeshwar June 26, 2023 at 5:23 am on Solution to Dwarfs-Rafting by codilityCan someone explain what is wrong with my solution in C++ ? int solution(int N, string &S, string &T) { int q = N /...
Pavankumar Nandeshwar June 23, 2023 at 10:25 pm on Solution to Flood-Depth by codilityMy C++ Solution. O(N) #include <climits> int solution(vector<int> &A) { int max_depth {}; int max_lvl = {}; int min_lvl = INT_MAX; for (unsigned int i...