数组

把数组拼接成最小的数

题目

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 例如输入数组[3, 32, 321]，则打印出这三个数字能排成的最小数字为321323。

const minNumber = (arr) => {
  // 排序规则变化一下
  arr.sort((a, b) => {
    const front = '' + a + b
    const end = '' + b + a
    return front - end
  })
  return arr.join('')
}
console.log(minNumber([3, 32, 321]))
console.log(minNumber([1, 21, 32, 242, 3]))

调整数组顺序使奇数位于偶数前面

题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分

const sort = (arr) => {
  let start = 0
  let end = arr.length - 1
  // 两端遍历，符合条件的时候进行交换位置
  while (start < end) {
    if (arr[start] % 2 === 1) {
      start++
      continue
    }
    if (arr[end] % 2 === 0) {
      end--
      continue
    }
    [arr[start], arr[end]] = [arr[end], arr[start]]
    start++
    end--
  }
  return arr
}

console.log(sort([2, 1, 32, 2, 13, 14, 23, 1]))
// [1,  1, 23, 13, 2, 14, 32,  2]

和为S的连续正整数序列

题目

输入一个正数S，打印出所有和为S的连续正数序列。 例如：输入15，有序1+2+3+4+5 = 4+5+6 = 7+8 = 15 所以打印出3个连续序列1-5，5-6和7-8。

const sequence = (targetSum) => {
  let start = 1
  let end = 1
  let sum = 1
  let result = []
  // 遍历到一半即可
  while (start < targetSum / 2) {
    // 滑动窗口
    if (sum < targetSum) {
      end += 1
      sum += end
      continue
    }
    if (sum > targetSum) {
      sum -= start
      start += 1
      continue
    }

    result.push([start, end])
    sum -= start
    start += 1
    end += 1
    sum += end
  }
  return result
}

console.log(' ==> ', sequence(15));
// [ [ 1, 5 ], [ 4, 6 ], [ 7, 8 ] ]

数组k数之和为S

题目

由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复） 例如： 输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

const calSum = (arr, k, sum, startIndex = 0, endIndex) => {
  const result = []
  if (k === 2) {
    let start = startIndex
    let end = endIndex || arr.length - 1
    while (start < end) {
      const total = arr[start] + arr[end]
      if (total < sum) {
        start += 1
        continue
      }
      if (total > sum) {
        end -= 1
        continue
      }
      result.push([arr[start], arr[end]])
      start += 1
      end -= 1
      // 去重
      if (arr[start] === arr[start - 1]) {
        start += 1
      }
      if (arr[end] === arr[end - 1]) {
        start -= 1
      }
    }
    return result
  }

  for (let i = startIndex;i < arr.length;i++) {
    calSum(arr, k - 1, sum - arr[i], i + 1, endIndex).forEach((target) => {
      target.unshift(arr[i])
      result.push(target)
    })
  }
  return result
}

const removeDuplicate = (arr) => {
  let map = {}
  return arr.filter((item) => {
    const key = item.join(',')
    if (map[key]) {
      return false
    }
    map[key] = true
    return true
  })
}

const fourSum = (nums, target) => {
  nums.sort((a, b) => a - b)
  const result = calSum(nums, 4, target)
  return removeDuplicate(result)
}

// console.log('result ==> ', calSum([1, 3, 5, 7, 8, 9], 2, 10));
// [ [ 1, 9 ], [ 3, 7 ] ]
// console.log('result ==> ', calSum([1, 3, 5, 7, 8, 9], 3, 16));
// [ [ 1, 7, 8 ], [ 3, 5, 8 ] ]
let arr = [1, 0, -1, 0, -2, 2]
// console.log('result ==> ', fourSum(arr, 0));
console.log('result ==> ', fourSum([2, 2, 2, 2, 2], 8));

题目

题目

题目