滑窗+hash|pii dfs
lc2423
// try -- every char
一个变量控制不明白 那就再加一个变量🤓👆🏻
++cnt; // restore
class Solution {
public:
bool equalFrequency(string word)
{
unordered_map<char,int> hash;
for(auto& c:word)
hash[c]++;
// try -- every char
for(auto& [ch, cnt] : hash)
{
--cnt;
bool f=true;
int t = 0; //freq
for(auto& [k, v] : hash)
{
if(v == 0) continue;
if(t == 0) t = v; // init
if(v != t)
{
f=false;
break;
}
}
if(f) return true;
++cnt; // restore
}
return false;
}
};
lc549
pii dfs遍历二叉树
记录每个节点“递增连续长度up”和“递减连续长度down”
计算以该节点为中心的最长连续序列长度
最终得到整棵树的最长连续序列
"递"获取每个node pii
"归"的时候return以该节点为中间的最长链
class Solution {
public:
int ans = 0;
int longestConsecutive(TreeNode* root) {
auto dfs = [&](this auto&& dfs, TreeNode* node) -> pair<int, int> {
if (!node) return {0, 0};
auto [lu, ld] = dfs(node->left);
auto [ru, rd] = dfs(node->right);
int u = 1, d = 1;
if (node->left && node->val == node->left->val + 1) u = max(u, lu + 1);
if (node->right && node->val == node->right->val + 1) u = max(u, ru + 1);
//record two path choice mx
if (node->left && node->val == node->left->val - 1) d = max(d, ld + 1);
if (node->right && node->val == node->right->val - 1) d = max(d, rd + 1);
ans = max(ans, u + d - 1);
return {u, d};
};
dfs(root);
return ans;
}
};
lc3641
滑窗和hash天生一对😋
class Solution {
//set size
//max len
public:
int longestSubarray(vector<int>& nums, int k)
{
int n=nums.size();
unordered_map<int,int> hash;
int l=0,r=0,mx=0,rp=0;
while(r<n)
{
if(++hash[nums[r]]==2)
rp++;
r++;
while(rp>k)
{
if(--hash[nums[l]]==1)
rp--;
l++;
}
mx=max(mx,r-l);
}
return mx;
}
};
rust导入hash
use std::collections::HashMap;
impl Solution {
pub fn longest_subarray(nums: Vec<i32>, k: i32) -> i32 {
let n = nums.len();
let mut hash = HashMap::new();
let mut l = 0;
let mut rp = 0;
let mut mx = 0;
for r in 0..n {
let cnt =hash.entry(nums[r]).and_modify(|c| *c += 1).or_insert(1);
if *cnt == 2 {
rp += 1;
}
while rp > k {
let cnt = hash.entry(nums[l]).and_modify(|c| *c -= 1).or_insert(0);
if *cnt == 1 {
rp -= 1;
}
l += 1;
}
mx = mx.max((r - l + 1) as i32);
}
mx
}
}