力扣9.23

1014. 最佳观光组合

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

数据范围

• 2 <= values.length <= 5 * 104
• 1 <= values[i] <= 1000

分析

若遍历，复杂度达到O(n^2)，此时会T，因此考虑优化，使用双指针，对于下标为r，去找下表比他小的贡献最大的值，用last记录其下表，接下来考虑怎么找这个last，对于下表i<j<r，若是value[j]+(j-i)>value[i]，此时j的贡献值更大，而且若下标j此时贡献最大，则若r往右移动，比j小的下标不可能贡献比他还大，具体看代码

代码

class Solution {
public:int maxScoreSightseeingPair(vector<int>& 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.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 为 'X' 或 'O'

分析

dfs找连通块

代码

typedef pair<int, 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, vector<vector<char>>& board, vector<PII> &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(vector<vector<char>>& 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;vector<PII> tmp;dfs(i, j, board, tmp);// cout << i << " " << j << " " << flag << endl;if(flag) {for(auto k : tmp) {board[k.first][k.second] = 'X';}}}}}}
};