bowang0911/leetcode huggingface dataset:
Transpose File

Given a text file `file.txt`, transpose its content.

You may assume that each row has the same number of columns, and each field is separated by the `' '` character.

**Example:**

If `file.txt` has the following content:

name age
alice 21
ryan 30

Output the following:

name alice ryan
age 21 30
House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given an integer array `nums` representing the amount of money of each house, return _the maximum amount of money you can rob tonight **without alerting the police**_.

**Example 1:**

**Input:** nums = \[1,2,3,1\]
**Output:** 4
**Explanation:** Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

**Example 2:**

**Input:** nums = \[2,7,9,3,1\]
**Output:** 12
**Explanation:** Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

**Constraints:**

*   `1 <= nums.length <= 100`
*   `0 <= nums[i] <= 400`
Binary Tree Right Side View

Given the `root` of a binary tree, imagine yourself standing on the **right side** of it, return _the values of the nodes you can see ordered from top to bottom_.

**Example 1:**

**Input:** root = \[1,2,3,null,5,null,4\]
**Output:** \[1,3,4\]

**Example 2:**

**Input:** root = \[1,null,3\]
**Output:** \[1,3\]

**Example 3:**

**Input:** root = \[\]
**Output:** \[\]

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 100]`.
*   `-100 <= Node.val <= 100`
Number of Islands

Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and `'0'`s (water), return _the number of islands_.

An **island** is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

**Example 1:**

**Input:** grid = \[
  \[ "1 ", "1 ", "1 ", "1 ", "0 "\],
  \[ "1 ", "1 ", "0 ", "1 ", "0 "\],
  \[ "1 ", "1 ", "0 ", "0 ", "0 "\],
  \[ "0 ", "0 ", "0 ", "0 ", "0 "\]
\]
**Output:** 1

**Example 2:**

**Input:** grid = \[
  \[ "1 ", "1 ", "0 ", "0 ", "0 "\],
  \[ "1 ", "1 ", "0 ", "0 ", "0 "\],
  \[ "0 ", "0 ", "1 ", "0 ", "0 "\],
  \[ "0 ", "0 ", "0 ", "1 ", "1 "\]
\]
**Output:** 3

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 300`
*   `grid[i][j]` is `'0'` or `'1'`.
Bitwise AND of Numbers Range

Given two integers `left` and `right` that represent the range `[left, right]`, return _the bitwise AND of all numbers in this range, inclusive_.

**Example 1:**

**Input:** left = 5, right = 7
**Output:** 4

**Example 2:**

**Input:** left = 0, right = 0
**Output:** 0

**Example 3:**

**Input:** left = 1, right = 2147483647
**Output:** 0

**Constraints:**

*   `0 <= left <= right <= 231 - 1`
Happy Number

Write an algorithm to determine if a number `n` is happy.

A **happy number** is a number defined by the following process:

*   Starting with any positive integer, replace the number by the sum of the squares of its digits.
*   Repeat the process until the number equals 1 (where it will stay), or it **loops endlessly in a cycle** which does not include 1.
*   Those numbers for which this process **ends in 1** are happy.

Return `true` _if_ `n` _is a happy number, and_ `false` _if not_.

**Example 1:**

**Input:** n = 19
**Output:** true
**Explanation:**
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

**Example 2:**

**Input:** n = 2
**Output:** false

**Constraints:**

*   `1 <= n <= 231 - 1`
Remove Linked List Elements

Given the `head` of a linked list and an integer `val`, remove all the nodes of the linked list that has `Node.val == val`, and return _the new head_.

**Example 1:**

**Input:** head = \[1,2,6,3,4,5,6\], val = 6
**Output:** \[1,2,3,4,5\]

**Example 2:**

**Input:** head = \[\], val = 1
**Output:** \[\]

**Example 3:**

**Input:** head = \[7,7,7,7\], val = 7
**Output:** \[\]

**Constraints:**

*   The number of nodes in the list is in the range `[0, 104]`.
*   `1 <= Node.val <= 50`
*   `0 <= val <= 50`
Count Primes

Given an integer `n`, return _the number of prime numbers that are strictly less than_ `n`.

**Example 1:**

**Input:** n = 10
**Output:** 4
**Explanation:** There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   `0 <= n <= 5 * 106`
Isomorphic Strings

Given two strings `s` and `t`, _determine if they are isomorphic_.

Two strings `s` and `t` are isomorphic if the characters in `s` can be replaced to get `t`.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

**Example 1:**

**Input:** s = "egg", t = "add"
**Output:** true

**Example 2:**

**Input:** s = "foo", t = "bar"
**Output:** false

**Example 3:**

**Input:** s = "paper", t = "title"
**Output:** true

**Constraints:**

*   `1 <= s.length <= 5 * 104`
*   `t.length == s.length`
*   `s` and `t` consist of any valid ascii character.
Reverse Linked List

Given the `head` of a singly linked list, reverse the list, and return _the reversed list_.

**Example 1:**

**Input:** head = \[1,2,3,4,5\]
**Output:** \[5,4,3,2,1\]

**Example 2:**

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

**Example 3:**

**Input:** head = \[\]
**Output:** \[\]

**Constraints:**

*   The number of nodes in the list is the range `[0, 5000]`.
*   `-5000 <= Node.val <= 5000`

**Follow up:** A linked list can be reversed either iteratively or recursively. Could you implement both?
Course Schedule

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you **must** take course `bi` first if you want to take course `ai`.

*   For example, the pair `[0, 1]`, indicates that to take course `0` you have to first take course `1`.

Return `true` if you can finish all courses. Otherwise, return `false`.

**Example 1:**

**Input:** numCourses = 2, prerequisites = \[\[1,0\]\]
**Output:** true
**Explanation:** There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

**Example 2:**

**Input:** numCourses = 2, prerequisites = \[\[1,0\],\[0,1\]\]
**Output:** false
**Explanation:** There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

**Constraints:**

*   `1 <= numCourses <= 2000`
*   `0 <= prerequisites.length <= 5000`
*   `prerequisites[i].length == 2`
*   `0 <= ai, bi < numCourses`
*   All the pairs prerequisites\[i\] are **unique**.
Implement Trie (Prefix Tree)

A [**trie**](https://en.wikipedia.org/wiki/Trie) (pronounced as "try ") or **prefix tree** is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

*   `Trie()` Initializes the trie object.
*   `void insert(String word)` Inserts the string `word` into the trie.
*   `boolean search(String word)` Returns `true` if the string `word` is in the trie (i.e., was inserted before), and `false` otherwise.
*   `boolean startsWith(String prefix)` Returns `true` if there is a previously inserted string `word` that has the prefix `prefix`, and `false` otherwise.

**Example 1:**

**Input**
\[ "Trie ",  "insert ",  "search ",  "search ",  "startsWith ",  "insert ",  "search "\]
\[\[\], \[ "apple "\], \[ "apple "\], \[ "app "\], \[ "app "\], \[ "app "\], \[ "app "\]\]
**Output**
\[null, null, true, false, true, null, true\]

**Explanation**
Trie trie = new Trie();
trie.insert( "apple ");
trie.search( "apple ");   // return True
trie.search( "app ");     // return False
trie.startsWith( "app "); // return True
trie.insert( "app ");
trie.search( "app ");     // return True

**Constraints:**

*   `1 <= word.length, prefix.length <= 2000`
*   `word` and `prefix` consist only of lowercase English letters.
*   At most `3 * 104` calls **in total** will be made to `insert`, `search`, and `startsWith`.
Minimum Size Subarray Sum

Given an array of positive integers `nums` and a positive integer `target`, return _the **minimal length** of a_ _subarray_ _whose sum is greater than or equal to_ `target`. If there is no such subarray, return `0` instead.

**Example 1:**

**Input:** target = 7, nums = \[2,3,1,2,4,3\]
**Output:** 2
**Explanation:** The subarray \[4,3\] has the minimal length under the problem constraint.

**Example 2:**

**Input:** target = 4, nums = \[1,4,4\]
**Output:** 1

**Example 3:**

**Input:** target = 11, nums = \[1,1,1,1,1,1,1,1\]
**Output:** 0

**Constraints:**

*   `1 <= target <= 109`
*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 104`

**Follow up:** If you have figured out the `O(n)` solution, try coding another solution of which the time complexity is `O(n log(n))`.
Course Schedule II

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you **must** take course `bi` first if you want to take course `ai`.

*   For example, the pair `[0, 1]`, indicates that to take course `0` you have to first take course `1`.

Return _the ordering of courses you should take to finish all courses_. If there are many valid answers, return **any** of them. If it is impossible to finish all courses, return **an empty array**.

**Example 1:**

**Input:** numCourses = 2, prerequisites = \[\[1,0\]\]
**Output:** \[0,1\]
**Explanation:** There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is \[0,1\].

**Example 2:**

**Input:** numCourses = 4, prerequisites = \[\[1,0\],\[2,0\],\[3,1\],\[3,2\]\]
**Output:** \[0,2,1,3\]
**Explanation:** There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is \[0,1,2,3\]. Another correct ordering is \[0,2,1,3\].

**Example 3:**

**Input:** numCourses = 1, prerequisites = \[\]
**Output:** \[0\]

**Constraints:**

*   `1 <= numCourses <= 2000`
*   `0 <= prerequisites.length <= numCourses * (numCourses - 1)`
*   `prerequisites[i].length == 2`
*   `0 <= ai, bi < numCourses`
*   `ai != bi`
*   All the pairs `[ai, bi]` are **distinct**.
Design Add and Search Words Data Structure

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the `WordDictionary` class:

*   `WordDictionary()` Initializes the object.
*   `void addWord(word)` Adds `word` to the data structure, it can be matched later.
*   `bool search(word)` Returns `true` if there is any string in the data structure that matches `word` or `false` otherwise. `word` may contain dots `'.'` where dots can be matched with any letter.

**Example:**

**Input**
\[ "WordDictionary ", "addWord ", "addWord ", "addWord ", "search ", "search ", "search ", "search "\]
\[\[\],\[ "bad "\],\[ "dad "\],\[ "mad "\],\[ "pad "\],\[ "bad "\],\[ ".ad "\],\[ "b.. "\]\]
**Output**
\[null,null,null,null,false,true,true,true\]

**Explanation**
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord( "bad ");
wordDictionary.addWord( "dad ");
wordDictionary.addWord( "mad ");
wordDictionary.search( "pad "); // return False
wordDictionary.search( "bad "); // return True
wordDictionary.search( ".ad "); // return True
wordDictionary.search( "b.. "); // return True

**Constraints:**

*   `1 <= word.length <= 25`
*   `word` in `addWord` consists of lowercase English letters.
*   `word` in `search` consist of `'.'` or lowercase English letters.
*   There will be at most `2` dots in `word` for `search` queries.
*   At most `104` calls will be made to `addWord` and `search`.
Word Search II

Given an `m x n` `board` of characters and a list of strings `words`, return _all words on the board_.

Each word must be constructed from letters of sequentially adjacent cells, where **adjacent cells** are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

**Example 1:**

**Input:** board = \[\[ "o ", "a ", "a ", "n "\],\[ "e ", "t ", "a ", "e "\],\[ "i ", "h ", "k ", "r "\],\[ "i ", "f ", "l ", "v "\]\], words = \[ "oath ", "pea ", "eat ", "rain "\]
**Output:** \[ "eat ", "oath "\]

**Example 2:**

**Input:** board = \[\[ "a ", "b "\],\[ "c ", "d "\]\], words = \[ "abcb "\]
**Output:** \[\]

**Constraints:**

*   `m == board.length`
*   `n == board[i].length`
*   `1 <= m, n <= 12`
*   `board[i][j]` is a lowercase English letter.
*   `1 <= words.length <= 3 * 104`
*   `1 <= words[i].length <= 10`
*   `words[i]` consists of lowercase English letters.
*   All the strings of `words` are unique.
House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are **arranged in a circle.** That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given an integer array `nums` representing the amount of money of each house, return _the maximum amount of money you can rob tonight **without alerting the police**_.

**Example 1:**

**Input:** nums = \[2,3,2\]
**Output:** 3
**Explanation:** You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

**Example 2:**

**Input:** nums = \[1,2,3,1\]
**Output:** 4
**Explanation:** Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

**Example 3:**

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

**Constraints:**

*   `1 <= nums.length <= 100`
*   `0 <= nums[i] <= 1000`
Shortest Palindrome

You are given a string `s`. You can convert `s` to a palindrome by adding characters in front of it.

Return _the shortest palindrome you can find by performing this transformation_.

**Example 1:**

**Input:** s = "aacecaaa"
**Output:** "aaacecaaa"

**Example 2:**

**Input:** s = "abcd"
**Output:** "dcbabcd"

**Constraints:**

*   `0 <= s.length <= 5 * 104`
*   `s` consists of lowercase English letters only.
Kth Largest Element in an Array

Given an integer array `nums` and an integer `k`, return _the_ `kth` _largest element in the array_.

Note that it is the `kth` largest element in the sorted order, not the `kth` distinct element.

You must solve it in `O(n)` time complexity.

**Example 1:**

**Input:** nums = \[3,2,1,5,6,4\], k = 2
**Output:** 5

**Example 2:**

**Input:** nums = \[3,2,3,1,2,4,5,5,6\], k = 4
**Output:** 4

**Constraints:**

*   `1 <= k <= nums.length <= 105`
*   `-104 <= nums[i] <= 104`
Combination Sum III

Find all valid combinations of `k` numbers that sum up to `n` such that the following conditions are true:

*   Only numbers `1` through `9` are used.
*   Each number is used **at most once**.

Return _a list of all possible valid combinations_. The list must not contain the same combination twice, and the combinations may be returned in any order.

**Example 1:**

**Input:** k = 3, n = 7
**Output:** \[\[1,2,4\]\]
**Explanation:**
1 + 2 + 4 = 7
There are no other valid combinations.

**Example 2:**

**Input:** k = 3, n = 9
**Output:** \[\[1,2,6\],\[1,3,5\],\[2,3,4\]\]
**Explanation:**
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

**Example 3:**

**Input:** k = 4, n = 1
**Output:** \[\]
**Explanation:** There are no valid combinations.
Using 4 different numbers in the range \[1,9\], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

**Constraints:**

*   `2 <= k <= 9`
*   `1 <= n <= 60`
Contains Duplicate

Given an integer array `nums`, return `true` if any value appears **at least twice** in the array, and return `false` if every element is distinct.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-109 <= nums[i] <= 109`
The Skyline Problem

A city's **skyline** is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return _the **skyline** formed by these buildings collectively_.

The geometric information of each building is given in the array `buildings` where `buildings[i] = [lefti, righti, heighti]`:

*   `lefti` is the x coordinate of the left edge of the `ith` building.
*   `righti` is the x coordinate of the right edge of the `ith` building.
*   `heighti` is the height of the `ith` building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height `0`.

The **skyline** should be represented as a list of "key points " **sorted by their x-coordinate** in the form `[[x1,y1],[x2,y2],...]`. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate `0` and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

**Note:** There must be no consecutive horizontal lines of equal height in the output skyline. For instance, `[...,[2 3],[4 5],[7 5],[11 5],[12 7],...]` is not acceptable; the three lines of height 5 should be merged into one in the final output as such: `[...,[2 3],[4 5],[12 7],...]`

**Example 1:**

**Input:** buildings = \[\[2,9,10\],\[3,7,15\],\[5,12,12\],\[15,20,10\],\[19,24,8\]\]
**Output:** \[\[2,10\],\[3,15\],\[7,12\],\[12,0\],\[15,10\],\[20,8\],\[24,0\]\]
**Explanation:**
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

**Example 2:**

**Input:** buildings = \[\[0,2,3\],\[2,5,3\]\]
**Output:** \[\[0,3\],\[5,0\]\]

**Constraints:**

*   `1 <= buildings.length <= 104`
*   `0 <= lefti < righti <= 231 - 1`
*   `1 <= heighti <= 231 - 1`
*   `buildings` is sorted by `lefti` in non-decreasing order.
Contains Duplicate II

Given an integer array `nums` and an integer `k`, return `true` _if there are two **distinct indices**_ `i` _and_ `j` _in the array such that_ `nums[i] == nums[j]` _and_ `abs(i - j) <= k`.

**Example 1:**

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

**Example 2:**

**Input:** nums = \[1,0,1,1\], k = 1
**Output:** true

**Example 3:**

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

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-109 <= nums[i] <= 109`
*   `0 <= k <= 105`
Contains Duplicate III

You are given an integer array `nums` and two integers `indexDiff` and `valueDiff`.

Find a pair of indices `(i, j)` such that:

*   `i != j`,
*   `abs(i - j) <= indexDiff`.
*   `abs(nums[i] - nums[j]) <= valueDiff`, and

Return `true` _if such pair exists or_ `false` _otherwise_.

**Example 1:**

**Input:** nums = \[1,2,3,1\], indexDiff = 3, valueDiff = 0
**Output:** true
**Explanation:** We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums\[i\] - nums\[j\]) <= valueDiff --> abs(1 - 1) <= 0

**Example 2:**

**Input:** nums = \[1,5,9,1,5,9\], indexDiff = 2, valueDiff = 3
**Output:** false
**Explanation:** After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.

**Constraints:**

*   `2 <= nums.length <= 105`
*   `-109 <= nums[i] <= 109`
*   `1 <= indexDiff <= nums.length`
*   `0 <= valueDiff <= 109`
Maximal Square

Given an `m x n` binary `matrix` filled with `0`'s and `1`'s, _find the largest square containing only_ `1`'s _and return its area_.

**Example 1:**

**Input:** matrix = \[\[ "1 ", "0 ", "1 ", "0 ", "0 "\],\[ "1 ", "0 ", "1 ", "1 ", "1 "\],\[ "1 ", "1 ", "1 ", "1 ", "1 "\],\[ "1 ", "0 ", "0 ", "1 ", "0 "\]\]
**Output:** 4

**Example 2:**

**Input:** matrix = \[\[ "0 ", "1 "\],\[ "1 ", "0 "\]\]
**Output:** 1

**Example 3:**

**Input:** matrix = \[\[ "0 "\]\]
**Output:** 0

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m, n <= 300`
*   `matrix[i][j]` is `'0'` or `'1'`.
Count Complete Tree Nodes

Given the `root` of a **complete** binary tree, return the number of the nodes in the tree.

According to **[Wikipedia](http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees)**, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between `1` and `2h` nodes inclusive at the last level `h`.

Design an algorithm that runs in less than `O(n)` time complexity.

**Example 1:**

**Input:** root = \[1,2,3,4,5,6\]
**Output:** 6

**Example 2:**

**Input:** root = \[\]
**Output:** 0

**Example 3:**

**Input:** root = \[1\]
**Output:** 1

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 5 * 104]`.
*   `0 <= Node.val <= 5 * 104`
*   The tree is guaranteed to be **complete**.
Rectangle Area

Given the coordinates of two **rectilinear** rectangles in a 2D plane, return _the total area covered by the two rectangles_.

The first rectangle is defined by its **bottom-left** corner `(ax1, ay1)` and its **top-right** corner `(ax2, ay2)`.

The second rectangle is defined by its **bottom-left** corner `(bx1, by1)` and its **top-right** corner `(bx2, by2)`.

**Example 1:**

**Input:** ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
**Output:** 45

**Example 2:**

**Input:** ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
**Output:** 16

**Constraints:**

*   `-104 <= ax1 <= ax2 <= 104`
*   `-104 <= ay1 <= ay2 <= 104`
*   `-104 <= bx1 <= bx2 <= 104`
*   `-104 <= by1 <= by2 <= 104`
Basic Calculator

Given a string `s` representing a valid expression, implement a basic calculator to evaluate it, and return _the result of the evaluation_.

**Note:** You are **not** allowed to use any built-in function which evaluates strings as mathematical expressions, such as `eval()`.

**Example 1:**

**Input:** s =  "1 + 1 "
**Output:** 2

**Example 2:**

**Input:** s =  " 2-1 + 2  "
**Output:** 3

**Example 3:**

**Input:** s =  "(1+(4+5+2)-3)+(6+8) "
**Output:** 23

**Constraints:**

*   `1 <= s.length <= 3 * 105`
*   `s` consists of digits, `'+'`, `'-'`, `'('`, `')'`, and `' '`.
*   `s` represents a valid expression.
*   `'+'` is **not** used as a unary operation (i.e., `"+1 "` and `"+(2 + 3) "` is invalid).
*   `'-'` could be used as a unary operation (i.e., `"-1 "` and `"-(2 + 3) "` is valid).
*   There will be no two consecutive operators in the input.
*   Every number and running calculation will fit in a signed 32-bit integer.