【C++】【LeetCode】2020.4.30~2020.5.7
10. Regular Expression Matching
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-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 = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
class Solution {
public:
/*
s: adadasadad
p: **ada**.*ad
下一位是*
当前位不能匹配
*当做0处理
当前位能匹配
和s的下一位继续比较
如果出现匹配不上，p向后跳2位
下一位不是*
当前s和p比较
*/
bool isMatch(string& s, string& p, int i, int j) {
if (j == p.size()) {
//p已经匹配完了
return (i == s.size());
}
//j不到末尾
if (j == p.size() - 1 || (j < p.size() - 1 && p[j+1] != '*')) {
//p已经到了最后一位或者下一位不为*,当前字符必须匹配
if (i < s.size() && (s[i] == p [j] || p[j] == '.')) {
return isMatch(s, p, i+1, j+1);
}
return false;
}
//j下一位为*且不在末尾
while (i < s.size()) {
if (s[i] == p [j] || p[j] == '.') {
//当前位匹配,跳两位看看行不行
if (isMatch(s, p, i, j+2)) {
return true;
}
//跳不了,s跳1位
i++;
} else {
//当前位不匹配,只能跳两位
return isMatch(s, p, i, j+2);
}
}
//说明s到末尾了，跳过p的两位看看有没有剩余
return isMatch(s, p, i, j+2);
}
bool isMatch(string s, string p) {
return isMatch(s, p, 0, 0);
}
};
11. Container With Most Water
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
Example :
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
class Solution {
public:
/*
如果两边向中间靠，有比两边面积更大的柱子，则一定有一柱比两边的高
每次一定是从较低的柱子开始向中间靠拢
*/
int CalScore(vector<int>& height, int l, int r) {
if (l == -1 || r == -1) {
return 0;
}
int Val = height[l] < height[r] ? height[l] : height[r];
return Val * (r - l);
}
int maxArea(vector<int>& height) {
if (height.size() < 2) {
return 0;
}
int l = 0;
int r = height.size() - 1;
int res = 0;
while (l < r) {
int iScore = CalScore(height, l, r);
res = (iScore > res) ? iScore : res;
if (height[l] > height[r]) {
r--;
} else {
l++;
}
}
return res;
}
};
12. Integer to Roman
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.
Example 1:
Input: 3
Output: "III"
Example 2:
Input: 4
Output: "IV"
Example 3:
Input: 9
Output: "IX"
Example 4:
Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.
Example 5:
Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
class Solution {
public:
/*
900 CM
400 CD
90 XC
40 XL
9 IX
4 IV
*/
const int Count = 13;
string intToRoman(int num) {
string res = "";
string strs[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
int nums[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
for (int i = 0; i < Count; ++i) {
while (num >= nums[i]) {
res += strs[i];
num -= nums[i];
}
}
return res;
}
};
13. Roman to Integer
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
Example 1:
Input: "III"
Output: 3
Example 2:
Input: "IV"
Output: 4
Example 3:
Input: "IX"
Output: 9
Example 4:
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
class Solution {
public:
int GetNum(string* strs, int* nums, char c) {
string ss(1, c);
for (size_t k = 0; k < 7; ++k) {
if (strs[k] == ss) {
return nums[k];
}
}
return -1;
}
int romanToInt(string s) {
string strs[] = {"M","D","C","L","X","V","I"};
int nums[] = {1000,500,100,50,10,5,1};
int res = GetNum(strs, nums, s[0]);
for (size_t i = 1; i < s.size(); ++i) {
int l1 = GetNum(strs, nums, s[i - 1]);
int l2 = GetNum(strs, nums, s[i]);
res += l2;
if (l1 < l2) {
res -= 2 * l1;
}
}
return res;
}
};
14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int minLen = 99999;
for (size_t i = 0; i < strs.size(); ++i) {
if (strs[i].size() < minLen) {
minLen = strs[i].size();
}
}
if (minLen == 99999 || strs.size() < 1) {
return "";
}
size_t i = 0;
for (; i < minLen; ++i) {
char c = strs[0][i];
for (size_t j = 1; j < strs.size(); ++j) {
if (strs[j][i] != c) {
return strs[0].substr(0, i);
}
}
}
return strs[0].substr(0, i);
}
};
《【C++】【LeetCode】2020.4.30~2020.5.7》有1条留言