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

Commit4bfa0ef

Browse files
committed
Merge branch 'master' into leetcode-containsduplicate-three
2 parentsdaf9453 +906e740 commit4bfa0ef

File tree

4 files changed

+442
-0
lines changed

4 files changed

+442
-0
lines changed

‎.idea/uiDesigner.xml‎

Lines changed: 124 additions & 0 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

‎src/talabat/route/README.MD‎

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
#Problem
2+
3+
We are tracking down our rouge agent and she
4+
travels from place to place to**avoid being tracked**.
5+
6+
Each of her travels are based on a list of itineraries
7+
in an unusual or incorrect order.
8+
9+
The task is to
10+
determine the complete**route** she will take.
11+
12+
You are given and array of routes containing her
13+
travel itineraries, convert this into a complete,
14+
**in-order list** of the places she will travel.
15+
16+
Specifications: findRoutes(routes) parameters:
17+
routes: array<array<string>> - array of itineraries
18+
19+
return value:**string**:**an order list of distinations**
20+
21+
**the correct path she took**
22+
23+
constraints: all inputs have at least one valid,
24+
complete route examples:
25+
26+
input:[[“USA”, “BRA”],[“JPN”, “CAI”],[“BRA”, “UAE”],[“UAE”, “JPN”]]
27+
Output: “USA, BRA, UAE, JPN, CAI”
28+
29+
input:[["Chicago", "Winnipeg"],["Halifax", "Montreal"],
30+
["Montreal", "Toronto"],["Toronto", "Chicago"],["Winnipeg", "Seattle"]]
31+
Output: “Halifax, Montreal, Toronto, Chicago, Winnipeg, Seattle”
32+
33+
#Solution
34+
35+
##Bruteforce Approach
36+
###Pseudocode
37+
1. Find the starting point
38+
2. Create route
39+
40+
##Refactor
41+
Let's review the input again
42+
[“USA”, “BRA”],[“JPN”, “CAI”],[“BRA”, “UAE”],[“UAE”, “JPN”]
43+
44+
The path is acyclic - there is one start and destination.
45+
46+
[“USA”, “BRA”],
47+
[“JPN”, “CAI”],
48+
[“BRA”, “UAE”],
49+
[“UAE”, “JPN”]
50+
51+
It looks like a key value pair.
52+
First solutions time complexity is O(n^2).
53+
Can storing the values in a hashmap improve
54+
time complexity? Or simplify our solution?
55+
56+
Let's store the input in the hashmap.
57+
58+
[“USA” => “BRA”],
59+
[“JPN” => “CAI”],
60+
[“BRA” => “UAE”],
61+
[“UAE” => “JPN”]
62+
63+
The basic solution remains the same.
64+
1. Find starting point
65+
2. Make route
66+
67+
###Find starting point
68+
The starting point is such a key that
69+
would not appear as a value.
70+
71+
We need to find the key such that it
72+
does not appear as the value of other
73+
pairs.
74+
75+
Hashmap has a functionality to check
76+
value exists.
77+
78+
**boolean containsValue(Object value)**
79+
80+
The probable time complexity of this function
81+
is O(n).
82+
https://stackoverflow.com/questions/55679728/how-does-java-util-hashmap-containsvalue-work-what-is-its-time-complexity
83+
84+
This method returns true if some value
85+
equals to the value exists within the map,
86+
else return false.
87+
88+
So we iterate through all the pairs until
89+
containsValue returns false.
90+
91+
###Make route
92+
We have the starting point as the key
93+
from one of the pairs.
94+
95+
Route is created such a way that value
96+
of a pair (destination) must be the key
97+
of other (source).
98+
99+
The final destination does not have another
100+
source.
101+
102+
So to create a route, first we need to
103+
find the key of another pair which is
104+
the value of the current key.
105+
106+
This is our simple solution to make a
107+
route.
108+

‎src/talabat/route/Solution.java‎

Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
packagetalabat.route;
2+
3+
importjava.util.HashMap;
4+
5+
classSolution {
6+
7+
publicStringtrackRoute(String[][]itineraries) {
8+
Stringroute ="";
9+
intitineraryLen =itineraries.length;
10+
11+
if(itineraryLen ==1 ) {
12+
returnitineraries[0][0] +", " +itineraries[0][1];
13+
}
14+
15+
// 1. Transform to hashmap
16+
// 2. Find starting point
17+
// 3. Make route
18+
19+
20+
// Transform to hashmap
21+
HashMap<String,String>itinerariesMap =newHashMap<>();
22+
23+
for (inti=0;i<itineraryLen;i++) {
24+
itinerariesMap.put(itineraries[i][0],itineraries[i][1]);
25+
}
26+
27+
// Find starting point
28+
booleanfoundStart =false;
29+
Stringstart ="";
30+
for (inti=0;i <itineraryLen &&foundStart ==false;i++ ) {
31+
start =itineraries[i][0];
32+
33+
if ( !itinerariesMap.containsValue(start) )
34+
foundStart =true;
35+
}
36+
37+
// Make route
38+
Stringend =itinerariesMap.get(start);
39+
route +=start +", " +end;
40+
41+
// As we can take start and end at once,
42+
// find the number of iterations to make
43+
intloop =itineraryLen/2 +itineraryLen%2 -1;
44+
45+
for (inti=0;i<loop;i++ ) {
46+
start =itinerariesMap.get(end);
47+
end =itinerariesMap.get(start);
48+
route +=", " +start +", " +end;
49+
50+
}
51+
52+
// Last destination is missed when itineraries
53+
// length is even
54+
if (itineraryLen %2 ==0 )
55+
route +=", " +itinerariesMap.get(end);
56+
57+
returnroute;
58+
}
59+
}
60+
61+
classSolutionLegacy {
62+
63+
publicStringtrackRoute(String[][]itineraries) {
64+
intstartIndex =this.findStartingIndex(itineraries);
65+
returnthis.createPath(startIndex,itineraries);
66+
}
67+
68+
publicintfindStartingIndex(String[][]itineraries) {
69+
intitineraryLen =itineraries.length;
70+
Stringstart ="";
71+
booleanstartFound =false;
72+
inti =0;
73+
74+
for (;i <itineraryLen &&startFound ==false;i++) {
75+
start =itineraries[i][0];
76+
intj =0;
77+
78+
for (;j <itineraryLen;j++) {
79+
80+
if (i !=j &&start ==itineraries[j][1]) {
81+
j =itineraryLen +1;
82+
}
83+
}
84+
85+
if (j ==itineraryLen) {
86+
startFound =true;
87+
}
88+
}
89+
90+
returni-1;
91+
}
92+
93+
publicStringcreatePath(intstartIndex,String[][]itineraries) {
94+
intitineraryLen =itineraries.length;
95+
Stringroute =itineraries[startIndex][0] +", " +itineraries[startIndex][1];
96+
StringnextStart =itineraries[startIndex][1];
97+
HashMap<Integer,Boolean>traversedIndex =newHashMap<Integer,Boolean>();
98+
traversedIndex.put(startIndex,true);
99+
100+
for (intl =0;l <itineraryLen+1;l++) {
101+
102+
if (traversedIndex.containsKey(l) ==false ) {
103+
intm =0;
104+
for (;m <itineraryLen;m++) {
105+
106+
if (traversedIndex.containsKey(m) ==false
107+
&&nextStart ==itineraries[m][0]) {
108+
nextStart =itineraries[m][1];
109+
route +=", " +itineraries[m][1];
110+
traversedIndex.put(m,true);
111+
}
112+
}
113+
}
114+
}
115+
116+
returnroute;
117+
}
118+
119+
}

0 commit comments

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