网站开发语言检测,做简约头像网站,网站推广的四个阶段包括,百度指数查询移动版1014. 最佳观光组合
给你一个正整数数组 values#xff0c;其中 values[i] 表示第 i 个观光景点的评分#xff0c;并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点#xff08;i j#xff09;组成的观光组合的得分为 values[i] values[j] i - j #xff0c;…1014. 最佳观光组合
给你一个正整数数组 values其中 values[i] 表示第 i 个观光景点的评分并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点i j组成的观光组合的得分为 values[i] values[j] i - j 也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
数据范围
2 values.length 5 * 1041 values[i] 1000
分析
若遍历复杂度达到O(n^2)此时会T因此考虑优化使用双指针对于下标为r去找下表比他小的贡献最大的值用last记录其下表接下来考虑怎么找这个last对于下表ijr若是value[j](j-i)value[i]此时j的贡献值更大而且若下标j此时贡献最大则若r往右移动比j小的下标不可能贡献比他还大具体看代码
代码
class Solution {
public:int maxScoreSightseeingPair(vectorint values) {int n values.size();int l 0, last 0;int ans 0;for(int r 0; r n; r ) {while(l r) {if(values[l] (l - last) values[last]) {last l;}l ;}if(r ! last)ans max(ans, values[r] values[last] - (r - last));}return ans;}
};130. 被围绕的区域
给你一个 m x n 的矩阵 board 由若干字符 X 和 O 组成捕获 所有 被围绕的区域
连接一个单元格与水平或垂直方向上相邻的单元格连接。 区域连接所有 ‘O’ 的单元格来形成一个区域。 围绕如果您可以用 ‘X’ 单元格 连接这个区域并且区域中没有任何单元格位于 board 边缘则该区域被 ‘X’ 单元格围绕。 通过将输入矩阵 board 中的所有 ‘O’ 替换为 ‘X’ 来 捕获被围绕的区域。
数据范围
m board.lengthn board[i].length1 m, n 200board[i][j] 为 X 或 O
分析
dfs找连通块
代码
typedef pairint, int PII;
class Solution {
public:const static int N 205;int n, m;int dx[4] {0, 1, 0, -1};int dy[4] {1, 0, -1, 0};bool vis[N][N];bool flag true;void dfs(int x, int y, vectorvectorchar board, vectorPII tmp) {if(x 0 || y 0 || x n || y m) return ;if(vis[x][y]) return ;if(board[x][y] X) return ;if(x 0 || y 0 || x n - 1 || y m - 1) flag false;vis[x][y] true;tmp.push_back({x, y});for(int i 0; i 4; i ) {int nx x dx[i];int ny y dy[i];dfs(nx, ny, board, tmp);}return ;}void solve(vectorvectorchar board) {n board.size();m board[0].size();for(int i 0; i n; i ) {for(int j 0; j m; j ) {if(!vis[i][j] board[i][j] O) {flag true;vectorPII tmp;dfs(i, j, board, tmp);// cout i j flag endl;if(flag) {for(auto k : tmp) {board[k.first][k.second] X;}}}}}}
};
