Skip to content

Commit 5475fb6

Browse files
codingClairecodingClaire
committed
lccup2022fall
1 parent 5c4454d commit 5475fb6

File tree

3 files changed

+267
-0
lines changed

3 files changed

+267
-0
lines changed

‎WeeklyCompetition/20220924/1.cpp‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
class Solution
2+
{
3+
public:
4+
int temperatureTrend(vector<int> &temperatureA, vector<int> &temperatureB)
5+
{
6+
int res=0;
7+
int left =0, right = 0;
8+
int n= temperatureA.size();
9+
int tmp = 0;
10+
for(int i=0;i<n-1;i++)
11+
{
12+
right =i+1;
13+
if(temperatureA[i]== temperatureA[i+1] && temperatureB[i]== temperatureB[i+1])
14+
{
15+
res = max(res, right-left);
16+
}
17+
else if(temperatureA[i]>temperatureA[i+1] && temperatureB[i]>temperatureB[i+1])
18+
{
19+
res = max(res, right-left);
20+
}
21+
else if(temperatureA[i]<temperatureA[i+1] && temperatureB[i]<temperatureB[i+1])
22+
{
23+
res = max(res, right-left);
24+
}
25+
else
26+
{
27+
left = i+1;
28+
}
29+
}
30+
return res;
31+
}
32+
};

‎WeeklyCompetition/20220924/2.cpp‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
class Solution
2+
{
3+
public:
4+
int transportationHub(vector<vector<int>> &path)
5+
{
6+
unordered_map<int,bool> mp;
7+
unordered_map<int,int> in_edges;
8+
for(int i=0;i<path.size();i++)
9+
{
10+
in_edges[path[i][1]]++;
11+
mp[path[i][0]] = false;
12+
if(!mp.count(path[i][1]) || mp[path[i][1]]!=false)
13+
mp[path[i][1]] = true;
14+
}
15+
int total_num = 0;
16+
for(auto iter=mp.begin();iter!=mp.end();iter++)
17+
{
18+
total_num++;
19+
}
20+
21+
for(auto iter=mp.begin();iter!=mp.end();iter++)
22+
{
23+
if(iter->second == true && in_edges[iter->first] == total_num-1)
24+
return iter->first;
25+
}
26+
return -1;
27+
}
28+
};

‎WeeklyCompetition/20220924/3.cpp‎

Lines changed: 207 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,207 @@
1+
2+
3+
/*
4+
5
5+
[".....","..E..",".WO..","....."]
6+
3
7+
[".....","....O","....O","....."]
8+
4
9+
["..E.",".EOW","..W."]
10+
1
11+
[".....","..O..","....."]
12+
41
13+
["E...W..WW",".E...O...","...WO...W","..OWW.O..",".W.WO.W.E","O..O.W...",".OO...W..","..EW.WEE."]
14+
69
15+
["W.W.WE..",".WWWEW..","EWW.WE.E","E.W.E.E.",".OEOO.EO","WE.WOE.W","WW...E..",".WEWO..O","E....E..",".OWE...."]
16+
55
17+
["..E..OEEO.","..O..EEEOE",".EE.WE..OW","..EEWE.W..","...EE.WEE.","W.E...WEE.","WW.WEEE.WW",".WW...WOOO"]
18+
输出：
19+
[]
20+
预期：
21+
[[0,2],[2,2]]
22+
[[0,2],[0,3],[0,5],[0,6],[1,0],[1,8],[3,0],[3,8],[4,0],[6,0],[7,1],[7,4]]
23+
55
24+
[[0,4],[1,0],[3,9],[4,9],[7,5]]
25+
*/
26+
27+
class Solution
28+
{
29+
public:
30+
static constexpr int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // up right down left
31+
string d[4] = {"up", "right", "down", "left"};
32+
33+
bool isLegal(int i, int j, vector<string> &plate, int curdir)
34+
{
35+
curdir = curdir >= 2 ? curdir - 2 : curdir + 2; // change opposite direction
36+
if (plate[i][j] != '.')
37+
return false;
38+
if (j == 0 && i > 0 && i < plate.size() - 1 && curdir == 1)
39+
return true;
40+
if (j == plate[0].size() - 1 && i>0 && i < plate.size() - 1 && curdir == 3)
41+
return true;
42+
if (i == 0 && j > 0 && j < plate[0].size() - 1 && curdir == 2)
43+
return true;
44+
if (i == plate.size() - 1 && j > 0 && j < plate[0].size() - 1 && curdir == 0)
45+
return true;
46+
return false;
47+
}
48+
49+
void backtrack(int num, vector<string> &plate, vector<vector<int>> &res, int i, int j, int curdir)
50+
{
51+
// cout << "cur num: " << num << " " << i << " " << j << " curdir:" << curdir << " " << d[curdir] << endl;
52+
53+
if (num < 0 || j < 0 || j > plate[0].size() - 1 || i < 0 || i > plate.size() - 1)
54+
return;
55+
if (isLegal(i, j, plate, curdir))
56+
{
57+
// cout<<i<<" "<<j<<endl;
58+
vector<int> tmp = {i, j};
59+
res.emplace_back(tmp);
60+
}
61+
if (plate[i][j] == 'O')
62+
{
63+
if (curdir == -1)
64+
{
65+
for (int k = 0; k < 4; k++)
66+
{
67+
int new_i = i + dirs[k][0];
68+
int new_j = j + dirs[k][1];
69+
backtrack(num - 1, plate, res, new_i, new_j, k);
70+
}
71+
}
72+
else
73+
{
74+
return;
75+
}
76+
}
77+
else if (plate[i][j] == 'E')
78+
{
79+
if (curdir == 0)
80+
curdir = 4;
81+
// cout<<i<<" "<<j<<" E "<<i + dirs[curdir - 1][0]<<" "<< j + dirs[curdir - 1][0]<<endl;
82+
backtrack(num - 1, plate, res, i + dirs[curdir - 1][0], j + dirs[curdir - 1][1], curdir - 1);
83+
}
84+
else if (plate[i][j] == 'W')
85+
{
86+
if (curdir == 3)
87+
curdir = -1;
88+
backtrack(num - 1, plate, res, i + dirs[curdir + 1][0], j + dirs[curdir + 1][1], curdir + 1);
89+
}
90+
else if (plate[i][j] == '.')
91+
{
92+
// cout<<i<<" "<<j<<" . "<<i + dirs[curdir][0]<<" "<< j + dirs[curdir][1]<<endl;
93+
backtrack(num - 1, plate, res, i + dirs[curdir][0], j + dirs[curdir][1], curdir);
94+
}
95+
}
96+
97+
static bool cmp(vector<int> a, vector<int> b)
98+
{
99+
if (a[0] == b[0])
100+
return a[1] < b[1];
101+
return a[0] < b[0];
102+
}
103+
104+
vector<vector<int>> ballGame(int num, vector<string> &plate)
105+
{
106+
vector<vector<int>> res;
107+
for (int i = 0; i < plate.size(); i++)
108+
{
109+
for (int j = 0; j < plate[0].size(); j++)
110+
{
111+
if (plate[i][j] == 'O')
112+
{
113+
backtrack(num, plate, res, i, j, -1);
114+
}
115+
}
116+
}
117+
//cout << res.size() << endl;
118+
sort(res.begin(), res.end(), cmp);
119+
auto it = unique(res.begin(), res.end());
120+
res.erase(it, res.end());
121+
return res;
122+
}
123+
};
124+
125+
126+
//// USE SET
127+
128+
class Solution
129+
{
130+
public:
131+
static constexpr int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // up right down left
132+
set<int> st;
133+
bool isLegal(int i, int j, vector<string> &plate, int curdir)
134+
{
135+
curdir = curdir >= 2 ? curdir - 2 : curdir + 2; // change opposite direction
136+
if (j == 0 && i > 0 && i < plate.size() - 1 && curdir == 1)
137+
return true;
138+
if (j == plate[0].size() - 1 && i>0 &&i < plate.size() - 1 && curdir == 3)
139+
return true;
140+
if (i == 0 && j > 0 && j < plate[0].size() - 1 && curdir == 2)
141+
return true;
142+
if (i == plate.size() - 1 && j > 0 && j < plate[0].size() - 1 && curdir == 0)
143+
return true;
144+
return false;
145+
}
146+
147+
void backtrack(int num, vector<string> &plate, vector<vector<int>> &res, int i, int j, int curdir)
148+
{
149+
if (num < 0 || j < 0 || j > plate[0].size() - 1 || i < 0 || i > plate.size() - 1)
150+
return;
151+
int m = plate[0].size();
152+
if (plate[i][j]=='.'&&!st.count(i*m + j) && isLegal(i, j, plate, curdir))
153+
{
154+
vector<int> tmp = {i, j};
155+
res.emplace_back(tmp);
156+
st.insert(i*m + j);
157+
}
158+
if (plate[i][j] == 'O')
159+
{
160+
if(curdir == -1)
161+
{
162+
for (int k = 0; k < 4; k++)
163+
{
164+
int new_i = i + dirs[k][0];
165+
int new_j = j + dirs[k][1];
166+
backtrack(num - 1, plate, res, new_i, new_j, k);
167+
}
168+
}
169+
else
170+
{
171+
return;
172+
}
173+
}
174+
else if (plate[i][j] == 'E')
175+
{
176+
if (curdir == 0)
177+
curdir = 4;
178+
backtrack(num - 1, plate, res, i + dirs[curdir - 1][0], j + dirs[curdir - 1][1], curdir - 1);
179+
}
180+
else if (plate[i][j] == 'W')
181+
{
182+
if (curdir == 3)
183+
curdir = -1;
184+
backtrack(num - 1, plate, res, i + dirs[curdir + 1][0], j + dirs[curdir + 1][1], curdir + 1);
185+
}
186+
else if (plate[i][j] == '.')
187+
{
188+
backtrack(num - 1, plate, res, i + dirs[curdir][0], j + dirs[curdir][1], curdir);
189+
}
190+
}
191+
192+
vector<vector<int>> ballGame(int num, vector<string> &plate)
193+
{
194+
vector<vector<int>> res;
195+
for (int i = 0; i < plate.size(); i++)
196+
{
197+
for (int j = 0; j < plate[0].size(); j++)
198+
{
199+
if (plate[i][j] == 'O')
200+
{
201+
backtrack(num, plate, res, i, j, -1);
202+
}
203+
}
204+
}
205+
return res;
206+
}
207+
};

0 commit comments

Comments
 (0)