- 53. 最大子数组和 - 力扣（LeetCode）
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> preSum(n + 1);
preSum[0] = 0;
for (int i = 1; i <= n; i++)
preSum[i] = preSum[i - 1] + nums[i - 1];
vector<int> preMin(n + 1);
preMin[0] = preSum[0];
for (int i = 1; i <= n; i++)
preMin[i] = min(preMin[i - 1], preSum[i]);
int ans = -1e9;
for (int i = 1; i <= n; i++)
ans = max(ans, preSum[i] - preMin[i - 1]);
return ans;
}
};
- 304. 二维区域和检索 - 矩阵不可变 - 力扣（LeetCode）
class NumMatrix {
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
preSum = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
int sumRegion(int row1, int col1, int row2, int col2) {
row1++; col1++; row2++; col2++;
return preSum[row2][col2] - preSum[row1 - 1][col2] - preSum[row2][col1 - 1] + preSum[row1 - 1][col1 - 1];
}
private:
vector<vector<int>> preSum;
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/
- 1109. 航班预订统计 - 力扣（LeetCode）
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int> delta(n + 2);
for (vector<int>& booking : bookings) {
int first = booking[0];
int last = booking[1];
int seats = booking[2];
delta[first] += seats;
delta[last + 1] -= seats;
}
vector<int> preSum(n + 1);
preSum[0] = delta[0];
vector<int> ans;
for (int i = 1; i <= n; i++) {
preSum[i] = preSum[i - 1] + delta[i];
ans.push_back(preSum[i]);
}
return ans;
}
};
- 167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
while (left < right) {
if (numbers[left] + numbers[right] > target) right--;
else if (numbers[left] + numbers[right] < target) left++;
else return {left + 1, right + 1};
}
return {};
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
int right = n - 1;
for (int left = 0; left < n; left++) {
while (left < right && numbers[left] + numbers[right] > target) right--;
if (left < right && numbers[left] + numbers[right] == target)
return {left + 1, right + 1};
}
return {};
}
};
- 15. 三数之和 - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
vector<vector<int>> jks = twoSum(nums, i + 1, -nums[i]);
for (vector<int> jk : jks)
ans.push_back({nums[i], jk[0], jk[1]});
}
return ans;
}
private:
vector<vector<int>> twoSum(vector<int>& nums, int start, int target) {
vector<vector<int>> ans;
int n = nums.size();
int j = n - 1;
for (int i = start; i < n; i++) {
if (i > start && nums[i] == nums[i - 1])
continue;
while (i < j && nums[i] + nums[j] > target)
j--;
if (i < j && nums[i] + nums[j] == target)
ans.push_back({nums[i], nums[j]});
}
return ans;
}
};
- 11. 盛最多水的容器 - 力扣（LeetCode）
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;
int ans = 0;
while (l < r) {
ans = max(ans, min(height[l], height[r]) * (r - l));
if (height[l] < height[r]) l++; else r--;
}
return ans;
}
};
- 78. 子集 - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
this->nums = nums;
n = nums.size();
recur(0);
return ans;
}
private:
vector<vector<int>> ans;
vector<int> chosen;
vector<int> nums;
int n;
void recur(int i) {
if (i == n) {
ans.push_back(chosen);
return;
}
recur(i + 1);
chosen.push_back(nums[i]);
recur(i + 1);
chosen.pop_back();
}
};
- 77. 组合 - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
this->n = n;
this->k = k;
recur(1);
return ans;
}
private:
void recur(int i) {
if (chosen.size() > k || chosen.size() + (n - i + 1) < k)
return;
if (i == n + 1)
ans.push_back(chosen);
recur(i + 1);
chosen.push_back(i);
recur(i + 1);
chosen.pop_back();
}
int n, k;
vector<int> chosen;
vector<vector<int>> ans;
};
- 46. 全排列 - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
n = nums.size();
used = vector<bool>(n, false);
this->nums = nums;
recur(0);
return ans;
}
private:
int n;
vector<bool> used;
vector<int> chosen;
vector<vector<int>> ans;
vector<int> nums;
void recur(int pos) {
if (pos == n) {
ans.push_back(chosen);
return;
}
for (int i = 0; i < n; i++)
if (!used[i]) {
chosen.push_back(nums[i]);
used[i] = true;
recur(pos + 1);
used[i] = false;
chosen.pop_back();
}
}
};
- 226. 翻转二叉树 - 力扣（LeetCode）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
invertTree(root->left);
invertTree(root->right);
return root;
}
};
- 98. 验证二叉搜索树 - 力扣（LeetCode）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
#define LL long long
class Solution {
public:
bool isValidBST(TreeNode* root) {
return check(root, -(1ll << 31), (1ll << 31) - 1);
}
private:
bool check(TreeNode* root, LL leftRange, LL rightRange) {
if (root == nullptr) return true;
if (root->val < leftRange || root->val > rightRange) return false;
return check(root->left, leftRange, root->val - 1ll)
&& check(root->right, root->val + 1ll, rightRange);
}
};
- 104. 二叉树的最大深度 - 力扣（LeetCode）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
depth = 1;
ans = 0;
recur(root);
return ans;
}
private:
int ans, depth;
void recur(TreeNode* root) {
if (root == nullptr) return;
ans = max(ans, depth);
depth++;
recur(root->left);
recur(root->right);
depth--;
}
};
- 50. Pow(x, n) - 力扣（LeetCode）
class Solution {
public:
double myPow(double x, int n) {
if (n == 0) return 1;
if (n == -(1ll << 31)) return 1.0 / (myPow(x, -(n + 1)) * x);
if (n < 0) return 1.0 / myPow(x, -n);
double temp = myPow(x, n / 2);
double ans = temp * temp;
if (n % 2 == 1) ans *= x;
return ans;
}
};
- 22. 括号生成 - 力扣（LeetCode）
class Solution {
public:
vector<string> generateParenthesis(int n) {
if (n == 0) return {""};
if (store.find(n) != store.end()) return store[n];
vector<string> ans;
for (int k = 1; k <= n; k++) {
vector<string> A = generateParenthesis(k - 1);
vector<string> B = generateParenthesis(n - k);
for (const string& a : A)
for (const string& b : B)
ans.push_back("(" + a + ")" + b);
}
store[n] = ans;
return ans;
}
private:
// (A)B
unordered_map<int, vector<string>> store;
};
- 23. 合并 K 个升序链表 - 力扣（LeetCode）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
private:
ListNode* merge(vector<ListNode*>& lists, int l, int r) {
if (l == r) return lists[l];
if (l > r) return nullptr;
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
if (a == nullptr || b == nullptr) return a ? a : b;
ListNode* head = new ListNode();
ListNode* tail = head;
ListNode* aPtr = a, * bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr;
aPtr = aPtr->next;
}
else {
tail->next = bPtr;
bPtr = bPtr->next;
}
tail = tail->next;
}
if (aPtr == nullptr) tail->next = bPtr;
if (bPtr == nullptr) tail->next = aPtr;
return head->next;
}
};
- 94. 二叉树的中序遍历 - 力扣（LeetCode）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
private:
vector<int> ans;
void dfs(TreeNode* root) {
if (root == nullptr) return;
dfs(root->left);
ans.push_back(root->val);
dfs(root->right);
}
};
- 589. N 叉树的前序遍历 - 力扣（LeetCode）
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<int> preorder(Node* root) {
dfs(root);
return ans;
}
private:
vector<int> ans;
void dfs(Node* root) {
if (root == nullptr) return;
ans.push_back(root->val);
for (int i = 0; i < root->children.size(); i++)
dfs(root->children[i]);
}
};
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> ans;
if (root == nullptr) return ans;
stack<Node*> s;
s.push(root);
while (!s.empty()) {
Node* node = s.top();
s.pop();
ans.push_back(node->val);
for (int i = node->children.size() - 1; i >= 0; i--)
s.push(node->children[i]);
}
return ans;
}
};
- 429. N 叉树的层序遍历 - 力扣（LeetCode）
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ans;
if (root == nullptr) return ans;
queue<pair<Node*, int>> q;
q.push({root, 0});
while (!q.empty()) {
auto kv = q.front();
Node* node = kv.first;
int depth = kv.second;
q.pop();
if (depth >= ans.size()) ans.push_back({});
ans[depth].push_back(node->val);
for (int i = 0; i < node->children.size(); i++)
q.push({node->children[i], depth + 1});
}
return ans;
}
};
