Sheng – Page 25 – Code Says

Solution to Next Permutation by LeetCode

28 Apr

Question: http://oj.leetcode.com/problems/next-permutation/ Question Name: Next Permutation This problem seems like a mathematic question, rather than a programming challenge.

class Solution:

# @param num, a list of integer

# @return a list of integer

def nextPermutation(self, num):

# In the greatest permutation of numbers, any number is larger

# than or equal to the right remaining numbers.

# If the num is not the greatest permutation, there must be

# one or more pairs being rule breakers. That is, in these pairs,

# the left hand number is smaller than the right hand one.

# Search from rightmost to leftmost to find out the least

# significant rule breaker.

back = len(num) - 2

while back >= 0:

front = len(num) - 1

while front > back :

if num[back] < num[front]:

# Rule breaker found.

num[back], num[front] = num[front], num[back]

num[back+1:] = sorted(num[back+1:])

return num

else:

front -= 1

back -= 1

# No rule breaker in this array. Return the lowest possible order.

num.sort()

return num

Solution to Substring with Concatenation of All Words by LeetCode

26 Apr

Question: http://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/ Question Name: Substring with Concatenation of All Words The brute force method works here. Assume the hash function is O(n). Let the length of S be M, the length of L be N, and the length of each … Read More »

Solution to Implement strStr() by LeetCode

25 Apr

Question: http://oj.leetcode.com/problems/implement-strstr/ Question Name: Implement strStr() The KMP is a much better solution. But as long as brute force passed all tests, let’s use brute force.

class Solution:

# @param haystack, a string

# @param needle, a string

# @return a string or None

def strStr(self, haystack, needle):

# Hanlde two special cases.

if needle == "": return haystack

if haystack == "": return None

lenHaystack = len(haystack)

lenNeedle = len(needle)

begin = 0

# Compare each substring as long as their length

# is >= the length of needle

while lenHaystack - begin >= lenNeedle:

for index in xrange(lenNeedle):

if haystack[begin+index] != needle[index]:

# Find a different char

break

else:

# Completely the same

return haystack[begin:]

begin += 1

return None

Solution to Divide Two Integers by LeetCode

24 Apr

Question: http://oj.leetcode.com/problems/divide-two-integers/ Question Name: Divide Two Integers

class Solution:

# @return an integer

def divide(self, dividend, divisor):

# Handle the special case that, dividend is zero

if dividend == 0: return 0

# Handle the special case that, divisor is zero

if divisor == 0: raise ZeroDivisionError()

result = 0 # Final result

# Determine the sign of final result, and convert

# dividend or/and divisor into positive integer.

positive = True

if dividend < 0:

dividend = -dividend

positive = (not positive)

if divisor < 0:

divisor = -divisor

positive = (not positive)

# Enlarge the divisor as long as it is <= dividend

step = divisor

stepRes = 1

while (step << 1) <= dividend:

step = step << 1

stepRes = stepRes << 1

while step >= divisor:

while dividend >= step:

dividend -= step

result += stepRes

# If current step is too large, try a smaller

# step (divisor).

step = step >> 1

stepRes = stepRes >> 1

if positive: return result

else: return -result

Solution to Remove Duplicates from Sorted Array by LeetCode

24 Apr

Question: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/ Question Name: Remove Duplicates from Sorted Array

class Solution:

# @param a list of integers

# @return an integer

def removeDuplicates(self, A):

# Handle the special case that, A is empty

if len(A) == 0: return 0

front, back = 1, 1

while front < len(A):

if A[front] != A[front-1]:

# Not a duplicate item

A[back] = A[front]

back += 1

front += 1

return back

Solution to Remove Element by LeetCode

24 Apr

Question: http://oj.leetcode.com/problems/remove-element/ Question Name: Remove Element

class Solution:

# @param A a list of integers

# @param elem an integer, value need to be removed

# @return an integer

def removeElement(self, A, elem):

front, back = 0, 0

while front < len(A):

if A[front] != elem:

# Not to be removed

A[back] = A[front]

back += 1

front += 1

return back

Solution to Reverse Nodes in k-Group by LeetCode

24 Apr

Question: http://oj.leetcode.com/problems/reverse-nodes-in-k-group/ Question Name: Reverse Nodes in k-Group

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param pre, a ListNode

# @param current, a ListNode

# @param k, an integer

# @return a ListNode

def _reverseNextK(self, pre, current, k):

# Not enough nodes to reverse

if current == None: return None, None

# Last node to reverse

if k == 1:

nextNode = current.next

current.next = pre

return current, nextNode

# Recursively reverse the remaining nodes

newHead, nextHead = self._reverseNextK(current, current.next, k-1)

if newHead == None:

# Not enough nodes to reverse

return None, None

else:

# Reversing

current.next = pre

return newHead, nextHead

# @param head, a ListNode

# @param k, an integer

# @return a ListNode

def reverseKGroup(self, head, k):

newHead, nextHead = self._reverseNextK(None, head, k)

if newHead == None: return head # Not enough nodes to reverse

else: result = newHead # Record the new head node

preTail = head

# As long as there are enough nodes to reverse, do it.

while nextHead != None:

currentNode = nextHead

# Reverse the nodes inside the next K-group

newHead, nextHead = self._reverseNextK(None, currentNode, k)

if newHead != None: preTail.next = newHead # Reversed

else: preTail.next = currentNode # Not reversed

preTail = currentNode

return result

Solution to Min-Abs-Sum-Of-Two by codility

21 Apr

Question: https://codility.com/demo/take-sample-test/min_abs_sum_of_two Question Name: Min-Abs-Sum-Of-Two or MinAbsSumOfTwo There are two O(nlogn) solutions for this question. Both solutions have the same overall time complexity and space complexity. And both solutions need to sort the array in non-decreasing order first. The first … Read More »

Solution to Count-Distinct-Slices by codility

17 Apr

Question: https://codility.com/demo/take-sample-test/count_distinct_slices Question Name: Count-Distinct-Slices or CountDistinctSlices

def solution(M, A):

accessed = [-1] * (M + 1) # -1: not accessed before

# Non-negative: the previous occurrence position

front, back = 0, 0

result = 0

for front in xrange(len(A)):

if accessed[A[front]] == -1:

# Met with a new unique item

accessed[A[front]] = front

else:

# Met with a duplicate item

# Compute the number of distinct slices between newBack-1 and back

# position.

newBack = accessed[A[front]] + 1

result += (newBack - back) * (front - back + front - newBack + 1) / 2

if result >= 1000000000: return 1000000000

# Restore and set the accessed array

for index in xrange(back, newBack):

accessed[A[index]] = -1

accessed[A[front]] = front

back = newBack

# Process the last slices

result += (front - back + 1) * (front - back + 2) / 2

return min(result, 1000000000)

Solution to Count-Triangles by codility

17 Apr

Question: https://codility.com/demo/take-sample-test/count_triangles Question Name: Count-Triangles or CountTriangles This problem is nearly the same as the exercise in presentation of lesson 13. Update on May 24, 2014: Thanks to @Adam. Fix a bug, which lower the performance.

def solution(A):

n = len(A)

result = 0

A.sort()

for first in xrange(n-2):

third = first + 2

for second in xrange(first+1, n-1):

while third < n and A[first] + A[second] > A[third]:

third += 1

result += third - second - 1

return result

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

Fabien November 7, 2024 at 4:42 am on Unofficial Solutions to the Training by CodilitySimilar but more compact solution using C++17 or later: #include <stack> #include <vector> using namespace std; using point = pair<int, int>; stack<point> pending; void explore(const...
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 /...