8.16 pq
lc993 找堂兄弟
bfs记录信息
int xDepth = -1, yDepth = -1;
TreeNode* xParent = nullptr, * yParent = nullptr;
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y)
{
queue<TreeNode*> q;
q.push(root);
int xDepth = -1, yDepth = -1;
TreeNode* xParent = nullptr, * yParent = nullptr;
int depth = 0;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
TreeNode* node = q.front();
q.pop();
if (node->left) {
q.push(node->left);
if (node->left->val == x) {
xDepth = depth + 1;
xParent = node;
} else if (node->left->val == y) {
yDepth = depth + 1;
yParent = node;
}
}
if (node->right) {
q.push(node->right);
if (node->right->val == x) {
xDepth = depth + 1;
xParent = node;
} else if (node->right->val == y) {
yDepth = depth + 1;
yParent = node;
}
}
}
depth++;
if (xDepth != -1 && yDepth != -1) {
return xDepth == yDepth && xParent != yParent;
}
}
return false;
}
};
lc374.二分
/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is higher than the picked number
* 1 if num is lower than the picked number
* otherwise return 0
* int guess(int num);
*/
class Solution {
public:
int guessNumber(int n) {
int l = 1;
int r = n;
while(l <= r){
int mid = l + (r - l)/2;
if(guess(mid) == 0){
return mid;
}
if(guess(mid) == 1){
l = mid + 1;
}else{
r = mid - 1;
}
}
return 0;
}
};
lc17.13
dp / dfs memo
class Solution {
public:
int respace(vector<string>& dictionary, string sentence) {
unordered_set<string> dict(dictionary.begin(), dictionary.end());
int n = sentence.size();
// dp[i] 表示前 i 个字符未识别的最少字符数
vector<int> dp(n + 1, n);
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
// 先假设当前字符不匹配，未识别字符数加 1
dp[i] = dp[i - 1] + 1;
for (int j = 0; j < i; ++j) {
if (dict.count(sentence.substr(j, i - j))) {
// 如果从 j 到 i - j 的子串在词典中，更新未识别字符数
dp[i] = min(dp[i], dp[j]);
}
}
}
return dp[n];
}
};
memo
lc17.15
dfs+tmp set
另外单词组成的检验
for(int i=1;i<=s.size();i++)
{
if (words.count(s.substr(0, i)) && isCombinated(s.substr(i), words))return true;
}
class Solution {
public:
string longestWord(vector<string>& words) {
unordered_set<string> allWords(words.begin(), words.end());
string ans;
for(auto word:words)
{
auto tmpCollects = allWords;
tmpCollects.erase(word);
if(isCombinated(word,tmpCollects))
{
if (word.size() > ans.size())
ans = word;
if (word.size() == ans.size())
ans = min(ans, word);
}
}
return ans;
}
private:
bool isCombinated(string s,unordered_set<string>& words)
{
if (s.size() == 0)return true;
for(int i=1;i<=s.size();i++)
{
if (words.count(s.substr(0, i)) && isCombinated(s.substr(i), words))
return true;
}
return false;
}
};
lc17.14 前k小元素
大顶堆--递减堆
class Solution {
public:
vector<int> smallestK(vector<int>& arr, int k) {
if (k == 0) return {};
priority_queue<int> pq; //默认递减堆
vector<int> ans(k);
for (int i = 0; i < arr.size(); i ++) {
if (pq.size() < k)
{
pq.push(arr[i]);
}
else{
if (pq.top() > arr[i]) //递减堆
{
pq.pop();
pq.push(arr[i]); //换更小
}
}
}
int idx = 0;
while (! pq.empty()) {
ans[idx ++] = pq.top();
pq.pop();
}
return ans;
}
};
lc17.17
//以每个位置为起始，开始测试
int k = 0;
while (k < sz && s[k] == big[j + k])
k++;
if (k == sz)
ret[i].push_back(j);
class Solution {
public:
vector<vector<int>> multiSearch(string big, vector<string>& smalls)
{
int m = big.size(), n = smalls.size();
vector<vector<int>> ret(n);
for (int i = 0; i < n; i++)
{
string s = smalls[i];
int sz = s.size();
// 如果短字符串为空，直接跳过（根据题目提示，可能不需要，但处理更鲁棒）
if (sz == 0) continue;
for (int j = 0; j <= m - sz; j++)
{
//以每个位置为起始，开始测试
int k = 0;
while (k < sz && s[k] == big[j + k])
{
k++;
}
if (k == sz)
ret[i].push_back(j);
}
}
return ret;
}
};