<jupyter_start><jupyter_text>MISC  Pre-run<jupyter_code>from typing import List
from helpers.misc import *<jupyter_output><empty_output><jupyter_text>Contents  * Stack: [20](https://leetcode.com/problems/valid-parentheses/), [225](https://leetcode.com/problems/implement-stack-using-queues/), [735](https://leetcode.com/problems/asteroid-collision/).* Heap: [1046](https://leetcode.com/problems/last-stone-weight/).<jupyter_code># max heap
class MaxHeap:
    def __init__(self, l: List[int]):
        self.heap = []
        for i in l:
            self.push(i)
    
    def __len__(self):
        return len(self.heap)
    
    def push(self, x: int):
        '''Push an integer into a heap.'''
        self.heap.append(x)
        i = len(self.heap)-1
        while i > 0:
            p = (i+1) // 2 - 1
            if self.heap[i] <= self.heap[p]:
                break
            else:
                self.heap[i], self.heap[p] = self.heap[p], self.heap[i]
                i = p
    
    def pop(self) -> int:
        '''Pop an integer out of a heap.'''
        self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
        l = len(self.heap)-1
        i = 0
        while 2*i+1 < l:
            if 2*i+2 >= l:
                if self.heap[i] < self.heap[2*i+1]:
                    self.heap[i], self.heap[2*i+1] = self.heap[2*i+1], self.heap[i]
                break
            if self.heap[2*i+1] > self.heap[2*i+2]:
                if self.heap[i] < self.heap[2*i+1]:
                    self.heap[i], self.heap[2*i+1] = self.heap[2*i+1], self.heap[i]
                    i = 2*i+1
                else:
                    break
            else:
                if self.heap[i] < self.heap[2*i+2]:
                    self.heap[i], self.heap[2*i+2] = self.heap[2*i+2], self.heap[i]
                    i = 2*i+2
                else:
                    break
        return self.heap.pop()
h = MaxHeap([2,7,4,1,8,1])
print(f'heap:{h.heap}, len:{len(h)}')
for _ in range(len(h.heap)):
    print(f'pop:{h.pop()}, heap:{h.heap}')<jupyter_output><empty_output><jupyter_text>20 [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) - E   Stack * Runtime: 24 ms, faster than 90.31% of Python3 online submissions for Valid Parentheses.* Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Valid Parentheses.<jupyter_code>class Solution:
    def isValid(self, s: str) -> bool:
        '''Check whether a given string of parentheses is valid by stack.'''
        d = {')':'(', '}':'{', ']':'['}
        stack = ['#']
        for p in s:
            # p is a back parenthese
            if p in d:
                # parentheses not paired
                if stack[-1] != d[p]:
                    return False
                # parentheses paired
                else:
                    stack.pop()
            # p is a front parenthese
            else:
                stack.append(p)
        return len(stack) == 1
# test
eq(Solution().isValid(''), True)
eq(Solution().isValid('()'), True)
eq(Solution().isValid('()[]{}'), True)
eq(Solution().isValid('(]'), False)
eq(Solution().isValid('([)]'), False)
eq(Solution().isValid('([])'), True)<jupyter_output><empty_output><jupyter_text>225 [Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/) - E * [Solution](https://leetcode.com/articles/implement-stack-using-queues/)  Two Queues Better Push * Runtime: 28 ms, faster than 56.46% of Python3 online submissions for Implement Stack using Queues.* Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Implement Stack using Queues.<jupyter_code>from collections import deque

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.q1.append(x)
        self.topper = x

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        for i in range(len(self.q1)-1):
            self.topper = self.q1.popleft()
            self.q2.append(self.topper)
        self.q1, self.q2 = self.q2, self.q1
        return self.q2.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.topper

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not bool(self.q1)


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()<jupyter_output><empty_output><jupyter_text>Two Queues Better Pop  * Make the main queue upside down.* Runtime: 24 ms, faster than 83.79% of Python3 online submissions for Implement Stack using Queues.* Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Implement Stack using Queues.<jupyter_code>from collections import deque

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.q2.append(x)
        for i in range(len(self.q1)):
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1
        
    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.q1.popleft() 

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.q1[0] 

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not bool(self.q1)


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()<jupyter_output><empty_output><jupyter_text>One Queue Better Pop * Runtime: 28 ms, faster than 56.46% of Python3 online submissions for Implement Stack using Queues.* Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Implement Stack using Queues.<jupyter_code>from collections import deque

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q = deque()

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.q.append(x)
        for _ in range(len(self.q)-1):
            self.q.append(self.q.popleft())
        
    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.q.popleft() 

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.q[0] 

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not bool(self.q)


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()<jupyter_output><empty_output><jupyter_text>735 [Asteroid Collision](https://leetcode.com/problems/asteroid-collision/) - M   Bad Stack  * Runtime: 108 ms, faster than 45.39% of Python3 online submissions for Implement Stack using Queues.* Memory Usage: 13.9 MB, less than 54.31% of Python3 online submissions for Implement Stack using Queues.<jupyter_code>class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        '''Find the result of the asteroid collision with a stack.'''
        ans = []
        
        def add_new_asteroid(asteroid: int):
            '''Add a new asteroid into a list of asteroids.'''
            ans.append(asteroid)
            while len(ans) > 1 and ans[-1] < 0:
                # same sign
                if ans[-1] * ans[-2] > 0:
                    break
                # different sign
                else:
                    if abs(ans[-1]) < abs(ans[-2]):
                        ans.pop()
                        break
                    elif abs(ans[-1]) == abs(ans[-2]):
                        ans.pop()
                        ans.pop()
                        break
                    else:
                        del(ans[-2])
        for a in asteroids:
            add_new_asteroid(a)
        return ans
eq(Solution().asteroidCollision([5,10,-5]), [5,10])
eq(Solution().asteroidCollision([8,-8]), [])
eq(Solution().asteroidCollision([10,2,-5]), [10])
eq(Solution().asteroidCollision([-2,-1,1,2]), [-2,-1,1,2])
eq(Solution().asteroidCollision([1,2,-3]), [-3])<jupyter_output><empty_output><jupyter_text>Better Stack  * Runtime: 100 ms, faster than 78.53% of Python3 online submissions for Asteroid Collision.* Memory Usage: 13.9 MB, less than 25.00% of Python3 online submissions for Asteroid Collision.<jupyter_code>class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        '''Find the result of the asteroid collision with a stack.'''
        ans = []
        for a in asteroids:
            while ans and a < 0 < ans[-1]:
                if -a > ans[-1]:
                    ans.pop()
                    continue
                elif -a == ans[-1]:
                    ans.pop()
                break
            else:
                ans.append(a)
        return ans
eq(Solution().asteroidCollision([5,10,-5]), [5,10])
eq(Solution().asteroidCollision([8,-8]), [])
eq(Solution().asteroidCollision([10,2,-5]), [10])
eq(Solution().asteroidCollision([-2,-1,1,2]), [-2,-1,1,2])
eq(Solution().asteroidCollision([1,2,-3]), [-3])<jupyter_output><empty_output><jupyter_text>1046 [Last Stone Weight](https://leetcode.com/problems/last-stone-weight/) - E  Heap * Runtime: 36 ms, faster than 16.81% of Python3 online submissions for Last Stone Weight.* Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Last Stone Weight.<jupyter_code># max heap
class MaxHeap:
    def __init__(self, l: List[int]):
        self.heap = []
        for i in l:
            self.push(i)
    
    def __len__(self):
        return len(self.heap)
    
    def push(self, x: int):
        '''Push an integer into a heap.'''
        self.heap.append(x)
        i = len(self.heap)-1
        while i > 0:
            p = (i+1) // 2 - 1
            if self.heap[i] <= self.heap[p]:
                break
            else:
                self.heap[i], self.heap[p] = self.heap[p], self.heap[i]
                i = p
    
    def pop(self) -> int:
        '''Pop an integer out of a heap.'''
        self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
        l = len(self.heap)-1
        i = 0
        while 2*i+1 < l:
            if 2*i+2 >= l:
                if self.heap[i] < self.heap[2*i+1]:
                    self.heap[i], self.heap[2*i+1] = self.heap[2*i+1], self.heap[i]
                break
            if self.heap[2*i+1] > self.heap[2*i+2]:
                if self.heap[i] < self.heap[2*i+1]:
                    self.heap[i], self.heap[2*i+1] = self.heap[2*i+1], self.heap[i]
                    i = 2*i+1
                else:
                    break
            else:
                if self.heap[i] < self.heap[2*i+2]:
                    self.heap[i], self.heap[2*i+2] = self.heap[2*i+2], self.heap[i]
                    i = 2*i+2
                else:
                    break
        return self.heap.pop()

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        '''Calculate the last stone weight by max heap.'''
        h = MaxHeap(stones)
        while len(h) > 1:
            x, y = h.pop(), h.pop()
            if x != y:
                h.push(abs(x-y))
            
        if len(h) == 0:
            return 0
        else:
            return h.pop()
eq(Solution().lastStoneWeight([2,7,4,1,8,1]), 1)
eq(Solution().lastStoneWeight([2,2]), 0)<jupyter_output><empty_output><jupyter_text>155 [Min Stack](https://leetcode.com/problems/min-stack/) - E  Design * Consider storing the local min at each node.* Runtime: 60 ms, faster than 76.82% of Python3 online submissions for Min Stack.* Memory Usage: 18.1 MB, less than 5.36% of Python3 online submissions for Min Stack.<jupyter_code>class MinStack:

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

    def push(self, x: int) -> None:
        if not self.s:
            self.s.append((x, x))
        else:
            self.s.append((x, min(x, self.s[-1][1])))

    def pop(self) -> None:
        self.s.pop()

    def top(self) -> int:
        return self.s[-1][0]

    def getMin(self) -> int:
        return self.s[-1][1]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14378679888441276, 'fraction_numerical': 0.028586922838549737, 'mean_word_length': 1.9166290103931316, 'pattern_counts': {'":': 0, '<': 55, '<?xml version=': 0, '>': 73, 'https://': 10, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '567481', 'license': 'MIT', 'n_tokens_mistral': 4397, 'n_tokens_neox': 4100, 'n_words': 1070, 'path': 'ipynb/misc.ipynb', 'repo_name': 'novate/brosseurs', 'size': '12908'}