Sheng – Page 5 – Code Says

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())

Solution to Factorial Trailing Zeroes by LeetCode

24 Apr

Question: https://leetcode.com/problems/factorial-trailing-zeroes/ Question Name: Factorial Trailing Zeroes I firstly saw this question on CTCI. The key points of the solution are: Every interger could be represented as (2^i)*(5^j)*x, where i, j >= 0 and x cannot be evenly divided by … Read More »

Solution to Excel Sheet Column Number by LeetCode

23 Apr

Question: https://leetcode.com/problems/excel-sheet-column-number/ Question Name: Excel Sheet Column Number This tiny website is hosted on a free provider. Therefore it is not as strong as the big guys. SORRY for any inconvenience recently.

class Solution:

# @param {string} s

# @return {integer}

def titleToNumber(self, s):

result = 0

for letter in s:

result = result * 26 + (ord(letter) - ord("A") + 1)

return result

Solution to Majority Element by LeetCode

9 Apr

Question: https://leetcode.com/problems/majority-element/ Question Name: Majority Element We can do it with a dictionary (O(N) time, O(N) space). For a better solution with O(N) time and O(1) space, we can remove pairs of different elements as many as possible, and the … Read More »

Solution to Excel Sheet Column Title by LeetCode

9 Apr

Question: https://leetcode.com/problems/excel-sheet-column-title/ Question Name: Excel Sheet Column

class Solution:

# @return a string

def convertToTitle(self, num):

result = []

while num != 0:

num -= 1

result.append(chr(ord("A") + (num % 26)))

num //= 26

return "".join(result[::-1])

Solution to Fraction to Recurring Decimal by LeetCode

8 Apr

Question: https://leetcode.com/problems/fraction-to-recurring-decimal/ Question Name: Fraction to Recurring Decimal Again, a little mathematical puzzle. Pay attention to some corner cases.

class Solution:

# @return a string

def fractionToDecimal(self, numerator, denominator):

# Adjust the sign of the input.

sign = ""

if numerator < 0 and denominator > 0:

numerator = -numerator

sign = "-"

if numerator > 0 and denominator < 0:

denominator = -denominator

sign = "-"

# Check the case when numerator is divisible by denominator

remaining = numerator % denominator

if remaining == 0: return sign + str(numerator // denominator)

# Process the fractional part. It is a mathematical story: balala...

result = [sign, str(numerator // denominator), "."]

position = {} # A dictionary of dictionary

current = 3

while remaining != 0:

remaining *= 10

newvalue = remaining // denominator

if not newvalue in position: position[newvalue] = {}

newRemaining = remaining % denominator

if newRemaining == 0:

# Division finished.

result.append(str(newvalue))

break

elif newRemaining in position[newvalue]:

# Loop is found.

result.insert(position[newvalue][newRemaining], "(")

result.append(")")

break

result.append(str(newvalue))

position[newvalue][newRemaining] = current

# Prepare the next digit.

remaining = remaining % denominator

current += 1

return "".join(result)

Solution to Compare Version Numbers by LeetCode

7 Apr

Question: https://leetcode.com/problems/compare-version-numbers/ Question Name: Compare Version Numbers Clean up the tailing 0(s), and the right answer is there.

class Solution:

# @param version1, a string

# @param version2, a string

# @return an integer

def compareVersion(self, version1, version2):

# Split the version number with dot, and clear the tailing 0(s)

versionList1 = [int(ver) for ver in version1.split(".")]

while len(versionList1) > 1 and versionList1[-1] == 0:

versionList1.pop()

versionList2 = [int(ver) for ver in version2.split(".")]

while len(versionList2) > 1 and versionList2[-1] == 0:

versionList2.pop()

shorterVersion = min(len(versionList1), len(versionList2))

# Compare the common part of version numbers.

for i in xrange(shorterVersion):

if versionList1[i] > versionList2[i]: return 1

elif versionList1[i] < versionList2[i]: return -1

# Check the remaining part of version number.

if len(versionList1) != shorterVersion: return 1

elif len(versionList2) != shorterVersion: return -1

else: return 0

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...