반응형
2024.05.09
1. Arrays DS
public static List<Integer> reverseArray(List<Integer> a) {
List<Integer> ret = new ArrayList<>(a.size());
for (int i = 0; i < a.size(); i++) {
ret.add(i, a.get(a.size() - 1 - i));
}
return ret;
}
2. 2D Arrays - DS
public static int hourglassSum(List<List<Integer>> arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.size() - 2; i++) {
int sum = 0;
for (int j = 0; j < arr.get(i).size() - 2; j++) {
sum = arr.get(i).get(j) + arr.get(i).get(j+1) + arr.get(i).get(j+2) + arr.get(i+1).get(j+1) + arr.get(i+2).get(j) + arr.get(i+2).get(j+1) + arr.get(i+2).get(j+2);
max = Math.max(max, sum);
}
}
return max;
}
2024.05.11
이 날은 Stack 위주로 풀었다.
1. Hackerrank Maximum Element
class Result {
/*
* Complete the 'getMax' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts STRING_ARRAY operations as parameter.
*/
public static List<Integer> getMax(List<String> operations) {
List<Integer> maxes = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
Stack<Integer> maxStack = new Stack<>();
for (String operation: operations) {
StringTokenizer st = new StringTokenizer(operation);
int number = Integer.parseInt(st.nextToken());
if (number == 1) {
int nextNumber = Integer.parseInt(st.nextToken());
if (stack.isEmpty()) {
maxStack.push(nextNumber);
}
stack.push(nextNumber);
if (!maxStack.isEmpty() && nextNumber >= maxStack.peek()) {
maxStack.push(nextNumber);
}
} else if (number == 2) {
int element = stack.pop();
if (element == maxStack.peek()) {
maxStack.pop();
}
} else {
maxes.add(maxStack.peek());
}
}
return maxes;
}
public static int getMaxElementInTheStack(Stack<Integer> stack) {
Iterator findMax = stack.iterator();
int max = 0;
while (findMax.hasNext()) {
max = Math.max(max, (int)findMax.next());
}
return max;
}
}
2. Hackerrank Balance Brackets
public static String isBalanced(String s) {
Stack<Character> stack = new Stack<>();
final String no = "NO";
final String yes = "YES";
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i); //c is the current character
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return no;
}
char popped = stack.pop();
if (c == ')') {
if (popped != '(') return no;
}
if (c == '}') {
if (popped != '{') return no;
}
if (c == ']') {
if (popped != '[') return no;
}
}
}
if (stack.isEmpty()) {
return yes;
}
return no;
}
3. Hackerrank Simple Text Editor
import java.io.*;
import java.util.*;
public class Solution {
private static Stack<Character> stack;
private static Stack<String> operations;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int q = Integer.parseInt(br.readLine());
stack = new Stack<>();
operations = new Stack<>();
for (int i = 0; i < q; i++) {
String current = br.readLine();
StringTokenizer st = new StringTokenizer(current);
int instruction = Integer.parseInt(st.nextToken());
if (instruction == 1) {
String w = st.nextToken();
append(w, false);
}
if (instruction == 2) {
int k = Integer.parseInt(st.nextToken());
delete(k, false);
}
if (instruction == 3) {
int k = Integer.parseInt(st.nextToken());
print(k);
}
if (instruction == 4) {
String previous = operations.pop();
undo(previous);
}
}
}
public static void append(String w, boolean undo) {
String toPush = "2 " + w.length();
if (!undo) {
operations.push(toPush);
}
for (int i = 0; i < w.length(); i++) {
char c = w.charAt(i);
stack.push(c);
}
}
public static void delete(int k, boolean undo) {
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= k; i++) {
if (!stack.isEmpty()) {
char c = stack.pop();
sb.append(c);
}
}
String toPush = "1 " + sb.reverse().toString();
if (!undo) {
operations.push(toPush);
}
}
public static void print(int k) {
Iterator iterator = stack.iterator();
for (int i = 1; i < k; i++) {
iterator.next();
}
System.out.println(iterator.next());
}
public static void undo(String previous) {
StringTokenizer st = new StringTokenizer(previous);
int operation = Integer.parseInt(st.nextToken());
if (operation == 1) {
String w = st.nextToken();
append(w, true);
} else {
int k = Integer.parseInt(st.nextToken());
delete(k, true);
}
}
}
4. Leetcode Min Stack
class MinStack {
private Stack<Integer> mainStack;
private Stack<Integer> minStack;
public MinStack() {
mainStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
if (mainStack.isEmpty()) {
minStack.push(val);
} else {
if (val <= minStack.peek()) {
minStack.push(val);
}
}
mainStack.push(val);
}
public void pop() {
int popped = mainStack.pop();
if (popped == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return mainStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
2024.05.12
1. Dynamic Array
public static List<Integer> dynamicArray(int n, List<List<Integer>> queries) {
List<List<Integer>> arr = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
arr.add(new ArrayList<>());
}
List<Integer> answers = new ArrayList<>();
int lastAnswer = 0;
for (List<Integer> list : queries) {
int query = list.get(0);
int x = list.get(1);
int y = list.get(2);
int idx = findIndex(x, lastAnswer, n);
if (query == 1) {
arr.get(idx).add(y);
} else {
lastAnswer = arr.get(idx).get(y % arr.get(idx).size());
answers.add(lastAnswer);
}
}
return answers;
}
public static int findIndex(int x, int lastAnswer, int n) {
int idx = ((x ^ lastAnswer) % n);
return idx;
}
2. Left Rotation
public static List<Integer> rotateLeft(int d, List<Integer> arr) {
int size = arr.size();
List<Integer> ret = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
int index = (((i + d) % size) + size) % size;
ret.add(i, arr.get(index));
}
return ret;
}
2024.05.13
1. Print the Elements of a Linked List
static void printLinkedList(SinglyLinkedListNode head) {
if (head == null) {
return;
}
while (head != null) {
System.out.println(head.data);
head = head.next;
}
}
2. Sparse Arrays
public static List<Integer> matchingStrings(List<String> stringList, List<String> queries) {
List<Integer> results = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
for (String input: stringList) {
map.put(input, map.getOrDefault(input, 0) + 1);
}
for (String query : queries) {
if (!map.containsKey(query)) {
results.add(0);
} else {
results.add(map.get(query));
}
}
return results;
}
3. Insert a Node at the Tail of a Linked List
static SinglyLinkedListNode insertNodeAtTail(SinglyLinkedListNode head, int data) {
SinglyLinkedListNode tail = new SinglyLinkedListNode(data);
if (head == null) {
return tail;
}
SinglyLinkedListNode next = head;
while (next.next != null) {
next = next.next;
}
next.next = tail;
return head;
}
4. Insert a node at the head of a linked list
static SinglyLinkedListNode insertNodeAtHead(SinglyLinkedListNode llist, int data) {
SinglyLinkedListNode newHead = new SinglyLinkedListNode(data);
if (llist == null) return newHead;
newHead.next = llist;
return newHead;
}
5. Queue using Two Stacks
public class Solution {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
MyQueue<Integer> queue = new MyQueue<>();
int q = Integer.parseInt(br.readLine());
for (int i = 0; i < q; i++) {
String s = br.readLine();
StringTokenizer st = new StringTokenizer(s);
int type = Integer.parseInt(st.nextToken());
if (type == 1) {
int x = Integer.parseInt(st.nextToken());
queue.enqueue(x);
}
if (type == 2) {
queue.dequeue();
}
if (type == 3) {
System.out.println(queue.peek());
}
}
}
}
class MyQueue<T> {
Stack<T> leftStack = new Stack<T>();
Stack<T> rightStack = new Stack<T>();
void enqueue(T item) {
leftStack.push(item);
}
T dequeue() {
transferIfNeeded();
return rightStack.pop();
}
T peek() {
transferIfNeeded();
return rightStack.peek();
}
void transferIfNeeded() {
if (rightStack.isEmpty()) {
while (!leftStack.isEmpty()) {
rightStack.push(leftStack.pop());
}
}
}
}
반응형
댓글