[CS学习]算法与数据结构题解 更新中

分类总结一些算法与数据结构的题目，持续更新中…小标题即为原题链接

Binary Tree

102. Binary Tree Level Order Traversal

class Solution {
public:
    vector<TreeNode*> que;
    vector<vector<int>> levelOrder(TreeNode* root) {
        que.push_back(root);
        vector<vector<int>> ans;
        if(!root) {
            return ans;
        }
        while(!que.empty()) {
            int n = que.size();
            vector<int> tmp;
            for(int i = 0; i < n; i++) {
                TreeNode* cur = que.front();
                que.erase(que.begin());
                tmp.push_back(cur->val);
                if(cur->left) {
                    que.push_back(cur->left);
                }
                if(cur->right) {
                    que.push_back(cur->right);
                }
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

need a queue ADT
while queue is not empty, pop front and push back its child

• output level order sequence only
• to obtain level info of nodes -> need to get que.size() first and implement a nested for loop(que.size() times), which dequeue nodes from the same level

103. Binary Tree Zigzag Level Order Traversal Level Order with Queue

class Solution {
public:
    vector<TreeNode*> que;
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        que.push_back(root);
        vector<vector<int>> ans;
        if(!root) {
            return ans;
        }
        int level = 0;
        while(!que.empty()) {
            int n = que.size();
            level++;
            vector<int> tmp;
            for(int i = 0; i < n; i++) {
                TreeNode* cur = que.front();
                que.erase(que.begin());
                tmp.push_back(cur->val);
                if(cur->left) {
                    que.push_back(cur->left);
                }
                if(cur->right) {
                    que.push_back(cur->right);
                }
            }
            if(0 == level % 2) {
                reverse(tmp.begin(), tmp.end());
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

zig-zag traversal of binary tree
reverse tmp sequence if current level is even number

106. Construct Binary Tree from Inorder and Postorder Traversal

class Solution {

public:

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {

        if(postorder.empty()) {

            return nullptr;

        }

        int rootVal = postorder.back();

        int leftSize = find(inorder.begin(), inorder.end(), rootVal) - inorder.begin();


        vector<int> il(inorder.begin(), inorder.begin() + leftSize);

        vector<int> ir(inorder.begin() + leftSize + 1, inorder.end());

        vector<int> pl(postorder.begin(), postorder.begin() + leftSize);

        vector<int> pr(postorder.begin() + leftSize, postorder.end() - 1);

        TreeNode* left = buildTree(il, pl);

        TreeNode* right = buildTree(ir, pr);

        return new TreeNode(rootVal, left, right);
    }
};

109. Convert Sorted List to Binary Search Tree

class Solution {

public:
    TreeNode* cons(vector<int> seq) {
        if(seq.empty()) {
            return nullptr;
        }
        int n = seq.size() - 1;
        int mid;
        if(n % 2 == 0) {
            mid = n / 2;
        } else {
            mid = n / 2 + 1;
        }
        cout<<mid<<" ";
        int val = seq[mid];
        if(0 == mid) {
            return new TreeNode(val, nullptr, nullptr);
        }
        vector<int> leftT(seq.begin(), seq.begin() + mid);
        vector<int> rightT(seq.begin() + mid + 1, seq.end());
        TreeNode* left = cons(leftT);
        TreeNode* right = cons(rightT);
        return new TreeNode(val, left, right);
    }



    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> seq;
        for(ListNode* n = head; n != nullptr; n = n->next) {
            seq.push_back(n->val);
        }
        int n = seq.size();
        cout<<n<<endl;
        return cons(seq);
    }
};

• find middle element
• recursively construct left and right sub trees

101. Symmetric Tree DFS/Preorder Traversal

bool left_right(struct TreeNode* Lroot, struct TreeNode* Rroot) {
    if ((NULL == Lroot) && (NULL == Rroot)) {
        return true;
    } else if ((NULL == Lroot) || (NULL == Rroot)) {
        return false;
    }
    if (Lroot->val != Rroot->val) {
        return false;
    } else {
        return (left_right(Lroot->left, Rroot->right) && left_right(Lroot->right, Rroot->left));
    }
}

bool isSymmetric(struct TreeNode* root) {
    return left_right(root->left, root->right);
}

Graph

2065. Maximum Path Quality of a Graph Dijkstra Algo

class Solution {

public:
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        //graph construction
        int n = values.size();
        vector<vector<pair<int, int>>> g(n);
        for(auto& p : edges) {
            int v = p[0], u = p[1], w = p[2];
            g[u].push_back(make_pair(v, w));
            g[v].push_back(make_pair(u, w));
        }
        //dijkstra algo

        vector<int> dis(n, INT_MAX);
        dis[0] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.emplace(0, 0);
        while(!pq.empty()) {
            auto [d, v] = pq.top();
            pq.pop();
            if(d > dis[v]) {
                continue;
            }
            for(auto& [u, w] : g[v]) {
                int newDis = d + w;
                if(newDis < dis[u]) {
                    dis[u] = newDis;
                    pq.emplace(newDis, u);
                }
            }
        }

        int ans = 0;
        vector<int> vis(n);
        vis[0] = true;
        auto dfs = [&](auto&& dfs, int x, int sum_time, int sum_value) -> void {
            if (x == 0) {
                ans = max(ans, sum_value);
            }
            for (auto& [y, t] : g[x]) {
                if (sum_time + t + dis[y] > maxTime) {
                    continue;
                }
                if (vis[y]) {
                    dfs(dfs, y, sum_time + t, sum_value);
                } else {
                    vis[y] = true;
                    // 每个节点的价值至多算入价值总和中一次
                    dfs(dfs, y, sum_time + t, sum_value + values[y]);
                    vis[y] = false; // 恢复现场
                }
            }
        };
        dfs(dfs, 0, 0, values[0]);
        return ans;
    }
};

Undefined

3115. Maximum Prime Difference 1294/3

class Solution {
public:
    int maximumPrimeDifference(vector<int>& nums) {
        int n = nums.size();
        vector<int> flag(n + 1, 0);
        for(int i = 0; i < n; i++) {
            int x = nums[i];
            bool isPrime = true;
            if(1 == x) {
                isPrime = false;
            }
            if(x % 2 == 0) {
                if(2 == x) {
                    isPrime = true;
                } else {
                    isPrime = false;
                }

            }
            for(int d = 3; d <= sqrt(x); d += 2) {
                if(x % d == 0) {
                    flag[i] = 0;
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) {
                flag[i] = 1;
            } else {
                flag[i] = 0;
            }

        }
        int p1 = 0;
        int p2 = n - 1;
        while(flag[p1++] != 1);
        while(flag[p2--] != 1);
        return (p2 + 1) - (p1 - 1);
    }
};

Math

3099. Harshad Number 1101/2

class Solution {
public:
    int sumOfTheDigitsOfHarshadNumber(int x) {
        int sum = 0;
        int tmp = x;
        while(tmp / 10 != 0) {
            sum += tmp % 10;
            tmp /= 10;
        }
        sum += tmp;
        return (x % sum == 0) ? sum : -1;
    }
};