分治策略

[lihuakkk]

分治策略通过将一个复杂的大问题分解成很多类似的小问题，然后由无数小问题的解得到最终的大问题的解。一般的解题步骤是列出状态转移方程和临界条件。

Q: Binary Watch (problemId: 401)

一个二进制手表，上面有 4 个 LED 灯表示小时，下面有 6 个 LED 灯表示分钟。

图中显示的时间是"3:25"

给一个非负整数 n，n 表示当前亮着的灯数，求可以表示的时间有那些。

Example 1:

Input: n = 1;
Return: [
  "1:00",
  "2:00",
  "4:00",
  "8:00",
  "0:01",
  "0:02",
  "0:04",
  "0:08",
  "0:16",
  "0:32"
];

Note：

• 输出顺序无关
• 小时表示不以 0 开头，01:00 -> 1:00
• 个位数分钟需要 0 前缀，10:2 -> 10:02

PS: 针对这个问题，下面的解法不是最合适的，只是当时我使用着下面的方法求解。

解法：

var readBinaryWatch = function(num) {
  if (num === 0) return ["0:00"];
  function zuHe(array, n) {
    if (array.length === n) {
      return [array.reduce((sum, a) => sum + a)];
    }
    if (n === 1) {
      return array.concat();
    }
    let _temp = array.concat();
    const char = _temp.shift();
    return zuHe(_temp, n - 1)
      .map(item => char + item)
      .concat(zuHe(_temp, n));
  }
  const hourMap = {
    0: ["0"]
  };
  const minMap = {
    0: ["00"]
  };
  function initMap(obj, array, max, prefix) {
    let len = array.length;
    while (len > 0) {
      obj[len] = zuHe(array.concat(), len)
        .filter(item => item < max)
        .map(item => (item < 10 ? prefix + item : String(item)));
      len--;
    }
  }
  initMap(hourMap, [1, 2, 4, 8], 12, "");
  initMap(minMap, [1, 2, 4, 8, 16, 32], 60, "0");

  const result = [];
  let _num = 0;
  while (_num <= num) {
    const _hourArray = hourMap[_num];
    if (_hourArray && _hourArray.length > 0) {
      const _minArray = minMap[num - _num];
      if (_minArray && _minArray.length > 0) {
        _hourArray.forEach(_hour => {
          _minArray.forEach(_min => result.push(_hour + ":" + _min));
        });
      }
    }
    _num++;
  }
  return result;
};

解释：

/**
这种解法是将所有的灯的情况列举出来。
核心方法是zuHe这个函数，这个函数对无序排列组合的一个实现。
array表示元素，n表示从array中取几个元素进行组合。
例：array = ['a', 'b', 'c', 'd', 'e'], n = 3;
第一步：移除第一个元素'a'，在剩下的元素里面['b', 'c', 'd', 'e']中取（n-1）个进行组合，将组合结果每个加上'a'
第二部：移除第一个元素'a'，在剩下的元素里面['b', 'c', 'd', 'e']中取n个进行组合
当n=1的时候返回当前的array
当array.length === n，返回array里面每个元素相加的结果。
状态转移函数：
first = array.shift()
array2 = array

zuHe(array, n) = (first + zuHe(array2, n - 1)) + zuHe(array2, n);
if(n = 1) return array;
if(array.length === n) return array[0]+array[1]+...array[n-1]

*/

function zuHe(array, n) {
  if (array.length === n) {
    return [array.reduce((sum, a) => sum + a)];
  }
  if (n === 1) {
    return array.concat();
  }
  let _temp = array.concat();
  const char = _temp.shift();
  return zuHe(_temp, n - 1)
    .map(item => char + item)
    .concat(zuHe(_temp, n));
}

Q: Median of Two Sorted Arrays (problemId: 4)

给两个已经排序的数组nums1和nums2，对应的长度是m和n。
找到这两个数组的中位数。
你可以认为nums1和nums2不可同时为空。

Example 1:

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

解法：

var findMedianSortedArrays = function(nums1, nums2) {
    function findIndex(arr, num, offset) {
      const length = arr.length;
      const first = arr[0];
      const last = arr[length - 1];
      const midIndex = Math.floor(length / 2);
      const mid = arr[midIndex];
      if(num <= first) {
        return offset + 0;
      }
      if(num >= last) {
        return offset + length;
      }
      if(num === mid) {
        return offset + midIndex;
      }
      if(num > mid) {
        return findIndex(arr.splice(midIndex), num, offset + midIndex);
      } else {
        return findIndex(arr.splice(0, midIndex), num, offset);
      }

    }
    function concatSortedArrays(array1, array2) {
      const len1 = array1.length;
      const len2 = array2.length;
      let dist, sour;
      if(len1 < len2) {
        dist = array2;
        sour = array1;
      } else {
        dist = array1;
        sour = array2;
      }
      for(let i = 0; i < sour.length; i++) {
        const num = sour[i];
        const insertIndex = findIndex(dist.concat(), num, 0);
        dist.splice(insertIndex, 0, num);
      }
      return dist;
    }
    const array = concatSortedArrays(nums1, nums2);
    const length = array.length;
    if(length % 2 === 0) {
      return (array[length / 2 - 1] + array[length / 2]) / 2 
    } else {
      return array[Math.floor(length/2)];
    }
};

解释：

/**
上面的解法只是我想这么做，受业务影响更倾向于找到一个通用的解法。
先将两个数组合并，然后找到中位数。
核心是findIndex这个函数，利用的二分法的**查找插入Index。
*/