TOC
笔记本
求两数之和等于某个数
var twoSum = function(nums, target) {
const sortedNums = nums.map((v, i) => ({ v, i }))
sortedNums.sort((a, b) => a.v - b.v)
let left = 0
let right = nums.length - 1
while (left < right) {
let sum = sortedNums[left].v + sortedNums[right].v
if (sum === target) {
return [sortedNums[left].i, sortedNums[right].i]
} else if (sum < target) {
left++
} else {
right--
}
}
}
求三数之和等于某个数 所有匹配项 而且去重
var threeSum = function(nums) {
let res = []
nums.sort((a, b) => a - b)
for (let i = 0; i < nums.length - 1; i++) {
if(nums[i] > 0) break
let j = i + 1
let k = nums.length - 1
if (i === 0 || nums[i] !== nums[i - 1]) {
while (j < k) {
const sum = nums[i] + nums[j] + nums[k]
if (sum === 0) {
let nc = [nums[i], nums[j++], nums[k--]]
res.push(nc)
while (j < k && nums[j] === nums[j - 1]) j++
} else if (sum < 0) {
// < 0
j++
} else {
// > 0
k--
}
}
}
}
return res
}
数组区间里面找重复数字
so1
var findDuplicate = function(nums) {
let n = nums.length
for (let i = 0; i < n; i++) {
while (true) {
if (nums[i] === nums[nums[i] - 1] && i !== nums[i] - 1) {
return nums[i]
} else if (nums[i] !== nums[nums[i] - 1] && i !== nums[i] - 1) {
swap(nums, i, nums[i] - 1)
}else {
break
}
}
}
}
const swap = (arr, i, j) => {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
so2 based floyd
var findDuplicate = function(nums) {
let slow = nums[0]
let fast = nums[0]
// find intersection point
while (true) {
slow = nums[slow]
fast = nums[nums[fast]]
if(slow === fast) break
}
// find circle entrace point
fast = nums[0]
while (slow !== fast) {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
寻找最小的丢失正整数
var firstMissingPositive = function(nums) {
const n = nums.length
for (let i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
swap(nums, i, nums[i] - 1)
}
}
for (let i = 0; i < n; i++) {
if (nums[i] !== i + 1) {
return i + 1
}
}
return n + 1
}
const swap = (arr, i, j) => {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
环检测
var hasCycle = function(head) {
if(!head || !head.next) return false
let slow = head
let fast = head
while(slow.next && fast.next && fast.next.next){
slow = slow.next
fast = fast.next.next
if(slow.val === fast.val) {
return true
}
}
return false
};
链表确定环的位置
var detectCycle = function(head) {
if (!head || !head.next) return null
let slow = head
let fast = head
let hasC = false
while (slow.next && fast.next && fast.next.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
hasC = true
break
}
}
if (!hasC) {
return null
}
fast = head
while (slow !== fast) {
fast = fast.next
slow = slow.next
}
return fast
}
合并两个有序链表
function mergeLists(a, b) {
const dummy = {}
let tail = dummy
while (a || b) {
if (a.val < b.val) {
tail.next = a
a = a.next
} else {
tail.next = b
b = b.next
}
tail = tail.next
}
tail.next = a ? a : b
return dummy.next
}
合并K个有序链表
function mergeLists(a, b) {
const dummy = {}
let tail = dummy
while (a || b) {
if (a.val < b.val) {
tail.next = a
a = a.next
} else {
tail.next = b
b = b.next
}
tail = tail.next
}
tail.next = a ? a : b
return dummy.next
}
var mergeKLists = function(lists) {
if (lists.length === 0) {
return null
}
while (lists.length > 1) {
let a = lists.shift()
let b = lists.shift()
let merged = mergeLists(a,b)
lists.push(merged)
}
return lists[0]
}