class Solution(object): def __init__(self): self.maxVal = 0 self.lookup = {} def rob(self, nums): “”” :type nums: List[int] :rtype: int “”” if len(nums) == 0: return 0 if len(nums) == 1: return nums[0] if len(nums) >= 2: self.lookup[0] = nums[0] self.lookup[1] = max(nums[0], nums[1]) for index in range(2, len(nums)): # There are two options at each […]

Read more## Palindrome Linked Lists O(1) Space Solution

There are three isolated steps: Find the mid of the list Reverse half of the list and create a new head Compare two heads class Solution(object): def findMiddle(self, head): slow = fast = head # find the mid node while fast and fast.next: fast = fast.next.next slow = slow.next if fast is None: return slow, […]

Read more## Pascal Triangle II

def getRow(self, rowIndex): “”” :type rowIndex: int :rtype: List[int] “”” if rowIndex == 0: return [1] numRows = rowIndex + 1 previous = [1] answer = None for x in range(2, numRows+1): row = [1]*x # Mutate the row for y in range(1, x-1): #print(“x={} y={} row={} prev={}”.format(x, y, row, previous)) row[y] = previous[y-1]+ previous[y] […]

Read more## Pascal Triangle

def generate(self, numRows): “”” :type numRows: int :rtype: List[List[int]] “”” answer = [] if numRows == 0: return [] row = [1] answer.append(row) for x in range(2, numRows+1): # Prepare the row row = [1]*x # The first and last element on each row is 1, so skip those # indexes. for y in range(1, […]

Read more## Why Use Python Ordered Dictionary?

The ordered dictionary offers same time complexity as the standard dict. The implementation is simple: Keep two dictionaries and a doubly-linked list of keys. The DLL maintains order. One dict maps key => DLL node Other dict maps key => value Implementation details https://github.com/python/cpython/blob/3.7/Lib/collections/init.py#L129 Example Problem: Find the first non-repeating char in a string. def […]

Read more## Check Two Strings are Anagrams?

class Solution(object): def isAnagram(self, s, t): “”” :type s: str :type t: str :rtype: bool “”” # Keep a frequency array frequency = {} for c in s: if c not in frequency: frequency[c] = 1 else: frequency[c] += 1 # Go over the other string for d in t: if d in frequency: frequency[d] […]

Read more## Python Cheatsheet – IV

Enumerate a list with index for index, value in enumerate(mylist): print(index, value) Enumerate from a different start index mylist = [5,6,7] for index, value in enumerate(mylist, start= 1): print(index, value) 1 5 2 6 3 7 Dictionary iterate for k, v in d.items(): print(k, v) References https://www.afternerd.com/blog/python-enumerate/ Written with StackEdit.

Read more