Neetcode problem 및 유형별 문제들 정리

Neetcode Problem

Array & Hashing

1) Contains Duplicate

sort랑 hash 다 하기

2) Valid Anagram

sort랑 hash 다 하기 (hash의 경우, 26개만 가지고 할 수도 있는거 인지)

3) Two Sum

 - 2 for loop  ||  struct 한 상태로 sort  || hash 로 target - num 으로 하는 방법 이

4) Group Anagrams

 - hash using vector<string>

+ ans 에다가 바로 넣어주려면 아래 처럼 만들면 됨

+ alphabet 개수 count하는거를 string으로 넣는 방법도 있음!

5) Top K frequent Elements

 - priority_queue 사용 익히기

const를 매게변수에서도(operator<에서) 사용해야하는데 해당 이유와 const가 뒤에붙이면 const member function이라고 불리는데 해당 이유도 좀 알아두기.

6) Product of Array Except Self

 - prefix postfix에 대해서 생각

+) O(1) space로 하려면 int 하나 필요한거 생

7) Valid  Sudoku

hash로 풀어버리기

8) Encode and Decode Strings

걍 string에서 \0 하면 멈춘다는 개념 보여주는 문제정도?;; 안풀어도

★★9) Longest Consecutive Sequence

- unordered_map [hash]를 잘 쓰는지 확인하는 문

 

Sliding window

좋은 표현 : 

Binary Searching

 

 

 

Tree

1) 226. Invert Binary Tree

맞는 풀이와 틀린풀이 같이 보기

2) 104. Maximum Depth of Binary Tree

queue로도 할줄 알기 + tail recursion이 뭔지 이해하고있기

3) Diameter of Binary Tree

left랑 right랑 따로 구해서 더하면 된다는 개념 인지

4) 110. Balanced Binary Tree

top-down recursion이 시간 복잡도가 오래걸리니까 bottom-up recursion으로 할줄 알아야함

5) 100. Same Tree

이런식으로 false조건 넣고 마지막까지 둘다 nullptr면 true다 이렇게 접근하는거 중요

queue이용해서면 2개 다 queue있어야

6) 572. Subtree of Another Tree

7) 235. Lowest Common Ancestor of a Binary Search Tree

iterative하게도 풀어보기

 

8) 102. Binary Tree Level Order Traversal

vector 생성 개념 알수있는 좋은 문

 // vector<int> tmp;
 이렇게 추가해서 ans.push_back(tmp); 하는 방법이 있고
 
 // ans.push_back(vector<int>()); 
 이렇게 ans vector에 바로 넣는 방법이 있다.

9) Binary Tree Right Side View

1) BFS를 하는데 뭐 매번 null을 넣는 풀이가 있고, 

2) BFS를 그냥 level order로 하는 풀이가 있고, (내가 푼거)

3) dfs를 오른쪽 우선으로 하는 풀이가 있다.

10) Count Good Nodes In Binary Tree

1) dfs 함수풀이 2) dfs stack 풀이 3) queue풀

11) Validate Binary Search Tree

최소, 최대를 못하면, 노드포인터를 넘길 생각을 하기

틀린 풀이 -> [-21억, -21억] 이렇게 나오면 못

맞는 풀

12) Kth Smallest Element In a Bst

 // 알게 된 것 2가지

 // 1) inorder traversal of BST which is an array sorted in the ascending order.

 // 2) stack으로 inorder 구현하려면 좌측을 다 stack에 넣고 우측 쑉 이동하면됨

13) Construct Binary Tree From Preorder And Inorder Traversal

=> 이건 좀 복잡한데,, 결국 inorder 이 나타내는건 왼쪽 subtree와 오른쪽 subtree를 나타내고, preorder는 root를 나타낸다고 이해하면 됨.

 

 

Linked list

1) 206. Reverse Linked List

기본적으로 이정도는 바로바로하기. 마지막에 head말고, prev return하는거 실수하지말고

point : (v) 가리키다.

traverse : (v) 순회하다.

대부분의 문제에서는 previous node가 주어지지 않으므로, 저 문장은 외워놓으면 바로 쓸수있음.

"Since a node does not have reference to its previous node, we must store its previous element beforehand."

+) recursive하게 푸려니까 은근 어렵던데 그것도 익혀놓기

2) 21. Merge Two Sorted Lists

오류 나게 설정함

1) head = move 해야하는데 head->next = move함. 이렇게 next 쓰려면 head도 new 사용해서 생성자가 필요

2) move->next를 사용할거기때문에 생성자가 필요

=> 반영한 부분

+) recursive하게도 풀어보기

+) c로 reference로 하나하나 연결하는 것도 풀어보기

 

3) 143. Reorder List

reverse도 있고, slow & fast로 중간 찾는 것도 있고, 좋은 문제임

오류 나게 한거 있는데 보니까 뺑뺑 돌게 만들면 heap use after free 이런거 나옴 ( when found circle in the list !!)

4) 19. Remove Nth Node From End of List

pointer 2개 사용해서 푸는 방법 익히기

표현들 익히기

1) n+1 step 앞에 있다. advances the list by n+1 steps from the beginning

2) n개의 node만큼 떨어져있다. both pointers are exactly separated by n nodes apart.

3) relink 다시 연결해주다.

5) 138. Copy List with Random Pointer

되게 간단한데 random pointer를 처리해줘야하는 문제가 있어서 (아직 생성되지 않은 것을 가리키게끔 해줘야하는 문제)

1) hash를 사용하거나 2) 기존 linked list를 각 노드 옆에 붙여서 늘려서 사용하거나

해서 문제를 풀어야하는데 두 풀이 다 신박하므로 익혀둘 

6) 2. Add Two Numbers

우선 아래의 단순 실수 확인하고, c++에서 매번 create하는거 익숙하게 하기

+) https://leetcode.com/problems/add-two-numbers/solutions/2055609/solution-in-c/ 참고해가며 c로도 할 줄 알

9) 141. Linked List Cycle

내가 만드는 hash로 풀 줄도 알기! + 그 싸이클 이론도 설명할 수 있게 공부하

10) 287. Find the Duplicate Number

풀이가 무슨 7개나 되는데,, 대충

1) 정렬 2) hash 3) [1-n] 이니까 index가 동시에 되니까, 순환 이용 4) binary search 5) bitmask (다음에,,) 6) floyd's tortoise and hare (circle 찾는 문제로 바꿔서 보기)

순환이용할때 설명

 

Two pointers

(1) Valid Palindrome

reverse도 된다는거 생각해놓기

(2) Two Sum II Input Array Is Sorted

two pointers 사용하는 어디서나 쓸수 있는 말이라서 암기해서 그대로 써도 될듯

+ 추가로 만약 long long 써야된다면 아래와 같이 casting하거나 if 로 막아놓으면 된다

(3) 3Sum

two sum을 사용하는 풀이와 hash map 쓰는 풀이가 있다.

twosum을 사용할때 중복되는 걸 없애게 하려고 받은 idx보다 1 큰거부터 시작하게 하고 + 같은 값은 쭉 증가시켜서 없애주는 전략을 사용했다! 그러면 값은 하나는 무조건 바뀌니까!

 

sort 안 하고도 풀 수 있는거 도전해보

(4) 11. Container With Most Water

height 비교해서 더 작은거 포인터 값 변경해주는 생각 필요

(5) 42. Trapping Rain Water

다시 해보기

+) 86. Partition List

 

Heap

(1) 703. Kth Largest Element in a Stream

Heap에 대해서 설명하기 좋은 거 있음

cmp 이용해서 priority_queue 순서 바꾸는거 이해하기

+) 나만의 heap 만들줄도 알기

나는 2번이나 maxHeap, minHeap 둘 다 구현해서 풀었는데, x번재로 largest는 maxHeap에서 x의 크기만큼 채워서 보관하면 된다는 것을 이해 

 

(2) 1046. Last Stone Weight

걍 기본 heap 문제

(3) 973. K Closest Points to Origin

heap 말고도 quick sort 같이 divide conquer로도 풀수있는거 같은데 좀 어려

(4) Kth Largest Element In An Array

걍 1번이랑 똑같음 풀필요 x 내 heap이나 심심하면 만들어보기

(5) 621. Task Scheduler

priority_queue 이용해서 schduler 구현 가능하다는 것도 알고있으면 좋은 정도, math로도 풀수있고 그게 사실 더 빠르긴함

+ pq나 q empty()확인 안 하고 pop()하면 heap-buffer-overflow 에러난다.

(6) 355. Design Twitter

unordered_map<int, vector<int> 나

unordered_map<int, priority_queue<Point> pq> 를 할수있다는거 알기

 

DP 

+) 95. Unique Binary Search Trees II

+) 139. Word Break

 

Trie

+)  139. Word Break

 

Top Interview 150

Array / String 

1) 459. Repeated Substring Pattern

=> substr 연습 및 반복 string 처리 어떻게 할지에 대한 생각

2) 168. Excel Sheet Column Title

=> 1) reserve (s.begin(), s.end() ) 하는 방법

     2) columnNumber-- 하고 하면 괜찮은데, 그냥 -1 하면 안 됨.

됨

안 됨

3) 767. Reorganize String

=> 문제가 핵 어려움

 

4) 97. Interleaving String

memoization을 잘 해야하는데, 익숙하게 해놓기

 

 

[마무리 멘트]

즉 = That being said,