Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6a85535

Browse files
committed
update some solutions
1 parent9148989 commit6a85535

File tree

2 files changed

+68
-61
lines changed

2 files changed

+68
-61
lines changed
Lines changed: 30 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,41 @@
1+
// Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
2+
3+
// Do not allocate extra space for another array, you must do this in place with constant memory.
4+
5+
// For example,
6+
// Given input array nums = [1,1,2],
7+
8+
// Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
9+
10+
111
/**
2-
*@param {number[]}A
12+
*@param {number[]}nums
313
*@return {number}
414
*/
5-
varremoveDuplicates=function(A){
6-
if(A===null){
15+
varremoveDuplicates=function(nums){
16+
if(!nums||nums.length===0){
717
return0;
818
}
19+
20+
varend=0;
921

10-
varindex=1;
22+
// index: 012345678
23+
// vals: 111222333
24+
// first swap happen when end = 0; i points at index 3 with val 2
25+
// end++ becomes end points at index 1 and swap with index 3
26+
// after that vals become:
27+
// vals: 121122333
28+
// i at at index 4 and end is at index 2
1129

12-
while(index<A.length){
13-
if(A[index]===A[index-1]){
14-
A.splice(index,1);
15-
}else{
16-
index++;
30+
for(vari=1;i<nums.length;i++){
31+
if(nums[i]!==nums[end]){
32+
end++;
33+
34+
if(i!==end){
35+
nums[end]=nums[i];
36+
}
1737
}
1838
}
1939

20-
returnA.length;
40+
returnend+1;
2141
};

‎286 Walls and Gates.js

Lines changed: 38 additions & 51 deletions
Original file line numberDiff line numberDiff line change
@@ -1,73 +1,60 @@
1-
// https://segmentfault.com/a/1190000003906674
2-
31
// You are given a m x n 2D grid initialized with these three possible values.
42

53
// -1 - A wall or an obstacle.
64
// 0 - A gate.
7-
// INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
8-
//For example, giventhe2D grid:
5+
// INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
6+
//Fill each empty room withthedistance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
97

8+
// For example, given the 2D grid:
109
// INF -1 0 INF
1110
// INF INF INF -1
1211
// INF -1 INF -1
13-
// 0 -1 INF INF
12+
// 0 -1 INF INF
1413
// After running your function, the 2D grid should be:
15-
1614
// 3 -1 0 1
1715
// 2 2 1 -1
1816
// 1 -1 2 -1
1917
// 0 -1 3 4
18+
// Hide Company Tags Google Facebook
19+
// Show Tags
20+
// Show Similar Problems
21+
2022

2123

22-
publicclassSolution{
23-
publicvoidwallsAndGates(int[][]rooms){
24-
if(rooms.length==0)return;
25-
for(inti=0;i<rooms.length;i++){
26-
for(intj=0;j<rooms[0].length;j++){
27-
// 如果遇到一个门，从门开始广度优先搜索，标记连通的节点到自己的距离
28-
if(rooms[i][j]==0)bfs(rooms,i,j);
24+
varwallsAndGates=function(rooms){
25+
vargates=[];
26+
27+
if(!rooms||rooms.length===0){
28+
return;
29+
}
30+
31+
varrows=rooms.length;
32+
varcols=rooms[0].length;
33+
34+
// find all gates
35+
for(vari=0;i<rows;i++){
36+
for(varj=0;j<cols;j++){
37+
if(rooms[i][j]===0){
38+
gates.push([i,j]);
2939
}
3040
}
3141
}
3242

33-
publicvoidbfs(int[][]rooms,inti,intj){
34-
Queue<Integer>queue=newLinkedList<Integer>();
35-
queue.offer(i*rooms[0].length+j);
36-
intdist=0;
37-
// 用一个集合记录已经访问过的点
38-
Set<Integer>visited=newHashSet<Integer>();
39-
visited.add(i*rooms[0].length+j);
40-
while(!queue.isEmpty()){
41-
intsize=queue.size();
42-
// 记录深度的搜索
43-
for(intk=0;k<size;k++){
44-
Integercurr=queue.poll();
45-
introw=curr/rooms[0].length;
46-
intcol=curr%rooms[0].length;
47-
// 选取之前标记的值和当前的距离的较小值
48-
rooms[row][col]=Math.min(rooms[row][col],dist);
49-
intup=(row-1)*rooms[0].length+col;
50-
intdown=(row+1)*rooms[0].length+col;
51-
intleft=row*rooms[0].length+col-1;
52-
intright=row*rooms[0].length+col+1;
53-
if(row>0&&rooms[row-1][col]>0&&!visited.contains(up)){
54-
queue.offer(up);
55-
visited.add(up);
56-
}
57-
if(col>0&&rooms[row][col-1]>0&&!visited.contains(left)){
58-
queue.offer(left);
59-
visited.add(left);
60-
}
61-
if(row<rooms.length-1&&rooms[row+1][col]>0&&!visited.contains(down)){
62-
queue.offer(down);
63-
visited.add(down);
64-
}
65-
if(col<rooms[0].length-1&&rooms[row][col+1]>0&&!visited.contains(right)){
66-
queue.offer(right);
67-
visited.add(right);
68-
}
69-
}
70-
dist++;
43+
// starting from all gates and traverse
44+
for(i=0;i<gates.length;i++){
45+
vargate=gates[i];
46+
traverse(rooms,gate[0],gate[1],rows,cols,0);
47+
}
48+
};
49+
50+
functiontraverse(rooms,i,j,rows,cols,dist){
51+
if(i>=0&&i<rows&&j>=0&&j<cols){
52+
if(rooms[i][j]!==-1&&rooms[i][j]>=dist){
53+
rooms[i][j]=dist;
54+
traverse(rooms,i+1,j,rows,cols,dist+1);
55+
traverse(rooms,i,j+1,rows,cols,dist+1);
56+
traverse(rooms,i-1,j,rows,cols,dist+1);
57+
traverse(rooms,i,j-1,rows,cols,dist+1);
7158
}
7259
}
7360
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp