問題1：
給一個數(shù)組a，求 a[i] + a[j] - (j - i) 的最大值。
input:
5 # 數(shù)組長度
11 6 5 12 18 # 數(shù)組元素
output:
29 # 12 + 18 - (5 - 4)
input:
5 # 數(shù)組長度
6 5 4 4 8 # 數(shù)組元素
output:
11 # 4 + 8 - (5 - 4)
解題思路：
1、直接暴力 O(n^2), 只能通過 30% 的 case，pass。
2、時間復(fù)雜度為 O(n) 的做法：
做法：因為 ans = a[i] + a[j] - (j - i) = a[i] + a[j] + i - j = (a[i] + i) + (a[j] - j)，在遍歷一遍數(shù)組時，每次更新 ans 和 a[i] + i 的最大值，遍歷結(jié)束后 ans 就是最終的結(jié)果。
注意：之所以這樣劃分，是因為 a[i] + i 的最大值可以在遍歷的過程中更新。
C++實現(xiàn)：
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int n, num;
scanf("%d", &n);
scanf("%d", &num); // 第一個數(shù)
int ans = 0;
int mymax = num + 1; // a[i]+i 的初始值
for(int i = 2; i <= n; i++) {
scanf("%d", &num);
ans = max(ans, num-i+mymax); // 更新 ans
mymax = max(mymax, num+i); // 更新 a[i]+i
}
cout << ans; // 輸出結(jié)果
return 0;
}
問題2：
給一個 M 行 N 列的 0, 1 數(shù)組，求由 1 連通的區(qū)塊個數(shù) （一個 1 的上下左右或者四條對角線也有 1，則代表相連通）。
input:
3 3 # 數(shù)組行，列
0 1 0
1 0 0
1 0 1 # 數(shù)組中的元素
output:
2 # 兩個區(qū)塊，右下角一個 1 單獨形成一個區(qū)塊，剩下的 3 個 1形成一個區(qū)塊。
解題思路：
很經(jīng)典的回溯法（DFS）求解問題。
1、遍歷二維數(shù)組，如果數(shù)組中的元素為 1，先將區(qū)塊數(shù) ans 加 1，然后利用回溯法（DFS）求解。
2、在 DFS 中，先把 1 的狀態(tài)改為 0，然后向它的 8 個方向搜索為 1 的元素，繼續(xù)調(diào)用 DFS 遍歷。
3、一個區(qū)塊找完后，標記為 1 的這些位置會變成 0。返回 1 繼續(xù)搜索下一個區(qū)塊。
注意： 數(shù)組下標不要越界。
實現(xiàn)技巧：如下，可以用一個 8 行 2 列的數(shù)組記錄搜索的 8 個方向的偏移位置，然后 for 循環(huán)遍歷，可以防止寫 8 個 if 條件。
| 向左上，左，左下搜索 | 向上，下搜索 | 向右上，右，右下搜索 |
|---|---|---|
| (-1, -1) | (-1, 0) | (-1, 1) |
| (0, -1) | 1（周圍8個方向） | (0, 1) |
| (1, -1) | (1, 0) | (1, 1) |
C++實現(xiàn)：
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n, m, ans;
// 記錄搜索的8個方向的偏移位置
int d[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,-1},{1,1},{-1,1},{1,-1}};
void DFS(vector<vector<int> > &array, int i, int j) {
array[i][j] = 0; // 狀態(tài)改為0
for(int k=0;k<8;k++) // 循環(huán)搜索8個方向
if( i+d[k][0]>=0 && i+d[k][0]<n
&& j+d[k][1]>=0 && j+d[k][1]<m
&& array[i+d[k][0]][j+d[k][1]] == 1) // 搜索的下一個位置元素不越界且為1
DFS(array, i+d[k][0], j+d[k][1]);
}
int main() {
scanf("%d%d", &n, &m);
vector<vector<int> > array(n); // vector<vector<int> > 要有一個空格
for(int i=0;i<n;i++) {
array[i].resize(m); // 定義n行m列數(shù)組
}
for(int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
scanf("%d",&array[i][j]); // 讀取元素
}
}
for(int i=0;i<n;i++)
for (int j=0;j<m;j++)
if(array[i][j] == 1) { // 如果為1，區(qū)塊數(shù)加1，然后DFS回溯
ans++;
DFS(array, i, j);
}
cout << ans; // 輸出結(jié)果
return 0;
}
問題3：
給一個包含數(shù)字、字母、% 和 # 的字符串，如 3%acm#2%acm#，將 # 號前面的字母（acm）重復(fù) % 號前面的數(shù)字（3、2）次，得到一個新字符串：acmacmacmacmacm?？梢栽试S嵌套，如 3%g2%n##，得到 gnngnngnn（n先重復(fù)兩次，然后和g組合，再重復(fù)3次）。
解題思路：
1、遍歷字符串，將字符依次入棧，直到碰到 #；
2、出棧，直到碰到 %，就會得到 # 前面的字符串；
3、再出棧，直到不是數(shù)字，就會得到 % 前面的數(shù)字；
4、將 2 中得到的字符串重復(fù) 3 中得到的次數(shù)，重新壓入棧。
5、直到遍歷結(jié)束，棧中的字符串就是最后的答案。
注意：出棧的過程中要判斷棧不為空。
按照上述解題思路，對于 3%g2%n##，棧的變化為 3%g2%n -> 3%g2% -> 3%g -> 3%gnn -> 3% -> [] -> gnngnngnn，即得到最終的答案。
C++實現(xiàn)：
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
stack<string> sta; // 棧
string getstr() { // 得到 % 后 # 前的字符串
string s,t;
while(sta.empty()==false) { // 棧不為空
t = sta.top(); sta.pop();
if(t[0] == '%') break;
s = t + s;
}
return s;
}
int getint() { // 得到 % 前的數(shù)字
int num=0,res=1;
string t;
while(sta.empty()==false) { // 棧不為空
t = sta.top();
if(t[0]>='0'&&t[0]<='9') num += (t[0]-'0')*res;
else break;
sta.pop();
res*=10; // 可能多位數(shù)字
}
return num;
}
string print() { // 出棧就是最后的答案
string s,t;
while(sta.empty()==false) {
t = sta.top(); sta.pop();
s = t + s;
}
return s;
}
int main() {
string s;
cin >> s;
int len = s.size();
for(int i=0;i<len;i++) {
string tmp;
tmp += s[i];
if(s[i]>='0'&&s[i]<='9') { // 不是 # 都入棧
sta.push(tmp);
} else if(s[i]>='a'&&s[i]<='z') {
sta.push(tmp);
} else if(s[i]>='A'&&s[i]<='Z') {
sta.push(tmp);
} else if(s[i]=='%') {
sta.push(tmp);
} else {
string newstr = getstr();
int num = getint();
string t;
for(int j=0;j<num;j++) // 一次展開的字符串
t += newstr;
sta.push(t); // 展開的字符串重新壓入棧
}
}
cout << print(); // 輸出結(jié)果
return 0;
}
