2024年2月9日力扣题目训练
2024年2月9日力扣题目训练
2024年2月9日第十六天编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和困难题1道。惰性太强现在才完成，不过之后我会认真完成的。
530. 二叉搜索树的最小绝对差
链接: 二叉搜索树的最小绝对差
难度： 简单
题目：
运行示例：
思路：
二叉搜索树的中序遍历是一个递增序列，利用这条性质，我们可以先得到一个序列，然后再找最小值。
代码：
class Solution {
private:
vector<int> nums;
public:
void inorder(TreeNode* root){
if(root == NULL) return;
inorder(root->left);
nums.push_back(root->val);
inorder(root->right);
}
int getMinimumDifference(TreeNode* root) {
inorder(root);
int ans = INT_MAX;
for(int i = 1; i < nums.size(); i++){
ans = min(ans,nums[i]-nums[i-1]);
}
return ans;
}
};
541. 反转字符串 II
链接: 反转字符串
难度： 简单
题目：
运行示例：
思路：
这道题按照所述要求去完成即可。
代码：
class Solution {
public:
string reverseStr(string s, int k) {
int i = 0,n = s.size();
while(i < n){
reverse(s.begin()+i, s.begin() + min(i + k, n));
i += 2 * k;
}
return s;
}
};
543. 二叉树的直径
链接: 二叉树的直径
难度： 简单
题目：
运行示例：
思路：
我们知道**一条路径的长度为该路径经过的节点数减一，**所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。所以我们可以利用深度优先求左右子树的最大深度。
代码：
class Solution {
public:
int ans = 0;
int depth(TreeNode* root){
if(root == NULL) return 0;
int L = depth(root->left);
int R = depth(root->right);
ans = max(ans, L+R+1);
return max(L,R) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
depth(root);
return ans-1;
}
};
238. 除自身以外数组的乘积
链接: 乘积
难度： 中等
题目：
运行示例：
思路：
这道题试求乘积，但是有0的问题，所以我们独立将0记录，将剩余的乘起来，然后根据记录从而进行判断和处理。
代码：
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int mt = 1;
int zero = 0;
vector<int> ans;
for(int i = 0; i < nums.size(); i++){
if(nums[i] == 0) zero++;
else mt *= nums[i];
}
for(int i = 0; i < nums.size(); i++){
if(zero != 0){
if(zero == 1 && nums[i] == 0) ans.push_back(mt);
else ans.push_back(0);
}else{
ans.push_back(mt/nums[i]);
}
}
return ans;
}
};
240. 搜索二维矩阵 II
链接: 搜索二维矩阵
难度： 中等
题目：
运行示例：
思路：
这道题我本来是利用递归来做的结果时间超时了，看了官方的题解，我发现我忽略了升序这一点，我们可以利用这一性质，对每行进行二分查找判断。这道题值得吐槽的是直接遍历也可以不会超时╮(╯▽╰)╭。
代码：
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix.size();
int m = matrix[0].size();
for(int i = 0; i < n; i++){
int left = 0,right = m-1;
while(left <= right){
int mid = (right - left)/2+left;
if(matrix[i][mid] == target) return true;
else if(matrix[i][mid] < target) left = mid+1;
else right = mid -1;
}
}
return false;
}
};
124. 二叉树中的最大路径和
链接: 最大路径和
难度： 困难
题目：
运行示例：
思路：
这道题本质就是遍历，我们需要计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。
代码：
class Solution {
private:
int maxSum = INT_MIN;
public:
int maxGain(TreeNode* root){
if(root == NULL) return 0;
int leftGain = max(maxGain(root->left),0);
int rightGain = max(maxGain(root->right),0);
int pricepath = root->val + leftGain + rightGain;
maxSum = max(maxSum,pricepath);
return root->val + max(leftGain,rightGain);
}
int maxPathSum(TreeNode* root) {
maxGain(root);
return maxSum;
}
};
