5.13 note
Linux下 如何更新文件名
借助mv命令
# 先退回上级目录（确保不在要修改的目录内操作）
lvy@host:~/old_name/io$ cd ../..
lvy@host:~$ # 执行重命名操作
lvy@host:~$ mv old_name new_name# 验证结果
lvy@host:~$ ls
new_name # 应显示新的目录名# 重新进入目标目录
lvy@host:~$ cd new_name/io
lvy@host:~/new_name/io$
并查集
并查集:数组模拟
数组存的为，该下标的父结点 。
实现代码
合并优化
防止树过高
这里写的是按size合并，最后面的状态压缩后的v3 我们用的是rank版本
状态压缩
实现了方便下一次的查找
代码
斜杠划分的区域
合并顶点
// 并查集常规模版
class Djset {
public:
vector<int> parent; // 记录父节点
vector<int> rank; // 记录节点的秩
int count; // 记录区域数
Djset(int n): parent(n), rank(n), count(1) {
for (int i = 0; i < n; i++) parent[i] = i;
}
// 查找 父结点
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}//状态压缩
return parent[x];
}
// 合并
void merge(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] < rank[rooty]){
swap(rootx, rooty);
}//按秩合并
parent[rooty] = rootx;
if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
}
else
count++;//区域数
}
int getCount()
{
return count;
}
};
class Solution {
public:
int regionsBySlashes(vector<string>& grid)
{
int n = grid.size();
if (n == 0) return 0;
// m : 每行顶点数目
int m = n + 1;
// num : 顶点总数
int num = m * m;
// 初始化： 将所有边缘合并
Djset ds(num + 1);
for (int i = 0; i < num; i++) {
if (i / m == 0 || i / m == m - 1 || i % m == 0 || i % m == m - 1)
ds.merge(num, i);
}
// 访问每个小网格
for (int r = 0; r < n; r++)
{
auto s = grid[r];
for (int c = 0; c < s.size(); c++)
{
if (s[c] == '/')
ds.merge((r + 1) * m + c, r * m + c + 1);
else if (s[c] == '\\')
ds.merge(r * m + c, (r + 1) * m + c + 1);
}
}
return ds.getCount();
}
};
dfs 子序列.去重
class Solution {
int ret = 0, n = 0;
unordered_set<string> set;
string path;
vector<bool> visited; // 访问标记数组
public:
int numTilePossibilities(string tiles) {
n = tiles.size();
sort(tiles.begin(), tiles.end()); // 排序处理重复
visited.resize(n, false);
dfs(tiles);
return ret;
}
void dfs(string& tiles) {
for (int i = 0; i < n; ++i) {
if (visited[i]) continue;
// 跳过重复元素
if (i > 0 && tiles[i] == tiles[i - 1] && !visited[i - 1])
//除了这么判==以外，用set去重也行
continue;
visited[i] = true;
path.push_back(tiles[i]);
ret++;
dfs(tiles);
path.pop_back(); // 回溯
visited[i] = false;
}
}
};
不排序，set去重方法
if (!set.count(path)) {
set.insert(path);
++ret;
}
`.dat` 文件是一种通用的数据文件扩展名，用于存储各种类型的数据。
平衡二叉树
class Solution {
public:
vector<TreeNode*> helper(int start,int end){
vector<TreeNode*> ret;
if(start > end)
ret.push_back(nullptr);
for(int i=start;i<=end;i++){
vector<TreeNode*> left = helper(start,i-1);
vector<TreeNode*> right = helper(i+1,end);
for(auto l : left){
for(auto r : right){
TreeNode* root = new TreeNode(i);
root -> left = l;
root -> right = r;
ret.push_back(root);
}
}
}
return ret;
}
vector<TreeNode*> generateTrees(int n) {
vector<TreeNode*> ret;
if(n == 0)
return ret;
ret = helper(1,n);
return ret;
}
};