[LeetCode] Surrounded Regions

130. Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

Example:

1
2
3
4
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

1
2
3
4
X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any ‘O’ on the border of the board are not flipped to ‘X’. Any ‘O’ that is not on the border and it is not connected to an ‘O’ on the border will be flipped to ‘X’. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Read more
[LeetCode] Validate Binary Search Tree

98. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.
Read more
[LeetCode] Remove K Digits

402. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.
Read more
[LeetCode] Decoded String at Index

880. Decoded String at Index

An encoded string S is given. To find and write the decoded string to a tape, the encoded string is read one character at a time and the following steps are taken:

  • If the character read is a letter, that letter is written onto the tape.
  • If the character read is a digit (say d), the entire current tape is repeatedly written d-1 more times in total.

Now for some encoded string S, and an index K, find and return the K-th letter (1 indexed) in the decoded string.

Read more
[LeetCode] Make Sum Divisible by P

1590. Make Sum Divisible by P

Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

Return the length of the smallest subarray that you need to remove, or -1 if it’s impossible.

A subarray is defined as a contiguous block of elements in the array.

Read more
[LeetCode] Ugly Number III

1201. Ugly Number III

Given four integers n, a, b, and c, return the nth ugly number.

Ugly numbers are positive integers that are divisible by a, b, or c.

Read more
[LeetCode] Minimum Jumps to Reach Home

1654. Minimum Jumps to Reach Home

A certain bug’s home is on the x-axis at position x. Help them get there from position 0.

The bug jumps according to the following rules:

  • It can jump exactly a positions forward (to the right).
  • It can jump exactly b positions backward (to the left).
  • It cannot jump backward twice in a row.
  • It cannot jump to any forbidden positions.

The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

Read more
[오브젝트] 서브클래싱과 서브타이핑

서브클래싱과 서브타이핑

Read more
[LeetCode] Design Linked List

707. Design Linked List

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.

A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.

If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked
list are 0-indexed.

Implement the MyLinkedList class:

  • MyLinkedList() Initializes the MyLinkedList object.
  • int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
  • void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
  • void addAtTail(int val) Append a node of value val as the last element of the linked list.
  • void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
  • void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.
Read more
[LeetCode] Count Good Meals

1711. Count Good Meals

A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two.

You can pick any two different foods to make a good meal.

Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the i​​​​​​th​​​​​​​​ item of food, return the number of different good meals you can make from this list modulo 109 + 7.

Note that items with different indices are considered different even if they have the same deliciousness value.

Read more