头像

haaai




离线:7小时前



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的叶子节点个数
最后用双指针计算每个节点满足条件的叶子对。
算法复杂度O(n*distance)

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个月前

用BFS往下搜索,同时用prob数组记录答案

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

        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;
                for (auto v : adj[u]){
                    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) {
        vector<ListNode*> head(k, nullptr), tail(k, nullptr);
        if (!root)  return head;
        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++){
                if (head[i] != nullptr)
                    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;

        return head;
    }
};



haaai
2个月前

利用双指针枚举第二个和为target的区间,并将当前求得的区间信息(长度和结尾坐标)存入队列中,作为第一个区间的信息。

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_l和stk_s分别记录当前未抵消的左括号’(‘和’*’的位置。
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个月前

栈——O(n)
用两个栈stk_l和stk_s分别记录当前未抵消的左括号’(‘和’*’的位置。
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个月前

代码同Leetcode 301 中的预处理

class Solution {
public:
    int minAddToMakeValid(string S) {
        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;
                addStr(ans, arr, 1, 1);
            }
            else {
                if (arr[2].first == 0)
                    return ans;
                addStr(ans, arr, 2, 2);
            }
        }
        return "";
    }
};