代码模板

代码模板

def divide_conquer(problem, param1, param2, ...):

  # recursion terminator
  if problem is None:
    print_result
    return

  # prepare data
  data = prepare_data(problem)
  subproblems = split_problem(problem, data)

  # conquer subproblems
  subresult1 = self.divide_conquer(subproblems[0], p1, ...)
  subresult2 = self.divide_conquer(subproblems[1], p1, ...)
  subresult3 = self.divide_conquer(subproblems[2], p1, ...)
  ...

  # process and generate the final result
  result = process_result(subresult1, subresult2, subresult3, ...)

Pow(x, n)

题目地址 (opens new window)

以下解法的时间复杂度都是 O(logn)。

var myPow = function(x, n) {
  if (!n) return 1;

  // n 为负数时，x 的 n 次方等于 1 除以 x 的 -n 次方
  if (n < 0) return 1 / myPow(x, -n);

  // n 为奇数时，n-1 就是偶数，传给下一层，此时就留到下一次递归的时候再通过偶数分治进行计算
  if (n % 2) return x * myPow(x, n - 1);

  // n 为偶数时，使用分治，一分为二进行计算
  return myPow(x * x, n / 2);
};

var myPow = function(x, n) {
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }

  let result = 1;
  while (n) {
    if (n & 1) result *= x;
    x *= x;
    n >>= 1;
  }

  return result;
};

多数元素

题目地址 (opens new window)

方法一：两层循环暴力破解，一层用来遍历，一层用来计数。时间复杂度为：O(n^2)。

var majorityElement = function(nums) {
  let middle = nums.length / 2;
  for (let i = 0; i < nums.length; i++) {
    let times = 1; // 这一行要放在第一层循环内，如果放在循环外会出错
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) {
        times++;
      }
    }
    if (times > middle) {
      return nums[i];
    }
  }
};

方法二：使用 map 来存储每个数出现的次数，这样只需要一次遍历。时间复杂度为：O(n)。

var majorityElement = function(nums) {
  let map = new Map();

  for (let num of nums) {
    if (map.has(num)) {
      map.set(num, map.get(num) + 1);
    } else {
      map.set(num, 1);
    }

    if (map.get(num) > nums.length / 2) return num;
  }
};

方法三：先排序，然后取 n/2 处的数字就是多数元素。时间复杂度为：O(nlogn)。

var majorityElement = function(nums) {
  nums.sort((a, b) => a - b);
  return nums[Math.floor(nums.length / 2)];
};

方法四：分治法。时间复杂度为：O(nlogn)。

var majorityElement = function(nums) {
  const helper = (start, end) => {
    if (start === end) return nums[start];

    // 拆分成更小的区间，一分为二
    let mid = Math.floor((start + end) / 2);

    let left = helper(start, mid);
    let right = helper(mid + 1, end);

    if (left === right) return left;

    let leftCount = getCount(left, start, end); // 统计区间内 left 的个数
    let rightCount = getCount(right, start, end); // 统计区间内 right 的个数

    return leftCount > rightCount ? left : right; // 返回 left 和 right 中个数多的那个
  };

  //统计 start 到 end 之间 num 的数量
  const getCount = (num, start, end) => {
    let count = 0;
    for (let i = start; i <= end; i++) {
      if (nums[i] === num) count++;
    }
    return count;
  };

  return helper(0, nums.length - 1);
};

方法五：摩尔投票法。时间复杂度为：O(n)。

var majorityElement = function(nums) {
  let res = nums[0],
    count = 1;
  for (let i = 1; i < nums.length; i++) {
    if (count === 0) {
      res = nums[i];
      count = 1;
    } else if (nums[i] === res) {
      count++;
    } else {
      count--;
    }
  }
  return res;
};