# 算法
# 数组
# 1. 两数之和 (opens new window)
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
# 暴力
两层for循环找
时间On2，空间O1
# 哈希表
边循环时边用个map记录当前值，map中有目标值-当前值的值时，即找到了
时间On，空间On
var twoSum = function(nums, target) {
const map = new Map()
for (let i = 0;i < nums.length; i++) {
const item = nums[i]
const val = target - item
if (map.has(val)) {
return [i, map.get(val)]
} else {
map.set(item, i)
}
}
};
# 15. 三数之和 (opens new window)
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
# 暴力
三层for循环
时间O(n^3)
# 双指针
时间O(n^2)
var threeSum = function (nums) {
let res = []
let length = nums.length;
nums.sort((a, b) => a - b) // 先排个队，最左边是最弱（小）的，最右边是最强(大)的
if (nums[0] <= 0 && nums[length - 1] >= 0) { // 优化1: 整个数组同符号，则无解
for (let i = 0; i < length - 2;) {
if (nums[i] > 0) break; // 优化2: 最左值为正数则一定无解
let first = i + 1
let last = length - 1
do {
if (first >= last || nums[i] * nums[last] > 0) break // 两人选相遇，或者三人同符号，则退出
let result = nums[i] + nums[first] + nums[last]
if (result === 0) { // 如果可以组队
res.push([nums[i], nums[first], nums[last]])
}
if (result <= 0 ) { // 实力太弱，把菜鸟那边右移一位
while (first < last && nums[first] === nums[++first]){} // 如果相等就跳过
} else { // 实力太强，把大神那边左移一位
while (first < last && nums[last] === nums[--last]) {}
}
} while (first < last)
while (nums[i] === nums[++i]) {} // 跳过相同的
}
}
return res
}
# 14. 最长公共前缀 (opens new window)
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if (strs.length === 0) return ''
let first = strs[0] // flower
// 从左往右
// let res = ''
// for(let i = 0; i < first.length; i++) {
// // ["flower","flow","flight"]
// const flag = strs.every(item => {
// return item[i] === first[i]
// })
// if (flag) {
// res += first[i]
// } else {
// break
// }
// }
// return res
// 从右往左
while(first.length) {
const flag = strs.every(item => {
return item.indexOf(first) === 0
})
if (flag) {
break
} else {
first = first.substring(0, first.length - 1)
}
}
return first
};
# 26. 删除有序数组中的重复项 (opens new window)
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
# 后面相同就删除
var removeDuplicates = function(nums) {
let { length } = nums;
for (let i = 1; i < length; i++) {
if (nums[i] === nums[i - 1]) {
nums.splice(i, 1)
i--
length--
}
}
return nums.length
};
# 快慢指针
用个指针记录没重复的索引，没重复时直接顶掉前面的
var removeDuplicates = function(nums) {
if(!nums.length) return 0;
let i = 0;
for(let j = 1; j < nums.length; j++){
if(nums[j] !== nums[i]){
i++;
nums[i] = nums[j];
}
}
return i + 1;
};
# 27. 移除元素 (opens new window)
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
// 相等时将最后的移到第一个
var removeElement = function(nums, val) {
let ans = nums.length;
for (let i = 0; i < ans;) {
if (nums[i] == val) {
nums[i] = nums[ans - 1];
ans--;
} else {
i++;
}
}
return ans;
}
# 66. 加一 (opens new window)
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
let { length } = digits;
var needAdd = false;
while(length > 0) {
if (digits[--length] === 9) {
digits[length] = 0
needAdd = true
} else {
digits[length] = digits[length] + 1;
needAdd = false
break
}
}
if (needAdd) {
digits.unshift(1)
}
return digits
};
# 122. 买卖股票的最佳时机 II (opens new window)
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let profit = 0
for (let i = 1;i < prices.length; i++) {
// 只要后一天大于前一天，就卖出
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1]
}
}
return profit
};
# 350. 两个数组的交集 II (opens new window)
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
// 1.map版
// const map = new Map()
// nums1.forEach(item => {
// if (map.has(item)) {
// map.set(item, map.get(item) + 1)
// } else {
// map.set(item, 1)
// }
// })
// const res = []
// nums2.forEach(item => {
// const itemNum = map.get(item)
// if (itemNum) {
// res.push(item)
// map.set(item, itemNum - 1)
// }
// })
// return res
// 2.双指针
nums1 = nums1.sort((a,b) => a - b)
nums2 = nums2.sort((a,b) => a - b)
let i = 0, j = 0, k = 0
while (i < nums1.length && j < nums2.length) {
const item1 = nums1[i]
const item2 = nums2[j]
if (item1 === item2) {
nums1[k] = item1
i++
j++
k++
} else if (item1 < item2) {
i++
} else if (item1 > item2) {
j++
}
}
return nums1.splice(0, k)
};
# 链表
# 2. 两数相加 (opens new window)
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
搞3个指针，相加，有进位就加上
var addTwoNumbers = function(l1, l2) {
const l3 = new ListNode(0)
let p1 = l1
let p2 = l2
let p3 = l3
let carry = 0
while(p1 || p2) {
const val1 = p1 ? p1.val : 0
const val2 = p2 ? p2.val : 0
const val = val1 + val2 + carry
carry = Math.floor(val / 10)
p3.next = new ListNode(val % 10)
if (p1) p1 = p1.next
if (p2) p2 = p2.next
p3 = p3.next
}
if (carry) {
p3.next = new ListNode(carry)
}
return l3.next
};
# 19. 删除链表的倒数第 N 个结点 (opens new window)
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
双指针，一个先往后走n步，再同时走，先走的那个到底了，后走的那个就是倒数第n个。然后删掉下一个即可。
var removeNthFromEnd = function(head, n) {
var result = new ListNode(null, head)
var pre = result, cur = result
while(n--) {
cur = cur.next;
}
while(cur && cur.next) {
cur = cur.next;
pre = pre.next;
}
pre.next = pre.next.next;
return result.next
};
# 21. 合并两个有序链表 (opens new window)
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
哪边小就用哪边，一边走完后，直接用另一边
var mergeTwoLists = function(l1, l2) {
const res = new ListNode(0)
let p = res
let p1 = l1
let p2 = l2
while(p1 && p2) {
if (p1.val < p2.val) {
p.next = p1
p1= p1.next
} else {
p.next = p2
p2= p2.next
}
p = p.next
}
if (p1) {
p.next = p1
}
if (p2) {
p.next = p2
}
return res.next
};
# 141. 环形链表 (opens new window)
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
# 加标记
var hasCycle = function(head) {
while (head !== null) {
if (head.repeat) {
return true
} else {
head.repeat = true
head = head.next
}
}
return false
};
# 快慢指针
var hasCycle = function(head) {
let fast = head, slow = head
while(slow && fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
return true
}
}
return false
};
# ------------------
# 冒泡排序
const {length} = arr === length = arr.length
普通版
let j=0;j<length-1 不减去i
改进版
function sort (arr) {
const {length} = arr
for (let i=0;i<length-1;i++){
for (let j=0;j<length-1-i;j++) {
if (arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}
let arr=[1,4,65,2,67,3,8,22,6]
console.log(sort(arr))
# 选择排序
找到最小的那个与当前的交换
function selectionSort (arr) {
const {length} = arr
let indexMin
for (let i=0;i<length-1;i++){
indexMin = i
for (let j=i;j<length;j++) {
if (arr[indexMin] > arr[j]) {
indexMin = j
}
}
if (i !== indexMin) {
[arr[indexMin], arr[i]] = [arr[i], arr[indexMin]]
}
}
return arr
}
let arr=[1,4,65,2,67,3,8,22,6]
console.log(selectionSort(arr))
# 插入排序
找到之前比本次小的，插到后面
function sort (arr) {
const {length} = arr
let temp
for (let i=1;i<length;i++){
let j = i
temp = arr[i]
while (j>0 && arr[j-1] > temp) {
arr[j] = arr[j-1]
j--
}
arr[j] = temp
}
return arr
}
let arr=[1,4,65,2,67,3,8,22,6]
console.log(sort(arr))
# 归并排序
Array.prototype.mergeSort = function() {
const rec = (arr) => {
if (arr.length === 1) return arr
const mid = Math.floor(arr.length / 2)
const left = arr.slice(0, mid)
const right = arr.slice(mid, arr.length)
const orderLeft = rec(left)
const orderRight = rec(right)
const res = []
while(orderLeft.length || orderRight.length) {
if (orderLeft.length && orderRight.length) {
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
} else if (orderLeft.length) {
res.push(orderLeft.shift())
} else if (orderRight.length) {
res.push(orderRight.shift())
}
}
return res
}
rec(this)
}
const arr = [7,3,5,1]
arr.mergeSort()
function mergeSort (arr) {
const {length} = arr
if (length === 1) return arr
const mid = Math.floor(length / 2)
const left = arr.slice(0, mid)
const right = arr.slice(mid, length)
const orderLeft = mergeSort(left)
const orderRight = mergeSort(right)
let res = []
while (orderLeft.length > 0 || orderRight.length > 0) {
if (orderLeft.length > 0 && orderRight.length > 0) {
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
} else if (orderRight.length) {
res.push(orderRight.shift())
} else if (orderLeft.length) {
res.push(orderLeft.shift())
}
}
return res
}
# 快排
Array.prototype.quickSort = function() {
const rec = (arr) => {
if (arr.length === 0 || arr.length === 1) return arr
const mid = arr[0]
const left = []
const right = []
for (let i = 1; i< arr.length; i++) {
if (arr[i] <mid) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...rec(left), mid, ...rec(right)]
}
const res = rec(this)
res.forEach((n, i) => this[i] = n)
}
const arr = [7,3,5,1]
arr.quickSort()
function quickSort(arr) {
const {length} = arr
if ([0, 1].includes(length)) return arr
let mid = arr[0]
let left = []
let right = []
for (let i = 1; i < length; i++) {
if (arr[i] < mid) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...quickSort(left), mid, ...quickSort(right)]
}
# 斐波那契
# 方法一：普通递归
function fibonacci(n) {
if ([1, 2].includes(n)) return 1;
return fibonacci(n - 2) + fibonacci(n - 1);
}
f: 1901.197998046875 ms
缺点：存在重复计算，容易爆栈
# 方法二：改进递归，作为函数参数
function fibonacci(n) {
function fib(n, v1, v2) {
if (n === 1) {
return v1
} else if (n === 2) {
return v2
} else {
return fib(n - 1, v2, v1 + v2)
}
}
return fib(n, 1, 1)
}
f: 7.71484375 ms
# 方法三：改进递归，用数组记录
function fibonacci(n) {
let memo = [0, 1]
function fib(n) {
if (memo[n] === undefined) {
memo[n] = fib(n - 1) + fib(n - 2)
}
return memo[n]
}
return fib(n)
}
f: 14.156005859375 ms
# 方法四： for循环
function fibonacci(n) {
let n1 = 1, n2 = 1
for (let i = 2; i < n; i++) {
[n1, n2] = [n2, n1 + n2]
}
return n2
}
f: 5.817138671875 ms
# 运行耗时
let x = 1
console.time('f')
while (x < 10000) {
fibonacci(20)
x++
}
console.timeEnd('f')
普通递归>改进递归>for循环
# 1. 五大算法
- 贪心算法: 局部最优解法
- 分治算法: 分成多个小模块，与原问题性质相同
- 动态规划: 每个状态都是过去历史的一个总结
- 回溯法: 发现原先选择不优时，退回重新选择
- 分支限界法
# 2. 基础排序算法
- 冒泡排序: 两两比较
function bubleSort(arr) {
var len = arr.length;
for (let outer = len ; outer >= 2; outer--) {
for(let inner = 0; inner <=outer - 1; inner++) {
if(arr[inner] > arr[inner + 1]) {
[arr[inner],arr[inner+1]] = [arr[inner+1],arr[inner]]
}
}
}
return arr;
}
复制代码
- 选择排序: 遍历自身以后的元素，最小的元素跟自己调换位置
function selectSort(arr) {
var len = arr.length;
for(let i = 0 ;i < len - 1; i++) {
for(let j = i ; j<len; j++) {
if(arr[j] < arr[i]) {
[arr[i],arr[j]] = [arr[j],arr[i]];
}
}
}
return arr
}
复制代码
- 插入排序: 即将元素插入到已排序好的数组中
function insertSort(arr) {
for(let i = 1; i < arr.length; i++) { //外循环从1开始，默认arr[0]是有序段
for(let j = i; j > 0; j--) { //j = i,将arr[j]依次插入有序段中
if(arr[j] < arr[j-1]) {
[arr[j],arr[j-1]] = [arr[j-1],arr[j]];
} else {
break;
}
}
}
return arr;
}
复制代码
# 3. 高级排序算法
- 快速排序
- 选择基准值(base)，原数组长度减一(基准值)，使用 splice
- 循环原数组，小的放左边(left数组)，大的放右边(right数组);
- concat(left, base, right)
- 递归继续排序 left 与 right
function quickSort(arr) {
if(arr.length <= 1) {
return arr; //递归出口
}
var left = [],
right = [],
current = arr.splice(0,1);
for(let i = 0; i < arr.length; i++) {
if(arr[i] < current) {
left.push(arr[i]) //放在左边
} else {
right.push(arr[i]) //放在右边
}
}
return quickSort(left).concat(current,quickSort(right));
}
复制代码
- 希尔排序：不定步数的插入排序，插入排序
- 口诀: 插冒归基稳定，快选堆希不稳定
稳定性： 同大小情况下是否可能会被交换位置, 虚拟dom的diff，不稳定性会导致重新渲染；
# 4. 递归运用(斐波那契数列)： 爬楼梯问题
初始在第一级，到第一级有1种方法(s(1) = 1)，到第二级也只有一种方法(s(2) = 1)， 第三级(s(3) = s(1) + s(2))
function cStairs(n) {
if(n === 1 || n === 2) {
return 1;
} else {
return cStairs(n-1) + cStairs(n-2)
}
}
复制代码
# 5. 数据树
- 二叉树: 最多只有两个子节点
- 完全二叉树
- 满二叉树
- 深度为 h, 有 n 个节点，且满足 n = 2^h - 1
- 二叉查找树: 是一种特殊的二叉树，能有效地提高查找效率
- 小值在左，大值在右
- 节点 n 的所有左子树值小于 n，所有右子树值大于 n
- 遍历节点
- 前序遍历
- 根节点
- 访问左子节点，回到 1
- 访问右子节点，回到 1
- 中序遍历
- 先访问到最左的子节点
- 访问该节点的父节点
- 访问该父节点的右子节点， 回到 1
- 后序遍历
- 先访问到最左的子节点
- 访问相邻的右节点
- 访问父节点， 回到 1
- 前序遍历
- 插入与删除节点
# 6. 天平找次品
有n个硬币，其中1个为假币，假币重量较轻，你有一把天平，请问，至少需要称多少次能保证一定找到假币?
三等分算法:
- 将硬币分成3组，随便取其中两组天平称量
- 平衡，假币在未上称的一组，取其回到 1 继续循环
- 不平衡，假币在天平上较轻的一组， 取其回到 1 继续循环
# 算法训练营
# 开篇
- 刻意练习
- 想到解法后需要再想更优解
- 做自己的脑图，形成树形知识
# code style
多google
自顶向下的编程方式：
先将主干逻辑步骤写好（方法名），再补充具体代码
用新的window terminal
vscode leetcode plugin
每道题多看国际站前三解法
# 时间空间复杂度
O(log(n))
O(1)
O(n)
O(2^n)
...
# 数组、链表、跳表
数组读取是O(1)，插入O(n)
链表读取是O(n)，插入O(1)
跳表就是优化了链表，加多层索引，将复杂度降到O(log2(n))
空间换时间，升维
# leetcode
# 两数之和 (opens new window)
用map记录，循环找差
var twoSum = function(nums, target) {
const map = new Map()
for (let i = 0;i < nums.length; i++) {
const item = nums[i]
const val = target - item
if (map.has(val)) {
return [i, map.get(val)]
} else {
map.set(item, i)
}
}
};
# 两数相加 (opens new window)
链表头相加
计算进位
然后链表往后走，一直加
var addTwoNumbers = function(l1, l2) {
const l3 = new ListNode(0)
let p1 = l1
let p2 = l2
let p3 = l3
let carry = 0
while (p1 || p2) {
const val1 = p1 ? p1.val : 0
const val2 = p2 ? p2.val : 0
const val = val1 + val2 + carry
carry = Math.floor(val / 10)
p3.next = new ListNode(val % 10)
if (p1) p1 = p1.next
if (p2) p2 = p2.next
p3 = p3.next
}
if (carry) {
p3.next = new ListNode(carry)
}
return l3.next
};
或者直接链表转数字，加完再转成链表
# 无重复字符的最长子串 (opens new window)
左指针，循环里右指针，如果map里有，移动左指针，计算最大值，更新索引
var lengthOfLongestSubstring = function(s) {
let l = 0
let res = 0
const map = new Map()
for (let i = 0; i < s.length; i++) {
if (map.has(s[i]) && map.get(s[i]) >= l) {
l = map.get(s[i]) + 1
}
res = Math.max(res, i - l + 1)
map.set(s[i], i)
}
return res
};
# 盛最多水的容器 (opens new window)
左右指针，找出对应的最小高度，并移动对应指针
var maxArea = function(a) {
let max = 0
let l = 0
let r = a.length - 1
while(l < r) {
const minHeight = a[l] <= a[r] ? a[l++] : a[r--]
let area = minHeight * (r - l + 1)
max = Math.max(area, max)
}
return max
};
# 三数之和 (opens new window)
数组升序排序
如果整个数组都是同符号则肯定没结果
从第一个开始循环
如果第一个大于0也没戏
搞两个指针，当前+1 和 最后
当左小于右时
当当前和右同符号也没戏
三个相加
等于0就记录
小于0说明左边大，左边一直加，相等则再加
右边同理
找完移动当前，相同的再加1
var threeSum = function (nums) {
let res = []
let length = nums.length;
nums.sort((a, b) => a - b) // 先排个队，最左边是最弱（小）的，最右边是最强(大)的
if (nums[0] <= 0 && nums[length - 1] >= 0) { // 优化1: 整个数组同符号，则无解
for (let i = 0; i < length - 2;) {
if (nums[i] > 0) break; // 优化2: 最左值为正数则一定无解
let first = i + 1
let last = length - 1
do {
if (first >= last || nums[i] * nums[last] > 0) break // 两人选相遇，或者三人同符号，则退出
let result = nums[i] + nums[first] + nums[last]
if (result === 0) { // 如果可以组队
res.push([nums[i], nums[first], nums[last]])
}
if (result <= 0 ) { // 实力太弱，把菜鸟那边右移一位
while (first < last && nums[first] === nums[++first]){} // 如果相等就跳过
} else { // 实力太强，把大神那边左移一位
while (first < last && nums[last] === nums[--last]) {}
}
} while (first < last)
while (nums[i] === nums[++i]) {} // 跳过相同的
}
}
return res
}
不然就暴力三重循环
# 有效的括号 (opens new window)
用栈解决
是左边的推入
不是就看栈顶是不是等于对应的左边
var isValid = function(s) {
if (s.length % 2 === 1) return false
const map = {
'(': ')',
'{': '}',
'[': ']'
}
let stack = []
for (let i =0;i<s.length;i++) {
if (map.hasOwnProperty(s[i])) {
stack.push(map[s[i]])
} else if (stack[stack.length - 1] === s[i]) {
stack.pop()
} else {
return false
}
}
return stack.length === 0
};
# 合并两个有序链表 (opens new window)
同时存在时判断小的，走小的
不然谁存在走谁
var mergeTwoLists = function(l1, l2) {
const res = new ListNode(0)
let p = res
let p1 = l1
let p2 = l2
while(p1 && p2) {
if (p1.val < p2.val) {
p.next = p1
p1= p1.next
} else {
p.next = p2
p2= p2.next
}
p = p.next
}
if (p1) {
p.next = p1
}
if (p2) {
p.next = p2
}
return res.next
};
# 合并K个升序链表 (opens new window)
用最小堆来解决
class MinHeap {
constructor () {
this.heap = []
}
swap (i1, i2) {
[this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]
}
getLeftIndex (i) {
return i * 2 + 1
}
getRightIndex (i) {
return i * 2 + 2
}
getParentIndex(i) {
return (i - 1) >> 1
}
shiftUp (index) {
if (index === 0) return
const parentIndex = this.getParentIndex(index)
if (this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val) {
this.swap(parentIndex, index)
this.shiftUp(parentIndex)
}
}
shiftDown (index) {
const leftIndex = this.getLeftIndex(index)
const rightIndex = this.getRightIndex(index)
if (this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val) {
this.swap(leftIndex, index)
this.shiftDown(leftIndex)
}
if (this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val) {
this.swap(rightIndex, index)
this.shiftDown(rightIndex)
}
}
insert(value) {
this.heap.push(value)
this.shiftUp(this.heap.length - 1)
}
pop() {
if (this.size() === 1) return this.heap.shift()
const top = this.heap[0]
this.heap[0] = this.heap.pop()
this.shiftDown(0)
return top
}
peek() {
return this.heap[0]
}
size() {
return this.heap.length
}
}
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
const res = new ListNode(0)
let p = res
const h = new MinHeap()
lists.forEach(n => {
n && h.insert(n)
})
while(h.size()) {
const n = h.pop()
p.next = n;
p = p.next;
if (n.next) h.insert(n.next)
}
return res.next
};
# 全排列 (opens new window)
递归实现
每个数字都循环，不存在就推入，长度等于给定就停止
var permute = function(nums) {
const res = []
const backTrack = (path) => {
if (path.length === nums.length) {
res.push(path)
return
}
nums.forEach(item => {
if (path.includes(item)) return
backTrack(path.concat(item))
})
}
backTrack([])
return res
};
# 有效数字 (opens new window)
用图来做，把可能的走向列出来，循环去走，走的通就是有效的
/**
* @param {string} s
* @return {boolean}
*/
var isNumber = function(s) {
const graph = {
0: {'blank': 0, 'sign': 1, '.': 2, 'digit': 6},
1: {'digit': 6, '.': 2},
2: {'digit': 3},
3: {'digit': 3, 'e': 4},
4: {'digit': 5, 'sign': 7},
5: {'digit': 5},
6: {'digit': 6, '.': 3, 'e': 4},
7: {'digit': 5}
}
let state = 0
for (c of s.trim()) {
if (c >= '0' && c <= '9') {
c = 'digit'
} else if (c === ' ') {
c = 'blank'
} else if (c === '+' || c === '-') {
c = 'sign'
}
state = graph[state][c]
if (state === undefined) {
return false
}
}
if (state === 3 || state === 5 || state === 6) {
return true
}
return false
};
# 爬楼梯 (opens new window)
用数学公式
var climbStairs = function(n) {
const sqrt_5 = Math.sqrt(5);
const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
return Math.round(fib_n / sqrt_5);
};
用斐波那契
用个数组缓存
var climbStairs = function(n) {
const dp = [1， 1];
for(let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
或者
function fibonacci(n) {
let n1 = 1, n2 = 1
for (let i = 2; i < n; i++) {
[n1, n2] = [n2, n1 + n2]
}
return n2
}
# 反转字符串 (opens new window)
var reverseString = function(s) {
let start = 0, end = s.length - 1
while (start < end) {
[s[start], s[end]] = [s[end], s[start]]
start++;
end--;
}
};
// 递归版
var reverseString = function(s) {
const reverse = (left, right) => {
if (left >= right) return
[s[left], s[right]] = [s[right], s[left]];
reverse(++left, --right)
}
reverse(0, s.length - 1)
};
# other
# 倒水问题
9l 4l 6l
得出x%9=6
找出x能整除4即可知道4往9倒多少次能得到6
# 非负整数组，拼出最大值
冒泡排序，比较当前值拼上前一个值的数是否大于前一个值的数拼上当前值
function findMaxNum (str) {
for (let i = 0; i < str.length; i++) {
for (let j = str.length - 1; j > i; j--) {
if (str[j] + '' + str[j-1] > str[j-1] + '' + str[j]) {
[str[j], str[j - 1]] = [str[j-1], str[j]]
}
}
}
return str.join('')
}
console.log(findMaxNum([10,50,54,45,9,7,8,5,5,4,44,46,456]))
# 去掉字符串中的空格并输出空格数
function empty (str) {
let num = 0
for (let i = 0; i < str.length; i++) {
const char = str[i]
if (char === ' ') {
str = str.substring(0, i) + str.substring(i + 1, str.length)
i--
num++
}
}
return {
str,
num
}
}
console.log(empty('s t t x'))
# 猴子吃桃
function monkey (n) {
let nums = 1
for (let i = n; i > 0; i--) {
nums = (nums + 1 ) * 2
}
console.log(nums)
}
monkey(9)
# 洗牌
一：简单版
缺点 改变原数组 且时间复杂度为O(n2)
function shuffle(arr) {
let random, result = []
while (arr.length) {
random = Math.floor(Math.random() * arr.length)
result.push(...arr.splice(random, 1))
}
return result
}
二：随机取前面一个与递减的最后一个交换
function shuffle(arr) {
let random, n = arr.length
while (n > 0) {
random = Math.floor(Math.random() * n--)
let temp = arr[n]
arr[n] = arr[random]
arr[random] = temp
}
return arr
}
# 寻找数组中，该元素大于左侧的所值，小于右侧的所有值
遍历找到当前位置的左侧最大值以及右侧最小值
当位置相同时则为解
function findNum (arr) {
const length = arr.length
let up = [], down = []
let max = 0, min = arr[length - 1]
let result = []
for (let i = 0; i < length; i++) {
max = Math.max(max, arr[i])
up.push(max)
}
for (let i = length - 1; i >= 0; i--) {
min = Math.min(min, arr[i])
down.push(min)
}
down.reverse()
for (let i = 0; i < length; i++) {
if (up[i] === down[i] && i !== length - 1) {
result.push(up[i])
}
}
return result.length ? result : -1
}
console.log(findNum([7,10,2,6,19,22,32]))
# 先投硬币
第一个人正面的概率
1-另一人没抛出的概率
等比前n项求和
1- (1/2 * 1/2 + 1/2 * 1/2 * 1/2 * 1/2 + ....) =
1- ((1/4) + (1/4)^2 + ... + (1/4)^(n/2)
= 1- (1/4)(1- (1/4) ^ (n/2)) / (1- 1/4)
在 n 趋于无穷大的时候，1-(1/4)^(n/2)为 1
所以上面的式子变成 1-1/3 = 2/3
# 有1000瓶水，其中有一瓶有毒 (opens new window)
给1000个瓶分别标上如下标签（10位长度）：
0000000001 （第1瓶） 0000000010 （第2瓶） 0000000011 （第3瓶） ...... 1111101000 （第1000瓶） 从编号最后1位是1的所有的瓶子里面取出1滴混在一起（比如从第一瓶，第三瓶，。。。里分别取出一滴混在一起）并标上记号为1。以此类推，从编号第一位是 1的所有的瓶子里面取出1滴混在一起并标上记号为10。现在得到有10个编号的混合液，小白鼠排排站，分别标上10，9，。。。1号，并分别给它们灌上对 应号码的混合液。24小时过去了，过来验尸吧： 从左到右，死了的小白鼠贴上标签1，没死的贴上0，最后得到一个序号，把这个序号换成10进制的数字，就是有毒的那瓶水的编号。
检验一下：假如第一瓶有毒，按照0000000001 （第1瓶），说明第1号混合液有毒，因此小白鼠的生死符为0000000001（编号为1的小白鼠挂了），0000000001二进制标签转换成十进 制=1号瓶有毒；假如第三瓶有毒，0000000011 （第3瓶），第1号和第2号混合液有毒，因此小白鼠的生死符为00000011（编号为1，2的鼠兄弟挂了），0000000011二进制标签转换成十进 制=3号瓶有毒。
至于这个算法的证明，大概的思路如下：有毒的水，喂食的那几条小狗肯定都会死，剩下的都不会死，只需要说明唯一性就可以了。10条小狗死亡情况的可能性，正好是2^10=1024，跟水瓶一一对应还是没问题的。
# 扔鸡蛋
100楼往下扔鸡蛋
1.从下往上
o(n)
2.二分查找
最坏时比1还多一次
3.每十层投一次
最多19次
# 判断两个升序数组其中一个是另外一个数组的子集
- 数组N的所有元素都能在数组M中找到；
- 数组N项中元素重复项的个数不能大于数组M中元素重复项的个数。
function isSubset(arrM,arrN){//两数组均为升序排序
let m = arrM.length;
let n = arrN.length;
let i = 0, j = 0;
while(m > n && i < m && j < n){
if(arrM[i] < arrN[j]){//M数组有重复项
i++;
}else if(arrM[i] > arrN[j]){//N数组重复项数大于M数组重复项数
return false;
}else{//两项相等
i++;
j++;
}
}
if(j < n){//N数组元素不全在M数组内
return false;
}else{
return true
}
}
let arrM = [1,2,2,3,3,4,4,5,5]
let arrN = [1,2,3,4,5]
console.log(isSubset(arrM,arrN))//true
# 扑克牌同花顺
现在有54张扑克牌，抽出5张牌，求出同花顺的概率，A代表1，且顺子不能重复
一种花色有9种可能a1234~910jqk
4种就有36种可能
所以是36/c54(5)
参考思路：
一把扑克除去大、小王，任意选3张或者5张出现同花顺的概率？任意选三张出现豹子的概率（三张同样数字）?任意三张组合有多少顺子？
五张与三张算法一样，只分析三张的情况：一副牌任选三张共有种组合。同花：共种组合；概率为1144/22100=0.05176顺子：假定顺子为A23到JQK共11个，不区分花色A23的顺子有种，同理任何固定顺序的顺子都是64种组合，这样一副牌有64*11=704个顺子；概率为704/22100=0.031855。同花顺：每个花色从A23到JQK有11个顺子，全副牌共44个同花顺；概率为44/22100=0.00199。豹子：共个；概率为52/22100=0.00235。
# 字符串找最长升序的数字
字符串，串中有字母也有阿拉伯数字，需要你从字符串中找到连续，是升序且串长度是符合前两个条件的前提下最长的串，比如说"abc123d2345f45e43"，将字符串"2345"找到并返回。
function findUpNumber (str) {
let left = 0, right = 0
let maxLeft = 0, maxRight = 0
for (let i = 0; i < str.length; i++) {
const char = str[i]
if (isNaN(char)) {
left = i + 1
} else {
// 是数字
const nextChar = str[i + 1]
// 下一个是数字且大于上一个
if (!isNaN(nextChar) && nextChar > char) {
right = i + 1
} else {
left = i + 1
right = i + 1
}
}
// 每次找完记录下最长的位置
if (right - left > maxRight - maxLeft) {
maxLeft = left
maxRight = right
}
}
return maxRight > maxLeft ? str.substring(maxLeft, maxRight + 1) : 'not valid data'
}
console.log(findUpNumber('ab43c1d234f4e43'))
# 货币格式化
正则
function numberWithCommas(n) {
// 正则解释: 匹配到 \B(非单词边界)后, 后面要匹配到 (\d{3})+(?!\d)
// (\d{3})+ 至少匹配到一次或多次三个数字
// (?!\d) 同时后面不是数字的话, 就匹配.
// 注意, 后面的(?=)那一段代码只是判断的规则, 匹配到后只替换掉\B
// 而\B 元字符匹配的是非单词边界
let num = n.toString().split('.');
num[0] = num[0].replace(/\B(?=(\d{3})+(?!\d))/g, ',');
return num.join('.');
}
console.log(numberWithCommas(12345678912.1234)) // "12,345,678,912.1234"ss
蠢方法
var dealNumber = function (money) {
if (money && money != null) {
money = String(money);
var left = money.split('.')[0], right = money.split('.')[1];
right = right ? (right.length >= 2 ? '.' + right.substr(0, 2) : '.' + right + '0') : '.00';
var temp = left.split('').reverse().join('').match(/(\d{1,3})/g);
console.log(temp)
return (Number(money) < 0 ? "-" : "") + temp.join(',').split('').reverse().join('') + right;
} else if (money === 0) { //注意===在这里的使用，如果传入的money为0,if中会将其判定为boolean类型，故而要另外做===判断
return '0.00';
} else {
return "";
}
};
console.log(dealNumber(12451331.22))
# 大整数相加
// bigNumberA和bigNumberB使用字符串存储，否则会自动转化为科学计数
let bigNumberAdd = (bigNumberA, bigNumberB) => {
let A = (bigNumberA + '').split('');
let B = (bigNumberB + '').split('');
let aLen = A.length, bLen = B.length, cLen = Math.max(aLen, bLen) + 1;
let result = [], prefix = 0;
for (let i = 0; i< cLen -1; i++ ) {
let a = aLen - i - 1 >= 0 ? parseInt(A[aLen - i - 1]) : 0, b = bLen - i - 1 >= 0 ? parseInt(B[bLen - i - 1]) : 0;
result[i] = (a + b + prefix) % 10;
prefix = Math.floor((a + b + prefix) / 10);
}
return result.reverse().join('');
};
bigNumberAdd('45486646468484544661134868968','544545867466464646');
# rgb排序
给定一个字符串里面只有"R" "G" "B" 三个字符，请排序 (opens new window)，最终结果的顺序是R在前 G中 B在后。时间复杂度为O(n),空间复杂度O(1)
function sortRGB(str) {
const length = str.length
let rLength = 0
let bLength = 0
for (let i = 0; i < length; i++) {
const char = str[i]
if (char === 'R') {
if (i !== rLength) {
str = str.substring(0, rLength) + 'R' + str.substring(rLength, i) + str.substring(i + 1, length)
}
rLength++
} else if (char === 'B') {
if (i < length - bLength) {
str = str.substring(0, i) + str.substring(i + 1, length) + 'B'
i--
}
bLength++
}
}
return str
}
console.log(sortRGB('BRGBRGRRGBBGBGR'))
function sortRGB(str) {
return str.split('').sort((a, b) => b > a ? 0 : -1).join('')
}
console.log(sortRGB('BRGBRGRRGBBGBGR'))
for循环记录次数
for循环拼出来
# 油漆比例
两桶油漆，A桶全是红色油漆，B桶全是蓝色油漆，将A桶中取一勺倒入B中，再从B桶中取一勺倒入A中，求A桶的蓝红比例和B桶的红蓝比例，是大于、小于还是等于？
x,y
然后算比例就可以了
最后是相等
# 扑克概率
52张扑克牌，取一张不放回，再取一张， 两张为相同颜色的概率是多少？
（1/4） * （12 /51）
# 小浩算法
# 字符串系列
# 实现Sunday匹配
var s1 = 'Here is a little Hao', s2 = 'little';
function strStr(origin, aim) {
if (origin == null || aim == null) {
return 0;
}
if (origin.length < aim.length) {
return -1;
}
//目标串匹配索
let originIndex = 0;
//模式串匹配索引
let aimIndex = 0;
// 成功匹配完终止条件：所有aim均成功匹配
while (aimIndex < aim.length) {
// 针对origin匹配完，但aim未匹配完情况处理 如 mississippi sippia
if (originIndex > origin.length - 1) {
return -1;
}
if (origin.charAt(originIndex) == aim.charAt(aimIndex)) {
// 匹配则index均加1
originIndex++;
aimIndex++;
} else {
//在我们上面的样例中，第一次计算值为6，第二次值为13
let nextCharIndex = originIndex - aimIndex + aim.length;
//判断下一个目标字符（上面图里的那个绿框框）是否存在。
if (nextCharIndex < origin.length) {
// 判断目标字符在模式串中匹配到，返回最后一个匹配的index
let step = aim.lastIndexOf(origin.charAt(nextCharIndex));
if (step == -1) {
// 不存在的话，设置到目标字符的下一个元素
originIndex = nextCharIndex + 1;
} else {
// 存在的话，移动对应的数字（参考上文中的存在公式）
originIndex = nextCharIndex - step;
}
//模式串总是从第一个开始匹配
aimIndex = 0;
} else {
return -1;
}
}
}
return originIndex - aimIndex;
}
console.log(strStr(s1, s2))
# 其他
# 三门问题
const door = [1,2,3]
let changeDoor = 0;
let noChangeDoor = 0;
const time = 10000000
function getRandomNum() {
return Math.round(Math.random() * (door.length - 1) + 1)
}
// true 换
function getTrueOrFalse() {
return Math.round(Math.random()) === 0
}
for (let i = 0; i < time; i++) {
// 生成随机天使所在门
const angelDoor = getRandomNum();
// 生成选择的门
const chooseDoor = getRandomNum();
const noChooseDoor = door.filter(item => item !== chooseDoor)
const noChooseDoorAngel = noChooseDoor.findIndex(item => item === angelDoor)
// 一开始就确定不换 noChangeDoor才会++
// 一开始就确定换 changeDoor才会++
if (noChooseDoorAngel === -1) {
// 上来就选中了天使
// if (getTrueOrFalse()) {
// } else {
noChangeDoor++
// }
} else {
// 主持人去掉了恶魔，剩下的肯定是天使
changeDoor++
// if (getTrueOrFalse()) {
// changeDoor++
// }
}
}
console.log('changeDoor', changeDoor / time);
console.log('noChangeDoor', noChangeDoor / time);
// changeDoor 0.6248973
// noChangeDoor 0.3751027