数组中两元素的最大乘积
数据范围较小：500
两个下标不同
两重循环枚举 i 和 j，在所有的 i 和 j 对中找最大值，时间复杂度 O( n^2 )
class Solution {
public:
int maxProduct(vector<int>& nums) {
//定义答案为最小值
int res = INT_MIN;
//枚举第一个下标 i
for(int i = 0;i < nums.size();i++ )
//枚举第二个下标 j-> 和第一个下标不同-> 定义第二个下标在第一个下标之前
for(int j = 0;j < i;j++ )
res = max(res,(nums[i] - 1) * (nums[j] - 1));
return res;
}
};
下标对应如下
1 0
2 0
2 1
3 0
3 1
3 2
切割后面积最大的蛋糕?
数组给出了所有横、竖切的线的位置，在所有切开的蛋糕块中找面积最大值，即找横竖中相间最大的：把 0 和 宽、高 都放进对应的数组中，然后排序，再分别找横竖中间隔最大的相乘然后取余→ 注意要取余后返回，否则会因为整数溢出而报错
横向、纵向的线会把蛋糕分成若干部分
任取一个横向，再任取一个纵向，都会对应一个小方块，小方块的高度、宽度就是横向的高度、纵向的宽度，行、列是独立的，让整个面积最大相当于：在horizontalCuts 中拿一个数，在 verticalCuts 中拿一个数，使得乘积最大→ 找竖方向最大的数与横方向最大的数相乘就是答案→ 注意乘积可能超过 int 的范围需要对 10^9 + 7 取余
需要扫描水平的最大值和竖直的最大值，时间复杂度为 O( n )
1??????? 1??????? 2??????? 1
1
2
1
class Solution {
public:
int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
//加入边界
horizontalCuts.push_back(0),horizontalCuts.push_back(h);
verticalCuts.push_back(0),verticalCuts.push_back(w);
//horizontalCuts 和 verticalCuts 不一定有序 需要先排序
sort(horizontalCuts.begin(),horizontalCuts.end());
sort(verticalCuts.begin(),verticalCuts.end());
//分别求行列的最大值-> 相邻两部分的差就是每一部分的值
int x = 0,y = 0;
//行
for(int i = 1;i < horizontalCuts.size();i++ ) x = max(x,horizontalCuts[i] - horizontalCuts[i - 1]);
//列
for(int i = 1;i < verticalCuts.size();i++ ) y = max(y,verticalCuts[i] - verticalCuts[i - 1]);
//注意转换为 long long
return (long long)x * y % 1000000007;
}
};重新规划路线
给出一棵树，n 个点，编号是 0 ~ n - 1，树的边用二元组给出，每一个二元组表示 a 到 b 的有向边，让所有的游客都能走到城市 0，但是所有线都是有向的，如果想让所有游客都走到城市 0，需要将树中的某些边反向，问：最少需要反向多少条线？
示例1：
如果把所有边看成无向的，就是一棵树
希望让每一个点都可以走到 0，走的时候让逆向的边反向
问：变更方向的最小路线数？由于是一棵树，把它看成无向边，每个点到根节点的路径是唯一的，需要把所有需要反向边都改变，所有同向边都不能变，实际上答案是唯一的
只需要统计从每个点到根节点的路径中，哪些边需要反向，把要反向的边的数量求出来即可
遍历时可以从根节点开始向每一个节点遍历整棵树，例如，遍历的时候发现从 0→ 1不是从下往上，就把它反向，并记录
在题目中存储的是有向边，但是在写代码时，要先存成无向边，记录一个方向，因为如果是存的有向边，如果边是从下往上，就不能往下走，因此要存储无向边，但记录真实的方向
实际上就是把整棵树遍历一遍，时间复杂度为 O( n )
由于不一定是二叉树，所以存储的时候用邻接表来存储，不仅要存编号，而且要存方向，用 pair 来存储
class Solution {
public:
vector<vector<pair<int,int>>> g;
int minReorder(int n, vector<vector<int>>& connections) {
//初始化 n 个点
g = vector<vector<pair<int,int>>>(n);
//枚举所有边
for(auto e : connections)
{
//第一个点 第二个点
int a = e[0],b = e[1];
//1 真实边的方向
g[a].push_back({b,1});
//0 反向
g[b].push_back({a,0});
}
//返回从根节点遍历的结果
return dfs(0,-1);
}
//无向树需要避免重复遍历
int dfs(int u,int father)
{
//需要变的边的数量
int res = 0;
for(auto e : g[u])
{
//节点编号 方向
int ver = e.first,dir = e.second;
//如果节点编号是来的这个点-> 表示从 father 下来
if(ver == father) continue;
//否则需要遍历 ver 这个点 方向是u
//加上当前边是否需要变化
res += dfs(ver,u) + dir;
}
return res;
}
};两个盒子中球的颜色数相同的概率
?
