Problem statement:
Gary is an avid hiker. He tracks his hikes meticulously, paying close attention to small details like topography. During his last hike he took exactly n steps. For every step he took, he noted if it was an uphill, U, or a downhill, D step. Gary's hikes start and end at sea level and each step up or down represents a 1 unit change in altitude. We define the following terms:
For example, if Gary's path is s=[DDUUUUDD] he first enters a valley 2 units deep. Then he climbs out an up onto a mountain 2 units high. Finally, he returns to sea level and ends his hike.
Input Format:
The first line contains an integer n, the number of steps in Gary's hike.
The second line contains a single string s, of n characters that describe his path.
Constraints:
2 <= n<=10^6
Output Format:
Print a single integer that denotes the number of valleys Gary walked through during his hike.
Sample Input:
8
UDDDUDUU
Sample Output:
1
Explanation:
If we represent _ as sea level, a step up as /, and a step down as \, Gary's hike can be drawn as:
_/\ _
\ /
\/\/
He enters and leaves one valley.
Solution:
Gary is an avid hiker. He tracks his hikes meticulously, paying close attention to small details like topography. During his last hike he took exactly n steps. For every step he took, he noted if it was an uphill, U, or a downhill, D step. Gary's hikes start and end at sea level and each step up or down represents a 1 unit change in altitude. We define the following terms:
- A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level.
- A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.
For example, if Gary's path is s=[DDUUUUDD] he first enters a valley 2 units deep. Then he climbs out an up onto a mountain 2 units high. Finally, he returns to sea level and ends his hike.
Input Format:
The first line contains an integer n, the number of steps in Gary's hike.
The second line contains a single string s, of n characters that describe his path.
Constraints:
2 <= n<=10^6
Output Format:
Print a single integer that denotes the number of valleys Gary walked through during his hike.
Sample Input:
8
UDDDUDUU
Sample Output:
1
Explanation:
If we represent _ as sea level, a step up as /, and a step down as \, Gary's hike can be drawn as:
_/\ _
\ /
\/\/
He enters and leaves one valley.
Solution:
- // countingValleys function below.
- static int countingValleys(int n, String s) {
- char c[] = s.toCharArray();
- int lvl = 0; // level
- int v = 0; // valley
- for(int i = 0; i <c.length; i++)
- {
- if(c[i] == 'U')
- {
- lvl = lvl +1;
- }
- if(c[i] == 'D')
- {
- lvl = lvl -1;
- }
- if(lvl == 0 && c[i] == 'U')
- {
- v = v +1;
- }
- }
- return v;
- }
No comments:
Post a Comment