【LBLD】二维数组的花式遍历技巧
151. 反转字符串中的单词
class Solution {
public:
string reversePartString(string s, int a, int b) {
if (a < 0 || b >= s.size()) {
cout << "索引错误！" << endl;
}
int p1 = a, p2 = b;
char c = 0;
while (p1 < p2) {
c = s[p1];
s[p1] = s[p2];
s[p2] = c;
p1++; p2--;
}
return s;
}
string reverseWords(string s) {
// 清除空格
int p1 = 0, p2 = 0;
while (p2 < s.size()) {
if (s[p2] != ' '
|| (p2-1 >= 0 && p2+1 < s.size()) && s[p2-1] != ' ') {
s[p1] = s[p2];
p1++;
p2++;
}
else while (p2 < s.size() && s[p2] == ' ') {
p2 ++;
}
}
if (s[p1-1] == ' ') p1--;
while (p1 < s.size()) {
s.erase(p1);
}
// 反转整个字符串
s = reversePartString(s, 0, s.size()-1);
// 反转每个单词
p1 = 0; p2 = 0;
while (p2 < s.size()) {
while (s[p2] != ' ' && p2 < s.size()) {
p2++;
}
s = reversePartString(s, p1, p2-1);
p1 = ++p2;
}
return s;
}
};
48. 旋转图像
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
// 对角
int temp = -1;
for (int a=0; a<matrix.size(); a++) {
for (int b=a; b<matrix.size(); b++) {
temp = matrix[a][b];
matrix[a][b] = matrix[b][a];
matrix[b][a] = temp;
}
}
// 垂直
int p1 = 0, p2 = matrix.size()-1;
for (int a=0; a<matrix.size(); a++) {
p1 = 0; p2 = matrix.size()-1;
while (p1 < p2) {
temp = matrix[a][p1];
matrix[a][p1] = matrix[a][p2];
matrix[a][p2] = temp;
p1++; p2--;
}
}
}
};
54. 螺旋矩阵
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int left_bound = -1, right_bound = n;
int upper_bound = -1, lower_bound = m;
vector<int> res;
while (res.size() < m * n) {
// 从左向右
for (int i=left_bound+1; i<right_bound; i++) {
res.push_back(matrix[upper_bound+1][i]);
}
upper_bound++;
if (upper_bound+1 >= lower_bound) break;
// 从上向下
for (int i=upper_bound+1; i<lower_bound; i++) {
res.push_back(matrix[i][right_bound-1]);
}
right_bound--;
if (left_bound+1 >= right_bound) break;
// 从右向左
for (int i=right_bound-1; i>left_bound; i--) {
res.push_back(matrix[lower_bound-1][i]);
}
lower_bound--;
if (upper_bound+1 >= lower_bound) break;
// 从下向上
for (int i=lower_bound-1; i>upper_bound; i--) {
res.push_back(matrix[i][left_bound+1]);
}
left_bound++;
if (left_bound+1 >= right_bound) break;
}
return res;
}
};
59. 螺旋矩阵 II
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int i = 1;
int i_bound = n*n;
int left = 0, right = n-1;
int upper = 0, lower = n-1;
while (i <= i_bound) {
for (int j=left; j<=right; j++) {
res[upper][j] = i;
i++;
}
upper++;
if (i > i_bound) break;
for (int j=upper; j<=lower; j++) {
res[j][right] = i;
i++;
}
right--;
for (int j=right; j>=left; j--) {
res[lower][j] = i;
i++;
}
lower--;
for (int j=lower; j>=upper; j--) {
res[j][left] = i;
i++;
}
left++;
}
return res;
}
};