網(wǎng)站關(guān)鍵詞推廣優(yōu)化如何找客戶資源
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';}}}}}}
};