Week 4: Stacks and Queues
| Q |
|---|
| Q |
| Q |
| Q |
| Q |
| Q |
A stack of Q’s 😉
Stack: first in, last out (FILO)
| METHOD | DESCRIPTION |
|---|---|
empty() |
Returns true if the stack is empty. Else, returns false. |
peek() |
Returns the element on the top of the stack, but does not remove it. |
pop() |
Removes and returns the top element of the stack. Depending on the language and implementation, an error may be thrown if pop() is called when the stack is empty. |
push(element) |
Pushes element to the top of the stack. |
Example
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
// Create a Stack
Stack<Integer> stack = new Stack<>();
// Push elements onto the stack
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
// stack = [1, 2, 3, 4]
boolean empty = stack.empty();
// empty = false
// Peek at the top element without removing it
Integer topOfStack = stack.peek();
// topOfStack = 4
// stack = [1, 2, 3, 4]
// Pop element from the stack
Integer popped = stack.pop();
// popped = 4
// stack = [1, 2, 3]
popped = stack.pop();
// popped = 3
// stack = [1, 2]
}
}
Queue: first in, first out (FIFO)
| METHOD | DESCRIPTION |
|---|---|
peek() |
Returns the element at the front of the queue, but does not remove it. |
poll() |
Removes and returns the front element of the queue or null. |
offer(element) |
Pushes element to the front of the queue. |
Example
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
// Create a Queue using LinkedList
Queue<Integer> queue = new LinkedList<>();
// Enqueue elements
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
// queue = [1, 2, 3, 4]
// Peek at the front element without removing it
Integer frontOfQueue = queue.peek();
// frontOfQueue = 1
// queue = [1, 2, 3, 4]
// Dequeue elements
Integer dequeuedElement = queue.poll();
// dequeuedElement = 1
// queue = [2, 3, 4]
dequeuedElement = queue.poll();
// dequeuedElement = 2
// queue = [3, 4]
}
}
1) Make The String Great
Given a string s of lower and upper case English letters.
A “good” string is a string that doesn’t have two adjacent characters s[i] and s[i + 1] where:
0 <= i <= s.length - 2s[i]is a lower-case letter ands[i + 1]is the same letter but in upper-case or vice-versa.
To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.
Return the string after making it good. The answer is guaranteed to be unique under the given constraints.
Notice that an empty string is also good.
Example 1:
Input: s = "paAanda"
Output: "panda"
Explanation: In the first step, either you choose i = 1 or i = 2,
both will result "paAanda" to be reduced to "panda".
Example 2:
Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer.
For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""
Example 3:
Input: s = "s"
Output: "s"
Constraints:
1 <= s.length <= 100scontains only lower and upper case English letters.
2) Baseball Game
You are keeping the scores for a baseball game with strange rules. At the beginning of the game, you start with an empty record.
You are given a list of strings operations, where operations[i] is the ith operation you must apply to the record and is one of the following:
- An integer
x: Record a new score ofx. +: Record a new score that is the sum of the previous two scores.D: Record a new score that is the double of the previous score.C: Invalidate the previous score, removing it from the record.
Return the sum of all the scores on the record after applying all the operations.
Example 1:
Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.
Example 2:
Input: ops = ["5","-2","4","C","D","9","+","+"]
Output: 27
Explanation:
"5" - Add 5 to the record, record is now [5].
"-2" - Add -2 to the record, record is now [5, -2].
"4" - Add 4 to the record, record is now [5, -2, 4].
"C" - Invalidate and remove the previous score, record is now [5, -2].
"D" - Add 2 * -2 = -4 to the record, record is now [5, -2, -4].
"9" - Add 9 to the record, record is now [5, -2, -4, 9].
"+" - Add -4 + 9 = 5 to the record, record is now [5, -2, -4, 9, 5].
"+" - Add 9 + 5 = 14 to the record, record is now [5, -2, -4, 9, 5, 14].
The total sum is 5 + -2 + -4 + 9 + 5 + 14 = 27.
Constraints:
1 <= operations.length <= 1000operations[i]is"C","D","+", or a string representing an integer in the range[-3 * 10^4, 3 * 10^4].- For operation
"+", there will always be at least two previous scores on the record. - For operations
"C"and"D", there will always be at least one previous score on the record.
3) Dota2 Senate
In the world of Dota2, there are two parties: the Radiant and the Dire.
The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:
Ban one senator’s right: A senator can make another senator lose all his rights in this and all the following rounds.
Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.
Given a string senate representing each senator’s party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.
The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.
Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "Radiant" or "Dire".
Example 1:
Input: senate = "RD"
Output: "Radiant"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.
Example 2:
Input: senate = "DDRRR"
Output: "Dire"
Explanation:
In the first round, the first and second senator are both from dire, using their ban right the first two senators from Radient are banned.
The last senator (Radient) will ban one of the Dire senator.
The senate string can be represented as "DR" at the start of the second round.
The Dire senator will ban the Radient senator and declare victory.
Constraints:
n == senate.length1 <= n <= 10^4senate[i]is either'R'or'D'.
4) Astroid Collision
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
Example 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
Example 3:
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Constraints:
2 <= asteroids.length <= 10^4-1000 <= asteroids[i] <= 1000asteroids[i] != 0