LeetCode Algorithm 0041 - 0045
文章目录
0041 - First Missing Positive (Hard)
Problem Link: https://leetcode.com/problems/first-missing-positive/description/
Description
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
Note:
Your algorithm should run in O(n) time and uses constant extra space.
Solution C++
#pragma once
#include "pch.h"
// Problem: https://leetcode.com/problems/first-missing-positive/description/
namespace P41FirstMissingPositive
{
class Solution
{
public:
int firstMissingPositive(vector<int>& nums)
{
// 寻找缺失的最小正整数
// 要求 时间O(n) 与 只使用常数空间O(1)
// 复杂度的限制，让许多方法不可行，比如排序再遍历，计数等
if (nums.empty())
{
return 1;
}
int size = nums.size();
for (int i = 0; i < size; i++)
{
// 将数字放入对应的 `下标 + 1` 中
if (nums[i] > 0 && nums[i] <= size && nums[i] != nums[nums[i] - 1])
{
swap(nums[i], nums[nums[i] - 1]);
i--;
}
}
for (int i = 0; i < size; i++)
{
if (nums[i] != i + 1)
{
return i + 1;
}
}
return size + 1;
}
};
}
0042 - Trapping Rain Water (Hard)
Problem Link: https://leetcode.com/problems/trapping-rain-water/description/
Description
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Solution C++
#pragma once
#include "pch.h"
// Problem: https://leetcode.com/problems/trapping-rain-water/description/
namespace P42TrappingRainWater
{
class Solution
{
public:
int trap(vector<int>& height)
{
if (height.empty() || height.size() <= 2)
{
return 0;
}
// 方法：从低值向高值移动，时间O(n)
// 有两种方式：1、直接累加空白。 2、用面积 - 黑色方块
#if true // 方法1
int left = 0;
int right = height.size() - 1;
int result = 0;
int leftMax = 0, rightMax = 0; // 山峰的最大值
while (left < right)
{
if (height[left] < height[right])
{
if (height[left] >= leftMax)
{
leftMax = height[left];
}
else
{
result += leftMax - height[left]; // 最大值 - 当前黑色方块
}
left++;
}
else
{
if (height[right] >= rightMax)
{
rightMax = height[right];
}
else
{
result += rightMax - height[right]; // 最大值 - 当前黑色方块
}
right--;
}
}
return result;
#endif // 方法1结尾
#if false // 方法2
int left = 0;
int right = height.size() - 1;
// 最左端的山峰
for (left; left < height.size() - 1; left++)
{
if (height[left] != 0 && height[left] > height[left + 1])
{
break;
}
}
// 最右端的山峰
for (right; right > left; right--)
{
if (height[right] != 0 && height[right] > height[right - 1])
{
break;
}
}
// 如果只有一个山峰
if (left == right)
{
return 0;
}
// lowIndex：低的山峰坐标
// highIndex: 高的山峰坐标
// dir: 从低向高的方向，1从左向右，-1从右向左
// i：当前坐标
int i, dir, lowIndex, highIndex;
if (height[left] > height[right])
{
lowIndex = right;
highIndex = left;
dir = -1;
}
else
{
lowIndex = left;
highIndex = right;
dir = 1;
}
i = lowIndex + dir;
int midCubeCount = 0; // 两个山峰之间的黑色Cube数量
int result = 0; // 结果
// 开始移动，当达到最高山峰时停止
while (lowIndex != highIndex)
{
if (height[i] < height[lowIndex])
{
if (height[i] != 0)
{
midCubeCount += height[i];
}
}
else // 如果遇到的山峰比最低的山峰(lowIndex)高
{
// 长 x 宽 - 中间的黑方格
result += (abs(i - lowIndex) - 1) * height[lowIndex] - midCubeCount;
midCubeCount = 0;
// 如果遇到的山峰比最高的山峰(highIndex)还高，则切换方向
if (height[i] > height[highIndex])
{
lowIndex = highIndex;
highIndex = i;
dir = -dir;
i = lowIndex;
}
else
{
lowIndex = i;
}
}
i += dir;
}
return result;
#endif // 方法2结尾
}
};
}
0043 - Multiply Strings (Medium)
Problem Link: https://leetcode.com/problems/multiply-strings/description/
Description
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"
Note:
The length of both
num1andnum2is < 110.Both
num1andnum2contain only digits0-9.Both
num1andnum2do not contain any leading zero, except the number 0 itself.You must not use any built-in BigInteger library or convert the inputs to integer directly.
Solution C++
#pragma once
#include "pch.h"
// Problem: https://leetcode.com/problems/multiply-strings/description/
namespace P43MultiplyStrings
{
class Solution
{
public:
string multiply(string num1, string num2)
{
// 题目明确说，输入只有0-9，而且除了0之外开头都不为0。
// 还要求不能将整个string直接转换成数字，不能使用大数库（built-in BigInteger）
int len1 = num1.size();
int len2 = num2.size();
if (len1 == 0 || len2 == 0
|| len1 >= 110 || len2 >= 110
|| num1 == "0" || num2 == "0")
{
return "0";
}
// 每一位数字
int maxLen = max(len1, len2);
vector<int> num1Int = vector<int>(maxLen, 0);
vector<int> num2Int = vector<int>(maxLen, 0);
// 从右向左填充每个数字
for (int i = 0; i < len1; i++)
{
num1Int[(maxLen - len1) + i] = num1[i] - '0';
}
for (int i = 0; i < len2; i++)
{
num2Int[(maxLen - len2) + i] = num2[i] - '0';
}
vector<int> resultArray = vector<int>(maxLen * 2, 0);
for (int i2 = maxLen - 1; i2 >= 0; i2--)
{
for (int i1 = maxLen - 1; i1 >= 0; i1--)
{
int product = num2Int[i2] * num1Int[i1];
int row = i2;
int col = i2 + i1 + 1;
resultArray[col] += product % 10;
resultArray[col - 1] += product / 10;
while (resultArray[col] > 9)
{
resultArray[col - 1] += resultArray[col] / 10;
resultArray[col] %= 10;
col--;
}
}
}
string result = "";
for (int i = 0; i < maxLen * 2; i++)
{
if (result == "" && resultArray[i] == 0)
{
continue;
}
result += to_string(resultArray[i]);
}
return result;
}
};
}
0044 - Wildcard Matching (Hard)
Problem Link: https://leetcode.com/problems/wildcard-matching/description/
Description
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
scould be empty and contains only lowercase lettersa-z.pcould be empty and contains only lowercase lettersa-z, and characters like?or*.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input:
s = "acdcb"
p = "a*c?b"
Output: false
Solution C++
#pragma once
#include "pch.h"
// Problem: https://leetcode.com/problems/wildcard-matching/description/
namespace P44WildcardMatching
{
class Solution
{
private:
static const char k_Letter = '?';
static const char k_Any = '*';
public:
bool isMatch(string s, string p)
{
if (p.empty())
{
return s.empty() ? true : false;
}
if (p == "*")
{
return true;
}
if (s.empty())
{
return false;
}
int sSize = s.size();
int pSize = p.size();
int anyIndex = -1;
int matchIndex = 0;
int j = 0;
for (int i = 0; i < sSize; i++)
{
if (j < pSize && (s[i] == p[j] || p[j] == k_Letter))
{
j++;
}
else if (j < pSize && p[j] == k_Any)
{
anyIndex = j;
matchIndex = i;
i--;
j++;
}
else if (anyIndex != -1)
{
j = anyIndex + 1;
matchIndex++;
i = matchIndex - 1;
}
else
{
return false;
}
}
while (j < pSize && p[j] == k_Any)
{
j++;
}
return j == pSize;
}
};
}
0045 - Jump Game II (Hard)
Problem Link: https://leetcode.com/problems/jump-game-ii/description/
Description
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
Solution C++
#pragma once
#include "pch.h"
// Problem: https://leetcode.com/problems/jump-game-ii/description/
namespace P45JumpGameII
{
#if true // 贪心算法
class Solution
{
public:
int jump(vector<int>& nums)
{
if (nums.empty() || nums.size() == 1)
{
return 0;
}
// 题目已经说明输入参数永远有解
// 以官方例子[2,3,1,1,4]来说
// nums[0] = 2 , 可以跳 [1, 2]
// nums[1] = 3 , 可以跳 [1, 2, 3]
// nums[2] = 1 , 可以跳 [1]
// nums[3] = 1 , 可以跳 [1]
// nums[4] = 4
// 每次能跳的最大距离，只需要跳一次
// 例如 从nums[1] 调到 num[4]
// 已经涵盖了 nums[2] 与 nums[3] 能跳的距离。
int result = 0;
int curIndex = 0;
int largest = 0;
for (int i = 0; i < nums.size() - 1; i++)
{
largest = max(largest, i + nums[i]);
if (i == curIndex)
{
result++;
curIndex = largest;
}
if (curIndex >= nums.size() - 1)
{
break;
}
}
return result;
}
};
#endif
#if false // 递归穷举
class Solution
{
public:
int jump(vector<int>& nums)
{
if (nums.empty() || nums.size() == 1)
{
return 0;
}
// 题目已经说明输入参数永远有解
int result = INT_MAX;
vector<int> path;
jumping(nums, nums.size(), path, 0, result);
return result;
}
private:
void jumping(vector<int>& nums, int size, vector<int>& path, int startIndex, int& result)
{
if (nums[startIndex] == 0)
{
return;
}
for (int i = 1; i <= nums[startIndex]; i++)
{
path.push_back(startIndex);
if (startIndex + i == size - 1)
{
result = min(result, (int)path.size());
}
else if (startIndex + i < size - 1)
{
jumping(nums, size, path, startIndex + i, result);
}
path.pop_back();
}
}
};
#endif
}