编程语言java算法
LeetCode 顺序刷题记录（11-20）
盛最多水的容器 **标签**：双指针 C++ Java 整数转罗马数字 **标签**：数学、字符串 方法一：模拟 方法二：硬编码 罗马数字转整数 **标签**：哈希表、数学、字符串 最长公共前缀 **标签**：字符串、二分查找 方法一：横向扫描 方法二：纵向扫描 方法三：分治 方法四：排序 三数之和 **标签**：排序、数组、双指针 最接近的三数之和 **标签**：排序、数组、双指针 电话号码的字…
盛最多水的容器 **标签**：双指针 C++ Java 整数转罗马数字 **标签**：数学、字符串 方法一：模拟 方法二：硬编码 罗马数字转整数 **标签**：哈希表、数学、字符串 最长公共前缀 **标签**：字符串、二分查找 方法一：横向扫描 方法二：纵向扫描 方法三：分治 方法四：排序 三数之和 **标签**：排序、数组、双指针 最接近的三数之和 **标签**：排序、数组、双指针 电话号码的字…
标签：双指针
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int ret = 0;
while (left < right) {
int v = min(height[left], height[right]) * (right - left);
ret = max(ret, v);
if (height[left] < height[right]) {
++left;
} else {
--right;
}
}
return ret;
}
};
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
int currentArea = Math.min(height[left], height[right]) * (right - left);
maxArea = Math.max(maxArea, currentArea);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
标签：数学、字符串
const 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"}
};
class Solution {
public:
string intToRoman(int num) {
string roman;
for (const auto& [value, symbol] : valueSymbols) {
while (num >= value) {
num -= value;
roman += symbol;
}
if (num == 0) break;
}
return roman;
}
};
const string thousands[] = {"", "M", "MM", "MMM"};
const string hundreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
const string tens[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
const string ones[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
class Solution {
public:
string intToRoman(int num) {
return thousands[num / 1000] + hundreds[num % 1000 / 100] + tens[num % 100 / 10] + ones[num % 10];
}
};
标签：哈希表、数学、字符串
class Solution {
private:
unordered_map<char, int> symbolValue = {
{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
{'C', 100}, {'D', 500}, {'M', 1000}
};
public:
int romanToInt(string s) {
int ret = 0;
int n = s.size();
for (int i = 0; i < n; ++i) {
int value = symbolValue[s[i]];
if (i < n - 1 && value < symbolValue[s[i + 1]]) {
ret -= value;
} else {
ret += value;
}
}
return ret;
}
};
标签：字符串、二分查找
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string ret = strs[0];
for (int i = 1; i < strs.size(); i++) {
ret = findCommon(ret, strs[i]);
}
return ret;
}
string findCommon(string& s1, string& s2) {
int i = 0;
while (i < min(s1.size(), s2.size()) && s1[i] == s2[i]) {
i++;
}
return s1.substr(0, i);
}
};
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
int length = strs[0].size();
int count = strs.size();
for (int i = 0; i < length; i++) {
char c = strs[0][i];
for (int j = 1; j < count; j++) {
if (i == strs[j].size() || strs[j][i] != c) {
return strs[0].substr(0, i);
}
}
}
return strs[0];
}
};
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
return longestCommonPrefix(strs, 0, strs.size() - 1);
}
string longestCommonPrefix(const vector<string>& strs, int start, int end) {
if (start == end) return strs[start];
int mid = (start + end) / 2;
string lcpLeft = longestCommonPrefix(strs, start, mid);
string lcpRight = longestCommonPrefix(strs, mid + 1, end);
return commonPrefix(lcpLeft, lcpRight);
}
string commonPrefix(const string& lcpLeft, const string& lcpRight) {
int minLength = min(lcpLeft.size(), lcpRight.size());
for (int i = 0; i < minLength; i++) {
if (lcpLeft[i] != lcpRight[i]) {
return lcpLeft.substr(0, i);
}
}
return lcpLeft.substr(0, minLength);
}
};
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
sort(strs.begin(), strs.end());
string start = strs.front();
string end = strs.back();
int n = min(start.size(), end.size());
int i = 0;
for (; i < n && start[i] == end[i]; i++);
return start.substr(0, i);
}
};
标签：排序、数组、双指针
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ret;
int n = nums.size();
for (int i = 0; i < n; ++i) {
if (nums[i] > 0) break;
int left = i + 1;
int right = n - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum > target) {
--right;
} else if (sum < target) {
++left;
} else {
ret.push_back({nums[i], nums[left], nums[right]});
++left;
--right;
while (left < right && nums[left] == nums[left - 1]) ++left;
while (left < right && nums[right] == nums[right + 1]) --right;
}
}
while (i < n - 1 && nums[i] == nums[i + 1]) ++i;
}
return ret;
}
};
标签：排序、数组、双指针
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
int ret = 1e7;
auto update = [&](int cur) {
if (abs(cur - target) < abs(ret - target)) {
ret = cur;
}
};
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) return target;
update(sum);
if (sum > target) {
right--;
while (left < right && nums[right] == nums[right + 1]) right--;
} else {
left++;
while (left < right && nums[left] == nums[left - 1]) left++;
}
}
}
return ret;
}
};
标签：哈希表、字符串、回溯
class Solution {
private:
string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string path;
vector<string> ret;
void dfs(string& digits, int pos) {
if (pos == digits.size()) {
ret.push_back(path);
return;
}
for (const auto& ch : hash[digits[pos] - '0']) {
path.push_back(ch);
dfs(digits, pos + 1);
path.pop_back();
}
}
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
dfs(digits, 0);
return ret;
}
};
标签：排序、数组、双指针
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
if (n < 4) return {};
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 3; i++) {
for (int j = i + 1; j < n - 2; j++) {
long long newtarget = (long long)target - nums[i] - nums[j];
int left = j + 1, right = n - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum > newtarget) {
right--;
} else if (sum < newtarget) {
left++;
} else {
ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
}
}
while (j < n - 2 && nums[j] == nums[j + 1]) j++;
}
(i < n - && nums[i] == nums[i + ]) i++;
}
ret;
}
};
标签：栈、链表、双指针
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* newhead = new ListNode(0, head);
int count = 0;
ListNode* cur = head;
while (cur) {
cur = cur->next;
count++;
}
int gap = count - n;
cur = newhead;
while (gap--) cur = cur->next;
ListNode* del = cur->next;
cur->next = del->next;
cur = newhead->next;
delete del;
delete newhead;
return cur;
}
};
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* newhead = new ListNode(0, head);
stack<ListNode*> s;
ListNode* cur = newhead;
while (cur) {
s.push(cur);
cur = cur->next;
}
for (int i = 0; i < n; ++i) {
s.pop();
}
ListNode* prev = s.top();
ListNode* del = prev->next;
prev->next = del->next;
cur = newhead->next;
delete del;
delete newhead;
return cur;
}
};
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode newhead;
newhead.next = head;
ListNode* slow = &newhead;
ListNode* fast = &newhead;
while (n--) {
fast = fast->next;
}
while (fast->next) {
slow = slow->next;
fast = fast->next;
}
ListNode* del = slow->next;
slow->next = del->next;
delete del;
return newhead.next;
}
};
标签：栈、哈希表、字符串
class Solution {
public:
bool isValid(string s) {
int n = s.size();
stack<char> st;
for (int i = 0; i < n; i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
st.push(s[i]);
} else if (s[i] == ')' && !st.empty() && st.top() == '(') {
st.pop();
} else if (s[i] == '}' && !st.empty() && st.top() == '{') {
st.pop();
} else if (s[i] == ']' && !st.empty() && st.top() == '[') {
st.pop();
} else {
return false;
}
}
return st.empty();
}
};
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if (n % 2 == 1) return false;
unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
stack<char> stk;
for (const char& ch : s) {
if (pairs.count(ch)) {
if (stk.empty() || stk.top() != pairs[ch]) return false;
stk.pop();
} else {
stk.push(ch);
}
}
return stk.empty();
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online