Continuing the Leetcode streak with more Python solving. I have a New Year's Resolution related to Leetcode but I feel that to speak it is to jynx it.
Before solving/typing these up (I do it at the same time) I completed 595. It required a short SQL query checking two conditions. The speed-up catch was using a UNION.
- Sort Array By Parity
Problem: Given a list
N return an array split by even/odd from the numbers in
I'm using more high performance collections from Python today. Get ready for a speedy double ended queue.
from collections import dequeclass Solution:def sortArrayByParity(self, A):""":type A: List[int]:rtype: List[int]"""even_odd = deque()for num in A:if num % 2 == 0:even_odd.appendleft(num)else:even_odd.append(num)return list(even_odd)
Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.
The runtime complexity for this solution is
O(n) due to the above statement and the fact that we have iterated through
N just once. The space complexity is
I wonder if there's a faster version where the deque isn't converted to a list..
- Robot Return to Origin
Problem: Will this robot return home? Moving on a 2D plane via the commands:
U R D L.
Or, up, right, down, or left. This solution came to me instantly.
class Solution:def judgeCircle(self, moves):""":type moves: str:rtype: bool"""x = 0y = 0for i in moves:if i == 'U':y += 1if i == 'R':x += 1if i == 'D':y -= 1if i == 'L':x -= 1return x == 0 and y == 0
I did like this person's (4x slower) Python one-liner though:
return moves.count('L') - moves.count('R') == moves.count('D') - moves.count('U') == 0
- Self Dividing Numbers
Problem: Given a range of numbers
M return a list of self-divding numbers within that range.
Note: the range is inclusive, and a self-dividing num doesn't have a 0.
The example they give is
128 % 1 == 0,
128 % 2 == 0,
128 % 8 == 0 hence 128 is self-dividing.
I used an enclosed function to break this one up a bit.
class Solution:def selfDividingNumbers(self, left, right):""":type left: int:type right: int:rtype: List[int]"""self_dividing = list()for i in range (left, right+1):def can_divide(num):digits = numwhile digits:digit = digits % 10if digit == 0 or num % digit != 0:return Falsedigits //= 10return Trueif can_divide(i):self_dividing.append(i)return self_dividing
Runtime: 68 ms, faster than 75.67% of Python3 online submissions for Self Dividing Numbers.
The trick here is getting the digits of the number without resorting to slow tricks like casting it to a string and slicing it.
Runtime complexity: Iterating through the range means
O(m - n) -- all other operations are
Space complexity: The range is the max list size we hold so
O(m - n) as well.