1. Three Numbers in an Array that Sum to a Target Value
Problem Description: Given an integer array and a target value, find all unique triplets in the array that sum up to the target value.Input and Output: Input the array and target value, output all triplets that meet the condition.Code Implementation:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums, int target) {
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; // Skip duplicates
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
result.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) ++left; // Skip duplicates
while (left < right && nums[right] == nums[right - 1]) --right; // Skip duplicates
++left;
--right;
} else if (sum < target) {
++left;
} else {
--right;
}
}
}
return result;
}
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4};
int target = 0;
vector<vector<int>> result = threeSum(nums, target);
cout << "Triplets that meet the condition:" << endl;
for (const auto& triplet : result) {
cout << "[" << triplet[0] << ", " << triplet[1] << ", " << triplet[2] << "]" << endl;
}
return 0;
}
Run Result:
Triplets that meet the condition:
[-1, -1, 2]
[-1, 0, 1]
2. Reverse a Linked List
Problem Description: Reverse a singly linked list.Input and Output: Input the head node of the linked list, output the head node of the reversed linked list.Code Implementation:
#include<iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
int main() {
// Create linked list: 1 -> 2 -> 3 -> 4 -> 5
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
// Reverse linked list
ListNode* reversedHead = reverseList(head);
// Print reversed linked list
cout << "Reversed linked list:";
while (reversedHead != nullptr) {
cout << reversedHead->val << " ";
reversedHead = reversedHead->next;
}
cout << endl;
// Free memory
while (head != nullptr) {
ListNode* temp = head;
head = head->next;
delete temp;
}
return 0;
}
Run Result:
Reversed linked list: 5 4 3 2 1
3. Merge Two Sorted Linked Lists
Problem Description: Merge two sorted singly linked lists and return the new merged linked list.Input and Output: Input the head nodes of two linked lists, output the head node of the merged linked list.Code Implementation:
#include<iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
int main() {
// Create linked list 1: 1 -> 3 -> 5
ListNode* l1 = new ListNode(1);
l1->next = new ListNode(3);
l1->next->next = new ListNode(5);
// Create linked list 2: 2 -> 4 -> 6
ListNode* l2 = new ListNode(2);
l2->next = new ListNode(4);
l2->next->next = new ListNode(6);
// Merge linked lists
ListNode* mergedHead = mergeTwoLists(l1, l2);
// Print merged linked list
cout << "Merged linked list:";
while (mergedHead != nullptr) {
cout << mergedHead->val << " ";
mergedHead = mergedHead->next;
}
cout << endl;
// Free memory
while (l1 != nullptr) {
ListNode* temp = l1;
l1 = l1->next;
delete temp;
}
while (l2 != nullptr) {
ListNode* temp = l2;
l2 = l2->next;
delete temp;
}
return 0;
}
Run Result:
Merged linked list: 1 2 3 4 5 6
4. Longest Palindromic Substring
Problem Description: Given a string, find the longest palindromic substring.Input and Output: Input a string, output the longest palindromic substring.Code Implementation:
#include<iostream>
#include<string>
using namespace std;
string longestPalindrome(string s) {
if (s.empty()) return "";
int n = s.size();
int maxLen = 1;
int start = 0;
// Single character palindrome
for (int i = 0; i < n; ++i) {
int left = i - 1;
int right = i + 1;
while (left >= 0 && right < n && s[left] == s[right]) {
int currentLen = right - left + 1;
if (currentLen > maxLen) {
maxLen = currentLen;
start = left;
}
--left;
++right;
}
}
// Double character palindrome
for (int i = 0; i < n - 1; ++i) {
int left = i;
int right = i + 1;
while (left >= 0 && right < n && s[left] == s[right]) {
int currentLen = right - left + 1;
if (currentLen > maxLen) {
maxLen = currentLen;
start = left;
}
--left;
++right;
}
}
return s.substr(start, maxLen);
}
int main() {
string s = "babad";
string result = longestPalindrome(s);
cout << "Longest palindromic substring:" << result << endl;
return 0;
}
Run Result:
Longest palindromic substring: bab
5. Valid Parentheses
Problem Description: Determine if a string is a valid parentheses string.Input and Output: Input a string, output whether it is valid.Code Implementation:
#include<iostream>
#include<string>
#include<stack>
using namespace std;
bool isValid(string s) {
stack<char> stack;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.empty()) return false;
char top = stack.top();
stack.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
return false;
}
}
}
return stack.empty();
}
int main() {
string s = "()[]{}";
if (isValid(s)) {
cout << "Valid parentheses string!" << endl;
} else {
cout << "Invalid parentheses string!" << endl;
}
return 0;
}
Run Result:
Valid parentheses string!
6. Remove Duplicates from Sorted Array
Problem Description: Given a sorted array, remove duplicates so that each element appears only once, and return the new length of the array.Input and Output: Input a sorted array, output the length of the array after removing duplicates.Code Implementation:
#include<iostream>
#include<vector>
using namespace std;
int removeDuplicates(vector<int>& nums) {
if (nums.empty()) return 0;
int n = nums.size();
int slow = 0;
int fast = 1;
while (fast < n) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
fast++;
}
return slow + 1;
}
int main() {
vector<int> nums = {0, 0, 1, 1, 1, 2, 2, 3};
int length = removeDuplicates(nums);
cout << "Length of array after removing duplicates:" << length << endl;
return 0;
}
Run Result:
Length of array after removing duplicates: 4
7. Best Time to Buy and Sell Stock
Problem Description: Given an array where the ith element represents the price of a stock on the ith day, find the best time to buy and sell stock to maximize profit.Input and Output: Input the stock price array, output the maximum profit.Code Implementation:
#include<iostream>
#include<vector>
using namespace std;
int maxProfit(vector<int>& prices) {
if (prices.size() < 2) return 0;
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.size(); ++i) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
int currentProfit = prices[i] - minPrice;
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
}
}
}
return maxProfit;
}
int main() {
vector<int> prices = {7, 1, 5, 3, 6, 4};
int profit = maxProfit(prices);
cout << "Maximum profit:" << profit << endl;
return 0;
}
Run Result:
Maximum profit: 5
8. Rotate Array
Problem Description: Rotate an array clockwise by k positions.Input and Output: Input the array and the number of rotations k, output the rotated array.Code Implementation:
#include<iostream>
#include<vector>
using namespace std;
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
if (k < 0) k += n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
int k = 3;
rotate(nums, k);
cout << "Rotated array:";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
Run Result:
Rotated array: 5 6 7 1 2 3 4
9. House Robber
Problem Description: Given an array representing the amount of money in each house, determine the maximum amount of money you can rob without robbing two adjacent houses.Input and Output: Input the array, output the maximum amount of money.Code Implementation:
#include<iostream>
#include<vector>
using namespace std;
int rob(vector<int>& nums) {
if (nums.empty()) return 0;
if (nums.size() == 1) return nums[0];
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); ++i) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp.back();
}
int main() {
vector<int> nums = {2, 7, 9, 3, 1};
int maxAmount = rob(nums);
cout << "Maximum amount:" << maxAmount << endl;
return 0;
}
Run Result:
Maximum amount: 12
10. Maximum Depth of Binary Tree
Problem Description: Given the root node of a binary tree, find its maximum depth.Input and Output: Input the root node, output the maximum depth.Code Implementation:
#include<iostream>
#include<queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> queue;
queue.push(root);
int depth = 0;
while (!queue.empty()) {
int size = queue.size();
depth++;
for (int i = 0; i < size; ++i) {
TreeNode* node = queue.front();
queue.pop();
if (node->left) queue.push(node->left);
if (node->right) queue.push(node->right);
}
}
return depth;
}
int main() {
// Create binary tree:
// 3
// / \
// 9 20
// / \
// 15 7
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
int depth = maxDepth(root);
cout << "Maximum depth of binary tree:" << depth << endl;
// Free memory
delete root->left;
delete root->right->left;
delete root->right->right;
delete root->right;
delete root;
return 0;
}
Run Result:
Maximum depth of binary tree: 3