# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: # Time: O(n) Space: O(1) defreverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: prev, curr = None, head while curr: next = curr.next# save next node before we break the pointer curr.next = prev # point to previous node prev = curr # shift previous pointer curr = next# shift current pointer
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: defreverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: # check if reverse is needed curr = head for _ inrange(k): ifnot curr: return head # no need to reverse, thus return the original head curr = curr.next
# Reverse the sub-list with k nodes # e.g. # None 1 -> 2 -> 3 -> 4 -> 5 -> 6, k = 3 # ^ ^ # prev head(curr) # # After reverse the first 3 nodes, # 3 -> 2 -> 1 -> 4 -> 5 -> 6 # ^ ^ ^ # prev head curr prev, curr = None, head for _ inrange(k): next = curr.next# save the next before we break the pointer curr.next = prev # point to previous node(reverse) prev = curr # shift previous pointer curr = next# shift current pointer
# after reverse, the curr pointer points to the "head" of next k nodes, # and the previous pointer points to the new "head" of the reversed k nodes. head.next = self.reverseKGroup(curr, k)
# the previous pointer points to the head of reversed list return prev
[Leetcoe 146] LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
classSolution: defcalculate(self, s: str) -> int: """ Refer to https://leetcode.com/problems/basic-calculator/solutions/546092/simple-python-solution-using-stack-with-explanation-inline/?envType=study-plan-v2&envId=top-interview-150 1. Take 3 containers: num -> to store current num value only sign -> to store sign value, initially +1 res -> to store sum When ( comes these containers used for calculate sum of intergers within () brackets. -------------------- 2. When c is + or - Move num to res, because we need to empty num for next integer value. set num = 0 sign = update with c -------------------- 3. When c is '(' Here, we need num, res, sign to calculate sum of integers within () So, move num and sign to stack => [num, sign] Now reset - res = 0, num = 0, sign = 1 (default) -------------------- 4. When c is ')' -> 2-(3+4), Here res=3, num=4, sign=1 stack [2, -] res +=sign*num -> calculate sum for num first, then pop items from stack, res=7 res *=stack.pop() - > Pop sign(+ or -) to multiply with res, res = 7*(-1) res +=stack.pop() - > Pop integer and add with prev. sum, res = -7 + 2 - 5 -------------------- Simple Example: 2 - 3 Initially res will have 2,i.e. res = 2 then store '-' in sign. it will be used when 3 comes. ie. sign = -1 Now 3 comes => res = res + num*sign Return statement: res+num*sign => res = 2 + 3(-1) = 2 - 3 = -1 """ num = 0 sign = 1 res = 0 stack =  for i inrange(len(s)): # iterate characters c = s[i] if c.isdigit(): # parse the consecutive digits. e.g. 23 -> 2 * 10 + 3 num = num*10 + int(c) elif c in'-+': # check for - and + # calculate the temporary result before '+' or '-' res += num*sign # save the new sign sign = -1if c == '-'else1 # reset num to 0 for parsing the next operand num = 0 elif c == '(': # we need res and sign to save the temporary result within '()'. Reset sign to default 1. stack.append(res) stack.append(sign) res = 0 sign = 1 elif c == ')': # calculate the result within '()' # e.g. 2 -(3 + 4) -> res = 3, num = 4, sign = 1, stack = [2, -] res +=sign*num # res = 3 * 1 + 4 = 7 res *=stack.pop() # res = 7 * (-1) = -7 res +=stack.pop() # res = -7 + 2 = -5 num = 0# reset num to 0 return res + num*sign