haaai

3357

haaai
23天前
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
typedef long long LL;
const int mod = 1e9 + 7;
class Solution {
public:
LL sum, ans = 0;

LL getSum(TreeNode* node){
if (!node)  return 0;
return getSum(node->left) + getSum(node->right) + node->val;
}

LL dfs(TreeNode* node){
if (!node)  return 0;
LL sum_d = dfs(node->left) + dfs(node->right) + node->val;
ans = max(ans, sum_d * (sum - sum_d));
return sum_d;
}

int maxProduct(TreeNode* root) {
sum = getSum(root);
dfs(root);
return ans % mod;
}
};


haaai
1个月前

DFS遍历整棵树，记录每个节点到所有左右子树叶子节点的距离。
dist[i][j][k] 表示第i个节点左子树(j = 0)或右子树(j = 1)距离为k的叶子节点个数

class Solution {
public:

int dist[1100][2][15];
int cnt = 0;

void dfs(TreeNode* node, int father, bool isRight){
if (!node)  return;
cnt++;
int idx = cnt;
dfs(node->left, idx, 0);
dfs(node->right, idx, 1);

//judge leaf node
if (!node->left && !node->right)    dist[idx][0][0]++;
for (int i = 0; i<=10; i++)
dist[father][isRight][i+1] = dist[idx][0][i] + dist[idx][1][i];
}

int countPairs(TreeNode* root, int distance) {
memset(dist, 0, sizeof dist);
dfs(root, 0, 0);

int ans = 0;
for (int i = 1; i<=cnt; i++){
int sum = 0;
for (int j = distance - 1, k = 1; j >=1; j--, k++){
sum += dist[i][1][k];
ans += dist[i][0][j] * sum;
}
}
return ans;
}
};


haaai
1个月前

class Solution {
public:
double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
for (auto &e : edges){
int u = e[0], v = e[1];
}

vector<double> prob(n+1, -1);
queue<int> q;

prob[1] = 1;
q.push(1);
while (t--){
for (int i = 0, siz = q.size(); i < siz; i++){
auto u = q.front(); q.pop();

bool isLeft = false;
if (prob[v] == 0)   continue;
isLeft =true;
q.push(v);
prob[v] = prob[u] / (adj[u].size() - (u != 1));
}
if (isLeft) prob[u] = 0;
}
}
return prob[target] == -1 ? 0 : prob[target];
}
};


haaai
2个月前
class Solution {
public:

int count(ListNode* node){
int len = 0;
while (node)
len++,  node = node->next;
return len;
}

vector<ListNode*> splitListToParts(ListNode* root, int k) {
int len = count(root);

auto p = root;
for (int i = 0; i<k; i++)
for (int j = 0; j < len / k + (i < len % k); j++){
tail[i]->next = p, tail[i] = p;
else
head[i] = p, tail[i] = p;
p = p->next;
}

for (int i = 0; i<k; i++)
if (tail[i])    tail[i]->next = nullptr;

}
};


haaai
2个月前

typedef pair<int, int> PII;
const int INF = 1e9;
class Solution {
public:
int minSumOfLengths(vector<int>& arr, int target) {
int n = arr.size();
int len1 = INF, ans = INF, sum = 0;
queue<PII> q;
for (int i = 0, j = 0; i<n; i++){
sum += arr[i];
while (j < n && sum > target)    sum -= arr[j++];
if (sum == target){
int len2 = i - j + 1;
while (q.size() && q.front().first < j){
len1 = min(len1, q.front().second);
q.pop();
}
ans = min(ans, len1 + len2);
q.push({i, len2});
}
}
return ans >= INF ? -1 : ans;
}
};


haaai
2个月前

const int N = 510;
int dx[] = {0,1};
int dy[] = {1,0};
class Solution {
public:

int n, m;
int p[N*N];

int getX(int i, int j){
return i *m + j;
}

int find(int x){
if (p[x] != x)  p[x] = find(p[x]);
return p[x];
}

bool containsCycle(vector<vector<char>>& grid) {
n = grid.size(), m = grid[0].size();
memset(p, -1, sizeof p);
for (int i = 0; i<n; i++)
for (int j = 0; j<m; j++)
p[getX(i, j)] = getX(i, j);

for (int i = 0; i<n; i++)
for (int j = 0; j <m; j++){
for (int k = 0; k < 2; k++){
int x_ne = i + dx[k], y_ne = j + dy[k];
if (x_ne >= n || y_ne >= m) continue;
if (grid[i][j] != grid[x_ne][y_ne]) continue;

int pa = find(getX(i, j)), pb = find(getX(x_ne, y_ne));
if (pa == pb)   return true;
p[pa] = pb;
}
}
return false;
}
};


haaai
2个月前

stk_s中的星号两种抵消方式
1. 左括号不够用来抵消当前的右括号，这时用stk_s中存的星号来抵消
2. 字符串遍历完后，stk_l 中剩余的左括号需要用在这些左括号右边的星号抵消

class Solution {
public:
bool checkValidString(string s) {
int n = s.size();
stack<int> stk_l, stk_s;
for (int i = 0; i<n; i++){
char &c = s[i];
if (c == '(')
stk_l.push(i);
else if (c == '*')
stk_s.push(i);
else if (c == ')'){
if (stk_l.size())  stk_l.pop();
else{
if (stk_s.size())    stk_s.pop();
else
return false;
}
}
}

while (stk_l.size()){
if (stk_s.size() && stk_s.top() > stk_l.top())
stk_s.pop(), stk_l.pop();
else return false;
}
return true;

}
};


haaai
2个月前

stk_s中的星号两种抵消方式
1. 左括号不够用来抵消当前的右括号，这时用stk_s中存的星号来抵消
2. 字符串遍历完后，stk_l 中剩余的左括号需要用在这些左括号右边的星号抵消

class Solution {
public:
bool checkValidString(string s) {
int n = s.size();
stack<int> stk_l, stk_s;
for (int i = 0; i<n; i++){
char &c = s[i];
if (c == '(')
stk_l.push(i);
else if (c == '*')
stk_s.push(i);
else if (c == ')'){
if (stk_l.size())  stk_l.pop();
else{
if (stk_s.size())    stk_s.pop();
else
return false;
}
}
}

while (stk_l.size()){
if (stk_s.size() && stk_s.top() > stk_l.top())
stk_s.pop(), stk_l.pop();
else return false;
}
return true;

}
};


haaai
2个月前

class Solution {
public:
int l = 0, r = 0;
for (auto &c : S){
if (c == '(')   l++;
else{
if (l) l--;
else    r++;
}
}
return l + r;
}
};


haaai
2个月前

typedef pair<int, int> PII;
class Solution {
public:

void addStr(string &str, vector<PII> &arr, int i, int maxv) {
int used = min(maxv, arr[i].first);
arr[i].first -= used;
while (used--)
str += 'a' + arr[i].second;
}

string longestDiverseString(int a, int b, int c) {
vector<PII> arr = { {a, 0}, {b, 1}, {c, 2} };

string ans ="";
while (1) {
sort(arr.begin(), arr.end());
if (ans.size() && ans.back() == 'a' + arr[2].second) {
if (arr[1].first == 0)
return ans;