跳到主要内容

数组✅

本章准确的说不算算法内容，只是针对数组常用操作做一些说明，

说一下 Array 的常用方法?​

答案

延伸阅读

数组合并？​

给定两个有序数组 s1、s2, 将 s1 和 s2 合并成一个有序数组。注意 s1 的长度可以容纳 s2 的所有元素。

const s1 = [1, 3, 5, 6, undefined, undefined, undefined]
const s2 = [3, 10]

function mergeArrays (arr1, arr2) {

}
答案
exports.mergeArrays = function mergeArrays(arr1, arr2) {
  let i = arr1.length - arr2.length - 1;
  let j = arr2.length - 1;
  let k = arr1.length - 1;

  while (j >= 0) {
    if (i >= 0 && arr1[i] > arr2[j]) {
      arr1[k--] = arr1[i--];
    } else {
      arr1[k--] = arr2[j--];
    }
  }
  return arr1;
}

Open browser consoleTests

三数求和？​

给定数组 s1, 返回所有 array[i, j, k] 的和为 0 的解，对应索引组成的集合

const s1 = [-1, -2, 1, 2, 0]

function threeSum (arr) {

}
答案
exports.threeSum = function threeSum(arr) {
  arr.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < arr.length - 2; i++) {
    if (i > 0 && arr[i] === arr[i - 1]) continue;
    let left = i + 1;
    let right = arr.length - 1;
    while (left < right) {
      const sum = arr[i] + arr[left] + arr[right];
      if (sum === 0) {
        result.push([arr[i], arr[left], arr[right]]);
        while (arr[left] === arr[left + 1]) left++;
        while (arr[right] === arr[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
  return result;
}

Open browser consoleTests

两数求和问题？​

给定一个数组 S 和一个整数 target，在数组 S 中找到两个数，使得它们的和等于 target。例如

const s1 = [1, 3, 5, 6]
const target = 9

function twoSum (arr, target) {

}
答案
exports.twoSum = function twoSum(arr, target) {
  const map = new Map();
  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];
    if (map.has(complement)) {
      return [complement, arr[i]];
    }
    map.set(arr[i], i);
  }
  return [];
}

Open browser consoleTests

最大子数组和​

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

function maxSubArray (nums) {

}
答案
function maxSubArray (nums) {
  let maxSum = nums[0]
  let currentSum = nums[0]
  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i])
    maxSum = Math.max(maxSum, currentSum)
  }
  return maxSum
}

module.exports = maxSubArray

Open browser consoleTests

寻找数组中的第 k 大元素​

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

const nums = [3, 2, 1, 5, 6, 4]
const k = 2

function findKthLargest (nums, k) {

}
答案
function findKthLargest (nums, k) {
  nums.sort((a, b) => b - a)
  return nums[k - 1]
}

module.exports = findKthLargest

Open browser consoleTests

Fizz Buzz 问题​

function fizzBuzz (n) {
  const result = []
  for (let i = 1; i <= n; i++) {
    if (i % 3 === 0 && i % 5 === 0) {
      result.push('FizzBuzz')
    } else if (i % 3 === 0) {
      result.push('Fizz')
    } else if (i % 5 === 0) {
      result.push('Buzz')
    } else {
      result.push(i.toString())
    }
  }
  return result
}

寻找首次匹配子序列​

function findSubsequence (arr, subseq) {
  let i = 0
  for (let j = 0; j < arr.length; j++) {
    if (arr[j] === subseq[i]) {
      i++
    }
    if (i === subseq.length) {
      return j - i + 1
    }
  }
  return -1
}

移动零​

function moveZeroes (nums) {
  let index = 0
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      nums[index++] = nums[i]
    }
  }
  for (let i = index; i < nums.length; i++) {
    nums[i] = 0
  }
}
22%