A continuación se presenta una guía concisa con soluciones a problemas de LeetCode que aparecen con alta frecuencia en listas como CodeTop. Se ha priorizado la claridad y la eficiencia del código.
3. Subcadena más larga sin caracteres repetidos
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> freq;
int maxLen = 0;
for (int right = 0, left = 0; right < s.size(); right++) {
freq[s[right]]++;
while (freq[s[right]] > 1) {
freq[s[left]]--;
left++;
}
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
};
395. Subcadena más larga con al menos K caracteres repetidos
class Solution {
public:
int k;
unordered_map<char,int> counter;
void addChar(char c, int &uniqueCount, int &validCount) {
if (counter[c] == 0) uniqueCount++;
counter[c]++;
if (counter[c] == k) validCount++;
}
void removeChar(char c, int &uniqueCount, int &validCount) {
if (counter[c] == k) validCount--;
counter[c]--;
if (counter[c] == 0) uniqueCount--;
}
int longestSubstring(string s, int _k) {
k = _k;
int result = 0;
for (int limit = 1; limit <= 26; limit++) {
counter.clear();
int unique = 0, valid = 0;
for (int left = 0, right = 0; right < s.size(); right++) {
addChar(s[right], unique, valid);
while (unique > limit) {
removeChar(s[left], unique, valid);
left++;
}
if (unique == valid) {
result = max(result, right - left + 1);
}
}
}
return result;
}
};
206. Invertir lista enlazada
// Versión iterativa
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
while (head) {
ListNode* nextNode = head->next;
head->next = prev;
prev = head;
head = nextNode;
}
return prev;
}
};
// Versión recursiva
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* nextNode = head->next;
ListNode* newHead = reverseList(nextNode);
nextNode->next = head;
head->next = nullptr;
return newHead;
}
};
146. Caché LRU
struct Node {
int key, value;
Node *prev, *next;
Node() : key(0), value(0), prev(nullptr), next(nullptr) {}
};
class LRUCache {
public:
unordered_map<int, Node*> cache;
int currentSize, capacity;
Node *head, *tail;
LRUCache(int cap) : capacity(cap), currentSize(0) {
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!cache.count(key)) return -1;
Node* node = cache[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (cache.count(key)) {
Node* node = cache[key];
node->value = value;
moveToHead(node);
} else {
Node* newNode = new Node();
newNode->key = key;
newNode->value = value;
addToHead(newNode);
cache[key] = newNode;
currentSize++;
if (currentSize > capacity) {
Node* toRemove = tail->prev;
removeNode(toRemove);
cache.erase(toRemove->key);
delete toRemove;
currentSize--;
}
}
}
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToHead(Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
void moveToHead(Node* node) {
removeNode(node);
addToHead(node);
}
};
215. K-ésimo elemento más grande en un arreglo
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
return quickSelect(nums, 0, n - 1, n - k);
}
int quickSelect(vector<int>& nums, int l, int r, int k) {
if (l == r) return nums[l];
int i = l - 1, j = r + 1;
int pivot = nums[l + (r - l) / 2];
while (i < j) {
while (nums[++i] < pivot);
while (nums[--j] > pivot);
if (i < j) swap(nums[i], nums[j]);
}
if (k <= j) return quickSelect(nums, l, j, k);
else return quickSelect(nums, j + 1, r, k);
}
};
25. Invertir lista enlazada en grupos de K
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || !head->next) return head;
ListNode* tail = head;
for (int i = 0; i < k; i++) {
if (!tail) return head;
tail = tail->next;
}
ListNode* newHead = reverseSegment(head, tail);
head->next = reverseKGroup(tail, k);
return newHead;
}
ListNode* reverseSegment(ListNode* start, ListNode* end) {
ListNode* prev = nullptr;
while (start != end) {
ListNode* nextNode = start->next;
start->next = prev;
prev = start;
start = nextNode;
}
return prev;
}
};
15. Suma de tres números (3Sum)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n - 2; 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 > 0) right--;
else if (sum < 0) left++;
else {
result.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
}
}
}
return result;
}
};
53. Subarreglo con suma máxima
// Algoritmo de Kadane
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = INT_MIN;
int currentSum = 0;
for (int num : nums) {
currentSum = max(num, currentSum + num);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
};
21. Combinar dos listas enlazadas ordenadas
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (!list1) return list2;
if (!list2) return list1;
if (list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
1. Suma de dos números
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> indexMap;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (indexMap.count(complement)) {
return {indexMap[complement], i};
}
indexMap[nums[i]] = i;
}
return {};
}
};
102. Recorrido por niveles de un árbol binario
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> levels;
if (!root) return levels;
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
while (!nodeQueue.empty()) {
int size = nodeQueue.size();
vector<int> currentLevel;
for (int i = 0; i < size; i++) {
TreeNode* node = nodeQueue.front();
nodeQueue.pop();
currentLevel.push_back(node->val);
if (node->left) nodeQueue.push(node->left);
if (node->right) nodeQueue.push(node->right);
}
levels.push_back(currentLevel);
}
return levels;
}
};
200. Número de islas
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int rows = grid.size(), cols = grid[0].size();
int islandCount = 0;
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
islandCount++;
queue<pair<int,int>> q;
q.push({i, j});
grid[i][j] = '0';
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (auto &d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == '1') {
grid[nx][ny] = '0';
q.push({nx, ny});
}
}
}
}
}
}
return islandCount;
}
};
121. Mejor momento para comprar y vender acciones (1 transacción)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX;
int profit = 0;
for (int price : prices) {
if (price < minPrice) minPrice = price;
else profit = max(profit, price - minPrice);
}
return profit;
}
};
20. Paréntesis válidos
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
stk.push(c);
} else {
if (stk.empty()) return false;
char top = stk.top(); stk.pop();
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
return false;
}
}
}
return stk.empty();
}
};
46. Permutaciones
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
vector<bool> used(nums.size(), false);
backtrack(nums, current, used, result);
return result;
}
void backtrack(vector<int>& nums, vector<int>& current, vector<bool>& used, vector<vector<int>>& result) {
if (current.size() == nums.size()) {
result.push_back(current);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (!used[i]) {
used[i] = true;
current.push_back(nums[i]);
backtrack(nums, current, used, result);
used[i] = false;
current.pop_back();
}
}
}
};
141. Detectar ciclo en lista enlazada
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head->next) return false;
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};
236. Ancestro común más cercano de un árbol binario
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}
};
23. Combinar K listas enlazadas ordenadas
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
return divideAndConquer(lists, 0, lists.size() - 1);
}
ListNode* divideAndConquer(vector<ListNode*>& lists, int left, int right) {
if (left == right) return lists[left];
int mid = left + (right - left) / 2;
ListNode* l1 = divideAndConquer(lists, left, mid);
ListNode* l2 = divideAndConquer(lists, mid + 1, right);
return mergeTwo(l1, l2);
}
ListNode* mergeTwo(ListNode* a, ListNode* b) {
if (!a) return b;
if (!b) return a;
if (a->val < b->val) {
a->next = mergeTwo(a->next, b);
return a;
} else {
b->next = mergeTwo(a, b->next);
return b;
}
}
};
42. Atrapando agua de lluvia
class Solution {
public:
int trap(vector<int>& height) {
int left = 0, right = height.size() - 1;
int leftMax = 0, rightMax = 0, total = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax)
leftMax = height[left];
else
total += leftMax - height[left];
left++;
} else {
if (height[right] >= rightMax)
rightMax = height[right];
else
total += rightMax - height[right];
right--;
}
}
return total;
}
};
56. Fusionar intervalos
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
merged.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] <= merged.back()[1]) {
merged.back()[1] = max(merged.back()[1], intervals[i][1]);
} else {
merged.push_back(intervals[i]);
}
}
return merged;
}
};
2. Suma de dos números (en listas enlazadas)
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* current = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
if (l1) { carry += l1->val; l1 = l1->next; }
if (l2) { carry += l2->val; l2 = l2->next; }
current->next = new ListNode(carry % 10);
carry /= 10;
current = current->next;
}
return dummy.next;
}
};
239. Máximo de una ventana deslizante
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq; // almacena índices
vector<int> result;
for (int i = 0; i < nums.size(); i++) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) result.push_back(nums[dq.front()]);
}
return result;
}
};
Nota: Los códigos mostrados priorizan la simplicidad y la eficiencia, siguiendo las convenciones de C++ moderno. Se recomienda practicar la escritura a mano y la comprensión profunda de cada algoritmo.