[LeetCode] Linked List Random Node

2016-09-08

Analysis:

Using Reservior sampling. Continuously sampling from the list and find an element that met
rand(0, cnt) < k

Time Complexity:

O(n)

Space Complexity：

O(1)

Code

import random
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):

    def __init__(self, head):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        :type head: ListNode
        """
        self.head = head

    def getRandom(self):
        """
        Returns a random node's value.
        :rtype: int
        """
        k = 1
        cnt = 0
        retNode = 0
        curnode = self.head
        while curnode is not None:
            if cnt < k:
                retNode = curnode.val
            else:
                rrand = random.randint(0, cnt)
                if rrand < k:
                    retNode = curnode.val

            cnt += 1
            curnode = curnode.next
        return retNode

展开全文 >>

[LeetCode] Lexicographical Numbers

2016-08-24

Analysis:

there are two layers: first determine the base number from [1-9], then DFS through all combinations

Time Complexity:

O(n)

Space Complexity：

O(n)

Code

class Solution(object):
    def dfsHelper(self, base, n, retlist):
        for i in xrange(10):
            curnum = base*10 + i
            if curnum <= n:
                retlist.append(curnum)
                self.dfsHelper(curnum, n, retlist)
            else:
                break

    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        retlist = []
        for i in xrange(1, 10):
            if i <= n:
                retlist.append(i)
                self.dfsHelper(i, n , retlist)
        return retlist

展开全文 >>

[LeetCode] Binary Tree Upside Down

2016-08-23

Analysis:

You should use recursion and treat every three nodes as a group

Then you can find that the left most node must be the root, then we return it as parent node

remember to reset root’s left node and right node to NULL

Time Complexity:

O(n)

Space Complexity：

O(n)

Code

class Solution(object):
	def helper(self, root):
		if root is None:
			return root, None

		if root.left is None and root.right is None:
			return root, root

		parent, newroot = self.helper(root.left)
		parent.right = root
		parent.left = root.right
		root.left, root.right = None, None
		return parent.right, newroot

	def upsideDownBinaryTree(self, root):
		"""
		:type root: TreeNode
		:rtype: TreeNode
		"""
		newroot = None
		__ , newroot = self.helper(root)
		return newroot

展开全文 >>

[LeetCode] Next Permutation

2016-08-21

Analysis:

find j in array in reverse order that nums[j]<nums[j+1]

find the first element that nums[i]>nums[j]

swap the elements nums[i], nums[j]

reverse nums[j+1:]

Time Complexity:

O(n)

Space Complexity：

O(1)

Code

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        lens = len(nums)
        j = lens-2
        while j >= 0 and nums[j] >= nums[j+1]:
            j -= 1

        if j < 0:
            nums.reverse()
            return

        i = lens-1
        while i > j and nums[i] <= nums[j]:
            i -= 1
        
        nums[i], nums[j] = nums[j], nums[i]
        nums[j+1:] = reversed(nums[j+1:])

展开全文 >>

[LeetCode] Maximum Size Subarray Sum Equals k

2016-08-18

Analysis:

use a dict to store sum of range sum as key and index as value
we can check if the remaining in the dict. If so, find the largest gap of them.

Time Complexity:

O(n)

Space Complexity：

O(n)

Code

class Solution(object):
    def maxSubArrayLen(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        sumstore = collections.defaultdict(list)
        cursum = 0
        for i in xrange(len(nums)):
            cursum += nums[i]
            sumstore[cursum].append(i)

        retval = 0
        for t in sumstore.keys():
            if t == k:
                retval = max(retval, sumstore[t][-1]+1)
            elif t-k in sumstore:
                retval = max(retval, sumstore[t][-1]-sumstore[t-k][0])
        return retval

展开全文 >>

[LeetCode] Shuffle an Array

2016-08-16

Analysis:

The method to solve this problem, please refer to Fisher–Yates shuffle

Time Complexity:

O(n)

Space Complexity：

O(n)

Code

class Solution(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        :type size: int
        """
        self.orig = nums[:]
        self.curstr = nums[:]

    def reset(self):
        """
        Resets the array to its original configuration and return it.
        :rtype: List[int]
        """
        self.curstr[:] = self.orig
        return self.orig

    def shuffle(self):
        """
        Returns a random shuffling of the array.
        :rtype: List[int]
        """
        lens = len(self.curstr)
        for i in xrange(lens-1, 0, -1):
            j = random.randint(0, i)
            self.curstr[i], self.curstr[j] = self.curstr[j], self.curstr[i]
        return self.curstr

展开全文 >>

[LeetCode] Insert Delete GetRandom O(1) - Duplicates allowed

2016-08-14

Analysis:

use set in defaultdict to store the index

Time Complexity:

O(1)

Space Complexity：

O(n)

Code

class RandomizedCollection(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.storemap = collections.defaultdict(set)
        self.vec = []
        self.lens = 0

    def insert(self, val):
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        retval = True if val not in self.storemap else False
        self.storemap[val].add(self.lens)
        self.vec.append(val)
        self.lens += 1
        return retval

    def remove(self, val):
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.storemap:
            return False

        idx = self.storemap[val].pop()
        tail = self.vec[-1]
        self.vec[idx] = tail
        self.storemap[tail].add(idx)
        self.storemap[tail].remove(self.lens-1)

        del self.vec[-1]
        if not self.storemap[val]:
            del self.storemap[val]
        self.lens -= 1
        return True

    def getRandom(self):
        """
        Get a random element from the collection.
        :rtype: int
        """
        return random.choice(self.vec)

展开全文 >>

[LeetCode] Insert Delete GetRandom O(1)

2016-08-14

Analysis:

define a dictionary to store the elements and a vector to store the index of them.
the key of removal is to move the tail element to the slot of removal element and update the tail element index.

Time Complexity:

O(1)

Space Complexity：

O(n)

Code

class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.storemap = collections.defaultdict(int)
        self.vec = []
        self.lens = 0

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.storemap:
            self.storemap[val] = self.lens
            self.vec.append(val)
            self.lens += 1
            return True
        else:
            return False
        

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.storemap:
            idx = self.storemap[val]
            tail = self.vec.pop()
            if idx < len(self.vec):
                self.vec[idx] = tail
                self.storemap[tail] = idx
            del self.storemap[val]
            self.lens -= 1
            return True
        else:
            return False
        

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return random.choice(self.vec)

展开全文 >>

[LeetCode] Combination Sum IV

2016-07-26

Analysis:

define a array dp[i] to depict the possible combination of i, then we have
if i+j <= target then dp[i+j] += dp[i]

Time Complexity:

O(n^2)

Space Complexity：

O(n)

Code

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [0] * (target+1)
        dp[0] = 1
        for x in xrange(target+1):
            for y in nums:
                if x + y <= target:
                    dp[x+y] += dp[x]
        return dp[target]

展开全文 >>

[LeetCode] Find K Pairs with Smallest Sums

2016-07-08

Analysis:

using a heap to store the sum numbers, using a two-dimensional array to mark the visited pairs,
also using a defaultdict to store the indexes.

Time Complexity:

O(nlogn)

Space Complexity：

O(n)

Code

class Solution(object):
    def kSmallestPairs(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[List[int]]
        """
        vec = []
        retlist = []
        dx, dy = [0, 1], [1, 0]
        if len(nums1) == 0 or len(nums2) == 0:
            return retlist
        storeMap = collections.defaultdict(list)

        len1, len2 = len(nums1), len(nums2)

        visited = [[0 for j in xrange(len2)] for i in xrange(len1)]
        visited[0][0] = 1

        vec.append(nums1[0]+nums2[0])
        storeMap[nums1[0]+nums2[0]].append([0, 0])
        heapq.heapify(vec)


        while len(vec) > 0 and k > 0:
            cur = heapq.heappop(vec)
            idx1, idx2 = storeMap[cur][0][0], storeMap[cur][0][1]
            storeMap[cur].pop(0)

            retlist.append([nums1[idx1], nums2[idx2]])
            for i in xrange(2):
                x, y = idx1+dx[i], idx2+dy[i]
                if x < len1 and y < len2 and visited[x][y] == 0:
                    heapq.heappush(vec, nums1[x]+nums2[y])
                    storeMap[nums1[x]+nums2[y]].append([x, y])
                    visited[x][y] = 1
            k -= 1

        return retlist

展开全文 >>