1014. 最佳觀光組合

給你一個(gè)正整數(shù)數(shù)組 values，其中 values[i] 表示第 i 個(gè)觀光景點(diǎn)的評(píng)分，并且兩個(gè)景點(diǎn) i 和 j 之間的 距離 為 j - i。

一對(duì)景點(diǎn)（i < j）組成的觀光組合的得分為 values[i] + values[j] + i - j ，也就是景點(diǎn)的評(píng)分之和 減去 它們兩者之間的距離。

返回一對(duì)觀光景點(diǎn)能取得的最高分。

數(shù)據(jù)范圍

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

分析

若遍歷，復(fù)雜度達(dá)到O(n^2)，此時(shí)會(huì)T，因此考慮優(yōu)化，使用雙指針，對(duì)于下標(biāo)為r，去找下表比他小的貢獻(xiàn)最大的值，用last記錄其下表，接下來(lái)考慮怎么找這個(gè)last，對(duì)于下表i<j<r，若是value[j]+(j-i)>value[i]，此時(shí)j的貢獻(xiàn)值更大，而且若下標(biāo)j此時(shí)貢獻(xiàn)最大，則若r往右移動(dòng)，比j小的下標(biāo)不可能貢獻(xiàn)比他還大，具體看代碼

代碼

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. 被圍繞的區(qū)域

給你一個(gè) m x n 的矩陣 board ，由若干字符 'X' 和 'O' 組成，捕獲 所有 被圍繞的區(qū)域：

連接：一個(gè)單元格與水平或垂直方向上相鄰的單元格連接。
區(qū)域：連接所有 ‘O’ 的單元格來(lái)形成一個(gè)區(qū)域。
圍繞：如果您可以用 ‘X’ 單元格 連接這個(gè)區(qū)域，并且區(qū)域中沒(méi)有任何單元格位于 board 邊緣，則該區(qū)域被 ‘X’ 單元格圍繞。
通過(guò)將輸入矩陣 board 中的所有 ‘O’ 替換為 ‘X’ 來(lái) 捕獲被圍繞的區(qū)域。

數(shù)據(jù)范圍

• 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';}}}}}}
};