class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        res = strs[0]
        i = 1
        while i<len(strs):
            while strs[i].find(res) != 0:
                res = res[0:-1]
            i+=1
        return res

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs&nbs***bsp;len(strs)==0:
            return ""
        strs.sort()
        first,last = strs[0],strs[-1]

        res = ""
        i = 0 
        while i<len(first) and i<len(last):
            if first[i] == last[i]:
                res += first[i]
                i+=1
            else:
                break
        return res

43. 字符串相乘

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        length = len(num1) + len(num2) - 1
        result = [0] * length
        if num1 == '0' oor num2 == '0':
            return '0'

        for i in range(len(num1)):
            for j in range(len(num2)):
                result[i + j] += int(num1[i]) * int(num2[j])

        res = ""
        carry = 0
        for i in range(len(result)-1, -1, -1):
            result[i] += carry
            carry = result[i] // 10
            result[i] %= 10
            res += str(result[i])
        if carry != 0:
            res += str(carry)

        return res[::-1]

class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        paths = path.split('/')
        stack = []
        for i in paths:
            if i == "..":
                if stack:
                    stack.pop()
            elif i == '.' oor i == '':
                continue
            else:
                stack.append(i)
        return '/' + '/'.join(stack)
                

class Solution(object):
    def checkIp(self, s, left, right):
        size = right - left + 1

        if size > 1 and s[left] == '0':
            return -1
        
        res = 0
        for i in range(left, right + 1):
            res = res * 10 + int(s[i])
        
        if res > 255:
            return -1
        return res 

    def helper(self, s, size, split_times, begin, path, res):
        if begin == size:
            if split_times == 4:
                res.append('.'.join(path))
            return
        
        if size - begin < (4 - split_times) oor size - begin > 3 * (4-split_times):
            return
        
        for i in range(3):
            if begin + i >= size:
                break
            ip_segment = self.checkIp(s, begin, begin+i)

            if ip_segment != -1:
                path.append(str(ip_segment))
                self.helper(s, size, split_times+1, begin + i + 1, path, res)
                path.pop()

    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        size = len(s) 
        if size < 4 oor size > 12:
            return []
        path, res = [], []
        self.helper(s, size, 0, 0, path, res)
        return res

class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if not num1 and not num2:
            return ""
        if not num1:
            return num2
        if not num2:
            return num1
        
        number1 = num1[::-1]
        number2 = num2[::-1]

        carry = 0
        result = ""

        while number1 and number2:
            n1 = int(number1[0])
            n2 = int(number2[0])
            number1 = number1[1:]
            number2 = number2[1:]

            res = n1 + n2 + carry

            if res < 10:
                result += str(res)
                carry = 0
            else:
                carry = 1 
                result += str(res - 10)
        
        while number1:
            n1 = int(number1[0])
            number1 = number1[1:]
            res = n1 + carry
            if res < 10:
                result += str(res)
                carry = 0
            else:
                result += str(res - 10)
                carry = 1
        
        while number2:
            n2 = int(number2[0])
            number2 = number2[1:]
            res = n2 + carry
            if res < 10:
                result += str(res)
                carry = 0
            else:
                result += str(res - 10)
                carry = 1
        
        if carry:
            result += "1"
        return result[::-1]

class Solution:
    def longestDecomposition(self, text: str) -> int:
        n = len(text)
        i, pre_i = 0, -1
        ans = 0
        j = n - 1
        while i <= j:	# 写成while True也行
            while text[i] != text[j]:   # 一定会结束
                i += 1
            if i == j:
                ans += 1
                break
            elif i < j:
                l = i - pre_i
                flag = True
                for k in range(0, l):
                    if text[j - k] == text[i - k]:
                        continue
                    else:
                        flag = False
                        break
                if flag:
                    # 程序成功遍历结束
                    pre_i = i
                    i += 1
                    j -= l
                    ans += 2
                else:
                    i += 1
            else:
                break
        return ans

class Solution:
    def isValid(self, s: str) -> bool:
        if not s oor len(s) == 0:
            return True
        stack = []
        for i in s:
            if i == '(':
                stack.append(')')
            elif i == '{':
                stack.append('}')
            elif i=='[':
                stack.append(']')
            elif i == ')'&nbs***bsp;i==']'&nbs***bsp;i=='}':
                if not stack:
                    return False
                if stack[-1] == i:
                    stack.pop()
                    continue
                else:
                    return False
            else:
                return False
        return len(stack) == 0

15. 三数之和

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        if not nums oor len(nums) < 3:
            return []
        nums.sort()
        for i in range(0,len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            target = -nums[i]
            left, right = i + 1, len(nums) - 1
            while left < right:
                if nums[left] + nums[right] == target:
                    result.append([nums[i], nums[left], nums[right]])
                    left += 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    right -= 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif nums[left] + nums[right] < target:
                    left += 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                else:
                    right -= 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
        return result

class Solution(object):
    def dfs(self, grid, i, j):
        if 0<= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j]:
            grid[i][j] = 0
            return 1 + self.dfs(grid, i-1, j) + self.dfs(grid, i+1, j) + self.dfs(grid, i, j-1) + self.dfs(grid, i, j+1)
        return 0

    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        result = 0 
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                result = max(result, self.dfs(grid, i, j))
        return result
   

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        start, end = 0, len(nums) - 1
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] == target:
                return mid
            if nums[start] <= nums[mid]:
                if nums[start] <= target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
            if nums[mid] <= nums[end]:
                if nums[mid] < target <= nums[end]:
                    start = mid + 1
                else:
                    end = mid - 1
        return -1

674. 最长连续递增序列

class Solution(object):
    def findLengthOfLCIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        if len(nums) < 2:
            return len(nums)
        result = 1
        i, j = 0, 0
        while j < len(nums):
            while j+1 < len(nums) and nums[j+1] > nums[j]:
                j += 1
            result = max(result, j - i + 1)
            j += 1
            i = j
        return result

from heapq import *
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        d = []
        for num in nums:
            if len(d) < k:
                heappush(d, num)
            elif num > d[0]:
                heappop(d)
                heappush(d, num)
        return heappop(d)

128. 最长连续序列

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = set(nums)
        result = 0
        while a:
            num = a.pop()
            start, end = num, num
            while start - 1 in a:
                start -= 1
                a.remove(start)
            while end + 1 in a:
                end += 1
                a.remove(end)
            result = max(result, end - start + 1)
        return result

60. 第k个排列

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        from itertools import permutations
        list_n = list(range(1, n+1))
        arr = list(permutations(list_n))
        return ''.join(map(str, list(arr[k-1])))

547. 朋友圈

class Solution(object):
    def dfs(self, visit, i, M):
        for j in range(len(M)):
            if M[i][j] and j not in visit:
                visit.add(j)
                self.dfs(visit, j, M)

    def findCircleNum(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        N = len(M)
        count = 0
        visit = set()

        for i in range(N):
            if i not in visit:
                count += 1
                visit.add(i)
                self.dfs(visit, i, M)
        return count

56. 合并区间

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        intervals.sort(key= lambda x:(x[0], x[1]))
        result = []
        for i in intervals:
            if not result oor result[-1][1] < i[0]:
                result.append(i)
            else:
                result[-1][1] = max(result[-1][1], i[1])
        return result
        

42. 接雨水

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left = [0] * len(height)
        leftMax = -1
        for i in range(0, len(height)):
            leftMax = max(leftMax, height[i])
            left[i] = leftMax
            
        right = [0] * len(height)
        rightMax = -1
        for i in range(len(height)-1, -1, -1):
            rightMax = max(rightMax, height[i])
            right[i] = rightMax
              
        result = 0
        for i in range(0,len(height)):
            result += min(right[i], left[i]) - height[i]
        return result

class Solution(object):
    def topKFrequent(self, nums, k):
        import heapq
        dic={}
        ans=[]
        re=[]
        n=0
        for x in nums:
            if x in dic:
                dic[x]+=1
            else:
                dic[x]=1
                n+=1
        for x in dic:
            heapq.heappush(ans,(dic[x],x))
        for i in range(n-k):
            heapq.heappop(ans)
        while ans:
            ix,x=heapq.heappop(ans)
            re.append(x)
        return re

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums oor len(nums) == 0:
            return 
        i, j = 0, 0
        while i < len(nums) and j < len(nums):
            if nums[i] == 0:
                i += 1
            else:
                nums[j] = nums[i]
                i += 1
                j += 1
        while j < len(nums):
            nums[j] = 0
            j += 1

21. 合并两个有序链表

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(0)
        p = l1
        q = l2
        node = dummy
        while p and q:
            if p.val < q.val:
                node.next = p
                p = p.next
                node = node.next
            else:
                node.next = q
                q = q.next
                node = node.next
        if p:
            node.next = p
        if q:
            node.next = q
        return dummy.next

206. 反转链表

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

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre = None
        cur = head
        while cur:
            nextNode = cur.next
            cur.next = pre
            pre = cur
            cur = nextNode
        return pre

2. 两数相加

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        len1, len2 = 0, 0
        p, q = l1, l2


        dummy = ListNode(0)
        node = dummy
        carry = 0 

        while p and q:
            value = (p.val + q.val + carry) % 10 
            carry = (p.val + q.val + carry) // 10
            node.next = ListNode(value)
            node = node.next
            p = p.next
            q = q.next
        
        while q:
            value = (q.val + carry) % 10
            carry = (q.val + carry) // 10
            node.next = ListNode(value)
            node = node.next
            q = q.next
        
        while p:
            value = (p.val + carry) % 10
            carry = (p.val + carry) // 10
            node.next = ListNode(value)
            node = node.next
            p = p.next

        if carry:
            node.next = ListNode(carry)
            
        return dummy.next

148. 排序链表

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

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        d = []
        while head:
            d.append(head.val)
            head = head.next
        d.sort()
        dummy = ListNode(0)
        node = dummy

        for i in range(0, len(d)):
            node.next = ListNode(d[i])
            node = node.next
        
        return dummy.next

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                fast = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return fast
        return 

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p, q = headA, headB
        len1, len2 = 0, 0
        while p:
            len1 += 1
            p = p.next
        while q:
            len2 += 1
            q = q.next
        
        p, q = headA, headB
        if len1 > len2:
            for i in range(len1 - len2):
                p = p.next
        if len2 > len1:
            for i in range(len2 - len1):
                q = q.next
        while p != q:
            p = p.next
            q = q.next
        return p 

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

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)

        if not l1 and not l2:
            return 
        if not l1:
            return l2
        if not l2:
            return l1

        p,q = l1,l2
        d = dummy
        while p and q:
            if p.val<q.val:
                d.next = p
                p = p.next
                d = d.next
            else:
                d.next=q
                q=q.next
                d=d.next
        if p:
            d.next = p
        if q:
            d.next= q
        return dummy.next

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists&nbs***bsp;len(lists) ==0:
            return
        if len(lists) == 1:
            return lists[0]
        node = self.mergeTwoLists(lists[0], lists[1])
        for i in range(2, len(lists)):
            node = self.mergeTwoLists(node, lists[i])
        return node

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == p oor root == q  oor not root:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        queue = [root]
        result = []
        layer = 0
        while queue:
            size = len(queue)
            curLayer = []
            layer += 1
            for k in range(size):
                node = queue.pop(0)
                curLayer.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if layer % 2 == 0:
                curLayer.reverse()
            result.append(curLayer)
        return result

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            length = len(stack)
            res = []
            for i in range(length):
                node = stack.pop(0)
                res.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
            result.append(res[-1])
        return result

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def helper(self, result, root, path, target):
        if not root:
            return
        target -= root.val 
        path.append(root.val)
        if target == 0 and not root.left and not root.right:
            result.append(path[:])
        self.helper(result, root.left, path, target)
        self.helper(result, root.right, path, target)
        path.pop() 

    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        result = []
        path = []
        self.helper(result, root, path, sum)
        return result

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

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head&nbs***bsp;k == 0:
            return head
        stack = []
        dummy = ListNode(0)
        dummy.next = head 
        p = dummy
        while True:
            count = k 
            tmp = head
            while count != 0 and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count -= 1
            if count != 0:
                p.next = head
                break
            while stack:
                p.next = stack.pop()
                p = p.next
            p.next = tmp 
            head = tmp
        return dummy.next
            

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isCompleteTree(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return False 
        queue = [root]
        occurNull = False
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.pop(0)
                if not node and not occurNull:
                    occurNull = True
                elif not node and occurNull:
                    continue
                elif node and occurNull:
                    return False
                # elif node and not occurNull :
                else:
                    queue.append(node.left)
                    queue.append(node.right)
        return True 

class Solution(object):
    def helper(self, p ,q):
        if not p and not q:
            return True
        if not p&nbs***bsp;not q:
            return False
        return p.val == q.val and self.helper(p.left, q.right) and self.helper(p.right, q.left)

    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.helper(root, root)

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

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow,fast = head,head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices oor len(prices) == 0:
            return 0
        
        min_val = float('inf')
        profit = 0
        for i in range(0, len(prices)):
            profit = max(profit, prices[i] - min_val)
            min_val = min(min_val, prices[i])

        return profit

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
               profit += (prices[i] - prices[i-1])
        return profit

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        m, n = len(matrix), len(matrix[0])
        d = [[0] * n for _ in range(m)]

        res = 0
        for i in range(m):
            if matrix[i][0] == "1":
                d[i][0] = 1
                res = 1
        
        for j in range(n):
            if matrix[0][j] == "1":
                d[0][j] = 1
                res = 1
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == "1":
                    if d[i-1][j] >= 1 and d[i][j-1] >= 1 and d[i-1][j-1] >= 1:
                        d[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1]) + 1
                    else:
                        d[i][j] = 1
                    res = max(res, d[i][j])
        return res * res

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 
        result= nums[0]
        cur = nums[0]
        for i in range(1,len(nums)):
            if cur < 0:
                cur = nums[i]
            else:
                cur += nums[i]
            result = max(result, cur)
        return result

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        m = len(triangle)

        for i in range(1, m):
            for j in range(i+1):
                if j== 0:
                    triangle[i][j] += triangle[i-1][j]
                elif j == i:
                    triangle[i][j] += triangle[i-1][j-1]
                elif 0 < j < i:
                    triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
        return min(triangle[-1])

class Solution(object):
    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        if not envelopes:
            return 0
        length = len(envelopes)
        d = [1] * length
        envelopes.sort(key = lambda x:(x[0], x[1]))
        result = 1
        for i in range(1, len(envelopes)):
            for j in range(0,i):
                if envelopes[i][0] > envelopes[j][0] and envelopes[i][1] > envelopes[j][1]:
                    d[i] = max(d[i], d[j] + 1)
            result = max(result, d[i])
        return result

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.minval = []
        self.stack = []


    def push(self, x: int) -> None:
        if not self.minval:
            self.stack.append(x)
            self.minval.append(x)
        else:
            currentmin=self.minval[-1]
            if currentmin<x:
                self.minval.append(currentmin)
                self.stack.append(x)
            else:
                self.minval.append(x)
                self.stack.append(x)


    def pop(self) -> None:
        if self.minval and self.stack:
            self.minval.pop()
            self.stack.pop()
        else:
            return 

    def top(self) -> int:
        if self.stack:
            return self.stack[-1]
        else:
            return 


    def getMin(self) -> int:
        if self.minval:
            return self.minval[-1]
        else:
            return 

class DLinkedNode(object):
    def __init__(self, key = 0, value = 0):
        self.key = key 
        self.value = value
        self.prev = None
        self.next = None

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.mapping = {}
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0


    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.mapping:
            return -1
        node = self.mapping[key]
        self.moveToHead(node)
        return node.value



    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key not in self.mapping:
            node = DLinkedNode(key, value)
            self.mapping[key] = node
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeTail()
                del self.mapping[removed.key]
                self.size -= 1
        else:
            node = self.mapping[key]
            node.value = value 
            self.moveToHead(node)


    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node 


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)