逻辑思维

[lihuakkk]

训练逻辑思维能力，可以帮助我们编程的时候思考更全面，减少因为疏忽导致的不必要的 bug。

Q: Nth Digit (problemId: 400)

找到无穷整数队列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中的第 n 个数。

Note:
n 是正整数而且 n < Math.pow(2, 31)

Example 1:

Input: 3;
Output: 3;

Example 2:

Input: 11
Output: 0
Explanation: 在队列1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 第11个数字是10中的第二个数0。

解法：

var findNthDigit = function(n) {
  if (n < 10) return n;
  let temp;
  function getN(index) {
    let sum = 0,
      n = 1;
    while (sum < index) {
      temp = sum;
      sum += 9 * Math.pow(10, n - 1) * n;
      n++;
    }
    return n - 1;
  }
  const N = getN(n);
  const _index = Math.ceil((n - temp) / N) - 1;
  const num = Math.pow(10, N - 1) + _index;
  let y = (n - temp) % N;
  if (y === 0) {
    y = N;
  }
  return ("" + num).charAt(y - 1);
};

解释：

先找到第n个数所在的数字，然后在找到对应的位置。

Q: Maximum Subarray (problemId: 53)

给一个整数数组，找出一个连续子串（至少包括一个数字）满足字串和在所有字串中最大，并返回这个字串的和。

Example 1:

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

解法：

var maxSubArray = function(nums) {
  const len = nums.length;
  let lastSum;
  let max = nums[0];
  if (max < 0) {
    lastSum = 0;
  } else {
    lastSum = max;
  }
  for (let i = 1; i < len; i++) {
    const value = nums[i];
    lastSum += value;
    if (lastSum > max) {
      max = lastSum;
    }
    if (lastSum < 0) {
      lastSum = 0;
    }
  }
  return max;
};

解释：

max表示当前最大的字串和，lastSum用作探针查找比当前更大字串和。