Leetcode Queue & Stack

[zxw018018]

Leetcode Queue and Stack

Queue

1. Initialize a queue.

Queue<Integer> q = new LinkedList();

2. Get the first element - return null if queue is empty.

System.out.println("The first element is: " + q.peek());

3. Push new element.

q.offer(5);

4. Pop an element.

q.poll();

5. Get the size of the queue.

System.out.println("The size is: " + q.size());

Problems

200. Number of Islands

Description

• Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Analysis

• Use DFS.

286. Walls and Gates

Description

• You are given a m x n 2D grid initialized with these three possible values.
  -1 - A wall or an obstacle.
  -0 - A gate.
  -INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
• Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Analysis

• Use queue with BFS to calculate the distance from gate.

346. Moving Average from Data Stream

Description

• Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Analysis

• None

542. 01 Matrix

Description

• Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
• The distance between two adjacent cells is 1.

Analysis

• Use BFS.

622. Design Circular Queue

Description

• Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".

Analysis

• None

752. Open the Lock

Description

• You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.
• The lock initially starts at '0000', a string representing the state of the 4 wheels.
• You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
• Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Analysis

• Use queue with BFS.
• Use two hashsets to store the deadlock and covered lock.

Stack

1. Initialize a stack.

Stack<Integer> s = new Stack<>();

2. Push new element.

s.push(5);

3. Check if stack is empty.

s.empty()

4. Pop an element.

s.pop()

5. Get the top element.

s.peek()

6. Get the size of the stack.

s.size()

Problems

20. Valid Parentheses

Description

• Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
• An input string is valid if:
• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

Analysis

• Use stack.

32. Longest Valid Parentheses

Description

• Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Analysis

• Use stack.

84. Largest Rectangle in Histogram

Description

• Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Analysis

• Use increasing stack.

133. Clone Graph

Description

• Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.

Analysis

• Use hashmap to record node.label, use recursion to clone the graph.

150. Evaluate Reverse Polish Notation

Description

• Evaluate the value of an arithmetic expression in Reverse Polish Notation.
• Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Analysis

• Use stack.

155. Min Stack

Description

• Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

1. push(x) -- Push element x onto stack.
2. pop() -- Removes the element on top of the stack.
3. top() -- Get the top element.
4. getMin() -- Retrieve the minimum element in the stack.

Analysis

• Use one more stack minStack.

225. Implement Stack using Queues

Description

• Implement the following operations of a stack using queues.
  push(x) -- Push element x onto stack.
  pop() -- Removes the element on top of the stack.
  top() -- Get the top element.
  empty() -- Return whether the stack is empty.

Analysis

• Use two queues.

232. Implement Queue using Stacks

Description

• Implement the following operations of a queue using stacks.
  push(x) -- Push element x to the back of queue.
  pop() -- Removes the element from in front of queue.
  peek() -- Get the front element.
  empty() -- Return whether the queue is empty.

Analysis

• Use two stacks.

394. Decode String

Description

• Given an encoded string, return it's decoded string.
• The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
• You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
• Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Analysis

• Use two stacks.

494. Target Sum

Description

• You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
• Find out how many ways to assign symbols to make sum of integers equal to target S.

Analysis

• Use recursion.

733. Flood Fill

Description

• An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).
• Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.

Analysis

• Use DFS.

739. Daily Temperatures

Description

• Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
• For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Analysis

• Use decreasing stack.

841. Keys and Rooms

Description

• There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.
• Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Analysis

• Use DFS.