1.罗马数字转整数
用unordered_map去存罗马数字对应的数值，分情况讨论，把所有情况都列出来即可
class Solution {
public:
unordered_map<char, int> mp = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}
};
int romanToInt(string s) {
int n = s.length();
int sum = 0;
for (int i = 0; i < n; i++) {
if ((i + 1 < n) && ((s[i] == 'I' && (s[i + 1] == 'V' || s[i + 1] == 'X')) ||
(s[i] == 'X' && (s[i + 1] == 'L' || s[i + 1] == 'C')) ||
(s[i] == 'C' && (s[i + 1] == 'D' || s[i + 1] == 'M'))))
{
sum = sum + mp[s[i + 1]] - mp[s[i]];
i++;
} else {
sum += mp[s[i]];
}
}
return sum;
}
};
2.整数转罗马数字
用vector<pair<int, string>>去存罗马数字symbol对应的数值val，如果val比num小，则num -= val; string ans + symbol
注意：
1.存储方式是vector<pair<int, string>> valueSymbols
2.遍历方式for (const auto &[value, symbol]: valueSymbols)
class Solution {
public:
vector<pair<int, string>> valueSymbols = {
{1000, "M"},
{900, "CM"},
{500, "D"},
{400, "CD"},
{100, "C"},
{90, "XC"},
{50, "L"},
{40, "XL"},
{10, "X"},
{9, "IX"},
{5, "V"},
{4, "IV"},
{1, "I"},
};
string intToRoman(int num) {
string ans = "";
for (const auto &[value, symbol]: valueSymbols) {
while (num >= value) {
num -= value;
ans += symbol;
}
if (num == 0) {
break;
}
}
return ans;
}
};
3.三数之和
遍历数组，target - nums[i], 按两数之和的方法求解。注意：答案中不可以包含重复的三元组。
需要注意的点：去重！！！！
左右指针相同去重
while (l < r && nums[r] == nums[r - 1]) r–;
起始位置相同去重
if (i > 0 && nums[i] == nums[i - 1]) continue;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int l = 0, r = nums.size() - 1, sum = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = nums.size() - 1;
int target = - nums[i];
while (l < r) {
if (nums[l] + nums[r] < target) {
l++;
} else if (nums[l] + nums[r] > target) {
r--;
} else {
ans.push_back({nums[i], nums[l], nums[r]});
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
r--;
l++;
}
}
}
return ans;
}
};
4.四数之和
与题目3相同，注意题目：不重复的四元组！这个题可以遍历数组，固定一个元素，target - nums[i]，就变成了3数之和的解法。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int target_tmp;
for (int i = 0; i < nums.size() - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size() - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1, r = nums.size() - 1;
target_tmp = target - nums[i] - nums[j];
while (l < r) {
if ((long)nums[l] + nums[r] < target_tmp) {
l++;
} else if ((long)nums[l] + nums[r] > target_tmp) {
r--;
} else {
ans.push_back({nums[i], nums[j], nums[l], nums[r]});
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++, r--;
}
}
}
}
return ans;
}
};
5.电话号码的字母组合
可以排列组合的题目都可以首先联想到全排列，递归时先判断是否符合递归终止条件，不符合则依次加当前电话号码位置对应的字母，加完后递归，
class Solution {
public:
unordered_map<char, string> mp ={
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
vector<string> ans;
string tmp;
vector<string> letterCombinations(string digits) {
if (digits.size() == 0) return ans;
dfs(digits, mp, 0);
return ans;
}
void dfs(string digits, unordered_map<char, string>& mp, int index) {
if (tmp.size() == digits.size()) {
ans.push_back(tmp);
return;
}
for (auto ch : mp[digits[index]]) {
tmp += ch;
dfs(digits, mp, index + 1);
tmp.pop_back();
}
}
};
6.有效的括号
碰到左括号入栈，右括号出栈看是否匹配
class Solution {
public:
bool isValid(string s) {
stack<char> valid;
for (auto ch: s){
if (ch == '(' || ch == '[' || ch == '{') {
valid.push(ch);
} else {
if(valid.empty()) return false;
auto left = valid.top();
valid.pop();
if ((ch == ')' && left != '(') || (ch == ']' && left != '[') || (ch == '}' && left != '{')) {
return false;
}
}
}
return valid.empty() ? true : false;
}
};
