bowang0911/leetcode huggingface dataset:
Rotated Digits

An integer `x` is a **good** if after rotating each digit individually by 180 degrees, we get a valid number that is different from `x`. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. For example:

*   `0`, `1`, and `8` rotate to themselves,
*   `2` and `5` rotate to each other (in this case they are rotated in a different direction, in other words, `2` or `5` gets mirrored),
*   `6` and `9` rotate to each other, and
*   the rest of the numbers do not rotate to any other number and become invalid.

Given an integer `n`, return _the number of **good** integers in the range_ `[1, n]`.

**Example 1:**

**Input:** n = 10
**Output:** 4
**Explanation:** There are four good numbers in the range \[1, 10\] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

**Example 2:**

**Input:** n = 1
**Output:** 0

**Example 3:**

**Input:** n = 2
**Output:** 1

**Constraints:**

*   `1 <= n <= 104`
Escape The Ghosts

You are playing a simplified PAC-MAN game on an infinite 2-D grid. You start at the point `[0, 0]`, and you are given a destination point `target = [xtarget, ytarget]` that you are trying to get to. There are several ghosts on the map with their starting positions given as a 2D array `ghosts`, where `ghosts[i] = [xi, yi]` represents the starting position of the `ith` ghost. All inputs are **integral coordinates**.

Each turn, you and all the ghosts may independently choose to either **move 1 unit** in any of the four cardinal directions: north, east, south, or west, or **stay still**. All actions happen **simultaneously**.

You escape if and only if you can reach the target **before** any ghost reaches you. If you reach any square (including the target) at the **same time** as a ghost, it **does not** count as an escape.

Return `true` _if it is possible to escape regardless of how the ghosts move, otherwise return_ `false`_._

**Example 1:**

**Input:** ghosts = \[\[1,0\],\[0,3\]\], target = \[0,1\]
**Output:** true
**Explanation:** You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you.

**Example 2:**

**Input:** ghosts = \[\[1,0\]\], target = \[2,0\]
**Output:** false
**Explanation:** You need to reach the destination (2, 0), but the ghost at (1, 0) lies between you and the destination.

**Example 3:**

**Input:** ghosts = \[\[2,0\]\], target = \[1,0\]
**Output:** false
**Explanation:** The ghost can reach the target at the same time as you.

**Constraints:**

*   `1 <= ghosts.length <= 100`
*   `ghosts[i].length == 2`
*   `-104 <= xi, yi <= 104`
*   There can be **multiple ghosts** in the same location.
*   `target.length == 2`
*   `-104 <= xtarget, ytarget <= 104`
Domino and Tromino Tiling

You have two types of tiles: a `2 x 1` domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return _the number of ways to tile an_ `2 x n` _board_. Since the answer may be very large, return it **modulo** `109 + 7`.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

**Example 1:**

**Input:** n = 3
**Output:** 5
**Explanation:** The five different ways are show above.

**Example 2:**

**Input:** n = 1
**Output:** 1

**Constraints:**

*   `1 <= n <= 1000`
Custom Sort String

You are given two strings order and s. All the characters of `order` are **unique** and were sorted in some custom order previously.

Permute the characters of `s` so that they match the order that `order` was sorted. More specifically, if a character `x` occurs before a character `y` in `order`, then `x` should occur before `y` in the permuted string.

Return _any permutation of_ `s` _that satisfies this property_.

**Example 1:**

**Input:** order =  "cba ", s =  "abcd "
**Output:**  "cbad "
**Explanation:** 
 "a ",  "b ",  "c " appear in order, so the order of  "a ",  "b ",  "c " should be  "c ",  "b ", and  "a ". 
Since  "d " does not appear in order, it can be at any position in the returned string.  "dcba ",  "cdba ",  "cbda " are also valid outputs.

**Example 2:**

**Input:** order =  "cbafg ", s =  "abcd "
**Output:**  "cbad "

**Constraints:**

*   `1 <= order.length <= 26`
*   `1 <= s.length <= 200`
*   `order` and `s` consist of lowercase English letters.
*   All the characters of `order` are **unique**.
Number of Matching Subsequences

Given a string `s` and an array of strings `words`, return _the number of_ `words[i]` _that is a subsequence of_ `s`.

A **subsequence** of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

*   For example, `"ace "` is a subsequence of `"abcde "`.

**Example 1:**

**Input:** s =  "abcde ", words = \[ "a ", "bb ", "acd ", "ace "\]
**Output:** 3
**Explanation:** There are three strings in words that are a subsequence of s:  "a ",  "acd ",  "ace ".

**Example 2:**

**Input:** s =  "dsahjpjauf ", words = \[ "ahjpjau ", "ja ", "ahbwzgqnuk ", "tnmlanowax "\]
**Output:** 2

**Constraints:**

*   `1 <= s.length <= 5 * 104`
*   `1 <= words.length <= 5000`
*   `1 <= words[i].length <= 50`
*   `s` and `words[i]` consist of only lowercase English letters.
Preimage Size of Factorial Zeroes Function

Let `f(x)` be the number of zeroes at the end of `x!`. Recall that `x! = 1 * 2 * 3 * ... * x` and by convention, `0! = 1`.

*   For example, `f(3) = 0` because `3! = 6` has no zeroes at the end, while `f(11) = 2` because `11! = 39916800` has two zeroes at the end.

Given an integer `k`, return the number of non-negative integers `x` have the property that `f(x) = k`.

**Example 1:**

**Input:** k = 0
**Output:** 5
**Explanation:** 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.

**Example 2:**

**Input:** k = 5
**Output:** 0
**Explanation:** There is no x such that x! ends in k = 5 zeroes.

**Example 3:**

**Input:** k = 3
**Output:** 5

**Constraints:**

*   `0 <= k <= 109`
Valid Tic-Tac-Toe State

Given a Tic-Tac-Toe board as a string array `board`, return `true` if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a `3 x 3` array that consists of characters `' '`, `'X'`, and `'O'`. The `' '` character represents an empty square.

Here are the rules of Tic-Tac-Toe:

*   Players take turns placing characters into empty squares `' '`.
*   The first player always places `'X'` characters, while the second player always places `'O'` characters.
*   `'X'` and `'O'` characters are always placed into empty squares, never filled ones.
*   The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
*   The game also ends if all squares are non-empty.
*   No more moves can be played if the game is over.

**Example 1:**

**Input:** board = \[ "O   ", "    ", "    "\]
**Output:** false
**Explanation:** The first player always plays  "X ".

**Example 2:**

**Input:** board = \[ "XOX ", " X  ", "    "\]
**Output:** false
**Explanation:** Players take turns making moves.

**Example 3:**

**Input:** board = \[ "XOX ", "O O ", "XOX "\]
**Output:** true

**Constraints:**

*   `board.length == 3`
*   `board[i].length == 3`
*   `board[i][j]` is either `'X'`, `'O'`, or `' '`.
Number of Subarrays with Bounded Maximum

Given an integer array `nums` and two integers `left` and `right`, return _the number of contiguous non-empty **subarrays** such that the value of the maximum array element in that subarray is in the range_ `[left, right]`.

The test cases are generated so that the answer will fit in a **32-bit** integer.

**Example 1:**

**Input:** nums = \[2,1,4,3\], left = 2, right = 3
**Output:** 3
**Explanation:** There are three subarrays that meet the requirements: \[2\], \[2, 1\], \[3\].

**Example 2:**

**Input:** nums = \[2,9,2,5,6\], left = 2, right = 8
**Output:** 7

**Constraints:**

*   `1 <= nums.length <= 105`
*   `0 <= nums[i] <= 109`
*   `0 <= left <= right <= 109`
Rotate String

Given two strings `s` and `goal`, return `true` _if and only if_ `s` _can become_ `goal` _after some number of **shifts** on_ `s`.

A **shift** on `s` consists of moving the leftmost character of `s` to the rightmost position.

*   For example, if `s = "abcde "`, then it will be `"bcdea "` after one shift.

**Example 1:**

**Input:** s = "abcde", goal = "cdeab"
**Output:** true

**Example 2:**

**Input:** s = "abcde", goal = "abced"
**Output:** false

**Constraints:**

*   `1 <= s.length, goal.length <= 100`
*   `s` and `goal` consist of lowercase English letters.
All Paths From Source to Target

Given a directed acyclic graph (**DAG**) of `n` nodes labeled from `0` to `n - 1`, find all possible paths from node `0` to node `n - 1` and return them in **any order**.

The graph is given as follows: `graph[i]` is a list of all nodes you can visit from node `i` (i.e., there is a directed edge from node `i` to node `graph[i][j]`).

**Example 1:**

**Input:** graph = \[\[1,2\],\[3\],\[3\],\[\]\]
**Output:** \[\[0,1,3\],\[0,2,3\]\]
**Explanation:** There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

**Example 2:**

**Input:** graph = \[\[4,3,1\],\[3,2,4\],\[3\],\[4\],\[\]\]
**Output:** \[\[0,4\],\[0,3,4\],\[0,1,3,4\],\[0,1,2,3,4\],\[0,1,4\]\]

**Constraints:**

*   `n == graph.length`
*   `2 <= n <= 15`
*   `0 <= graph[i][j] < n`
*   `graph[i][j] != i` (i.e., there will be no self-loops).
*   All the elements of `graph[i]` are **unique**.
*   The input graph is **guaranteed** to be a **DAG**.
Smallest Rotation with Highest Score

You are given an array `nums`. You can rotate it by a non-negative integer `k` so that the array becomes `[nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]]`. Afterward, any entries that are less than or equal to their index are worth one point.

*   For example, if we have `nums = [2,4,1,3,0]`, and we rotate by `k = 2`, it becomes `[1,3,0,2,4]`. This is worth `3` points because `1 > 0` \[no points\], `3 > 1` \[no points\], `0 <= 2` \[one point\], `2 <= 3` \[one point\], `4 <= 4` \[one point\].

Return _the rotation index_ `k` _that corresponds to the highest score we can achieve if we rotated_ `nums` _by it_. If there are multiple answers, return the smallest such index `k`.

**Example 1:**

**Input:** nums = \[2,3,1,4,0\]
**Output:** 3
**Explanation:** Scores for each k are listed below: 
k = 0,  nums = \[2,3,1,4,0\],    score 2
k = 1,  nums = \[3,1,4,0,2\],    score 3
k = 2,  nums = \[1,4,0,2,3\],    score 3
k = 3,  nums = \[4,0,2,3,1\],    score 4
k = 4,  nums = \[0,2,3,1,4\],    score 3
So we should choose k = 3, which has the highest score.

**Example 2:**

**Input:** nums = \[1,3,0,2,4\]
**Output:** 0
**Explanation:** nums will always have 3 points no matter how it shifts.
So we will choose the smallest k, which is 0.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `0 <= nums[i] < nums.length`
Champagne Tower

We stack glasses in a pyramid, where the **first** row has `1` glass, the **second** row has `2` glasses, and so on until the 100th row. Each glass holds one cup of champagne.

Then, some champagne is poured into the first glass at the top. When the topmost glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it. When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on. (A glass at the bottom row has its excess champagne fall on the floor.)

For example, after one cup of champagne is poured, the top most glass is full. After two cups of champagne are poured, the two glasses on the second row are half full. After three cups of champagne are poured, those two cups become full - there are 3 full glasses total now. After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.

Now after pouring some non-negative integer cups of champagne, return how full the `jth` glass in the `ith` row is (both `i` and `j` are 0-indexed.)

**Example 1:**

**Input:** poured = 1, query\_row = 1, query\_glass = 1
**Output:** 0.00000
**Explanation:** We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

**Example 2:**

**Input:** poured = 2, query\_row = 1, query\_glass = 1
**Output:** 0.50000
**Explanation:** We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.

**Example 3:**

**Input:** poured = 100000009, query\_row = 33, query\_glass = 17
**Output:** 1.00000

**Constraints:**

*   `0 <= poured <= 109`
*   `0 <= query_glass <= query_row < 100`
Similar RGB Color

The red-green-blue color `"#AABBCC "` can be written as `"#ABC "` in shorthand.

*   For example, `"#15c "` is shorthand for the color `"#1155cc "`.

The similarity between the two colors `"#ABCDEF "` and `"#UVWXYZ "` is `-(AB - UV)2 - (CD - WX)2 - (EF - YZ)2`.

Given a string `color` that follows the format `"#ABCDEF "`, return a string represents the color that is most similar to the given color and has a shorthand (i.e., it can be represented as some `"#XYZ "`).

**Any answer** which has the same highest similarity as the best answer will be accepted.

**Example 1:**

**Input:** color =  "#09f166 "
**Output:**  "#11ee66 "
**Explanation:** 
The similarity is -(0x09 - 0x11)2 -(0xf1 - 0xee)2 - (0x66 - 0x66)2 = -64 -9 -0 = -73.
This is the highest among any shorthand color.

**Example 2:**

**Input:** color =  "#4e3fe1 "
**Output:**  "#5544dd "

**Constraints:**

*   `color.length == 7`
*   `color[0] == '#'`
*   `color[i]` is either digit or character in the range `['a', 'f']` for `i > 0`.
Minimum Swaps To Make Sequences Increasing

You are given two integer arrays of the same length `nums1` and `nums2`. In one operation, you are allowed to swap `nums1[i]` with `nums2[i]`.

*   For example, if `nums1 = [1,2,3,8]`, and `nums2 = [5,6,7,4]`, you can swap the element at `i = 3` to obtain `nums1 = [1,2,3,4]` and `nums2 = [5,6,7,8]`.

Return _the minimum number of needed operations to make_ `nums1` _and_ `nums2` _**strictly increasing**_. The test cases are generated so that the given input always makes it possible.

An array `arr` is **strictly increasing** if and only if `arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1]`.

**Example 1:**

**Input:** nums1 = \[1,3,5,4\], nums2 = \[1,2,3,7\]
**Output:** 1
**Explanation:** 
Swap nums1\[3\] and nums2\[3\]. Then the sequences are:
nums1 = \[1, 3, 5, 7\] and nums2 = \[1, 2, 3, 4\]
which are both strictly increasing.

**Example 2:**

**Input:** nums1 = \[0,3,5,8,9\], nums2 = \[2,1,4,6,9\]
**Output:** 1

**Constraints:**

*   `2 <= nums1.length <= 105`
*   `nums2.length == nums1.length`
*   `0 <= nums1[i], nums2[i] <= 2 * 105`
Find Eventual Safe States

There is a directed graph of `n` nodes with each node labeled from `0` to `n - 1`. The graph is represented by a **0-indexed** 2D integer array `graph` where `graph[i]` is an integer array of nodes adjacent to node `i`, meaning there is an edge from node `i` to each node in `graph[i]`.

A node is a **terminal node** if there are no outgoing edges. A node is a **safe node** if every possible path starting from that node leads to a **terminal node** (or another safe node).

Return _an array containing all the **safe nodes** of the graph_. The answer should be sorted in **ascending** order.

**Example 1:**

**Input:** graph = \[\[1,2\],\[2,3\],\[5\],\[0\],\[5\],\[\],\[\]\]
**Output:** \[2,4,5,6\]
**Explanation:** The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.

**Example 2:**

**Input:** graph = \[\[1,2,3,4\],\[1,2\],\[3,4\],\[0,4\],\[\]\]
**Output:** \[4\]
**Explanation:**
Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.

**Constraints:**

*   `n == graph.length`
*   `1 <= n <= 104`
*   `0 <= graph[i].length <= n`
*   `0 <= graph[i][j] <= n - 1`
*   `graph[i]` is sorted in a strictly increasing order.
*   The graph may contain self-loops.
*   The number of edges in the graph will be in the range `[1, 4 * 104]`.
Bricks Falling When Hit

You are given an `m x n` binary `grid`, where each `1` represents a brick and `0` represents an empty space. A brick is **stable** if:

*   It is directly connected to the top of the grid, or
*   At least one other brick in its four adjacent cells is **stable**.

You are also given an array `hits`, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location `hits[i] = (rowi, coli)`. The brick on that location (if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will **fall**. Once a brick falls, it is **immediately** erased from the `grid` (i.e., it does not land on other stable bricks).

Return _an array_ `result`_, where each_ `result[i]` _is the number of bricks that will **fall** after the_ `ith` _erasure is applied._

**Note** that an erasure may refer to a location with no brick, and if it does, no bricks drop.

**Example 1:**

**Input:** grid = \[\[1,0,0,0\],\[1,1,1,0\]\], hits = \[\[1,0\]\]
**Output:** \[2\]
**Explanation:** Starting with the grid:
\[\[1,0,0,0\],
 \[1,1,1,0\]\]
We erase the underlined brick at (1,0), resulting in the grid:
\[\[1,0,0,0\],
 \[0,1,1,0\]\]
The two underlined bricks are no longer stable as they are no longer connected to the top nor adjacent to another stable brick, so they will fall. The resulting grid is:
\[\[1,0,0,0\],
 \[0,0,0,0\]\]
Hence the result is \[2\].

**Example 2:**

**Input:** grid = \[\[1,0,0,0\],\[1,1,0,0\]\], hits = \[\[1,1\],\[1,0\]\]
**Output:** \[0,0\]
**Explanation:** Starting with the grid:
\[\[1,0,0,0\],
 \[1,1,0,0\]\]
We erase the underlined brick at (1,1), resulting in the grid:
\[\[1,0,0,0\],
 \[1,0,0,0\]\]
All remaining bricks are still stable, so no bricks fall. The grid remains the same:
\[\[1,0,0,0\],
 \[1,0,0,0\]\]
Next, we erase the underlined brick at (1,0), resulting in the grid:
\[\[1,0,0,0\],
 \[0,0,0,0\]\]
Once again, all remaining bricks are still stable, so no bricks fall.
Hence the result is \[0,0\].

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 200`
*   `grid[i][j]` is `0` or `1`.
*   `1 <= hits.length <= 4 * 104`
*   `hits[i].length == 2`
*   `0 <= xi <= m - 1`
*   `0 <= yi <= n - 1`
*   All `(xi, yi)` are unique.
Unique Morse Code Words

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows:

*   `'a'` maps to `".- "`,
*   `'b'` maps to `"-... "`,
*   `'c'` maps to `"-.-. "`, and so on.

For convenience, the full table for the `26` letters of the English alphabet is given below:

\[ ".- ", "-... ", "-.-. ", "-.. ", ". ", "..-. ", "--. ", ".... ", ".. ", ".--- ", "-.- ", ".-.. ", "-- ", "-. ", "--- ", ".--. ", "--.- ", ".-. ", "... ", "- ", "..- ", "...- ", ".-- ", "-..- ", "-.-- ", "--.. "\]

Given an array of strings `words` where each word can be written as a concatenation of the Morse code of each letter.

*   For example, `"cab "` can be written as `"-.-..--... "`, which is the concatenation of `"-.-. "`, `".- "`, and `"-... "`. We will call such a concatenation the **transformation** of a word.

Return _the number of different **transformations** among all words we have_.

**Example 1:**

**Input:** words = \[ "gin ", "zen ", "gig ", "msg "\]
**Output:** 2
**Explanation:** The transformation of each word is:
 "gin " ->  "--...-. "
 "zen " ->  "--...-. "
 "gig " ->  "--...--. "
 "msg " ->  "--...--. "
There are 2 different transformations:  "--...-. " and  "--...--. ".

**Example 2:**

**Input:** words = \[ "a "\]
**Output:** 1

**Constraints:**

*   `1 <= words.length <= 100`
*   `1 <= words[i].length <= 12`
*   `words[i]` consists of lowercase English letters.
Split Array With Same Average

You are given an integer array `nums`.

You should move each element of `nums` into one of the two arrays `A` and `B` such that `A` and `B` are non-empty, and `average(A) == average(B)`.

Return `true` if it is possible to achieve that and `false` otherwise.

**Note** that for an array `arr`, `average(arr)` is the sum of all the elements of `arr` over the length of `arr`.

**Example 1:**

**Input:** nums = \[1,2,3,4,5,6,7,8\]
**Output:** true
**Explanation:** We can split the array into \[1,4,5,8\] and \[2,3,6,7\], and both of them have an average of 4.5.

**Example 2:**

**Input:** nums = \[3,1\]
**Output:** false

**Constraints:**

*   `1 <= nums.length <= 30`
*   `0 <= nums[i] <= 104`
Number of Lines To Write String

You are given a string `s` of lowercase English letters and an array `widths` denoting **how many pixels wide** each lowercase English letter is. Specifically, `widths[0]` is the width of `'a'`, `widths[1]` is the width of `'b'`, and so on.

You are trying to write `s` across several lines, where **each line is no longer than** `100` **pixels**. Starting at the beginning of `s`, write as many letters on the first line such that the total width does not exceed `100` pixels. Then, from where you stopped in `s`, continue writing as many letters as you can on the second line. Continue this process until you have written all of `s`.

Return _an array_ `result` _of length 2 where:_

*   `result[0]` _is the total number of lines._
*   `result[1]` _is the width of the last line in pixels._

**Example 1:**

**Input:** widths = \[10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10\], s =  "abcdefghijklmnopqrstuvwxyz "
**Output:** \[3,60\]
**Explanation:** You can write s as follows:
abcdefghij  // 100 pixels wide
klmnopqrst  // 100 pixels wide
uvwxyz      // 60 pixels wide
There are a total of 3 lines, and the last line is 60 pixels wide.

**Example 2:**

**Input:** widths = \[4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10\], s =  "bbbcccdddaaa "
**Output:** \[2,4\]
**Explanation:** You can write s as follows:
bbbcccdddaa  // 98 pixels wide
a            // 4 pixels wide
There are a total of 2 lines, and the last line is 4 pixels wide.

**Constraints:**

*   `widths.length == 26`
*   `2 <= widths[i] <= 10`
*   `1 <= s.length <= 1000`
*   `s` contains only lowercase English letters.