133. Clone Graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

1 2 3 4

class Node { public int val; public List<Node> neighbors; }

Test case format:

For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

250. Count Univalue Subtrees

Given the root of a binary tree, return the number of uni-value subtrees.

A uni-value subtree means all nodes of the subtree have the same value.

1618. Maximum Font to Fit a Sentence in a Screen

You are given a string text. We want to display text on a screen of width w and height h. You can choose any font size from array fonts, which contains the available font sizes in ascending order.

You can use the FontInfo interface to get the width and height of any character at any available font size.

The FontInfo interface is defined as such:

1 2 3 4 5 6 7 8

interface FontInfo { // Returns the width of character ch on the screen using font size fontSize. // O(1) per call public int getWidth(int fontSize, char ch); // Returns the height of any character on the screen using font size fontSize. // O(1) per call public int getHeight(int fontSize); }

The calculated width of text for some fontSize is the sum of every getWidth(fontSize, text[i]) call for each 0 <= i < text.length (0-indexed). The calculated height of text for some fontSize is getHeight(fontSize). Note that text is displayed on a single line.

It is guaranteed that FontInfo will return the same value if you call getHeight or getWidth with the same parameters.

It is also guaranteed that for any font size fontSize and any character ch:

• getHeight(fontSize) <= getHeight(fontSize+1)
• getWidth(fontSize, ch) <= getWidth(fontSize+1, ch)

Return the maximum font size you can use to display text on the screen. If text cannot fit on the display with any font size, return -1.

276. Paint Fence

You are painting a fence of n posts with k different colors. You must paint the posts following these rules:

• Every post must be painted exactly one color.
• There cannot be three or more consecutive posts with the same color.

Given the two integers n and k, return the number of ways you can paint the fence.

1706. Where Will the Ball Fall

You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides.

Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left.

• A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1.
• A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -1.

We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a “V” shaped pattern between two boards or if a board redirects the ball into either wall of the box.

Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the ith column at the top, or -1 if the ball gets stuck in the box.

1554. Strings Differ by One Character

Given a list of strings dict where all the strings are of the same length.

Return true if there are 2 strings that only differ by 1 character in the same index, otherwise return false.

286. Walls and Gates

You are given an m x n grid rooms 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.

676. Implement Magic Dictionary

Design a data structure that is initialized with a list of different words. Provided a string, you should determine if you can change exactly one character in this string to match any word in the data structure.

Implement the MagicDictionary class:

• MagicDictionary() Initializes the object.
• void buildDict(String[] dictionary) Sets the data structure with an array of distinct strings dictionary.
• bool search(String searchWord) Returns true if you can change exactly one character in searchWord to match any string in the data structure, otherwise returns false.

379. Design Phone Directory

Design a phone directory that initially has maxNumbers empty slots that can store numbers. The directory should store numbers, check if a certain slot is empty or not, and empty a given slot.

Implement the PhoneDirectory class:

• PhoneDirectory(int maxNumbers) Initializes the phone directory with the number of available slots maxNumbers.
• int get() Provides a number that is not assigned to anyone. Returns -1 if no number is available.
• bool check(int number) Returns true if the slot number is available and false otherwise.
• void release(int number) Recycles or releases the slot number.

249. Group Shifted Strings

We can shift a string by shifting each of its letters to its successive letter.

• For example, “abc” can be shifted to be “bcd”.
  We can keep shifting the string to form a sequence.

• For example, we can keep shifting “abc” to form the sequence: “abc” -> “bcd” -> … -> “xyz”.

Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.