題目
一如既往菜的我只a了三道堕澄。
題目鏈接：
題目分析
1455.檢查單詞是否為句中其他單詞的前綴
這道題目思路還是比較清晰的，遍歷原字符串敬特，遍歷到空字符或遍歷到最后一位表示遍歷到了一個單詞柔吼，對比給定的單詞毒费，看看是否是其前綴即可。
1456.定長子串中元音的最大數(shù)目
這道題目可以使用滑動窗口的思路愈魏。
首先創(chuàng)建一個數(shù)組觅玻，然后遍歷一遍原字符串溪厘，如果當前字符是元音僻爽，則當前數(shù)組為1秽荤；如果不是元音晨继，則當前數(shù)組為0紊扬。
vector<int> res;
for (auto temp : s) {
if (temp == 'a' || temp == 'e' || temp == 'i' || temp == 'o' || temp == 'u') {
res.push_back(1);
}else res.push_back(0);
}
然后按照給定的k固定好窗口左端和右端啤挎，并計算窗口內(nèi)元音個數(shù)（由于我們將其轉(zhuǎn)換為了01數(shù)組驻谆，其實求和即可）：
int left = 0;
int right = k - 1;
int count = 0;
int temp = 0;
for (int i = left; i <= right; i++) {
temp += res[i];
}
count = count > temp ? count : temp;
然后開始移動窗口兩端，移動的方式也很簡單:
- 如果當前左指針指向的是元音庆聘，則
temp--; - 如果當前右指針的下一位指向的是原因胜臊，則
temp++； - 然后左指針和右指針同時向前移動一位伙判，更新
count象对。
while (right + 1 < res.size()) {
if (res[left] == 1) {
temp--;
}
if (res[right + 1] == 1) {
temp++;
}
count = count > temp ? count : temp;
left++;
right++;
}
返回count即可。
1457.二叉樹中的偽回文路徑
我這道題采用的是模擬的方式宴抚，首先用回溯算法遍歷所有根節(jié)點到葉子結(jié)點的路徑勒魔，然后檢驗這個路徑是否是偽回文路徑。
回溯算法求根節(jié)點到葉子結(jié)點的路徑：
// res儲存?zhèn)位匚穆窂絺€數(shù)菇曲，path儲存當前路徑
void BackTrack(TreeNode* root, int& res, vector<int>& path) {
if (!root->left && !root->right) {
// 找到了葉子結(jié)點冠绢，檢驗這個路徑是不是偽回文
return ;
}
if (root->left) {
path.push_back(root->left->val);
BackTrack(root->left);
path.pop_back();
}
if (root->right) {
path.push_back(root->right->val);
BackTrack(root->right);
path.pop_back();
}
}
然后檢驗是不是回文路徑，其實也很簡單常潮，區(qū)分偶數(shù)和奇數(shù)就可以：
- 如果路徑元素個數(shù)是偶數(shù)個弟胀，若要構(gòu)成回文，則每一種元素都應(yīng)該是偶數(shù)個喊式；
- 如果路徑元素個數(shù)是奇數(shù)個孵户，若要構(gòu)成回文，則最多有一種元素可以是奇數(shù)個岔留。
bool isPal(vector<int> s) {
int len = s.size();
if (len == 1) return true;
if (len == 2) return false;
int res = 0;
sort(s.begin(), s.end());
for (int i = 0; i < len - 1; i++) {
if (s[i] == s[i + 1]) i++;
else {
res++;
}
}
if (len % 2 == 0) {
return res == 0;
}else {
return res <= 1;
}
}
最后返回res即可夏哭。
題目解答
1455.檢查單詞是否為句中其他單詞的前綴
class Solution {
public:
bool isPre(string s, string t, int l, int r) {
int len = t.length();
int flag = 0;
while (flag < len) {
// printf("%c %c\n", t[flag], s[l]);
if (t[flag] != s[l]) return false;
else {
flag++;
l++;
}
}
return true;
}
int isPrefixOfWord(string sentence, string searchWord) {
if (sentence.size() < searchWord.size()) return -1;
int n = searchWord.size();
int left = 0;
int right = 0;
int res = 0;
for (int i = 0; i < sentence.size() + 1; i++) {
if (sentence[i] == ' ' || i == sentence.size()) {
res++;
right = i - 1;
// printf("%d %d %d\n", left, right, right - left + 1);
if (right - left + 1 >= n) {
if(isPre(sentence, searchWord, left, right)) return res;
}
left = i + 1;
}
}
return -1;
}
};
1456.定長子串中元音的最大數(shù)目
class Solution {
public:
int maxVowels(string s, int k) {
vector<int> res;
for (auto temp : s) {
if (temp == 'a' || temp == 'e' || temp == 'i' || temp == 'o' || temp == 'u') {
res.push_back(1);
}else res.push_back(0);
}
int left = 0;
int right = k - 1;
int count = 0;
int temp = 0;
for (int i = left; i <= right; i++) {
temp += res[i];
}
count = count > temp ? count : temp;
while (right + 1 < res.size()) {
if (res[left] == 1) {
temp--;
}
if (res[right + 1] == 1) {
temp++;
}
count = count > temp ? count : temp;
left++;
right++;
}
return count;
}
};
1457.二叉樹中的偽回文路徑
class Solution {
public:
bool isPal(vector<int> s) {
int len = s.size();
if (len == 1) return true;
if (len == 2) return false;
int res = 0;
sort(s.begin(), s.end());
for (int i = 0; i < len - 1; i++) {
if (s[i] == s[i + 1]) i++;
else {
res++;
}
}
if (len % 2 == 0) {
return res == 0;
}else {
return res <= 1;
}
}
void PreOrder(TreeNode* root, vector<int>& path, int& res) {
if ( !root->right && !root->left ){
if (isPal(path)) res++;
return ;
}
if (root->left) {
path.push_back(root->left->val);
PreOrder(root->left, path, res);
path.pop_back();
}
if (root->right) {
path.push_back(root->right->val);
PreOrder(root->right, path, res);
path.pop_back();
}
}
int pseudoPalindromicPaths (TreeNode* root) {
if (!root) return 0;
if (!root->left && !root->right) return 1;
vector<int> path;
path.push_back(root->val);
int res = 0;
PreOrder(root, path, res);
return res;
}
};
