Huahua’s Tech Road

花花酱 LeetCode 65. Valid Number

By zxi on November 26, 2021

A valid number can be split up into these components (in order):

A decimal number or an integer.
(Optional) An 'e' or 'E', followed by an integer.

A decimal number can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One of the following formats:
1. One or more digits, followed by a dot '.'.
2. One or more digits, followed by a dot '.', followed by one or more digits.
3. A dot '.', followed by one or more digits.

An integer can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One or more digits.

For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"], while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].

Given a string s, return true if s is a valid number.

Example 1:

Input: s = "0"
Output: true

Example 2:

Input: s = "e"
Output: false

Example 3:

Input: s = "."
Output: false

Example 4:

Input: s = ".1"
Output: true

Constraints:

1 <= s.length <= 20
s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

Solution: Rule checking

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool isNumber(string s) {

for (int i = 0; i < s.length(); ++i)

if (s[i] != ' ') {

s = s.substr(i);

break;

}

while (!s.empty() && s.back() == ' ') s.pop_back();

bool dot = false;

bool e = false;

bool digit = false;

for (int i = 0; i < s.length(); ++i) {

s[i] = tolower(s[i]);

if (isdigit(s[i])) {

digit = true;

} else if (s[i] == '.') {

if (e || dot) return false;

dot = true;

} else if (s[i] == 'e') {

if (e || !digit) return false;

e = true;

digit = false;

} else if (s[i] == '-' || s[i] == '+') {

if (i != 0 && s[i - 1] != 'e')

return false;

} else {

return false;

}

return digit;

}

};

花花酱 LeetCode 41. First Missing Positive

By zxi on November 26, 2021

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

Constraints:

1 <= nums.length <= 5 * 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

Solution: Marking

First pass, marking nums[i] to INT_MAX if nums[i] <= 0
Second pass, use a negative number to mark the presence of a number x at nums[x – 1]
Third pass, the first positive number is the missing index i, return i +1
If not found return n + 1.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int firstMissingPositive(vector<int>& nums) {

const int n = nums.size();

for (int& x : nums)

if (x <= 0) x = INT_MAX;

for (int x : nums) {

x = abs(x);

if (x >= 1 && x <= n && nums[x - 1] > 0)

nums[x - 1] *= -1;

}

for (int i = 0; i < n; ++i)

if (nums[i] > 0)

return i + 1;

return n + 1;

}

};

花花酱 LeetCode 34. Find First and Last Position of Element in Sorted Array

By zxi on November 26, 2021

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums is a non-decreasing array.
-10⁹ <= target <= 10⁹

Solution: Binary Search

Use lower_bound to find first
Use upper_bound to find last + 1

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> searchRange(vector<int>& nums, int target) {

auto it = lower_bound(begin(nums), end(nums), target);

int l = (it == end(nums) || *it != target) ? -1 : it - begin(nums);

auto it2 = upper_bound(begin(nums), end(nums), target);

int r = (it2 == begin(nums) || *prev(it2) != target) ? -1 : prev(it2) - begin(nums);

return {l, r};

}

};

花花酱 LeetCode 33. Search in Rotated Sorted Array

By zxi on November 26, 2021

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10⁴ <= target <= 10⁴

Solution: Binary Search

If the current range [l, r] is ordered, reduce to normal binary search. Otherwise, determine the range to search next by comparing target and nums[0].

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int search(vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

int m = l + (r - l) / 2;

int x = (nums[m] < nums[0]) == (target < nums[0])

? nums[m]

: target < nums[0] ? INT_MIN : INT_MAX;

if (x < target)

l = m + 1;

else if (x > target)

r = m;

else

return m;

}

return -1;

}

};

花花酱 LeetCode 30. Substring with Concatenation of All Words

By zxi on November 26, 2021

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Constraints:

1 <= s.length <= 10⁴
s consists of lower-case English letters.
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] consists of lower-case English letters.

Solution: Hashtable + Brute Force

Try every index and use a hashtable to check coverage.

Time complexity: O(n*m*l)
Space complexity: O(m*l)

C++

// Author: Huahua

class Solution {

public:

vector<int> findSubstring(string_view s, vector<string>& words) {

const int n = s.length();

const int m = words.size();

const int l = words[0].size();

if (m * l > n) return {};

unordered_map<string_view, int> freq;

for (const string& word : words) ++freq[word];

vector<int> ans;

for (int i = 0; i <= n - m * l; ++i) {

unordered_map<string_view, int> seen;

int count = 0;

for (int k = 0; k < m; ++k) {

string_view t = s.substr(i + k * l, l);

auto it = freq.find(t);

if (it == end(freq)) break;

if (++seen[t] > it->second) break;

++count;

}

if (count == m) ans.push_back(i);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 65. Valid Number

Solution: Rule checking

C++

花花酱 LeetCode 41. First Missing Positive

Solution: Marking

C++

花花酱 LeetCode 34. Find First and Last Position of Element in Sorted Array

C++

花花酱 LeetCode 33. Search in Rotated Sorted Array

Solution: Binary Search

C++

花花酱 LeetCode 30. Substring with Concatenation of All Words

Solution: Hashtable + Brute Force

C++