Huahua’s Tech Road

花花酱 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;

}

};

花花酱 LeetCode 29. Divide Two Integers

By zxi on November 26, 2021

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹ − 1]. For this problem, if the quotient is strictly greater than 2³¹ - 1, then return 2³¹ - 1, and if the quotient is strictly less than -2³¹, then return -2³¹.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Example 3:

Input: dividend = 0, divisor = 1
Output: 0

Example 4:

Input: dividend = 1, divisor = 1
Output: 1

Constraints:

-2³¹ <= dividend, divisor <= 2³¹ - 1
divisor != 0

Solution: Binary / Bit Operation

The answer can be represented in binary format.

a / b = c
a >= b * Σ(d_i*2ⁱ)
c = Σ(d_i*2ⁱ)

e.g. 1: 10 / 3
=> 10 >= 3*(2¹ + 2⁰) = 3 * (2 + 1) = 9
ans = 2¹ + 2⁰ = 3

e.g. 2: 100 / 7
=> 100 >= 7*(2³ + 2²+2¹) = 7 * (8 + 4 + 2) = 7 * 14 = 98
ans = 2³+2²+2¹=8+4+2=14

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

C++

// Author: Huahua

class Solution {

public:

int divide(int A, int B) {

if (B == INT_MIN)

return A == INT_MIN ? 1 : 0;

if (A == INT_MIN) {

if (B == -1) return INT_MAX;

return B > 0 ? divide(A + B, B) - 1 : divide(A - B, B) + 1;

}

int a = abs(A);

int b = abs(B);

int ans = 0;

for (int x = 31; x >= 0; --x)

if (a >> x >= b)

ans += 1 << x, a -= b << x;

return (A > 0) == (B > 0) ? ans : -ans;

}

};

Huahua's Tech Road

花花酱 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++

花花酱 LeetCode 29. Divide Two Integers

Solution: Binary / Bit Operation

C++