8.20刷题笔记

215.数组中的第K个最大元素

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {std::priority_queue<int, vector<int>, std::greater<int>> minHeap;for (int i = 0; i < k; i++) {minHeap.push(nums[i]);}for (int i = k; i < nums.size(); i++) {if (minHeap.top() < nums[i]) {minHeap.pop();minHeap.push(nums[i]);}}return minHeap.top();}
}

300.最长递增子序列

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.empty()) return 0;vector<int> dp(nums.size(), 1);int maxLength = 1;for (int i = 0; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = max(dp[i], dp[j] + 1);}}}return maxLength;}
}

912.排序数组

class Solution {
public: vector<int> sortArray(vector<int>& nums) {randomized_quickSort(nums, 0, nums.size() - 1);return nums;}void randomized_quickSort(vector<int>& nums, int low, int high) {if (low < high) {int pivotIndex = randomized_partition(nums, low, high);randomized_quickSort(nums, low, pivotIndex - 1);randomized_quickSort(nums, pivotIndex + 1, high);}}int randomized_partition(vector<int>& nums, int low, int high) {int i = rand() % (high - low + 1) + low;std::swap(nums[high], nums[i]);return partition(nums, low, high);}int partition(vector<int>& nums, int low, int high) {int pivot = nums[high];int i = low - 1;for (int j = low; j < high; j++) {if (nums[j] < pivot) {i++;std::swap(nums[i], nums[j]);}}std::swap(nums[i + 1], nums[high]);return i + 1;}
}

572.另一棵树的子树

class Solution {
public:bool isSubtree(TreeNode* root, TreeNode* subRoot) {if (!root) return false;bool isMatch = checktree(root, subRoot);if (!isMatch) {isMatch = isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);}return isMatch;}bool checktree(TreeNode* root, TreeNode* subRoot) {if (!root && !subRoot) return true;if ((!root && subRoot) || (root && !subRoot) || root->val != subRoot->val) {return false;}return checktree(root->left, subRoot->left) && checktree(root->right, subRoot->right);}
};

53.最大子数组和

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();int maxsum = nums[0];int pre = 0;for (int i = 0; i < n; i++) {pre = max(nums[i], pre + nums[i]);maxsum = max(maxsum, pre);}return maxsum;}
}