力扣题目训练（22）

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];}
};