bowang0911/leetcode huggingface dataset:
Read N Characters Given Read4

Given a `file` and assume that you can only read the file using a given method `read4`, implement a method to read `n` characters.

**Method read4:**

The API `read4` reads **four consecutive characters** from `file`, then writes those characters into the buffer array `buf4`.

The return value is the number of actual characters read.

Note that `read4()` has its own file pointer, much like `FILE *fp` in C.

**Definition of read4:**

    Parameter:  char\[\] buf4
    Returns:    int

buf4\[\] is a destination, not a source. The results from read4 will be copied to buf4\[\].

Below is a high-level example of how `read4` works:

File file( "abcde `"); // File is  "`abcde `", initially file pointer (fp) points to 'a' char[] buf4 = new char[4]; // Create buffer with enough space to store characters read4(buf4); // read4 returns 4. Now buf4 =  "abcd ", fp points to 'e' read4(buf4); // read4 returns 1. Now buf4 =  "e ", fp points to end of file read4(buf4); // read4 returns 0. Now buf4 =  " ", fp points to end of file`

**Method read:**

By using the `read4` method, implement the method read that reads `n` characters from `file` and store it in the buffer array `buf`. Consider that you cannot manipulate `file` directly.

The return value is the number of actual characters read.

**Definition of read:**

    Parameters:	char\[\] buf, int n
    Returns:	int

buf\[\] is a destination, not a source. You will need to write the results to buf\[\].

**Note:**

*   Consider that you cannot manipulate the file directly. The file is only accessible for `read4` but not for `read`.
*   The `read` function will only be called once for each test case.
*   You may assume the destination buffer array, `buf`, is guaranteed to have enough space for storing `n` characters.

**Example 1:**

**Input:** file =  "abc ", n = 4
**Output:** 3
**Explanation:** After calling your read method, buf should contain  "abc ". We read a total of 3 characters from the file, so return 3.
Note that  "abc " is the file's content, not buf. buf is the destination buffer that you will have to write the results to.

**Example 2:**

**Input:** file =  "abcde ", n = 5
**Output:** 5
**Explanation:** After calling your read method, buf should contain  "abcde ". We read a total of 5 characters from the file, so return 5.

**Example 3:**

**Input:** file =  "abcdABCD1234 ", n = 12
**Output:** 12
**Explanation:** After calling your read method, buf should contain  "abcdABCD1234 ". We read a total of 12 characters from the file, so return 12.

**Constraints:**

*   `1 <= file.length <= 500`
*   `file` consist of English letters and digits.
*   `1 <= n <= 1000`
Longest Substring with At Most Two Distinct Characters

Given a string `s`, return _the length of the longest_ _substring_ _that contains at most **two distinct characters**_.

**Example 1:**

**Input:** s =  "eceba "
**Output:** 3
**Explanation:** The substring is  "ece " which its length is 3.

**Example 2:**

**Input:** s =  "ccaabbb "
**Output:** 5
**Explanation:** The substring is  "aabbb " which its length is 5.

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of English letters.
One Edit Distance

Given two strings `s` and `t`, return `true` if they are both one edit distance apart, otherwise return `false`.

A string `s` is said to be one distance apart from a string `t` if you can:

*   Insert **exactly one** character into `s` to get `t`.
*   Delete **exactly one** character from `s` to get `t`.
*   Replace **exactly one** character of `s` with **a different character** to get `t`.

**Example 1:**

**Input:** s =  "ab ", t =  "acb "
**Output:** true
**Explanation:** We can insert 'c' into s to get t.

**Example 2:**

**Input:** s =  " ", t =  " "
**Output:** false
**Explanation:** We cannot get t from s by only one step.

**Constraints:**

*   `0 <= s.length, t.length <= 104`
*   `s` and `t` consist of lowercase letters, uppercase letters, and digits.
Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Given a **0-indexed** integer array `nums`, find a peak element, and return its index. If the array contains multiple peaks, return the index to **any of the peaks**.

You may imagine that `nums[-1] = nums[n] = -∞`. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in `O(log n)` time.

**Example 1:**

**Input:** nums = \[1,2,3,1\]
**Output:** 2
**Explanation:** 3 is a peak element and your function should return the index number 2.

**Example 2:**

**Input:** nums = \[1,2,1,3,5,6,4\]
**Output:** 5
**Explanation:** Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `-231 <= nums[i] <= 231 - 1`
*   `nums[i] != nums[i + 1]` for all valid `i`.
Missing Ranges

You are given an inclusive range `[lower, upper]` and a **sorted unique** integer array `nums`, where all elements are in the inclusive range.

A number `x` is considered **missing** if `x` is in the range `[lower, upper]` and `x` is not in `nums`.

Return _the **smallest sorted** list of ranges that **cover every missing number exactly**_. That is, no element of `nums` is in any of the ranges, and each missing number is in one of the ranges.

Each range `[a,b]` in the list should be output as:

*   `"a->b "` if `a != b`
*   `"a "` if `a == b`

**Example 1:**

**Input:** nums = \[0,1,3,50,75\], lower = 0, upper = 99
**Output:** \[ "2 ", "4->49 ", "51->74 ", "76->99 "\]
**Explanation:** The ranges are:
\[2,2\] -->  "2 "
\[4,49\] -->  "4->49 "
\[51,74\] -->  "51->74 "
\[76,99\] -->  "76->99 "

**Example 2:**

**Input:** nums = \[-1\], lower = -1, upper = -1
**Output:** \[\]
**Explanation:** There are no missing ranges since there are no missing numbers.

**Constraints:**

*   `-109 <= lower <= upper <= 109`
*   `0 <= nums.length <= 100`
*   `lower <= nums[i] <= upper`
*   All the values of `nums` are **unique**.
Maximum Gap

Given an integer array `nums`, return _the maximum difference between two successive elements in its sorted form_. If the array contains less than two elements, return `0`.

You must write an algorithm that runs in linear time and uses linear extra space.

**Example 1:**

**Input:** nums = \[3,6,9,1\]
**Output:** 3
**Explanation:** The sorted form of the array is \[1,3,6,9\], either (3,6) or (6,9) has the maximum difference 3.

**Example 2:**

**Input:** nums = \[10\]
**Output:** 0
**Explanation:** The array contains less than 2 elements, therefore return 0.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `0 <= nums[i] <= 109`
Compare Version Numbers

Given two version numbers, `version1` and `version2`, compare them.

Version numbers consist of **one or more revisions** joined by a dot `'.'`. Each revision consists of **digits** and may contain leading **zeros**. Every revision contains **at least one character**. Revisions are **0-indexed from left to right**, with the leftmost revision being revision 0, the next revision being revision 1, and so on. For example `2.5.33` and `0.1` are valid version numbers.

To compare version numbers, compare their revisions in **left-to-right order**. Revisions are compared using their **integer value ignoring any leading zeros**. This means that revisions `1` and `001` are considered **equal**. If a version number does not specify a revision at an index, then **treat the revision as `0`**. For example, version `1.0` is less than version `1.1` because their revision 0s are the same, but their revision 1s are `0` and `1` respectively, and `0 < 1`.

_Return the following:_

*   If `version1 < version2`, return `-1`.
*   If `version1 > version2`, return `1`.
*   Otherwise, return `0`.

**Example 1:**

**Input:** version1 =  "1.01 ", version2 =  "1.001 "
**Output:** 0
**Explanation:** Ignoring leading zeroes, both  "01 " and  "001 " represent the same integer  "1 ".

**Example 2:**

**Input:** version1 =  "1.0 ", version2 =  "1.0.0 "
**Output:** 0
**Explanation:** version1 does not specify revision 2, which means it is treated as  "0 ".

**Example 3:**

**Input:** version1 =  "0.1 ", version2 =  "1.1 "
**Output:** -1
**Explanation:** version1's revision 0 is  "0 ", while version2's revision 0 is  "1 ". 0 < 1, so version1 < version2.

**Constraints:**

*   `1 <= version1.length, version2.length <= 500`
*   `version1` and `version2` only contain digits and `'.'`.
*   `version1` and `version2` **are valid version numbers**.
*   All the given revisions in `version1` and `version2` can be stored in a **32-bit integer**.
Fraction to Recurring Decimal

Given two integers representing the `numerator` and `denominator` of a fraction, return _the fraction in string format_.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return **any of them**.

It is **guaranteed** that the length of the answer string is less than `104` for all the given inputs.

**Example 1:**

**Input:** numerator = 1, denominator = 2
**Output:**  "0.5 "

**Example 2:**

**Input:** numerator = 2, denominator = 1
**Output:**  "2 "

**Example 3:**

**Input:** numerator = 4, denominator = 333
**Output:**  "0.(012) "

**Constraints:**

*   `-231 <= numerator, denominator <= 231 - 1`
*   `denominator != 0`
Two Sum II - Input Array Is Sorted

Given a **1-indexed** array of integers `numbers` that is already **_sorted in non-decreasing order_**, find two numbers such that they add up to a specific `target` number. Let these two numbers be `numbers[index1]` and `numbers[index2]` where `1 <= index1 < index2 <= numbers.length`.

Return _the indices of the two numbers,_ `index1` _and_ `index2`_, **added by one** as an integer array_ `[index1, index2]` _of length 2._

The tests are generated such that there is **exactly one solution**. You **may not** use the same element twice.

Your solution must use only constant extra space.

**Example 1:**

**Input:** numbers = \[2,7,11,15\], target = 9
**Output:** \[1,2\]
**Explanation:** The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return \[1, 2\].

**Example 2:**

**Input:** numbers = \[2,3,4\], target = 6
**Output:** \[1,3\]
**Explanation:** The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return \[1, 3\].

**Example 3:**

**Input:** numbers = \[\-1,0\], target = -1
**Output:** \[1,2\]
**Explanation:** The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return \[1, 2\].

**Constraints:**

*   `2 <= numbers.length <= 3 * 104`
*   `-1000 <= numbers[i] <= 1000`
*   `numbers` is sorted in **non-decreasing order**.
*   `-1000 <= target <= 1000`
*   The tests are generated such that there is **exactly one solution**.
Excel Sheet Column Title

Given an integer `columnNumber`, return _its corresponding column title as it appears in an Excel sheet_.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

**Example 1:**

**Input:** columnNumber = 1
**Output:**  "A "

**Example 2:**

**Input:** columnNumber = 28
**Output:**  "AB "

**Example 3:**

**Input:** columnNumber = 701
**Output:**  "ZY "

**Constraints:**

*   `1 <= columnNumber <= 231 - 1`
Majority Element

Given an array `nums` of size `n`, return _the majority element_.

The majority element is the element that appears more than `⌊n / 2⌋` times. You may assume that the majority element always exists in the array.

**Example 1:**

**Input:** nums = \[3,2,3\]
**Output:** 3

**Example 2:**

**Input:** nums = \[2,2,1,1,1,2,2\]
**Output:** 2

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 5 * 104`
*   `-109 <= nums[i] <= 109`

**Follow-up:** Could you solve the problem in linear time and in `O(1)` space?
Two Sum III - Data structure design

Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.

Implement the `TwoSum` class:

*   `TwoSum()` Initializes the `TwoSum` object, with an empty array initially.
*   `void add(int number)` Adds `number` to the data structure.
*   `boolean find(int value)` Returns `true` if there exists any pair of numbers whose sum is equal to `value`, otherwise, it returns `false`.

**Example 1:**

**Input**
\[ "TwoSum ",  "add ",  "add ",  "add ",  "find ",  "find "\]
\[\[\], \[1\], \[3\], \[5\], \[4\], \[7\]\]
**Output**
\[null, null, null, null, true, false\]

**Explanation**
TwoSum twoSum = new TwoSum();
twoSum.add(1);   // \[\] --> \[1\]
twoSum.add(3);   // \[1\] --> \[1,3\]
twoSum.add(5);   // \[1,3\] --> \[1,3,5\]
twoSum.find(4);  // 1 + 3 = 4, return true
twoSum.find(7);  // No two integers sum up to 7, return false

**Constraints:**

*   `-105 <= number <= 105`
*   `-231 <= value <= 231 - 1`
*   At most `104` calls will be made to `add` and `find`.
Excel Sheet Column Number

Given a string `columnTitle` that represents the column title as appears in an Excel sheet, return _its corresponding column number_.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

**Example 1:**

**Input:** columnTitle =  "A "
**Output:** 1

**Example 2:**

**Input:** columnTitle =  "AB "
**Output:** 28

**Example 3:**

**Input:** columnTitle =  "ZY "
**Output:** 701

**Constraints:**

*   `1 <= columnTitle.length <= 7`
*   `columnTitle` consists only of uppercase English letters.
*   `columnTitle` is in the range `[ "A ", "FXSHRXW "]`.
Factorial Trailing Zeroes

Given an integer `n`, return _the number of trailing zeroes in_ `n!`.

Note that `n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1`.

**Example 1:**

**Input:** n = 3
**Output:** 0
**Explanation:** 3! = 6, no trailing zero.

**Example 2:**

**Input:** n = 5
**Output:** 1
**Explanation:** 5! = 120, one trailing zero.

**Example 3:**

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

**Constraints:**

*   `0 <= n <= 104`

**Follow up:** Could you write a solution that works in logarithmic time complexity?
Binary Search Tree Iterator

Implement the `BSTIterator` class that represents an iterator over the **[in-order traversal](https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR))** of a binary search tree (BST):

*   `BSTIterator(TreeNode root)` Initializes an object of the `BSTIterator` class. The `root` of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
*   `boolean hasNext()` Returns `true` if there exists a number in the traversal to the right of the pointer, otherwise returns `false`.
*   `int next()` Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to `next()` will return the smallest element in the BST.

You may assume that `next()` calls will always be valid. That is, there will be at least a next number in the in-order traversal when `next()` is called.

**Example 1:**

**Input**
\[ "BSTIterator ",  "next ",  "next ",  "hasNext ",  "next ",  "hasNext ",  "next ",  "hasNext ",  "next ",  "hasNext "\]
\[\[\[7, 3, 15, null, null, 9, 20\]\], \[\], \[\], \[\], \[\], \[\], \[\], \[\], \[\], \[\]\]
**Output**
\[null, 3, 7, true, 9, true, 15, true, 20, false\]

**Explanation**
BSTIterator bSTIterator = new BSTIterator(\[7, 3, 15, null, null, 9, 20\]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 105]`.
*   `0 <= Node.val <= 106`
*   At most `105` calls will be made to `hasNext`, and `next`.

**Follow up:**

*   Could you implement `next()` and `hasNext()` to run in average `O(1)` time and use `O(h)` memory, where `h` is the height of the tree?
Dungeon Game

The demons had captured the princess and imprisoned her in **the bottom-right corner** of a `dungeon`. The `dungeon` consists of `m x n` rooms laid out in a 2D grid. Our valiant knight was initially positioned in **the top-left room** and must fight his way through `dungeon` to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to `0` or below, he dies immediately.

Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).

To reach the princess as quickly as possible, the knight decides to move only **rightward** or **downward** in each step.

Return _the knight's minimum initial health so that he can rescue the princess_.

**Note** that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

**Example 1:**

**Input:** dungeon = \[\[-2,-3,3\],\[-5,-10,1\],\[10,30,-5\]\]
**Output:** 7
**Explanation:** The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

**Example 2:**

**Input:** dungeon = \[\[0\]\]
**Output:** 1

**Constraints:**

*   `m == dungeon.length`
*   `n == dungeon[i].length`
*   `1 <= m, n <= 200`
*   `-1000 <= dungeon[i][j] <= 1000`
Largest Number

Given a list of non-negative integers `nums`, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

**Example 1:**

**Input:** nums = \[10,2\]
**Output:**  "210 "

**Example 2:**

**Input:** nums = \[3,30,34,5,9\]
**Output:**  "9534330 "

**Constraints:**

*   `1 <= nums.length <= 100`
*   `0 <= nums[i] <= 109`
Reverse Words in a String II

Given a character array `s`, reverse the order of the **words**.

A **word** is defined as a sequence of non-space characters. The **words** in `s` will be separated by a single space.

Your code must solve the problem **in-place,** i.e. without allocating extra space.

**Example 1:**

**Input:** s = \["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"\]
**Output:** \["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"\]

**Example 2:**

**Input:** s = \["a"\]
**Output:** \["a"\]

**Constraints:**

*   `1 <= s.length <= 105`
*   `s[i]` is an English letter (uppercase or lowercase), digit, or space `' '`.
*   There is **at least one** word in `s`.
*   `s` does not contain leading or trailing spaces.
*   All the words in `s` are guaranteed to be separated by a single space.
Repeated DNA Sequences

The **DNA sequence** is composed of a series of nucleotides abbreviated as `'A'`, `'C'`, `'G'`, and `'T'`.

*   For example, `"ACGAATTCCG "` is a **DNA sequence**.

When studying **DNA**, it is useful to identify repeated sequences within the DNA.

Given a string `s` that represents a **DNA sequence**, return all the **`10`\-letter-long** sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in **any order**.

**Example 1:**

**Input:** s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
**Output:** \["AAAAACCCCC","CCCCCAAAAA"\]

**Example 2:**

**Input:** s = "AAAAAAAAAAAAA"
**Output:** \["AAAAAAAAAA"\]

**Constraints:**

*   `1 <= s.length <= 105`
*   `s[i]` is either `'A'`, `'C'`, `'G'`, or `'T'`.
Best Time to Buy and Sell Stock IV

You are given an integer array `prices` where `prices[i]` is the price of a given stock on the `ith` day, and an integer `k`.

Find the maximum profit you can achieve. You may complete at most `k` transactions: i.e. you may buy at most `k` times and sell at most `k` times.

**Note:** You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

**Example 1:**

**Input:** k = 2, prices = \[2,4,1\]
**Output:** 2
**Explanation:** Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

**Example 2:**

**Input:** k = 2, prices = \[3,2,6,5,0,3\]
**Output:** 7
**Explanation:** Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

**Constraints:**

*   `1 <= k <= 100`
*   `1 <= prices.length <= 1000`
*   `0 <= prices[i] <= 1000`
Rotate Array

Given an integer array `nums`, rotate the array to the right by `k` steps, where `k` is non-negative.

**Example 1:**

**Input:** nums = \[1,2,3,4,5,6,7\], k = 3
**Output:** \[5,6,7,1,2,3,4\]
**Explanation:**
rotate 1 steps to the right: \[7,1,2,3,4,5,6\]
rotate 2 steps to the right: \[6,7,1,2,3,4,5\]
rotate 3 steps to the right: \[5,6,7,1,2,3,4\]

**Example 2:**

**Input:** nums = \[-1,-100,3,99\], k = 2
**Output:** \[3,99,-1,-100\]
**Explanation:** 
rotate 1 steps to the right: \[99,-1,-100,3\]
rotate 2 steps to the right: \[3,99,-1,-100\]

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-231 <= nums[i] <= 231 - 1`
*   `0 <= k <= 105`

**Follow up:**

*   Try to come up with as many solutions as you can. There are at least **three** different ways to solve this problem.
*   Could you do it in-place with `O(1)` extra space?
Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

**Note:**

*   Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
*   In Java, the compiler represents the signed integers using [2's complement notation](https://en.wikipedia.org/wiki/Two%27s_complement). Therefore, in **Example 2** above, the input represents the signed integer `-3` and the output represents the signed integer `-1073741825`.

**Example 1:**

**Input:** n = 00000010100101000001111010011100
**Output:**    964176192 (00111001011110000010100101000000)
**Explanation:** The input binary string **00000010100101000001111010011100** represents the unsigned integer 43261596, so return 964176192 which its binary representation is **00111001011110000010100101000000**.

**Example 2:**

**Input:** n = 11111111111111111111111111111101
**Output:**   3221225471 (10111111111111111111111111111111)
**Explanation:** The input binary string **11111111111111111111111111111101** represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is **10111111111111111111111111111111**.

**Constraints:**

*   The input must be a **binary string** of length `32`

**Follow up:** If this function is called many times, how would you optimize it?
Number of 1 Bits

Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the [Hamming weight](http://en.wikipedia.org/wiki/Hamming_weight)).

**Note:**

*   Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
*   In Java, the compiler represents the signed integers using [2's complement notation](https://en.wikipedia.org/wiki/Two%27s_complement). Therefore, in **Example 3**, the input represents the signed integer. `-3`.

**Example 1:**

**Input:** n = 00000000000000000000000000001011
**Output:** 3
**Explanation:** The input binary string **00000000000000000000000000001011** has a total of three '1' bits.

**Example 2:**

**Input:** n = 00000000000000000000000010000000
**Output:** 1
**Explanation:** The input binary string **00000000000000000000000010000000** has a total of one '1' bit.

**Example 3:**

**Input:** n = 11111111111111111111111111111101
**Output:** 31
**Explanation:** The input binary string **11111111111111111111111111111101** has a total of thirty one '1' bits.

**Constraints:**

*   The input must be a **binary string** of length `32`.

**Follow up:** If this function is called many times, how would you optimize it?