8000 New Solution "Mirror Reflection" · AlphaWang/leetcode@93d6399 · GitHub
[go: up one dir, main page]

Skip to content 8000

Commit 93d6399

Browse files
committed
New Solution "Mirror Reflection"
1 parent e66a31f commit 93d6399

File tree

2 files changed

+82
-1
lines changed

2 files changed

+82
-1
lines changed

README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,8 +8,9 @@ LeetCode
88

99
| # | Title | Solution | Difficulty |
1010
|---| ----- | -------- | ---------- |
11+
|858|[Mirror Reflection](https://leetcode.com/problems/mirror-reflection/description/) | [C++](./algorithms/cpp/mirrorReflection/MirrorReflection.cpp)|Medium|
1112
|837|[Most Common Word](https://leetcode.com/problems/most-common-word/) | [C++](./algorithms/cpp/mostCommonWord/MostCommonWord.cpp)|Easy|
12-
|782|[Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/description) | [C++](./algorithms/cpp/jewelsAndStones/JewelsAndStones.cpp< 10000 /span>)|Easy|
13+
|771|[Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/description) | [C++](./algorithms/cpp/jewelsAndStones/JewelsAndStones.cpp)|Easy|
1314
|643|[Maximum Average Subarray I](https://leetcode.com/problems/maximum-average-subarray-i/description/) | [C++](./algorithms/cpp/maximumAverageSubarray/MaximumAverageSubarray.I.cpp)|Easy|
1415
|477|[Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/) | [C++](./algorithms/cpp/totalHammingDistance/totalHammingDistance.cpp)|Medium|
1516
|418|[SentenceScreenFitting](https://leetcode.com/problems/sentence-screen-fitting/) &hearts; | [C++](./algorithms/cpp/sentenceScreenFitting/sentenceScreenFitting.cpp)|Easy|
Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
// Source : https://leetcode.com/problems/mirror-reflection/description/
2+
// Author : Hao Chen
3+
// Date : 2018-06-27
4+
5+
/***************************************************************************************
6+
*
7+
* There is a special square room with mirrors on each of the four walls. Except for
8+
* the southwest corner, there are receptors on each of the remaining corners, numbered
9+
* 0, 1, and 2.
10+
*
11+
* The square room has walls of length p, and a laser ray from the southwest corner
12+
* first meets the east wall at a distance q from the 0th receptor.
13+
*
14+
* Return the number of the receptor that the ray meets first. (It is guaranteed that
15+
* the ray will meet a receptor eventually.)
16+
*
17+
*
18+
*
19+
*
20+
* Example 1:
21+
*
22+
*
23+
* Input: p = 2, q = 1
24+
* Output: 2
25+
* Explanation: The ray meets receptor 2 the first time it gets reflected back to the
26+
* left wall.
27+
*
28+
*
29+
*
30+
*
31+
* Note:
32+
*
33+
*
34+
* 1 <= p <= 1000
35+
* 0 <= q <= p
36+
*
37+
***************************************************************************************/
38+
39+
/*
40+
* Solution
41+
* --------
42+
*
43+
* We know the following things:
44+
* 1)every reflection will increase the step of `q`.
45+
* 2) when reach the top, the reflection would go down, when reach the bottom the reflection would go up.
46+
*
47+
* So, we can image if there have two walls, left one and right one, then the reflection can go up instanstly,
48+
*
49+
* - the reflection points on left wall would be even times of `q`.
50+
* - the reflection points on right wall would be odd times of `q`.
51+
*
52+
* And in the right wall, the receptors `#0` would be the times of `2p`.
53+
*
54+
* So, we need find the least common multiple of `p` and `q`, then we can have the answer.
55+
*/
56+
57+
58+
class Solution {
59+
private:
60+
//GCD - greatest common divisor 最大公因数
61+
int greatestCommonDivisor (int a, int b) {
62+
if(b) while((a %= b) && (b %= a));
63+
return a + b;
64+
}
65+
//LCM - least common multiple 最小公倍数
66+
int leastCommonMultiple(int a, int b) {
67+
return a * b / greatestCommonDivisor(a, b);
68+
}
69+
public:
70+
int mirrorReflection(int p, int q) {
71+
int lcm = leastCommonMultiple(p, q);
72+
if (lcm % (2*p) == 0 ) return 0;
73+
74+
int nq = lcm / q;
75+
76+
if (nq % 2 == 0 ) return 2;
77+
return 1;
78+
}
79+
};
80+

0 commit comments

Comments
 (0)
0