134. Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

To give minimum candies basically it means that we need to maintain a minimal candy array to meet the requirement 2. 

My approach has 2 passes:

  1. First scan from the left to right on the ratings, if the current rating is higher than previous rating, but the candy is less or equal than previous rating, I increase the candy of the current rating to previous’s candy plus 1. This makes sure the minimal candies which meet the requirement 2 on the left neighbor.
  2. Then scan from right to left on the ratings, if the current rating is higher than previous rating (from right to left, so it is index + 1), but the candy has less or equal, I increase the candy again to be the right’s candy plus one. This makes sure the minimal candies which meet the requirement 2 on the right neighbor.
  3. Count all the candies to get the result.

The time complexity is O(n).

You can read my code here.

https://gist.github.com/zyzyis/2b6ffee4648ecd534f67

72. Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0

01 - 1

11 - 3

10 - 2

My approach is to create a hash set H and start with number 0. For each iteration I change one bit from my current number and check whether it is not already in set H, if not we adds it in the result and start the iteration again. The time complexity in the end is O(N).

You can read my code here.

UPC-A barcodes can be printed at various densities to accommodate a variety of printing and scanning processes. The significant dimensional parameter is called x-dimension, the ideal width of single module element. A single x-dimension must be used uniformly within a given UPC-A barcode. The width of each bar and space is determined by multiplying the x-dimension by the module width of each bar or space (1, 2, 3, or 4 units).