电商网站开发合同,建设母婴网站的总结,东莞教育网站建设,大型网站开发公司2024年2月15日力扣题目训练 2024年2月15日力扣题目训练563. 二叉树的坡度637. 二叉树的层平均值643. 子数组最大平均数 I304. 二维区域和检索 - 矩阵不可变154. 寻找旋转排序数组中的最小值 II 2024年2月15日力扣题目训练
2024年2月15日第二十二天编程训练#xff0c;今天主要… 2024年2月15日力扣题目训练 2024年2月15日力扣题目训练563. 二叉树的坡度637. 二叉树的层平均值643. 子数组最大平均数 I304. 二维区域和检索 - 矩阵不可变154. 寻找旋转排序数组中的最小值 II 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:vectordouble averageOfLevels(TreeNode* root) {vectordouble ans;queueTreeNode* 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(vectorint 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:vectorvectorint sums;NumMatrix(vectorvectorint matrix) {int n matrix.size();if(n 0){int m matrix[0].size();sums.resize(n,vectorint(m1));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][col21] - sums[i][col1];}return ans;}
};154. 寻找旋转排序数组中的最小值 II
链接: 最小值 难度 困难 题目
运行示例
思路 这道题其实数组本质还是存在升序的情况数组中的最后一个元素 x在最小值右侧的元素它们的值一定都小于等于 x而在最小值左侧的元素它们的值一定都大于等于 x。因此我们可以根据这一条性质通过二分查找的方法找出最小值。 代码
class Solution {
public:int findMin(vectorint 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 mid1;}else{r--;}}return nums[l];}
};
