2024年2月15日力扣题目训练
2024年2月15日力扣题目训练
2024年2月15日第二十二天编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和困难题1道。惰性太强现在才完成，不过之后我会认真完成的,我会慢慢补回来，争取一天发两篇，把之前的都补上。
563. 二叉树的坡度
链接: 二叉树的坡度
难度： 简单
题目：
运行示例：
思路：
这道题就是遍历，统计左右子树节点之和的差值即可。
代码：
class Solution {
public:
int ans = 0;
int dfs(TreeNode* root){
if(root == NULL) return 0;
int sumleft = dfs(root->left);
int sumright= dfs(root->right);
ans += abs(sumleft-sumright);
return sumleft + sumright + root->val;
}
int findTilt(TreeNode* root) {
dfs(root);
return ans;
}
};
637. 二叉树的层平均值
链接: 二叉树的层平均值
难度： 简单
题目：
运行示例：
思路：
这道题可以看出我们就是求每一层的平均值，所以我们可以采用层次遍历。
代码：
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> ans;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
double sum = 0;
int n = q.size();
for(int i = 0; i < n; i++){
TreeNode* node = q.front();
q.pop();
sum += node->val;
if(node->left != NULL) q.push(node->left);
if(node->right != NULL) q.push(node->right);
}
ans.push_back(sum/n);
}
return ans;
}
};
643. 子数组最大平均数 I
链接: 子数组最大平均数
难度： 简单
题目：
运行示例：
思路：
这道题我本来是直接暴力遍历的，但是时间超了，所以我看了题解有了启发，我采用了求前K项和然后从而得到平均值即题解提到的滑动窗口方法。
代码：
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
for(int i = 1; i < nums.size(); i++){
nums[i] += nums[i-1];
}
double ans = (nums[k-1])/(double(k));
for(int i = k; i < nums.size(); i++){
double avg = (nums[i]-nums[i-k])/(double(k));
ans = (ans > avg)?ans: avg;
}
return ans;
}
};
运行示例：
运行示例
思路：
这道题可以看出是使用层次遍历来完成，故利用队列完成。
代码：
304. 二维区域和检索 - 矩阵不可变
链接: 二维区域和检索 - 矩阵不可变
难度： 中等
题目：
运行示例：
思路：
这道题就是统计求前项和，我们可以按照行进行统计从而减少计算量。此题与之前303. 区域和检索 - 数组不可变的类似。
代码：
class NumMatrix {
public:
vector<vector<int>> sums;
NumMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
if(n > 0){
int m = matrix[0].size();
sums.resize(n,vector<int>(m+1));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
sums[i][j + 1] = sums[i][j] + matrix[i][j];
}
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int ans = 0;
for(int i = row1; i <= row2; i++){
ans += sums[i][col2+1] - sums[i][col1];
}
return ans;
}
};
154. 寻找旋转排序数组中的最小值 II
链接: 最小值
难度： 困难
题目：
运行示例：
思路：
这道题其实数组本质还是存在升序的情况，数组中的最后一个元素 x：在最小值右侧的元素，它们的值一定都小于等于 x；而在最小值左侧的元素，它们的值一定都大于等于 x。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。
代码：
class Solution {
public:
int findMin(vector<int>& nums)
{
int l = 0;
int r = nums.size()-1;
while(l < r){
int mid = l + (r-l)/2;
if(nums[mid] < nums[r]){
r = mid;
}else if(nums[mid] > nums[r]){
l = mid+1;
}else{
r--;
}
}
return nums[l];
}
};
