Skip to content

Commit a5167b9

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request algorithm001#582 from hotboy/master
第三周作业代码
2 parents 50ce030 + accee50 commit a5167b9

3 files changed

Lines changed: 222 additions & 0 deletions

File tree

‎Week_03/id_34/LeetCode_200_34.cs‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
public class Solution {
2+
public int NumIslands(char[][] grid)
3+
{
4+
int islandCount = 0;
5+
for (int y = 0; y < grid.Length; y++)
6+
{
7+
for (int x = 0; x < grid[y].Length; x++)
8+
{
9+
if (grid[y][x] == '1')
10+
{
11+
TraceIsland(grid, y, x);
12+
islandCount++;
13+
}
14+
}
15+
}
16+
17+
return islandCount;
18+
}
19+
20+
21+
public void TraceIsland(char[][] grid, int y, int x)
22+
{
23+
if (y < 0 || x < 0 || y >= grid.Length || x >= grid[y].Length)
24+
{
25+
return;
26+
}
27+
if (grid[y][x] == '1')
28+
{
29+
grid[y][x] = '2';
30+
TraceIsland(grid, y + 1, x);
31+
TraceIsland(grid, y - 1, x);
32+
TraceIsland(grid, y, x + 1);
33+
TraceIsland(grid, y, x - 1);
34+
}
35+
else
36+
{
37+
return;
38+
}
39+
}
40+
}

‎Week_03/id_34/LeetCode_295_34.cs‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
public class MedianFinder
2+
{
3+
List<int> numberList;
4+
/** initialize your data structure here. */
5+
public MedianFinder()
6+
{
7+
numberList = new List<int>();
8+
}
9+
10+
public void AddNum(int num)
11+
{
12+
int index = 0;
13+
if (numberList.Count == 0)
14+
{
15+
numberList.Add(num);
16+
return;
17+
}
18+
if (num >= numberList[numberList.Count / 2])
19+
{
20+
index = numberList.Count / 2;
21+
}
22+
while (index < numberList.Count)
23+
{
24+
if (numberList[index] >= num)
25+
{
26+
numberList.Insert(index, num);
27+
return;
28+
}
29+
index++;
30+
}
31+
numberList.Add(num);
32+
}
33+
34+
35+
public double FindMedian()
36+
{
37+
if(numberList.Count==0)
38+
{
39+
return 0;
40+
}else
41+
{
42+
if(numberList.Count%2==1)
43+
{
44+
return numberList[numberList.Count / 2];
45+
}else
46+
{
47+
return (numberList[numberList.Count / 2 - 1]+ numberList[numberList.Count / 2])/(double)2;
48+
}
49+
}
50+
}
51+
}
52+
/**
53+
* Your MedianFinder object will be instantiated and called as such:
54+
* MedianFinder obj = new MedianFinder();
55+
* obj.AddNum(num);
56+
* double param_2 = obj.FindMedian();
57+
*/

‎Week_03/id_34/LeetCode_827_34.cs‎

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
public class Solution {
2+
public class IslandSqurePoint
3+
{
4+
public int x;
5+
public int y;
6+
public IslandSqurePoint(int y,int x)
7+
{
8+
this.y = y;
9+
this.x = x;
10+
}
11+
}
12+
13+
public class IslandInfo
14+
{
15+
public int IslandSize;
16+
public List<IslandSqurePoint> GroundList = new List<IslandSqurePoint>();
17+
public List<IslandSqurePoint> WaterEdgeList = new List<IslandSqurePoint>();
18+
}
19+
20+
List<IslandInfo> islandList = new List<IslandInfo>();
21+
22+
public int LargestIsland(int[][] grid)
23+
{
24+
//解题思路：先找出岛屿的个数，再找出岛屿边缘水域，再找岛屿之间的边缘水域是否有重合，有的话即能链接在一起
25+
//目前性能不好，有时候报超时，有时候能通过，待优化
26+
int maxAra = 0;
27+
int gridSize = grid.Length * grid[0].Length;
28+
for(int y=0;y<grid.Length;y++)
29+
{
30+
for(int x=0;x<grid[y].Length;x++)
31+
{
32+
if(grid[y][x]==1)
33+
{
34+
IslandInfo ii = new IslandInfo();
35+
TraceIsland(grid, y, x, ii);
36+
FindEdgeWater(ii,grid);
37+
if(ii.IslandSize>maxAra)
38+
{
39+
maxAra = ii.IslandSize;
40+
}
41+
islandList.Add(ii);
42+
}
43+
}
44+
}
45+
if (maxAra == gridSize)
46+
{
47+
return gridSize;
48+
49+
}else
50+
{
51+
maxAra += 1;
52+
}
53+
for (int y = 0; y < grid.Length; y++)
54+
{
55+
for (int x = 0; x < grid[y].Length; x++)
56+
{
57+
if (grid[y][x] == 0)
58+
{
59+
int totalArea = 0;
60+
foreach (var item in islandList)
61+
{
62+
if (item.WaterEdgeList.Where(p => p.x == x && p.y == y).ToList().Count >= 1)
63+
{
64+
totalArea += item.IslandSize;
65+
}
66+
}
67+
totalArea += 1;
68+
if (totalArea > maxAra)
69+
{
70+
maxAra = totalArea;
71+
}
72+
}
73+
}
74+
}
75+
return maxAra;
76+
}
77+
78+
public void FindEdgeWater(IslandInfo iland,int[][] grid)
79+
{
80+
foreach(var item in iland.GroundList)
81+
{
82+
if(iland.GroundList.Where(p=>p.x==item.x&&p.y==item.y-1).ToList().Count==0)
83+
{
84+
iland.WaterEdgeList.Add(new IslandSqurePoint(item.y-1, item.x));
85+
}
86+
87+
if (iland.GroundList.Where(p => p.x == item.x && p.y == item.y + 1).ToList().Count == 0)
88+
{
89+
iland.WaterEdgeList.Add(new IslandSqurePoint( item.y + 1, item.x));
90+
}
91+
92+
if (iland.GroundList.Where(p => p.x == item.x-1 && p.y == item.y).ToList().Count == 0)
93+
{
94+
iland.WaterEdgeList.Add(new IslandSqurePoint( item.y, item.x - 1));
95+
}
96+
97+
if (iland.GroundList.Where(p => p.x == item.x+1 && p.y == item.y).ToList().Count == 0)
98+
{
99+
iland.WaterEdgeList.Add(new IslandSqurePoint( item.y, item.x + 1));
100+
}
101+
}
102+
}
103+
104+
public void TraceIsland(int[][] grid, int y,int x,IslandInfo ilandInfo)
105+
{
106+
if(y<0||x<0||y>=grid.Length||x>=grid[y].Length)
107+
{
108+
return;
109+
}
110+
if(grid[y][x]==1)
111+
{
112+
grid[y][x] = 2;
113+
ilandInfo.IslandSize++;
114+
ilandInfo.GroundList.Add(new IslandSqurePoint(y, x));
115+
TraceIsland(grid, y + 1, x, ilandInfo);
116+
TraceIsland(grid, y - 1, x, ilandInfo);
117+
TraceIsland(grid, y, x + 1, ilandInfo);
118+
TraceIsland(grid, y, x - 1, ilandInfo);
119+
}
120+
else
121+
{
122+
return;
123+
}
124+
}
125+
}

0 commit comments

Comments
 (0)