Google – Binary Clock

Google – Binary Clock
有一个用binary code来表示的clock, 比如10:15可以表示为1010:1111，每个bit是一个小灯泡。
题目是input一个n，输出所有能用n盏灯表示的时间。
比如n = 0的话，只有零点（00:00）一种可能。
[Solution]
backtracking题.
首先得问清楚是12小时制还是24小时制。如果是24小时制，那么小时部分最多可能有5位(10111 = 23)，分钟部分最多可能有6位（1111011 = 59）
所以最多只能有9盏灯亮，也就是n不能大于9. 但是递归的时候可以开一个5 + 6 = 11位的数组，当小时或分钟不合法之后再backtracking就好了。

  public List<String> timesWithNLights(int n) {

    List<String> result = new ArrayList<>();

    if (n < 0 || n > 9) {

      return result;

    }

    if (n == 0) {

      result.add("0:0");

      return result;

    }

 

    int[] clock = new int[11];

    backtracking(clock, n, 0, result);

    return result;

  }

 

  private void backtracking(int[] clock, int n, int pos, List<String> result) {

    if (n == 0) {

      int h = 0;

      int m = 0;

      for (int i = 10; i >= 0; i--) {

        if (i > 4 && clock[i] == 1) {

          m += (1 << (10 - i));

        }

        if (i <= 4 && clock[i] == 1) {

          h += (1 << (4 - i));

        }

      }

      if (h <= 23 && m <= 59) {

        result.add(String.valueOf(h) + ":" + String.valueOf(m));

      }

      return;

    }

 

    int i = pos;

    while (i < clock.length) {

      clock[i] = 1;

      n--;

      backtracking(clock, n, i + 1, result);

      n++;

      clock[i] = 0;

      i++;

    }

  }

Read full article from Google – Binary Clock