第 102 场力扣夜喵双周赛

模拟

class Solution {
public:vector<int> findColumnWidth(vector<vector<int>> &g) {int m = g.size(), n = g[0].size();vector<int> res(n);for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)res[j] = max(res[j], (int)to_string(g[i][j]).size());return res;}
};

还是模拟

class Solution {
public:vector<long long> findPrefixScore(vector<int> &a) {int n = a.size();vector<long long> res(n);res[0] = a[0] * 2;long long mx = a[0];for (int i = 1; i < n; i++) {mx = max(mx, (long long) a[i]);res[i] = res[i - 1] + a[i] + mx;}return res;}
};

记录每层节点值之和，哈希记录每个节点的 父节点的所有儿子节点的值之和，二者做差即为所求

class Solution {
public:typedef long long ll;int s[100001];unordered_map<TreeNode *, int> bro;void dfs(TreeNode *root, int cur) {if (!root) return;s[cur] += root->val;if (root->left && root->right) {bro[root->left] = root->left->val + root->right->val;bro[root->right] = root->left->val + root->right->val;} else if (root->left)bro[root->left] = root->left->val;else if (root->right)bro[root->right] = root->right->val;dfs(root->left, cur + 1);dfs(root->right, cur + 1);}void get(TreeNode *root, int cur) {if (!root)return;root->val = s[cur] - bro[root];get(root->left, cur + 1);get(root->right, cur + 1);}TreeNode *replaceValueInTree(TreeNode *root) {memset(s, 0, sizeof(s));dfs(root, 0);bro[root] = root->val;get(root, 0);return root;}
};

dijkstra模板题

class Graph {
public:vector<pair<int, int>> e[100];int n;Graph(int n, vector<vector<int>> &edges) {this->n = n;for (auto &ei: edges)e[ei[0]].emplace_back(ei[1], ei[2]);}void addEdge(vector<int> edge) {e[edge[0]].emplace_back(edge[1], edge[2]);}int shortestPath(int node1, int node2) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;vector<int> d(n, 1e9);d[node1] = 0;heap.emplace(0, node1);while (!heap.empty()) {auto [cur, t] = heap.top();heap.pop();if (cur > d[t])continue;for (auto [j, w]: e[t]) {if (cur + w < d[j]) {d[j] = cur + w;heap.emplace(d[j], j);}}}return d[node2] == 1e9 ? -1 : d[node2];}
};