800. Similar RGB Color##
class Solution {
int getn(int k){
return (k+8)/17;
}
string strd(int k){
char ret[3];
if(k<=9){
ret[1]=char(k+'0');
ret[0]=char(k+'0');
}
else{
ret[0]=char(k-10+'a');
ret[1]=char(k-10+'a');
}
ret[2]='\0';
return string(ret);
}
public:
string similarRGB(string color) {
string a=string("#");
for(int i=1;i<=5;i+=2){
int y=getn(strtoul(color.substr(i,2).c_str(),0,16));
// printf("%d\n",y);
a+=strd(y);
}
return a;
}
};
以上是我的解法，网上搜了一下rbg string 转int的方式
归一的时候使用了四舍五入的技巧
801. Minimum Swaps To Make Sequences Increasing##
动态规划
在每一个位置分别记录两个状态 ，在这个 位置换 和在这个位置不换得到的最小操作数（当然前提是可以）
考虑倒 上一个位置就有两种可能， 那么一共有四种递推可能，地推方程略
class Solution {
public:
int minSwap(vector<int>& A, vector<int>& B) {
const int maxn=200000;
int len=A.size();
int t=1,n=0;
for(int i=1;i<len;i++){
int pt=t,pn=n;
int tt=0,nn=0,tn=0,nt=0;
if(A[i]>A[i-1]&&B[i]>B[i-1]){
tt=1;
nn=1;
}
if(A[i]>B[i-1]&&B[i]>A[i-1]){
tn=1;
nt=1;
}
n=min(tn?(pt):maxn,nn?(pn):maxn);
t=min((tt)?(pt+1):(maxn),(nt)?(pn+1):(maxn));
}
return min(t,n);
}
};
下面是一个简介的py 版本大意相同
def minSwap(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
n = len(A)
pre = [0, 1]
for i in range(1, n):
cur = [sys.maxsize, sys.maxsize]
if A[i]>A[i-1] and B[i]>B[i-1]:
cur[0] = min(cur[0], pre[0])
cur[1] = min(cur[1], pre[1]+1)
if A[i]>B[i-1] and B[i]>A[i-1]:
cur[0] = min(cur[0], pre[1])
cur[1] = min(cur[1], pre[0]+1)
pre = cur
return min(pre)
802. Find Eventual Safe States##
tarjan 算法的变形。
总而言之，我们定义一个bad 的连通分量： 如果他的 规模大于1 或者有子环或者通向其他bad的连通分量则为bad 联通分量 ,问非bad的联通分量有多少个
在经典的tarjan 算法中，判断一个下一个节点是否是自己（标机bad)
遍历到 没有vis 但是dfn 确有的节点时要注意（ 因为一次深搜有可能无法解决所有的节点） 我们需要选择多个入口，就出现了这种问题
然后发现一个强连通分量的时候判断规模 是否大于1个 如果大于 那么这个强连通分量就标记为bad
下面是代码
class Solution {
int cnt,top;
int dfn[10002];
int low[10002];
int stack[10002];
int bad[10002];
int vis[10002];
int dfs(int k,vector<vector<int> >&graph2){
if(vis[k])return low[k];
dfn[k]=++cnt; //时间戳
low[k]=dfn[k]; //扩展戳
stack[top++]=k; //栈中节点
vis[k]=1; //栈中标记
int len=graph2[k].size();
for(int i=0;i<len;i++){
if(graph2[k][i]==k)bad[k]=1;//子环标志
if(!vis[graph2[k][i]]&&dfn[graph2[k][i]]){ //如果没有vis栈上没有，又已经被访问过了，只有一种可能 多次沿不同路径的访问
if(bad[graph2[k][i]])bad[k]=1;
continue;
}
low[k]=min(low[k],dfs(graph2[k][i],graph2));
if(bad[graph2[k][i]])bad[k]=1;//通向bad;
}
if(low[k]==dfn[k]){ //发现一个强连通分量 目标是找到所有的 只能通往非bad且自身也非bad的强连通分量
// bad 1 存在子环或者规模大于1或者可以通向bad
if(stack[top-1]!=k){
while(stack[top-1]!=k){
vis[stack[--top]]=0;
bad[stack[top]]=1;
}
vis[stack[--top]]=0;
bad[stack[top]]=1;
}else{
while(stack[top-1]!=k){
vis[stack[--top]]=0;
}
vis[stack[--top]]=0;
}
}
return low[k];
}
public:
vector<int> eventualSafeNodes(vector<vector<int> >& graph) {
vector<int> ans;
int len=graph.size();
cnt=0,top=0;
ans.clear();
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(bad,0,sizeof(bad));
memset(vis,0,sizeof(vis));
for(int i=0;i<len;i++){
if(!dfn[i])dfs(i,graph);
}
for(int i=0;i<len;i++){
if(dfn[i]==low[i]&&!bad[i])ans.push_back(i);
}
return ans;
}
};
官方Solution
先找到没有出度的点 标记为safe
然后一次处理这些safe 的点 从反向图中找到这些safe 点的上家，如果上家
class Solution(object):
def eventualSafeNodes(self, graph):
N = len(graph)
safe = [False] * N
graph = map(set, graph) #从list 模式转换到set 模式
rgraph = [set() for _ in xrange(N)] 为反向图创建 list of set
q = collections.deque() 处理队列
for i, js in enumerate(graph):
if not js:
q.append(i) #没有出度的节点先进入队列 等待处理
for j in js:
rgraph[j].add(i) #创建反向图
while q:
j = q.popleft() # 取出一个安全的节点
safe[j] = True # 标记为safe
for i in rgraph[j]: #找到他所有的上家
graph[i].remove(j) #在正常图中移除 上家连接他的关系
if len(graph[i]) == 0: #如果上家移除了之后没有其余下家了 就认为上家同样安全
q.append(i)
return [i for i, v in enumerate(safe) if v]
这个思路简介明了 直奔主题， 确实是好思路
官方Solution2 暴力深搜
entry 标记为gray
exit 就标记为black 没有访问就是white
实际上这个流程非常实用,我们进行少许的修改
我们认为如果一个节点的出节点 连接了任意那怕一个gray我们就认为他是gray，反之则标记为gray
class Solution(object):
def eventualSafeNodes(self, graph):
WHITE, GRAY, BLACK = 0, 1, 2
color = collections.defaultdict(int)
def dfs(node):
if color[node] != white:
return color[node] == BLACK
color[node] = GRAY
for nei in graph[node]:
if color[nei] == BLACK:
continue
if color[nei] == GRAY or not dfs(nei):
return False
color[node] = BLACK
return True
return filter(dfs, range(len(graph)))
803. Bricks Falling When Hit##
受过启发的naive 思路先把所有的cut 点都去掉 然后做一遍深搜 将safe的点标记出来
从尾到头依次加入cut 点，每加入一个cut 就在那个cut周围做一次dfs 但是bug 是明显的
官方Solution
倒叙加入利用并查集的实现
并查集的经典操作
class DSU:
def __init__(self, R, C):
#R * C is the source, and isn't a grid square
self.par = range(R*C + 1)
self.rnk = [0] * (R*C + 1)
self.sz = [1] * (R*C + 1)
def find(self, x): #经典的并查集操作，
# if par[x] !=x
# par[x]=find(par[x])
# return par[x]
if self.par[x] != x:
self.par[x] = self.find(self.par[x])
return self.par[x]
def union(self, x, y):
xr, yr = self.find(x), self.find(y)
if xr == yr: return
if self.rnk[xr] < self.rnk[yr]:
xr, yr = yr, xr
if self.rnk[xr] == self.rnk[yr]:
self.rnk[xr] += 1
## 保证rnk[xr] 稍大一点
self.par[yr] = xr
self.sz[xr] += self.sz[yr]
def size(self, x):
return self.sz[self.find(x)]
def top(self):
# Size of component at ephemeral "source" node at index R*C,
# minus 1 to not count the source itself in the size
return self.size(len(self.sz) - 1) - 1
class Solution(object):
def hitBricks(self, grid, hits):
R, C = len(grid), len(grid[0]) #gird的行和 列
def index(r, c): #索引 index的函数
return r * C + c
def neighbors(r, c): #神奇的操作，生成邻居器
for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc
A = [row[:] for row in grid] 我感觉，就是grid的拷贝？？？
for i, j in hits: #将相应的cut 置零
A[i][j] = 0
dsu = DSU(R, C)
for r, row in enumerate(A):
for c, val in enumerate(row): #枚举 处理后图 的节点
if val: #如果为1
i = index(r, c)
if r == 0:
dsu.union(i, R*C) #如果是第一行，就union 到假想节点RC
if r and A[r-1][c]:
dsu.union(i, index(r-1, c)) #如果他的下侧有值 ，就union 到一起
if c and A[r][c-1]:
dsu.union(i, index(r, c-1)) #如果他的上侧有值 ， 就union 到一起
ans = []
for r, c in reversed(hits): #倒叙 枚举 可算找到了，倒叙枚举用reversed
pre_roof = dsu.top() #查照总共有多少个节点
if grid[r][c] == 0: #如果在原图中就是空 直接就是0好了
ans.append(0)
else:
i = index(r, c)
for nr, nc in neighbors(r, c):
if A[nr][nc]:
dsu.union(i, index(nr, nc)) #枚举所有的邻居，和邻居union
if r == 0:
dsu.union(i, R*C) #如果是roof 节点，还要和假想节点union
A[r][c] = 1
ans.append(max(0, dsu.top() - pre_roof - 1)) #最后输出前后的差异
return ans[::-1]