每日一题
86. 分隔链表
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* h1 = new ListNode(0);
h1->next = head;
ListNode *t1 = h1;
//t1->next找到第一个大于等于x的节点
while(t1->next && t1->next->val < x) t1 = t1->next;
//将所有小于x的节点插入到t1后面
ListNode* t2 = t1;
while(t2 && t2->next){
if(t2->next->val < x){
ListNode* q = t2->next;
t2->next = t2->next->next;
q->next = t1->next;
t1->next = q;
t1 = t1->next;
}else //如果发生了修改，实际上已经发生了对t2->next的更新
t2 = t2->next;
}
return h1->next;
}
};
/*
执行用时：8 ms, 在所有 C++ 提交中击败了58.78%的用户
内存消耗：7 MB, 在所有 C++ 提交中击败了64.16%的用户
相当于一个in-place变换，多出来的时间应该是维护内部结构的操作
**/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode *h1 = new ListNode(0), *t1 = h1;
ListNode *h2 = new ListNode(0), *t2 = h2;
while(head){
if(head->val < x){
t1->next = head;
t1 = t1->next;
}else{
t2->next = head;
t2 = t2->next;
}
head = head->next;
}
t2->next = NULL;
t1->next = h2->next;
return h1->next;
}
};
/*
用两个指针分别指向较小和较大，忽略对原链表的维护
**/
2021/1/3
509. 斐波那契数
class Solution {
public:
int fib(int n) {
int a=0, b=1, c;
if(n==0) return a;
else if(n==1) return b;
else{
while(n>=2){
c=a+b;
a=b;
b=c;
n--;
}
return c;
}
}
};
/*就这**/
或者
class Solution {
public:
int fib(int n) {
if(n<2)
return n;
else{
int a=0, b=1, c;
while(n-->1){
c=b;
b+=a;
a=c;
}
return b;
}
}
};
2021/1/4
830. 较大分组的位置
class Solution {
public:
//找到每一个不同的分组的起始点并重新计数
vector<vector<int>> largeGroupPositions(string s) {
int start=0, cnt=1;
char pre='\0';
vector<vector<int> > res;
for(int i=0; i<=s.size(); i++){
if(s[i] != pre || i==s.size()){
if(cnt >= 3){
res.push_back({start, start+cnt-1});
}
start = i; cnt=1; pre = s[i];
}else{
cnt++;
}
}
return res;
}
};
/* 96% **/
另解，双指针
class Solution {
public:
vector<vector<int>> largeGroupPositions(string s) {
vector<vector<int> > res;
int i=0, j=0;
for(; j<=s.size(); j++){
if(s[i] != s[j]){
if(j-i>=3)
res.push_back({i, j-1});
i=j;
}
}
return res;
}
};
/* 100% **/
2021/1/5
399. 除法求值
class Solution {
public:
struct Edge{
string variable;
double value;
Edge* next;
Edge(string variable, double value, Edge* next=NULL)
:variable(variable), value(value), next(next){}
};
struct Tmp{
string arg;
double res;
Tmp(string arg, double res=1):arg(arg), res(res){}
};
void appendEdge(map<string, Edge* >& m, string arg1, string arg2, double value){
if(!m[arg1]){ //如果节点不存在
m[arg1] = new Edge(arg2, value);
}else{
Edge* head = m[arg1];
while(head->next) head = head->next;
head->next = new Edge(arg2, value);
}
}
void buildGraph(map<string, Edge* >& m, vector<vector<string> >& equations, vector<double>& values){
for(int i=0; i<equations.size(); i++){
string arg1 = equations[i][0], arg2 = equations[i][1];
appendEdge(m, arg1, arg2, values[i]);
appendEdge(m, arg2, arg1, 1/values[i]);
}
}
double bfs(map<string, Edge* >& m, string& arg1, string& arg2){
map<string, bool> vis;
queue<Tmp> q;
q.push(Tmp(arg1)); vis[arg1]=true;
while(!q.empty()){
Tmp cur = q.front(); q.pop();
if(cur.arg == arg2) return cur.res;
Edge* head = m[cur.arg];;
while(head){
if(!vis[head->variable]){
q.push(Tmp(head->variable, cur.res*head->value));
vis[head->variable] = true;
}
head = head->next;
}
}
return -1;
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
vector<double> res;
map<string, Edge* > m; buildGraph(m, equations, values);
for(int i=0; i<queries.size(); i++){
string arg1 = queries[i][0], arg2 = queries[i][1];
if(!m[arg1] || !m[arg2])
res.push_back(-1);
else
res.push_back(bfs(m, arg1, arg2));
}
return res;
}
};
/* 64.5% **/
我麻了。
大概思路就是将这个二维数组转化为图，然后通过图的bfs搜索出答案。所以下一步优化应该是如何直接bfs
看了看题解，一解是如此，二解是Floyd，感觉复杂度挺高，三解是带权并查集，来试试。
2021/01/06
547. 省份数量
分类：图、并查集
class Solution {
public:
int root(int* u, int j){ //找到j的集合根
while(j != u[j]) j = u[j];
return j;
}
void combine(int* u, int i, int j){ //把j接到i上
u[root(u, j)] = root(u, i);
}
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
int* u = new int[n];
for(int i=0; i<n; i++) u[i]=i;
for(int i=0; i<n-1; i++){
for(int j=i+1; j<n; j++){
if(isConnected[i][j]) combine(u, i, j);
}
}
set<int> s;
for(int i=0; i<n; i++) s.insert(root(u, i));
return s.size();
}
};
/* 91.5% **/
错误1，两个集的合并应该是根进行合并，而不是单个点的合并
优化。不使用辅助set怎么判断集合个数？根等于自己代表这是集合的顶部，数出来就有几个集合。
for(i range n) if(u[i] == i) cnt++;
2021/01/07
189. 旋转数组
分类:
- 数组
数组循环移位经典题
class Solution { // 翻转数组
public:
void reverse(vector<int>& nums, int i, int j){
int t;
while(i < j){
t = nums[i];
nums[i++] = nums[j];
nums[j--] = t;
}
}
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n; // 处理当k大于数组长度的情况
reverse(nums, 0, n-k-1);
reverse(nums, n-k ,n-1);
reverse(nums, 0, n-1);
}
};
/* 17% **/
/* i++; j--; 拿到外面来就是98% 迷惑**/
class Solution { // 复制数组
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> res(n);
for(int i=0; i<n; i++){
res[(i+k)%n] = nums[i];
}
nums = res;
}
};/* 50% **/
还有一种，记录被覆盖位置，交换
2021/01/08
123. 买卖股票的最佳时机 III
分类:
- dp
我以为是动态规划之实际上是暴力
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
// 记录区间[i, j]上的最小值最大值，以使dp[i][j]=该区间上的最大差
int sum = 0;
for(int i=0; i<n; i++){
int _min = prices[i], _max = 0;
dp[i][i] = _max;
for(int j=i+1; j<n; j++){
int diff = prices[j] - _min;
_max = max(_max, diff);
dp[i][j] = _max;
_min = min(_min, prices[j]);
}
sum = max(dp[0][i] + dp[i][n-1], sum);
}
return sum;
}
};
/* O(n^2) TLE **/
动态规划。第i结束时，存在4中产生利润变动的操作：
- 第一次购入股票
buy1 - 第一次卖出股票
sell1 - 已经卖出一次的前提下，第二次购入股票
buy2 - 第二次卖出股票
sell2
对于每一种操作，动态记录操作后的最大利润，那么就有第i+1天的最大利润为：（看代码）
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ini = -prices[0];
int buy1 = ini, sell1 = 0;
int buy2 = ini, sell2 = 0;
for(int i=1; i<prices.size(); i++){
buy1 = max(buy1, -prices[i]);
sell1 = max(sell1, buy1+prices[i]);
buy2 = max(buy2, sell1-prices[i]);
sell2 = max(sell2, buy2+prices[i]);
}
return sell2;
}
};/* 71% **/
2021/01/09
228. 汇总区间
分类：
- 数组
简单题，但是边界条件挺细节，特别是c++，还要额外注意int的边界，不然 nums[i] == nums[i-1] + 1会overflow
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> res;
if(nums.size() == 0) return res;
int start = 0;
for(int i=1; i<nums.size()+1; i++){ // 最后多一次循环来进行扫尾
if(i<nums.size() && nums[i] == nums[i-1] + 1) continue;
else{
res.push_back(
i-1 == start
? to_string(nums[start])
: to_string(nums[start]) + "->" + to_string(nums[i-1])
);
start = i;
}
}
return res;
}
};
2021/01/10
1202. 交换字符串中的元素
分类：图、并查集
同一个连通分量内的字符可任意交换，故各分量内部排序再放回原本位置
class Solution {
public:
int root(int *u, int p){
if (p != u[p])
u[p] = root(u, u[p]); //路径压缩优化
return u[p];
}
void connect(int *u, int i, int j){
u[root(u, j)] = root(u, i);
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int *u = new int[s.size()];
for(int i=0; i<s.size(); i++) u[i] = i;
for(int i=0; i<pairs.size(); i++){
connect(u, pairs[i][0], pairs[i][1]);
}
priority_queue<char, vector<char>, greater<char> > qs[s.size()];
for(int i=0; i<s.size(); i++){
int indexOfSet = root(u, i);
qs[indexOfSet].push(s[i]);
}
string res;
for(int i=0; i<s.size(); i++){
int indexOfSet = root(u, i);
res.push_back(qs[indexOfSet].top());
qs[indexOfSet].pop();
}
delete[] u;
return res;
}
};/* 12% **/
2021/01/11
1203. 项目管理
分类：图、拓扑排序
这题不会，照着题解做的
一个组有一些任务，没有被发配组的任务假设由从m开始递增的唯一组接手（如果不存在没有被分配组的任务，那么这些组接手的任务数量为0，总保持组的数量与任务数量相等）。由于任务与任务存在前后依赖，且同一组的任务需要排在一起。所以通过任务之间的依赖关系形成组之间的依赖关系。
故，先对组进行拓扑排序，再依次对组所拥有的任务进行拓扑排序，即为结果
class Solution {
public:
vector<int> topSort(vector<int>& degree, vector<vector<int> >& graph, vector<int>& ids){
queue<int> q;
vector<int> res;
for(int i : ids)
if(degree[i] == 0) q.push(i);
while(!q.empty()){
int cur = q.front(); q.pop(); res.push_back(cur);
for(int next : graph[cur])
if(--degree[next] == 0) q.push(next);
}
return res.size() == ids.size() ? res : vector<int>();
}
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
vector<int> res;
//组到任务的映射
vector<vector<int> > group2Item(n+m);
//初始化图
vector<vector<int> > groupGraph(n+m);
vector<vector<int> > itemGraph(n);
vector<int> groupDegree(n+m, 0);
vector<int> itemDegree(n, 0);
//给没有被分配的组分配一个不重复的组，初始化组到任务的映射
int leftGroup = m;
for(int i=0; i<n; i++){
if(group[i] == -1) group[i] = leftGroup++;
group2Item[group[i]].emplace_back(i);
}
//初始化任务的图
for(int curItem=0; curItem<beforeItems.size(); curItem++){
int curGroup = group[curItem];
for(int beforeItem : beforeItems[curItem]){
int beforeGroup = group[beforeItem];
if(curGroup==beforeGroup){ //同一组内任务的依赖关系
itemGraph[beforeItem].emplace_back(curItem);
itemDegree[curItem] += 1;
}else{ //不同组之间的依赖关系
groupGraph[beforeGroup].emplace_back(curGroup);
groupDegree[curGroup] += 1;
}
}
}
//组间拓扑排序
vector<int> groupIds(n+m); for(int i=0; i<n+m; i++) groupIds[i]=i;
vector<int> groupTopSort = topSort(groupDegree, groupGraph, groupIds);
if (groupTopSort.size() == 0) return vector<int>();
//组内拓扑排序
for(int groupId : groupTopSort){
int size = group2Item[groupId].size();
if(size == 0) continue;
vector<int> groupItemTopSort = topSort(itemDegree, itemGraph, group2Item[groupId]);
if(groupItemTopSort.size() == 0) return vector<int>();
for(int item : groupItemTopSort) res.push_back(item);
}
return res;
}
};
/* 42% */
2021/01/12
684. 冗余连接
分类：图、并查集
树是有n-1条边的图，再增加一条边，某个子图形成环。按照给定的边，依次在并查集中相连，首次出现集合内相连的边，就是形成环的冗余边
class Solution {
public:
int root(int *u, int p){
if (p != u[p])
u[p] = root(u, u[p]); //路径压缩优化
return u[p];
}
void connect(int *u, int i, int j){
u[root(u, j)] = root(u, i);
}
bool isConnected(int *u, int i, int j){
return root(u, i) == root(u, j);
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size(), *u = new int[n+1];
vector<int> res(2);
for(int i=1; i<n+1; i++) u[i] = i;
for(int i=0; i<n; i++){
int from = edges[i][0], to = edges[i][1];
if(!isConnected(u, from, to)) connect(u, from, to);
else {
res[0] = from, res[1] = to;
break;
}
}
delete[] u;
return res;
}
};
/* 99.8% **/
2010/01/14
1018. 可被 5 整除的二进制前缀
分类：数学
个位为0或5
class Solution {
public:
vector<bool> prefixesDivBy5(vector<int>& A) {
int cur = 0;
vector<bool> res(A.size());
for(int i=0; i<A.size(); i++){
cur = ((cur<<1) | A[i]) % 5;
res[i] = (cur == 0);
}
return res;
}
};/* 100% **/
2010/01/14
947. 移除最多的同行或同列石头
分类：图、并查集
以前的并查集中，总是元素由一个一元表示，而这次元素由一个二元表示
最初的想法是，把行或列相同的点连接，最后点的总数-集合总数就是最多可移除。但是实际上一些例子是无法通过的。暂时想不通为什么。
参考题解，做法是将每个石头的行和列连接。我觉得可以这么考虑，如果所有的石头都不同行列，那么二元的每一个位置都没有交集，二元的两个位置相连接，一共有多少个石头就有多少个集合。如果两个石头产生交集，二元连接后就只产生一个集合，视为一个元素。
class Solution {
public:
int root(unordered_map<int, int> &u, int p){
if(!u.count(p))
u[p] = p;
return p == u[p] ? p : u[p] = root(u, u[p]);
}
void connect(unordered_map<int, int> &u, int i, int j){
u[root(u, j)] = root(u, i);
}
bool isConnected(unordered_map<int, int> &u, int i, int j){
return root(u, i) == root(u, j);
}
int numberOfConnectedComponent(unordered_map<int, int> &u){
int num = 0;
for (auto &[k, v] : u) {
if (k == v) {
num++;
}
}
return num;
}
int removeStones(vector<vector<int>>& stones) {
int n = stones.size();
unordered_map<int, int> u;
for(int i=0; i<n; i++){
connect(u, stones[i][0], stones[i][1]+10000);
}
return n-numberOfConnectedComponent(u);
}
};
2010/01/15
803. 打砖块
这题属实不会
2010/01/16
1232. 缀点成线
分类：数学
class Solution {
public:
bool checkStraightLine(vector<vector<int>>& coordinates) {
int deltx = coordinates[1][0]-coordinates[0][0];
int delty = coordinates[1][1]-coordinates[0][1];
double k = (deltx == 0 ? INT_MAX : delty*1.0/deltx);
for(int i=1; i<coordinates.size()-1; i++){
int deltx2 = coordinates[i+1][0]-coordinates[i][0];
int delty2 = coordinates[i+1][1]-coordinates[i][1];
double k2 = (deltx2 == 0 ? INT_MAX : delty2*1.0/deltx2);
if(k2 != k) return false;
}
return true;
}
};
2021/01/17
1584. 连接所有点的最小费用
分类：图、最小生成树
Prime算法
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
vector<bool> visited(n, false);
vector<int> cost(n, 0);//动态记录触发节点到其他节点的距离
vector<vector<int> > g(n, vector<int>(n));//图
//所有点两两连接
for(int i=0; i<n; i++){
for(int j=i; j<n; j++){
int val = abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1]);
g[i][j] = g[j][i] = val;
}
}
//从出发点开始
int v0 = 0;
for(int i=0; i<n; i++){
cost[i] = g[v0][i];
}
visited[v0] = true;
int sum = 0;
for(int k=0; k<n-1; k++){
//找到当前子图出发的最短边
int _min = INT_MAX, next;
for(int j=0; j<n; j++){
if(!visited[j] && cost[j]<_min){
_min = cost[j];
next = j;
}
}
//边加入当前子图
visited[next]=true;
sum += _min;
//更新当前子图到其他的距离
for(int i=0; i<n; i++){
if(!visited[i] && g[next][i] < cost[i]){
cost[i] = g[next][i];
}
}
}
return sum;
}
};
另解kruskal算法，叕是并查集
2021/01/19
628. 三个数的最大乘积
分类：数学
class Solution {
public:
int maximumProduct(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
//要么两负一正，要么三正
return max(nums[0]*nums[1]*nums[n-1], nums[n-1]*nums[n-2]*nums[n-3]);
}
};
2021/01/20
1489. 找到最小生成树里的关键边和伪关键边
分类：图论、最小生成树、并查集
首先，用正常方法求出生成最小生成树的cost
然后遍历每一条边：
* 如果去掉这条边，图不连通或者生成树`cost2`>`cost`，那么说这条边是关键边
* 如果一开始就连接这条边，生成树`cost2`==`cost`，那么说明这条边是伪关键边
* 其他，说明边不需要
* 关键边同样满足伪关键边情况，伪关键边同样满足不需要的边的情况，所以依次判断关键边、伪关键边
class UnionFind{
private:
unordered_map<int, int> u;
public:
int root(int i){
if(!u.count(i))
u[i] = i;
return u[i] == i? i : u[i] = root(u[i]);
}
void connect(int i, int j){
u[root(i)] = root(j);
}
bool isConnected(int i, int j){
return root(i) == root(j);
}
};
class Edge{
public:
int from, to, weight;
Edge(int f, int t, int w):from(f), to(t), weight(w){}
};
class Compare{
public:
bool operator() (const Edge& a, const Edge& b){
return a.weight > b.weight;
}
};
class Solution {
public:
int kruskal(vector<Edge>& edges, UnionFind u, int n){
priority_queue<Edge, vector<Edge>, Compare> q(edges.begin(), edges.end());
int cost = 0, edgesCnt = 0;
while(!q.empty()){
Edge e = q.top(); q.pop();
if(!u.isConnected(e.from, e.to)){
u.connect(e.from, e.to);
cost += e.weight;
edgesCnt += 1;
}
}
return n-1 == edgesCnt ? cost : INT_MAX;
}
vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
vector<Edge> edges2;
for(vector<int> & v : edges){
edges2.push_back(Edge(v[0], v[1], v[2]));
}
int cost = kruskal(edges2, UnionFind(), n);
vector<int> critical, pseudoCritical;
for(int i=0; i<edges2.size(); i++){
vector<Edge> tmpEdge; UnionFind tmpU;
for(int j=0; j<edges2.size(); j++){
if(i==j) continue;
tmpEdge.push_back(edges2[j]);
}
bool isCritical = (kruskal(tmpEdge, UnionFind(), n) > cost);
if (isCritical){
critical.push_back(i);
}else{
tmpU.connect(edges2[i].from, edges2[i].to);
bool isPseudoCritical = (kruskal(tmpEdge, tmpU, n-1)+edges2[i].weight == cost);
if(isPseudoCritical) pseudoCritical.push_back(i);
}
}
return {critical, pseudoCritical};
}
}; /* 5.9% = = **/
减少不必要的排序过程；并查集容器改为使用vector，unordered_map属实耗时过多
class UnionFind{
private:
vector<int> u;
vector<int> sz;
public:
int member;
UnionFind(int n):member(n), u(n), sz(n, 1){
iota(u.begin(), u.end(), 0);
}
int root(int i){
return u[i] == i? i : u[i] = root(u[i]);
}
bool connect(int i, int j){
int ri = root(i), rj = root(j);
if(ri == rj){
return false;
}
if(sz[ri] < sz[rj]){
swap(ri, rj);
}
u[rj] = ri;
sz[ri] += sz[rj];
member--;
return true;
}
};
class Solution {
public:
static bool compare(const vector<int>& a, const vector<int>& b){
return a[2] < b[2];
}
vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
int m = edges.size();
for (int i=0; i<m; i++) {
edges[i].push_back(i);
} //排序后下标变动
sort(edges.begin(), edges.end(), compare);
int cost = 0; UnionFind u(n);
for(int i=0; i<m; i++){
if(u.connect(edges[i][0], edges[i][1])){
cost += edges[i][2];
}
}
vector<vector<int> > res(2, vector<int>());
for(int i=0; i<m; i++){
int cost1=0; UnionFind u1(n);
for(int j=0; j<m; j++){
if(j!=i && u1.connect(edges[j][0], edges[j][1])){
cost1+=edges[j][2];
}
}
if(u1.member!=1 || cost1 > cost){
res[0].push_back(edges[i][3]);
continue;
}
cost1=edges[i][2]; u1 = UnionFind(n);
u1.connect(edges[i][0], edges[i][1]);
for(int j=0; j<m; j++){
if(j!=i && u1.connect(edges[j][0], edges[j][1])){
cost1+=edges[j][2];
}
}
if(u1.member == 1 && cost1 == cost){
res[1].push_back(edges[i][3]);
}
}
return res;
}
};/* 32.8% **/
2021/01/21
989. 数组形式的整数加法
分类：数学
class Solution {
public:
vector<int> addToArrayForm(vector<int>& A, int K) {
int take = 0;
vector<int> res;
for(int i=A.size()-1; i>=0; i--){
take = A[i] + K%10;
K /= 10;
res.push_back(take%10);
K += take/10;
}
while(K){
res.push_back(K%10);
K /= 10;
}
//尾插再倒转比头插方便，特别是K比A长
reverse(res.begin(), res.end());
return res;
}
};
2021/01/22
1319. 连通网络的操作次数
分类：图论、并查集
一条边如果连接的是同一集合的两个点，那么待使用边++
将已经联通的集合看成点，每减少一个未连通点需要一条待使用边
class UnionFind{
private:
vector<int> u;
vector<int> sz;
public:
int member;
UnionFind(int n):member(n), u(n), sz(n, 1){
iota(u.begin(), u.end(), 0);
}
int root(int i){
return u[i] == i? i : u[i] = root(u[i]);
}
bool connect(int i, int j){
int ri = root(i), rj = root(j);
if(ri == rj){
return false;
}
if(sz[ri] < sz[rj]){
swap(ri, rj);
}
u[rj] = ri;
sz[ri] += sz[rj];
member--;
return true;
}
};
class Solution {
public:
int makeConnected(int n, vector<vector<int>>& connections) {
UnionFind u(n);
int useless=0;
for(vector<int>& conn : connections){
if(!u.connect(conn[0], conn[1])){
useless++;
}
}
// cout << "useless: " << useless << " member: " << u.member;
return u.member-useless<=1 ? u.member-1 : -1;
}
};/* 95% **/
2021/01/23
674. 最长连续递增序列
分类：emmmm贪心？
不要i也行，换成一个计数记递增长度就好
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
if(nums.size() == 0) return 0;
int i=0, j=0, n=nums.size(), maxsize=1;
while(j<n-1){
if(nums[j] < nums[j+1]){
j++;
maxsize = max(maxsize, j-i+1);
}else{
j++;
i=j;
}
}
return maxsize;
}
};
2021/01/24
959. 由斜杠划分区域
分类：图论、并查集
完全没想到…
每一个单元格可能被 、/、\划分。为了使划分结果一致，将一个单元格看做沿对角线拼成的四个等腰直角三角形，顺时针标号0 1 2 3
单元格内：如果是 ，连接0123；如果是/，连接23 12；如果是..
单元格间：每个单元格与自己的右方和下方连接
class UnionFind{
private:
vector<int> u;
vector<int> sz;
public:
int member;
UnionFind(int n):member(n), u(n), sz(n, 1){
iota(u.begin(), u.end(), 0);
}
int root(int i){
return u[i] == i? i : u[i] = root(u[i]);
}
bool connect(int i, int j){
int ri = root(i), rj = root(j);
if(ri == rj){
return false;
}
if(sz[ri] < sz[rj]){
swap(ri, rj);
}
u[rj] = ri;
sz[ri] += sz[rj];
member--;
return true;
}
};
class Solution {
public:
int regionsBySlashes(vector<string>& grid) {
if(grid.size() == 0) return 0;
int n = grid.size();
UnionFind u(4*n*n);
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
//单元格内
if(grid[i][j] == ' '){
u.connect((i*n+j)*4, (i*n+j)*4+1);
u.connect((i*n+j)*4, (i*n+j)*4+3);
u.connect((i*n+j)*4 ,(i*n+j)*4+2);
}else if(grid[i][j] == '/'){
u.connect((i*n+j)*4, (i*n+j)*4+3);
u.connect((i*n+j)*4+1, (i*n+j)*4+2);
}else if(grid[i][j] == '\\'){
u.connect((i*n+j)*4, (i*n+j)*4+1);
u.connect((i*n+j)*4+2, (i*n+j)*4+3);
}
//单元格间：右、下
if(j+1 < n) u.connect((i*n+j)*4+1, (i*n+j+1)*4+3);
if(i+1 < n) u.connect((i*n+j)*4+2, (i*n+j+n)*4);
}
}
return u.member;
}
};/* 89.9% **/
2021/01/25
1128. 等价多米诺骨牌对的数量
分类：哈希
对key进行规范
class Solution {
public:
int numEquivDominoPairs(vector<vector<int>>& dominoes) {
vector<int> cnt(100);
int res=0;
for(vector<int>& v:dominoes){
int val = v[0]<v[1] ? v[0]*10+v[1] : v[1]*10+v[0];
res += cnt[val];
cnt[val]++;
}
return res;
}
};
2021/01/26
1579. 保证图可完全遍历
分类：图论、并查集
type3对两个图都可用，优先考虑；再分别构建两个图就行
意外地不像一个hard
class UnionFind{
private:
vector<int> u;
vector<int> sz;
public:
int member;
UnionFind(int n):member(n), u(n), sz(n, 1){
iota(u.begin(), u.end(), 0);
}
int root(int i){
return u[i] == i ? i : u[i] = root(u[i]);
}
bool connect(int i, int j){
int ri = root(i), rj = root(j);
if(ri == rj){
return false;
}
if(sz[ri] < sz[rj]){
swap(ri, rj);
}
u[rj] = ri;
sz[ri] += sz[rj];
member--;
return true;
}
};
class Solution {
public:
int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
if(edges.size() == 0) return 0;
UnionFind alice(n+1), bob(n+1);
alice.connect(0, 1); bob.connect(0, 1);
int cnt=0;
for(vector<int>& edge : edges){
if(edge[0]!=3) continue;
if(alice.connect(edge[1], edge[2])) bob.connect(edge[1], edge[2]);
else cnt++;
}
for(vector<int>& edge : edges){
if(edge[0]==1 && !alice.connect(edge[1], edge[2])){
cnt++;
}else if(edge[0]==2 && !bob.connect(edge[1], edge[2])){
cnt++;
}
}
return (alice.member==1&&bob.member==1 ? cnt : -1);
}
};/* 84% **/
2021/01/27
724. 寻找数组的中心索引
分类：数组
左右两边相等也就是2倍等于和嘛
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int n = nums.size(), total = 0, left = 0;
for(int i=0; i<n; i++){
total += nums[i];
}
for(int i=0; i<n; i++){
if(left*2 == total-nums[i])
return i;
left+=nums[i];
}
return -1;
}
};
2021/01/28
1631. 最小体力消耗路径
分类：并查集、二分答案、最短路
并查集思路类似于Kruskal，将所有的路径看成边，边的权值就是高度差，边按照高度差排序，挨个连接，最后一个使左上和右下连通的边的权值就是最小高度差
class UnionFind{
private:
vector<int> u;
vector<int> sz;
public:
int member;
UnionFind(int n):member(n), u(n), sz(n, 1){
iota(u.begin(), u.end(), 0);
}
int root(int i){
return u[i] == i ? i : u[i] = root(u[i]);
}
bool connect(int i, int j){
int ri = root(i), rj = root(j);
if(ri == rj){
return false;
}
if(sz[ri] < sz[rj]){
swap(ri, rj);
}
u[rj] = ri;
sz[ri] += sz[rj];
member--;
return true;
}
bool isConnected(int i, int j){
return root(i) == root(j);
}
};
class Solution {
public:
struct edge{
int p1, p2, v;
edge(int p1, int p2, int v):p1(p1),p2(p2),v(v){}
bool operator < (const edge& other){
return v < other.v;
}
};
int minimumEffortPath(vector<vector<int>>& heights) {
int n = heights.size(), m = heights[0].size();
vector<edge> edges;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
int p1 = i*m+j;
if(i+1 < n)
edges.push_back(edge(p1, p1+m, abs(heights[i][j]-heights[i+1][j])));
if(j+1 < m)
edges.push_back(edge(p1, p1+1, abs(heights[i][j]-heights[i][j+1])));
}
}
sort(edges.begin(), edges.end());
UnionFind u(n*m);
for(int i=0; i<edges.size(); i++){
u.connect(edges[i].p1, edges[i].p2);
if(u.isConnected(0, n*m-1))
return edges[i].v;
}
return 0;
}
};
二分答案思路；界定左右两个区间，如果左区间内能够使连通，则将左区间再次划分为两个区间，如果不能，则到右区间搜索。最后一个成功的区间即为答案。搜索可用bfs、dfs
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int n = heights.size(), m = heights[0].size();
int left = 0, right = 1e6, ans=0;
while(left <= right){
int mid = (left+right) >> 1;
queue<pair<int, int>> q;
q.emplace(0, 0);
vector<bool> vis(n*m);
vis[0] = true;
while(!q.empty()){
pair<int, int> cur = q.front(); q.pop();
for(int i=0; i<4; i++){
int x = cur.first + mv[i][0];
int y = cur.second + mv[i][1];
if(x<n&& y<m && x>-1 && y>-1 && !vis[x*m+y] &&
abs(heights[cur.first][cur.second]-heights[x][y])<=mid){
q.emplace(x, y);
vis[x*m+y]=true;
}
}
}
if(vis[n*m-1]){
ans=mid;
right=mid-1;
}else{
left=mid+1;
}
}
return mid;
}
};
最短路思路。比如Dijkstra，改一下对路径长度的定义。虽然我不会
2021/01/29
778. 水位上升的泳池中游泳
分类：并查集、二分答案、最短路
并查集思路挺简单的。由小到大挨个加，检查下连上了没就行。
class UnionFind{
private:
vector<int> u;
vector<int> sz;
public:
int member;
UnionFind(int n):member(n), u(n), sz(n, 1){
iota(u.begin(), u.end(), 0);
}
int root(int i){
return u[i] == i ? i : u[i] = root(u[i]);
}
bool connect(int i, int j){
int ri = root(i), rj = root(j);
if(ri == rj){
return false;
}
if(sz[ri] < sz[rj]){
swap(ri, rj);
}
u[rj] = ri;
sz[ri] += sz[rj];
member--;
return true;
}
bool isConnected(int i, int j){
return root(i) == root(j);
}
};
class Solution {
public:
struct edge{
int i, j, v;
edge(int i, int j, int v):i(i), j(j), v(v){}
bool operator < (const edge & other) const {
return v > other.v;
}
};
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
priority_queue<edge> q;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
q.push(edge(i, j, grid[i][j]));
}
}
UnionFind u(n*n);
while(!q.empty()){
edge cur = q.top(); q.pop();
for(int i=0; i<4; i++){
int x = cur.i + d[i][0], y = cur.j + d[i][1];
if(x>-1 && y>-1 && x<n && y<n && grid[x][y]<cur.v){
u.connect(x*n+y, cur.i*n+cur.j);
}
if(u.isConnected(0, n*n-1)) return cur.v;
}
}
return n*n-1;
}
};
二分答案和最短路思路同昨天的题，摸了
2021/01/30
839. 相似字符串组
分类：并查集
注意提示，所有单词都是字母异位词，另规模较小，暴力比较就行
class UnionFind{
private:
vector<int> u;
vector<int> sz;
public:
int member;
UnionFind(int n):member(n), u(n), sz(n, 1){
iota(u.begin(), u.end(), 0);
}
int root(int i){
return u[i] == i ? i : u[i] = root(u[i]);
}
bool connect(int i, int j){
int ri = root(i), rj = root(j);
if(ri == rj){
return false;
}
if(sz[ri] < sz[rj]){
swap(ri, rj);
}
u[rj] = ri;
sz[ri] += sz[rj];
member--;
return true;
}
bool isConnected(int i, int j){
return root(i) == root(j);
}
};
class Solution {
public:
bool check(string& a, string& b){
for(int i=0, diff=0; i<a.size(); i++){
if(a[i] != b[i] && ++diff > 2) return false;
}
return true;
}
int numSimilarGroups(vector<string>& strs) {
int n = strs.size();
UnionFind u(n);
for(int i=0; i<n-1; i++){
for(int j=i+1; j<n; j++){
if(!u.isConnected(i, j) && check(strs[i], strs[j])){
u.connect(i, j);
}
}
}
return u.member;
}
};
2021/01/31
PREVIOUSLeetcode - 树
NEXTLeetcode - 链表