前言
- 本文是当C++遇上LeetCode系列文章，关于本系列，请参看当C++遇上LeetCode
Vector
- Vector是类似数组的万能容器，可以容纳几乎所有数据类型，包括可以定义想vector<string> 这样的数据类型
- 同样你可以想这样vector<vector<int>>去定义一个二维数组
- 常用的操作(假如定义了一个vector<int> test)
- test.push_back(a) //在底部压入数据
- test.pop_back() //出栈
- sort(test.begin(), test.end()) //从小到大排序
- 此外遍历时可以使用for (int i : test)这样复制一个i来遍历整个test
- 或者此外遍历时可以使用for (int &i : test)这样取出真正的i来遍历整个test
- test.size()作为数组长度这种常规操作就不提了
String
- 基本上面有的操作都能做
- 唯一不太一样的是在vector<string>中，不能用push_back给test[0]压入字符这样的，这是我目前都没能理解的
参考题目
-
3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的
grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。
示例：
输入: [[4,3,8,4],
[9,5,1,9],
[2,7,6,2]]
输出: 1
解释:
下面的子矩阵是一个 3 x 3 的幻方：
438
951
276
而这一个不是：
384
519
762
总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
提示:
1 <= grid.length <= 101 <= grid[0].length <= 100 <= grid[i][j] <= 15
参考文章
class Solution {
public:
int numMagicSquaresInside(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), res = 0;
for (int i = 0; i < m - 2; ++i) {
for (int j = 0; j < n - 2; ++j) {
if (grid[i + 1][j + 1] == 5 && isValid(grid, i, j)) ++res;
}
}
return res;
}
bool isValid(vector<vector<int>>& grid, int i, int j) {
vector<int> cnt(10);
for (int x = i; x < i + 2; ++x) {
for (int y = j; y < j + 2; ++y) {
int k = grid[x][y];
if (k < 1 || k > 9 || cnt[k] == 1) return false;
cnt[k] = 1;
}
}
if (15 != grid[i][j] + grid[i][j + 1] + grid[i][j + 2]) return false;
if (15 != grid[i + 1][j] + grid[i + 1][j + 1] + grid[i + 1][j + 2]) return false;
if (15 != grid[i + 2][j] + grid[i + 2][j + 1] + grid[i + 2][j + 2]) return false;
if (15 != grid[i][j] + grid[i + 1][j] + grid[i + 2][j]) return false;
if (15 != grid[i][j + 1] + grid[i + 1][j + 1] + grid[i + 2][j + 1]) return false;
if (15 != grid[i][j + 2] + grid[i + 1][j + 2] + grid[i + 2][j + 2]) return false;
if (15 != grid[i][j] + grid[i + 1][j + 1] + grid[i + 2][j + 2]) return false;
if (15 != grid[i + 2][j] + grid[i + 1][j + 1] + grid[i][j + 2]) return false;
return true;
}
};
class Solution {
public:
int numMagicSquaresInside(vector<vector<int>>& grid) {
int counter = 0;
int x = grid.size(), y = grid[0].size();
if (x < 3 || y < 3) {
return 0;
}
for (int i = 0; i < x - 2; i++) {
for (int j = 0; j < y - 2; j++) {
if (!judgeOneToNine(grid, i, j)) {
continue;
}
if (judgeMagicNum(grid, i, j)) {
counter++;
}
}
}
return counter;
}
bool judgeOneToNine (vector<vector<int>>& grid, int x, int y) {
int bucket[20];
for (int i = 0; i < 20; i++) {
bucket[i] = 0;
}
for (int i = x; i < x + 3; i++) {
for (int j = y; j < y + 3; j++) {
bucket[grid[i][j]]++;
}
}
for (int i = 1; i < 10; i++) {
if (bucket[i] != 1) {
return false;
}
}
return true;
}
bool judgeMagicNum (vector<vector<int>>& grid, int x, int y) {
for (int i = x; i < x + 3; i++) {
if (grid[i][y] + grid[i][y + 1] + grid[i][y + 2] == 15) {
;
} else {
return false;
}
}
for (int i = y; i < y + 3; i++) {
if (grid[x][i] + grid[x + 1][i] + grid[x + 2][i] == 15) {
;
} else {
return false;
}
}
if (grid[x][y] + grid[x + 1][y + 1] + grid[x + 2][y + 2] == 15) {
;
} else {
return false;
}
if (grid[x][y + 2] + grid[x + 1][y + 1] + grid[x + 2][y] == 15) {
;
} else {
return false;
}
return true;
}
};
- 优化思路，找到5作为核心点，可以减少很多无用测试，可我不想写了
-
给定一个由空格分割单词的句子
S。每个单词只包含大写或小写字母。我们要将句子转换为 “Goat Latin”（一种类似于 猪拉丁文 - Pig Latin 的虚构语言）。
山羊拉丁文的规则如下：
- 如果单词以元音开头（a, e, i, o, u），在单词后添加
"ma"。
例如，单词"apple"变为"applema"。 - 如果单词以辅音字母开头（即非元音字母），移除第一个字符并将它放到末尾，之后再添加
"ma"。
例如，单词"goat"变为"oatgma"。 - 根据单词在句子中的索引，在单词最后添加与索引相同数量的字母
'a'，索引从1开始。
例如，在第一个单词后添加"a"，在第二个单词后添加"aa"，以此类推。
返回将
S转换为山羊拉丁文后的句子。示例 1:
输入: "I speak Goat Latin" 输出: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"示例 2:
输入: "The quick brown fox jumped over the lazy dog" 输出: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"说明:
-
S中仅包含大小写字母和空格。单词间有且仅有一个空格。 -
1 <= S.length <= 150。
- 如果单词以元音开头（a, e, i, o, u），在单词后添加
参考文章
//Line 933: Char 34: runtime error: reference binding to null pointer of type 'struct value_type' (stl_vector.h)
//不懂C++不知道哪里错了是最惨的
class Solution {
public:
string toGoatLatin(string S) {
vector<string> wordVec;
string result = "";
int len = S.size();
//录入数组中的单词
for (int i = 0; i < len; i++) {
int j = i, count = 0;
while (S[j] != ' ') {
wordVec[count].push_back(S[j]);
j++;
}
i = j + 1;
}
int addIndex = 1;
for (string &temp : wordVec) {
if (temp[0] == 'a' || temp[0] == 'e' || temp[0] == 'i' || temp[0] == 'o' || temp[0] == 'u') {
temp.push_back('m');
temp.push_back('a');
} else {
temp.push_back(temp[0]);
temp.erase(0, 1);
}
for (int i = 0; i < addIndex; i++) {
temp.push_back('a');
}
addIndex++;
result += temp;
}
return result;
}
};
//现在已知的情报就是我们不能使用vector<string> stringVec中的stringVec[0] 去push_back某个字符，完全不懂为什么
class Solution {
public:
string toGoatLatin(string S) {
if (S.empty()) {
return S;
}
vector<string> wordVec;
string result = "";
int len = S.size();
int count = 0;
bool flag = true;
string tempS = "";
//录入数组中的单词
for (char c : S) {
if (flag) {
;
} else {
wordVec.push_back(tempS);
tempS = "";
flag = !flag;
}
if (c == ' ') {
flag = !flag;
continue;
} else {
tempS.push_back(c);
}
}
wordVec.push_back(tempS);
int addIndex = 1;
for (string &temp : wordVec) {
if (temp[0] == 'a' || temp[0] == 'e' || temp[0] == 'i' || temp[0] == 'o' || temp[0] == 'u' || temp[0] == 'A' || temp[0] == 'E' || temp[0] == 'I' || temp[0] == 'O' || temp[0] == 'U') {
temp.push_back('m');
temp.push_back('a');
} else {
temp.push_back(temp[0]);
temp.erase(0, 1);
temp.push_back('m');
temp.push_back('a');
}
for (int i = 0; i < addIndex; i++) {
temp.push_back('a');
}
addIndex++;
result += temp;
result += ' ';
}
result.erase(result.size() - 1, 1);
return result;
}
};
class Solution {
public:
string toGoatLatin(string S) {
unordered_set<char> vowel{'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
istringstream ss(S);
string res, t;
int cnt = 1;
while (ss >> t) {
res += ' ' + (vowel.count(t[0]) ? t : t.substr(1) + t[0]) + "ma" + string(cnt, 'a');
++cnt;
}
return res.substr(1);
}
};
