美众议院通过 TikTok 法案
之前我们讲了 老美要求字节跳动在 165 天内剥离短视频应用 TikTok，当时的最新进度是 TikTok 给 1.7 亿美国用户发弹窗，发动用户群众给国会打电话进行抗议。
但显然这点力度的抗议并不会造成什么实质影响。
昨晚，美国众议院的议员们正式投票通过了该法案（H.R.7521），之后的流程还需要得到美国参议院的通过，然后才是提交给总统拜登批准。
看似流程还长，但大概率不会出现什么变数，毕竟针对 TikTok 是两党的少数共识。
在正式投票之前，白宫秘书就公开称赞该提案，称拜登政府”希望看到这项法案得以通过，这样它就能被送到总统的办公桌上”。
这事儿如果真的被美国得逞，真的是很坏的示范。
现在比较合理的破局方式，只能是期望当时躲过特朗普狙击的方法能再奏效一次。
希望会有一些线下的抗议活动，动静越大越好，尽量拖延法案通过的日期。
只要法案通过日期延后，再加上法案生效后还有 165 天时间，就有可能避开美国大选，到时如果发生新政交接，或许就能再次获得喘息机会。
…
回归主线。
真心希望 TikTok 不会原地变外企，先不做字节跳动相关题目了。
来看一道 OPPO 二面算法原题。
蓝厂的花边新闻虽然不多，但一直是低调赚大钱的代表之一。
这次二面出的算法题水平也不错。
相比原题，题面稍有修改，但数据范围和解法完全一致。
题目描述
平台：LeetCode
题号：864
给定一个二维网格g，其中：
'.'代表一个空房间'#'代表一堵墙'@'是起点小写字母代表钥匙 大写字母代表锁
我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。
我们不能在网格外面行走，也无法穿过一堵墙。
如果途经一个钥匙，我们就把它捡起来，除非我们手里有对应的钥匙，否则无法通过锁。
假设 k为 钥匙/锁 的个数，且满足 ，字母表中的前 k个字母在网格中都有自己对应的一个小写和一个大写字母。
换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。
返回获取所有钥匙所需要的移动的最少次数。
如果无法获取所有钥匙，返回-1。
示例 1： 
输入：g=["@.a.#","###.#","b.A.B"]
输出：8
解释：目标是获得所有钥匙，而不是打开所有锁。
示例 2： 
输入：g=["@..aA","..B#.","....b"]
输出：6
示例 3: 
输入:g=["@Aa"]
输出:-1
提示：
g[i][j]只含有'.','#','@','a'-'f'以及'A'-'F'钥匙的数目范围是 每个钥匙都对应一个不同的字母 每个钥匙正好打开一个对应的锁
BFS + 状态压缩
一道常规的 BFS 运用题，只不过需要在 BFS 过程中记录收集到的钥匙状态。
利用「钥匙数量不超过 ，并按字母顺序排列」，我们可以使用一个 int 类型二进制数 state 来代指当前收集到钥匙情况：
若 state的二进制中的第 位为1，代表当前种类编号为 的钥匙 「已被收集」，后续移动若遇到对应的锁则 「能通过」若 state的二进制中的第 位为0，代表当前种类编号为 的钥匙 「未被收集」，后续移动若遇到对应的锁则 「无法通过」
其中「钥匙种类编号」则按照小写字母先后顺序，从 开始进行划分对应：即字符为 a 的钥匙编号为 0，字符为 b 的钥匙编号为 1，字符为 c 的钥匙编号为 2 …
当使用了这样的「状态压缩」技巧后，我们可以很方便通过「位运算」进行 「钥匙检测」 和 「更新钥匙收集状态」：
钥匙检测： (state >> k) & 1，若返回1说明第 位为1，当前持有种类编号为k的钥匙更新钥匙收集状态： state |= 1 << k，将state的第 位设置为1，代表当前新收集到种类编号为k的钥匙
搞明白如何记录当前收集到的钥匙状态后，剩下的则是常规 BFS 过程：
起始遍历一次棋盘，找到起点位置，并将其进行入队，队列维护的是 三元组状态（其中 代表当前所在的棋盘位置， 代表当前的钥匙收集情况） 同时统计整个棋盘所包含的钥匙数量
cnt，并使用 数组/哈希表 记录到达每个状态所需要消耗的最小步数step进行四联通方向的
BFS，转移过程中需要注意「遇到锁时，必须有对应钥匙才能通过」&「遇到钥匙时，需要更新对应的state再进行入队」当
BFS过程中遇到state = (1 << cnt) - 1时，代表所有钥匙均被收集完成，可结束搜索
Java 代码：
classSolution{
staticintN=35,K=10,INF=0x3f3f3f3f;
staticint[][][]dist=newint[N][N][1<<K];
staticint[][]dirs=newint[][]{{1,0},{-1,0},{0,1},{0,-1}};
publicintshortestPathAllKeys(String[]g){
intn=g.length,m=g[0].length(),cnt=0;
Deque<int[]>d=newArrayDeque();
for(inti=0;i<n;i++){
for(intj=0;j<m;j++){
Arrays.fill(dist[i][j],INF);
charc=g[i].charAt(j);
if(c=='@'){
d.addLast(newint[]{i,j,0});
dist[i][j][0]=0;
}elseif(c>='a'&&c<='z')cnt++;
}
}
while(!d.isEmpty()){
int[]info=d.pollFirst();
intx=info[0],y=info[1],cur=info[2],step=dist[x][y][cur];
for(int[]di:dirs){
intnx=x+di[0],ny=y+di[1];
if(nx<0||nx>=n||ny<0||ny>=m)continue;
charc=g[nx].charAt(ny);
if(c=='#')continue;
if((c>='A'&&c<='Z')&&(cur>>(c-'A')&1)==0)continue;
intncur=cur;
if(c>='a'&&c<='z')ncur|=1<<(c-'a');
if(ncur==(1<<cnt)-1)returnstep+1;
if(step+1>=dist[nx][ny][ncur])continue;
dist[nx][ny][ncur]=step+1;
d.addLast(newint[]{nx,ny,ncur});
}
}
return-1;
}
}
C++ 代码：
classSolution{
intN=35,K=10,INF=0x3f3f3f3f;
vector<vector<vector<int>>>dist=vector<vector<vector<int>>>(N,vector<vector<int>>(N,vector<int>(1<<K,INF)));
vector<vector<int>>dirs={{1,0},{-1,0},{0,1},{0,-1}};
public:
intshortestPathAllKeys(vector<string>&g){
intn=g.size(),m=g[0].size(),cnt=0;
queue<vector<int>>d;
for(inti=0;i<n;i++){
for(intj=0;j<m;j++){
fill(dist[i][j].begin(),dist[i][j].end(),INF);
charc=g[i][j];
if(c=='@'){
d.push({i,j,0});
dist[i][j][0]=0;
}elseif(c>='a'&&c<='z')cnt++;
}
}
while(!d.empty()){
vector<int>info=d.front();
d.pop();
intx=info[0],y=info[1],cur=info[2],step=dist[x][y][cur];
for(vector<int>di:dirs){
intnx=x+di[0],ny=y+di[1];
if(nx<0||nx>=n||ny<0||ny>=m)continue;
charc=g[nx][ny];
if(c=='#')continue;
if((c>='A'&&c<='Z')&&(cur>>(c-'A')&1)==0)continue;
intncur=cur;
if(c>='a'&&c<='z')ncur|=1<<(c-'a');
if(ncur==(1<<cnt)-1)returnstep+1;
if(step+1>=dist[nx][ny][ncur])continue;
dist[nx][ny][ncur]=step+1;
d.push({nx,ny,ncur});
}
}
return-1;
}
};
Python3 代码：
classSolution:
defshortestPathAllKeys(self,g:List[str])->int:
dirs=[[0,1],[0,-1],[1,0],[-1,0]]
n,m,cnt=len(g),len(g[0]),0
dist=defaultdict(lambda:0x3f3f3f3f)
foriinrange(n):
forjinrange(m):
c=g[i][j]
ifc=='@':
d=deque([(i,j,0)])
dist[(i,j,0)]=0
elif'a'<=c<='z':
cnt+=1
whiled:
x,y,cur=d.popleft()
step=dist[(x,y,cur)]
fordiindirs:
nx,ny=x+di[0],y+di[1]
ifnx<0ornx>=norny<0orny>=m:
continue
c=g[nx][ny]
ifc=='#':
continue
if'A'<=c<='Z'and(cur>>(ord(c)-ord('A'))&1)==0:
continue
ncur=cur
if'a'<=c<='z':
ncur|=(1<<(ord(c)-ord('a')))
ifncur==(1<<cnt)-1:
returnstep+1
ifstep+1>=dist[(nx,ny,ncur)]:
continue
dist[(nx,ny,ncur)]=step+1
d.append((nx,ny,ncur))
return-1
TypeScript 代码：
functionshortestPathAllKeys(g:string[]):number{
constdirs=[[1,0],[-1,0],[0,1],[0,-1]]
letn=g.length,m=g[0].length,cnt=0
constdist=newArray<Array<Array<number>>>()
for(leti=0;i<n;i++){
dist[i]=newArray<Array<number>>(m)
for(letj=0;j<m;j++){
dist[i][j]=newArray<number>(1<<10).fill(0x3f3f3f3f)
}
}
constd=[]
for(leti=0;i<n;i++){
for(letj=0;j<m;j++){
if(g[i][j]=='@'){
d.push([i,j,0]);dist[i][j][0]=0
}elseif(g[i][j]>='a'&&g[i][j]<='z')cnt++
}
}
while(d.length>0){
constinfo=d.shift()
constx=info[0],y=info[1],cur=info[2],step=dist[x][y][cur]
for(constdiofdirs){
constnx=x+di[0],ny=y+di[1]
if(nx<0||nx>=n||ny<0||ny>=m)continue
constc=g[nx][ny]
if(c=='#')continue
if('A'<=c&&c<='Z'&&((cur>>(c.charCodeAt(0)-'A'.charCodeAt(0))&1)==0))continue
letncur=cur
if('a'<=c&&c<='z')ncur|=1<<(c.charCodeAt(0)-'a'.charCodeAt(0))
if(ncur==(1<<cnt)-1)returnstep+1
if(step+1>=dist[nx][ny][ncur])continue
d.push([nx,ny,ncur])
dist[nx][ny][ncur]=step+1
}
}
return-1
}
时间复杂度： 空间复杂度：
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地