| | Class name: RemoteControl
Method name: getMinClicks
Parameters: int[], int, int, int[]
Returns: int
Lazy Bob is watching TV from his couch. He has highlighted in his TV guide the
channels he would like to watch every half hour. Every click of his remote
control drains Bob of precious energy - so he would like to minimize the number
of buttons he needs to press to get him through his television marathon. There
are 13 buttons on his remote: 10 buttons for the digits (0-9), a "Next Channel"
button, a "Previous Channel" button, and a "Flashback" button:
-The digit buttons allow you to jump directly to a desired channel. (Ex: go to
channel 63 by typing [\u147]6[\u148], [\u147]3[\u148].)
-The "Next Channel" button increments the current channel to the next higher
viewable channel, unless the current channel is the highest viewable channel,
in which case it goes to the lowest viewable channel. The "Previous Channel"
button decrements to the next lower viewable channel, unless the current
channel is the lowest viewable channel, in which case it goes to the highest
viewable channel.
-The "Flashback" button reverts to whatever channel was on the television
before the current channel. (Ex: If channel 1 is viewed, then channel 100,
then Flashback is pressed, the TV will go to channel 1.)
Bob can get from one channel to the next in one of two ways:
1) Clicking any combination of "Next Channel", "Previous Channel", and
"Flashback" buttons.
2) Keying in the digits to the channel.
Bob will never combine "Flashback" and digit buttons when moving from one
channel to the next.
There are certain channels that are blocked on Bob's television. These
channels are not viewable, so they are skipped by the "Next Channel" and
"Previous Channel" buttons.
Implement a class RemoteControl which contains the method getMinClicks. The
method takes as parameters a int[] of channels to view, an int that is the
lowest channel, an int that is the highest channel, and a int[] of blocked
channels. The method returns the minimum number of clicks necessary to get
through all the shows that Bob would like to watch.
The method signature is:
public: int getMinClicks(int[] sequence, int lowestChannel, int highestChannel,
int[] blocked);
*int[] sequence - The sequence of channels that Bob must view (in order). All
channels in this sequence are not in the blocked list and are between
lowestChannel and highestChannel, inclusive. The int[] contains between 1 and
50 elements, inclusive.
*int lowestChannel - The lowest channel on the television. Must be greater
than 0, and less than or equal to 10,000.
*int highestChannel - The highest channel on the television - must be greater
than or equal to lowestChannel, and less than or equal to 10,000.
*int[] blocked - The list of channels that are blocked on Bob's television.
All the channels in this array must be valid channels (greater than or equal to
lowestChannel, less than or equal to highestChannel). Duplicates may be
ignored. The int[]contains at most 50 elements.
Note:
*When keying in digits: The television will not actually change channels until
there's a significant pause between digit clicks - Bob can move fast enough
that he can key in the digits of a channel without pausing long enough for the
television to go to the wrong channel. (If Bob wants to go to channel 35 and
then 42, he can key in "3","5" and then "4","2" and the tv will visit only
those channels and when at channel 42, flashback will go to 35.)
*If multiple successive channels in the sequence are the same: it takes 0
clicks to go from one channel to another if the channels are the same. Also,
flashback contains the value of the last different channel (if there is one).
*The TV assumes no channel when turned on, so the first channel must be keyed
in. Also, when the TV is turned on, and when viewing the first channel, there
is no channel in flashback and pressing flashback does nothing.
*Flashback only remembers one channel, so pressing flashback multiple times in
a row loops between the same two channels. That is, if Bob pressed 17 30
flashback flashback flashback he would visit, in order, channels 17, 30, 17,
30, 17.
Examples:
sequence - 15, 14, 17, 1, 17
lowestChannel - 1
highestChannel - 20
blocked - 18, 19
First, Bob must key in channel 15.. that's two clicks ("1", "5").Then, Bob will
click "Previous Channel" to get to channel 14.
Then, Bob will key in channel 17.. that's two more clicks ("1", "7").
Bob will then key in channel 1.. that's one click ("1").
Finally, Bob will hit flashback to get back to channel 17.
result: 7 clicks
----------------------------------------
sequence - 105, 106, 107, 103
lowestChannel - 103
highestChannel - 108
blocked - 104
First, Bob keys in channel 105.. three clicks ("1", "0", "5").
Then, Bob clicks "Next Channel" to get to channel 106.
Again, Bob clicks "Next Channel" to get to channel 107.
Then, Bob clicks "Next Channel" twice to get to channel 103 (107->108->103).
result: 7
----------------------------------------
sequence [\u150] 1, 100, 1, 101
lowestChannel [\u150] 1
highestChannel [\u150] 200
blocked [\u150] empty
Bob clicks
[\u147]1[\u148]...[\u148]1[\u148],[\u148]0[\u148],[\u148]0[\u148],...[\u148]flas
hback[\u148],[\u148]flashback[\u148],[\u148]Next Channel[\u148].
result: 7
----------------------------------------
sequence - 10, 13, 13, 100, 99, 98, 77, 81
lowestChannel - 1
highestChannel - 100
blocked - 78, 79, 80, 3
result: 12
----------------------------------------
sequence - 1, 3, 5, 10, 2, 10
lowestChannel - 1
highestChannel - 10
blocked - 4, 6
result: 7
-----------------------------------------
sequence [\u150] 600, 1000
lowestChannel [\u150] 1
highesChannel [\u150] 1000
blocked [\u150] empty
result: 7
|