int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好 vector<int> father = vector<int> (n, 0); // 数组结构 // 并查集里寻根的过程 intfind(int u){ if (u == father[u]) return u; // 如果根就是自己，直接返回 elsereturnfind(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找 } // 并查集初始化 voidinit(){ for (int i = 0; i < n; ++i) { father[i] = i; } } // 将v，u 这条边加入并查集 voidjoin(int u, int v){ u = find(u); // 寻找u的根 v = find(v); // 寻找v的根 if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回 father[v] = u; } // 判断 u 和 v是否找到同一个根 boolisSame(int u, int v){ u = find(u); v = find(v); return u == v; } // 计算集合的个数 intcount_sets(int n){ int cnt = 0; for (int i = 0; i < n; i++) if (find(i) == i) cnt++; return cnt; }
// 快速排序 voidQuickSort(int arr[], int start, int end){ if (start >= end) return; int i = start; int j = end; // 基准数 int baseval = arr[start]; while (i < j){ // 先右后左 // 从右向左找比基准数小的数 while (i < j && arr[j] >= baseval){ j--; } if (i < j){ arr[i] = arr[j]; i++; } // 从左向右找比基准数大的数 while (i < j && arr[i] < baseval){ i++; } if (i < j){ arr[j] = arr[i]; j--; } } // 把基准数放到i的位置 arr[i] = baseval; // 递归 QuickSort(arr, start, i - 1); QuickSort(arr, i + 1, end); }
classSolution{ public: inttrap(vector<int> &height){ int res = 0; int n = height.size(); int waterFlag = false; // 当前状态是否可以装水【即是否在桶内】 int maxHigh = 0; // 当前左边最高柱子 int waterHigh = 0; // 当前最高水位
vector<int> rightMax(n, 0); for (int i = n - 2; i >= 0; i--) // 记录右边最高的柱子，限制最高水位 waterHigh rightMax[i] = max(rightMax[i + 1], height[i + 1]); for (int i = 0; i < n; i++){ if (height[i] > maxHigh) // 更新左边最高柱子 maxHigh = height[i]; waterHigh = min(maxHigh, rightMax[i]); // 根据左边高度和右边高度来限制水位
if (waterHigh > height[i]) res += waterHigh - height[i]; } return res; } };
classSolution { public: vector<string> fullJustify(vector<string>& words, int maxWidth){ vector<string> res; int n = words.size(); string line; int line_l = 0; int idx_s = 0; for(int i = 0; i < n; i++){ string tmp_s = words[i]; int tmp_l = tmp_s.size(); if((line_l + tmp_l) > maxWidth){ line = processLine(idx_s, i, words, maxWidth); res.emplace_back(line); idx_s = i; line = tmp_s; // 删除并替换 if(i != n - 1) line += " "; line_l = line.size(); }elseif((line_l + tmp_l) == maxWidth){ line += tmp_s; res.emplace_back(line);
idx_s = i + 1; line = ""; line_l = 0; } else{ if(i != n - 1){ line += tmp_s + " "; line_l = line.size(); }else{ line += tmp_s; line_l = line.size(); } } } if(line_l != 0) res.emplace_back(line.append(maxWidth - line_l, ' ')); return res; }
string processLine(int idx_s, int idx_e, vector<string>& words, int maxWidth){ int wordsCnt = idx_e - idx_s; int len = 0; for(int i = idx_s; i < idx_e; i++) len += words[i].size();
classSolution { public: intminSubArrayLen(int s, vector<int>& nums){ int n = nums.size(); int res = n + 1; // 结果最大只能是 n, 设为n + 1 int sum = 0; int left = 0, right = 0; while(right < n){ sum += nums[right]; while(sum >= s){ // 说明目前right右边界最优，这时候优化左边。 res = min(right - left + 1, res); sum -= nums[left]; left++; // 之所以左边能++，以left为边界的最优情况都考虑过了 } right++; } return res == (n + 1) ? 0 : res; } };
classSolution { public: vector<int> findSubstring(string &s, vector<string> &words){ vector<int> res; // 存储结果的数组 int m = words.size(); // 单词数量 int n = words[0].size(); // 单词长度 int ls = s.size(); // 字符串 s 的长度 for (int i = 0; i < n && i + m * n <= ls; i++) { // 外层循环，从每个可能的起始位置 i 开始【i 属于 [0, ls % mn]】 unordered_map<string, int> differ; // 用于统计当前窗口内单词的出现次数 // 初始化窗口（能容纳 m 个单词），分为两步 // 1. 统计 s 中从当前起始位置 i 开始的 m 个单词 for (int j = 0; j < m; j++) { ++differ[s.substr(i + j * n, n)]; // 将子串加入到 differ 中并计数 } // 2. 遍历 words 中的每个单词，检查其在 differ 中的出现次数 for (string &word: words) { if (--differ[word] == 0) { // 如果单词的计数减为 0，则从 differ 中删除 differ.erase(word); } }
// 内层循环，从起始位置 i 开始滑动窗口 for (int start = i; start < ls - m * n + 1; start += n) { // 滑动到最后所剩不到一个窗口时停止 if (start != i) { // 添加新进入窗口的单词到 differ 中 string word = s.substr(start + (m - 1) * n, n);//窗口右边加的单词 if (++differ[word] == 0) { differ.erase(word); } // 移除窗口左侧移出的单词 word = s.substr(start - n, n); if (--differ[word] == 0) { differ.erase(word); } } // 如果 differ 为空，表示当前窗口符合要求，将起始位置加入结果数组 res if (differ.empty()) { res.emplace_back(start); } } } return res; // 返回所有符合要求的起始位置数组 } };
int left = 0, right = - 1; // 滑动窗口边界 int resL = -1; // 最终结果左边界 int len = INT_MAX; // 最终结果长度 while(right < sl){ if(t.find(s[++right]) != string::npos){ // s[right] 当前元素在 t 当中 s_map[s[right]]++; }
while(check() && left <= right){ if(int tmp; (tmp = right - left + 1) < len){ len = tmp; resL = left; }
classUnionFind{ private: vector<int> parent; vector<int> rank; // 根节点的权重，岛屿的主陆地 public: UnionFind(int n){ rank = vector<int>(n, 0); parent = vector<int>(n, 0); for(int i = 0; i < n; i++) parent[i] = i; } intfind(int x){ if(x== parent[x]) return x; else return parent[x] = find(parent[x]); } voidjoin(int u, int v){ u = find(u); // 寻找u的根 v = find(v); // 寻找v的根 if (u != v) { if (rank[u] > rank[v]) { parent[v] = u; } elseif (rank[u] < rank[v]) { parent[u] = v; } else { parent[v] = u; rank[u]++; } } } }; classSolution { public: intcountSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2){ int m = grid1.size(); int n = grid1[0].size(); int N = m * n; UnionFind uf(N); for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(grid2[i][j]){ if(i > 0 && grid2[i - 1][j]){ // 连接上边 uf.join(i * n + j, (i-1) * n + j); } if(j > 0 && grid2[i][j - 1]){ // 连接左边 uf.join(i * n + j, i * n + j - 1); } } } }
unordered_set<int> islands; for(int i = 0; i < N; i++){ int r = i / n; int c = i % n; if(grid2[r][c]){ islands.emplace(uf.find(i)); } } for(int i = 0; i < N; i++){ int r = i / n; int c = i % n; if(!grid1[r][c]){ // 如果grid1是海，但是grid2是land，需要删除这片land，因为不是子land islands.erase(uf.find(i)); } } return islands.size(); } };
structPoint { int x; int y; Point (int x_ = -1, int y_ = -1) : x(x_), y(y_){} }; boolisValid(int x, int y, int r, int c){ if(x < 0 || x >= r || y < 0 || y >= c) returnfalse; returntrue; } string processXY(int x, int y){ return ("(" + to_string(x) + "," + to_string(y) + ")"); }
intmain(){ // 分别对应，上 下 左 右 int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1};
// 处理输入 int r, c; cin >> r >> c; vector<vector<int>> board(r, vector<int>(c)); for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) cin >> board[i][j];
微信
支付宝