Hi this is Di. It has been a while since last time I post the blog. I hada a time indulging in the Elden Ring: Nightreign. But it did no help to my career and knowledge. So i guess im back on that.
452. Minimum number of arrows to burst balloons
There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.
Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.
Given the array points, return the minimum number of arrows that must be shot to burst all balloons.
This problem is quite similar to the interval problems before. But this time we should find the intersection of two overlapping interval. My first thought is to reuse the code before and fix max to min. Since it only require the number of the arrows, though there is a little inaccuracy in it, but it still work.
The optimized version of it is as follows:
def findMinArrowShots(self, points: list[list[int]]) -> int:
if not points:
return 0
# Sort balloons by their end coordinates
points.sort(key=lambda x: x[1])
# Initialize the first arrow at the end of the first balloon
arrows = 1
current_end = points[0][1]
for i in range(1, len(points)):
# If the current balloon starts after the last arrow's range
if points[i][0] > current_end:
arrows += 1
# Update the position of the arrow to the end of the current balloon
current_end = points[i][1]
return arrows
After sorting the intervals by end point in ascending order, if the first balloon got be bursted, the best position is at the end because if the second balloon is overlapped with it, one arrow can burst two. This method requires less storage memory.
71. Simplify Path
You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path.
The rules of a Unix-style file system are as follows:
A single period '.' represents the current directory.
A double period '..' represents the previous/parent directory.
Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'.
Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...' and '....' are valid directory or file names.
The simplified canonical path should follow these rules:
The path must start with a single slash '/'.
Directories within the path must be separated by exactly one slash '/'.
The path must not end with a slash '/', unless it is the root directory.
The path must not have any single or double periods ('.' and '..') used to denote current or parent directories.
Return the simplified canonical path.
To be honest, at first glance i have totally no idea what's going on to use a stack to solve it until i found the secret of split().
The funtion split("/") will return all the elements between "/". Even if ///, it will return ["","","",""],including head and tail.
So when we encounter "..", if the stack is not empty, we just pop it out because ".." represent the last directory.
At last we "/".join the stack. The join fucntion will not add leading and trailing "/".
def simplifyPath(self, path: str) -> str:
# Split the path by '/' and filter out empty strings and '.'
# Example: "/a/./b/../../c/" -> ["a", ".", "b", "..", "..", "c"]
parts = path.split("/")
stack = []
for part in parts:
if part == "..":
# Go up one level if the stack is not empty
if stack:
stack.pop()
elif part == "." or not part:
# Ignore current directory markers and consecutive slashes
continue
else:
# Valid directory name, push to stack
stack.append(part)
# Join the stack elements with '/' and ensure it starts with '/'
return "/" + "/".join(stack)
155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
At first glance, i feel like the min heap problem. Yet it's not the same. The good practice is mantain two stacks. One serves as the normal stack while the other records the min element.
We treat the first element as the first min and when new element comes which is less or equal than it, we also push it to the min list, and change the min to it.
class MinStack:
def __init__(self):
# Main stack to store all elements
self.data_stack = []
# Auxiliary stack to store minimum values
self.min_stack = []
def push(self, val: int) -> None:
self.data_stack.append(val)
# If min_stack is empty, or the new value is <= the current minimum
# We must use <= to handle duplicate minimum values correctly
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
# If the element being popped is the current minimum, pop it from min_stack too
if self.data_stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
# Standard stack top operation
return self.data_stack[-1]
def getMin(self) -> int:
# The top of min_stack is always the minimum of data_stack
return self.min_stack[-1]
141. Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Still hit me clueless at first. Then I get the idea of fast-slow pointer. The fast pointer go 2 steps while the slow pointer go 1 step. If a linkedlist has no cycle, the fast pointer shall be bound to reach the end first. In other hand, if a linkedlist has a cycle, the fast one will enter the cycle and finally reach the slow one. But before we jump the fast pointer, we should make sure the fast.next and fast themselves exist, or error will pop out.
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return False
slow = head
fast = head
# Move fast and slow pointers
while fast and fast.next:
slow = slow.next # Move 1 step
fast = fast.next.next # Move 2 steps
# If they meet, there is a cycle
if slow == fast:
return True
# If fast reaches the end, no cycle exists
return False
Top comments (0)