linxiaowu66 / algorithms-of-these-years Goto Github PK
View Code? Open in Web Editor NEW记录做过的算法题目
algorithms-of-these-years's People
Contributors
Stargazers
Watchers
algorithms-of-these-years's Issues
有效的括号
有效的括号
题目来源：leetcode
题目详情
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解法
使用栈模型，保证顺序有效性
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
if (s === "") {
return true
}
if (s.length % 2) {
return false
}
const temp = {
')': '(',
'}': '{',
']': '['
}
const array = []
for (let i = 0; i < s.length; i++) {
if (['(', '{', '['].includes(s[i])) {
array.push(s[i])
} else if (array[array.length - 1] !== temp[s[i]]) {
return false
} else if (array[array.length - 1] === temp[s[i]]) {
array.pop()
}
}
if (array.length > 0) {
return false
}
return true
};实现reduce函数并且支持异步
字典序
字典序
题目来源：牛客网
题目详情
给定整数n和m, 将1到n的这n个整数按字典序排列之后, 求其中的第m个数。
对于n=11, m=4, 按字典序排列依次为1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9, 因此第4个数是2.
对于n=200, m=25, 按字典序排列依次为1 10 100 101 102 103 104 105 106 107 108 109 11 110 111 112 113 114 115 116 117 118 119 12 120 121 122 123 124 125 126 127 128 129 13 130 131 132 133 134 135 136 137 138 139 14 140 141 142 143 144 145 146 147 148 149 15 150 151 152 153 154 155 156 157 158 159 16 160 161 162 163 164 165 166 167 168 169 17 170 171 172 173 174 175 176 177 178 179 18 180 181 182 183 184 185 186 187 188 189 19 190 191 192 193 194 195 196 197 198 199 2 20 200 21 22 23 24 25 26 27 28 29 3 30 31 32 33 34 35 36 37 38 39 4 40 41 42 43 44 45 46 47 48 49 5 50 51 52 53 54 55 56 57 58 59 6 60 61 62 63 64 65 66 67 68 69 7 70 71 72 73 74 75 76 77 78 79 8 80 81 82 83 84 85 86 87 88 89 9 90 91 92 93 94 95 96 97 98 99 因此第25个数是120…
输入描述:
输入仅包含两个整数n和m。
数据范围:
对于20%的数据, 1 <= m <= n <= 5 ;
对于80%的数据, 1 <= m <= n <= 10^7 ;
对于100%的数据, 1 <= m <= n <= 10^18.
输出描述:
输出仅包括一行, 即所求排列中的第m个数字.
解法
如果提供的数字不超过js可以正常表达的区间，那么下面的答案符合要求
function getNodeCount(rootValue, n) {
let base = 10
let count = 1
while (rootValue * base <= n) {
// 这个计算看下面的解析
if (((rootValue + 1) * base) - 1 < n) {
count += base
} else {
count += n + 1 - rootValue * base
}
base *= 10
}
return count
}
function lexicalOrder(n, m) {
let ans = 1
while(m !== 0) {
const count = getNodeCount(ans, n)
if (count >= m) {
m--
if (m === 0) {
return ans
}
ans *= 10
} else {
m -= count
ans += 1
}
}
}但是如果数字很大，可能达到10^18，那么就需要用到标准的bigInt新特性，因此答案是：
function getNodeCount(rootValue, n) {
let base = 10n
let count = 1n
while (BigInt(rootValue) * BigInt(base) <= BigInt(n)) {
// 计算见解析
if (((BigInt(rootValue) + 1n) * BigInt(base)) - 1n < BigInt(n)) {
count = BigInt(count) + BigInt(base)
} else {
count = BigInt(count) + BigInt(n) + 1n - BigInt(rootValue) * BigInt(base)
}
base = BigInt(base) * 10n
}
return count
}
function lexicalOrder(n, m) {
let ans = 1
while(m !== 0) {
const count = getNodeCount(ans, n)
console.log(count, m, ans)
if (BigInt(count) >= BigInt(m)) {
m = BigInt(m) - 1n
if (BigInt(m) === 0n) {
return ans
}
ans = BigInt(ans) * 10n
} else {
m = BigInt(m) - BigInt(count)
ans = BigInt(ans) + 1n
}
}
}
const m = 5555555555555555n
console.log(`字典序排在第${m}是：`, lexicalOrder(10000000000000000n, m))简约版本的throttle
throttle的简单实现
题目详情
实现一个简易版本的节流函数，没有别的配置参数，原型如下：
const throttle = function(fn, waitTime) {}
解法
因为是节流，所以主关键的点是设置一个超时函数，在有效的waitTime时间内，仅允许触发一次节流函数，其他的时候都忽略掉直到触发的时间点超过waitTime时间段内之后，重新清空等待下一次触发
const throttle = function(fn, waitTime) {
let timeout = null
let previous = 0
let result = 0
const later = function() {
result = fn.apply(this, arguments)
clearTimeout(timeout)
timeout = null
previous = Date.now()
}
return function() {
const now = Date.now()
if (!previous) {
previous = Date.now()
}
const remaining = waitTime - (now - previous)
const context = this
const args = arguments
if (remaining > 0 && !timeout) {
timeout = setTimeout(later.bind(context, args), remaining)
} else if (remaining <= 0) {
previous = now
if (timeout) {
clearTimeout(timeout)
timeout = null
}
}
return result
}
}两数之和
两数之和
题目来源：力扣（LeetCode）
题目详情
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解法
这个解法真的是很巧妙！！
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
// 维护一份nums反向的数组列表
let temp = []
for (let i = 0; i < nums.length; i++) {
const diff = target - nums[i]
if (temp[diff] !== undefined) {
return [i, temp[diff]]
}
temp[nums[i]] = i
}
};字符串全排列
字符串全排列
题目来源：字节跳动面试题
题目详情
给定字符串，求出所有由该串内字符组合的全排列。所包含的字符不重复。
输入："abc"
输出：["abc","acb","bac","bca","cab","cba"]
解法
这种穷举的，我看网上都是使用递归来穷举。递归本质是找到递归主体，而递归主体的寻找其实就是将问题简化到最最简单的情况。所以本题使用递归的话，我们将问题缩放到只有两个字符串的情况，
使用插空的形式，将字符串'ab'中的'a'插入到'b'的两次，得到'ab'和'ba'，于是有了下面的解法
function pailie(str) {
const result = []
if (str.length === 1) {
return [str]
} else {
const pailieRes = pailie(str.slice(1))
for (let i = 0; i < pailieRes.length; i++) {
for(let j =0; j < pailieRes[i].length + 1; j++) {
const temp = pailieRes[i].slice(0, j) + str[0] + pailieRes[i].slice(j)
result.push(temp)
}
}
}
return result
}
pailie('abc')下面一种不是递归的方式：
function pailie(str) {
if (str.length <= 1) { return [str] }
const result = []
const strArray = str.split('')
let resultStr = [strArray[0]]
for (let i = 1; i < strArray.length; i++) {
let result = []
for (let j=0; j < resultStr.length; j++) {
for (let k = 0; k < resultStr[j].length + 1; k++) {
const temp = resultStr[j].slice(0, k) + strArray[i] + resultStr[j].slice(k)
result.push(temp)
}
}
resultStr = result
}
return resultStr
}
pailie('abc')
其核心**是从无到有的形式，也就是先使用字符串的首字母，然后一个个取剩下的字符和之前排序好的字符再进行填空，举个例子：
字符串”abcd“，那么我们先取出字符：a，于是有resultStr = ["a"]，然后开始循环取字符”b"，排列出的组合有：
["ab", "ba"]
于是这个结果在第二次循环使用，与字符"c"一起排列，得到的结果是：
["cab", "acb", "abc", "cba", "bca", "bac"]。
一直循环下去，直到循环结束
这种方式得到的结果，在排列字符串”abcdefghijkm"的时候也是会卡住！
如果提供的字符串有重复的字符，要求重复的字符不相邻，那么我们可以使用上面的结果之后再做个正则表达式过滤：/(.)\1+/g
字典序排序
题目来源：字典序排序
题目详情
给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如，
给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
解法
var lexicalOrder = function(n) {
const result = []
const iteration = function(result, current, max) {
if(current != null && current > max){
return;
}
if(current != null) {
result.push(current);
}
for (let i = 0; i <= 9; i++) {
if (current === null) {
if (i === 0) {
continue
} else {
current = 0
}
}
iteration(result, current * 10 + i, max)
}
}
iteration(result, null, n)
return result
};函数柯里化实现
函数柯里化实现
题目来源：头条面试
题目详情
实现一个函数，允许下面的函数改造成柯里化函数，实现下面的效果
fn(1, 2, 3)
fn(1, 2)(3)
fn(1)(2)(3
得到的结果都可以是6
解法
柯里化的核心**是一个聚散的过程，表面看是可以将一个函数的调用打散掉，可以多次调用执行，实际内在实现是聚合参数，直到参数的个数符合被柯里化函数的参数个数的要求。
比如：
function sum(a) {
return function(b) {
return a + b
}
}
sum(1)(2)
因此解法是：
function sum(a, b, c) {
const result = a + b + c
}
const fn = curry(sum)
function curry(fn) {
const args = Array.from(arguments).slice(1)
const length = args.length
return function() {
const _args = args.concat(Array.from(arguments))
if (_args.length < fn.length) {
return curry.call(this, fn, _args)
} else {
return fn.apply(this, _args)
}
}
}
fn(1, 2, 3)
fn(1, 2)(3)
fn(1)(2)(3)最小二叉堆
题目来源：无
题目详情
实现最小二叉堆，包括插入、删除根节点等操作，最后利用堆排序得到排序结果
解法
const array = [8, 10, 4342, 2, 34, 18, 11, 77, 16, 66]
class MinBinaryHeap {
constructor(array) {
this.heap = [...array]
this.length = this.heap.length
this.buildHeap()
}
buildHeap() {
for(let i = Math.floor(this.length / 2) - 1; i >= 0; i -= 1) {
this.bubbleDown(this.heap, i, this.length - 1)
}
}
bubbleDown(array, parentIndex, length) {
// 可以看出这种向下调整的操作是以父节点找子节点的行为
let childIndex = parentIndex * 2 + 1
// parentIndex的值会和子节点、孙子节点等节点进行比较，直到找到属于自己的位置
let temp = array[parentIndex]
while (childIndex < length) {
if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
childIndex += 1
}
// 找到了有一个节点比父节点大，此时的位置便是父节点的最终位置
if (temp <= array[childIndex]) {
break
}
array[parentIndex] = array[childIndex]
// 将替换的节点作为父节点，继续遍历下面的子节点
parentIndex = childIndex
childIndex = childIndex * 2 + 1
}
array[parentIndex] = temp
}
bubbleUp(array) {
// 可以看出这种向上调整的操作是以子节点找父节点的行为
let childIndex = array.length - 1
let parentIndex = Math.floor((childIndex - 1) / 2)
let temp = array[childIndex]
while(childIndex > 0 && array[parentIndex] > temp) {
array[childIndex] = array[parentIndex]
childIndex = parentIndex
parentIndex = Math.floor((parentIndex - 1) / 2)
}
array[childIndex] = temp
}
insert(newNode) {
// 插入节点操作，放在最后面，然后进行自下而上的操作
this.heap.push(newNode)
this.length++
this.bubbleUp(this.heap)
}
print() {
return this.heap
}
remove() {
// 二叉堆的删除操作指的是删除根节点，之后自稳定
if (this.length === 1) {
return this.heap[0]
}
const lastEle = this.heap.pop()
const top = this.heap[0]
this.heap[0] = lastEle
this.length--
this.bubbleDown(this.heap, 0, this.length)
return top
}
sort() {
const result = []
let i = this.heap.length
while (i > 0) {
result.push(this.remove())
i -= 1
}
return result
}
}
const heap = new MinBinaryHeap(array)
console.log('最小二叉堆是：', heap.print())
heap.insert(5)
console.log('插入5之后的最小二叉堆是：', heap.print())
heap.remove()
console.log('删除根节点之后的最小二叉堆是：', heap.print())
console.log('二叉堆进行堆排序结果：', heap.sort())
console.log(heap.print())红黑树
题目来源：无
题目详情
实现红黑树的添加、删除、查找等操作
解法
const RED = 'red'
const BLACK = 'black'
function Node(data) {
this.leftNode = null
this.rightNode = null
this.parentNode = null
this.data = data
this.rbColor = RED
}
class RbTree {
constructor(array) {
this.root = null
array.forEach(it => this.insert(it))
}
/*************对红黑树节点x进行左旋操作 ******************/
/*
* 左旋示意图：对节点x进行左旋
* p p
* / /
* x y
* / \ / \
* lx y -----> x ry
* / \ / \
* ly ry lx ly
* 左旋做了三件事：
* 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
* 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
* 3. 将y的左子节点设为x，将x的父节点设为y
********************************************************/
rotateLeft(beRotatedNode) {
// x节点的右节点y
const rightNode = beRotatedNode.rightNode
// x节点的右节点变更掉，将y的左节点赋值过来
beRotatedNode.rightNode = rightNode.leftNode
// 如果y节点的左节点有值，那么x将是y节点的左节点的父节点
if (rightNode.leftNode) {
rightNode.leftNode.parentNode = beRotatedNode
}
// 将x的父节点赋值给y节点的父节点
rightNode.parentNode = beRotatedNode.parentNode
// 如果x的父节点存在的话
if (beRotatedNode.parentNode) {
// 如果x节点之前是其父节点的左节点
if (beRotatedNode === beRotatedNode.parentNode.leftNode) {
beRotatedNode.parentNode.leftNode = rightNode
} else {
beRotatedNode.parentNode.rightNode = rightNode
}
} else {
// 如果x的父节点为空，那么说明是根节点
this.root = rightNode
}
// 3. 将y的左节点设为x，将x的父节点设为y
rightNode.leftNode = beRotatedNode
beRotatedNode.parentNode = rightNode
}
/*************对红黑树节点y进行右旋操作 ******************/
/*
* 右旋示意图：对节点y进行右旋
* p p
* / /
* y x
* / \ / \
* x ry -----> lx y
* / \ / \
* lx rx rx ry
* 右旋做了三件事：
* 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
* 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
* 3. 将x的右子节点设为y，将y的父节点设为x
*/
rotateRight(beRotatedNode) {
// y节点的左节点x
const leftNode = beRotatedNode.leftNode
// y节点的左节点变更掉，将x的右节点赋值过来
beRotatedNode.leftNode = leftNode.rightNode
// 如果x节点的右节点有值，那么y将是x节点的右节点的父节点
if (leftNode.rightNode) {
leftNode.rightNode.parentNode = beRotatedNode
}
// 将y的父节点赋值给x节点的父节点
leftNode.parentNode = beRotatedNode.parentNode
// 如果y的父节点存在的话
if (beRotatedNode.parentNode) {
// 如果y节点之前是其父节点的左节点
if (beRotatedNode === beRotatedNode.parentNode.leftNode) {
beRotatedNode.parentNode.leftNode = leftNode
} else {
beRotatedNode.parentNode.rightNode = leftNode
}
} else {
// 如果x的父节点为空，那么说明是根节点
this.root = leftNode
}
// 3. 将x的左节点设为y，将y的父节点设为x
leftNode.rightNode = beRotatedNode
beRotatedNode.parentNode = leftNode
}
insert(data) {
// 1. 实例化新节点
const node = new Node(data)
if (node) {
this.__insert(node)
}
}
//将节点插入到红黑树中，这个过程与二叉搜索树是一样的
// 查找适合存放该节点的位置
__insert(node) {
let root = this.root
let parent = null
let compareRes
// 2. 查找插入节点适合存放的位置，并与其父节点建立联系
while(root !== null) {
parent = root
compareRes = node.data - root.data
// 如果插入的节点比当前父节点大，那么继续寻找该父节点的右节点
if (compareRes > 0) {
root = root.rightNode
} else if (compareRes < 0) {
root = root.leftNode
} else {
return root
}
}
// 找到插入节点的父节点了，此时parent表示的就是插入节点的父节点
node.parentNode = parent
// 接着判断是插入到该父节点的左边还是右边
if (parent) {
if (compareRes < 0) {
parent.leftNode = node
} else {
parent.rightNode = node
}
} else {
this.root = node
}
// 3. 修整整个红黑树
this.__insert_color(this.root, node)
return null
}
__insert_color(root, node) {
let parent = node.parentNode
let gparent, uncle
// 第一种情况和第二种情况都不会进入这个while语句，所以都是很简单的
// 只有第三种情况才会进入，也就是父节点存在并且父节点是红色
while(parent !== null && parent.rbColor === RED) {
gparent = parent.parentNode
// 如果父节点是祖父节点的左节点
if (parent === gparent.leftNode) {
// 取叔叔节点，也就是父节点的兄弟节点
uncle = gparent.rightNode
// case3.1情况：如果叔叔节点存在并且颜色是红色
if (uncle && uncle.rbColor === RED) {
// 1、将叔叔节点、父节点、祖父节点分别置为黑黑红
uncle.rbColor = BLACK
parent.rbColor = BLACK
gparent.rbColor = RED
// 2、将祖父节点置为当前节点
node = gparent
// 祖父节点变更后，父节点必然也得变更
parent = node.parentNode
continue
}
// case3.2.2、如果叔叔节点不存在或者叔叔节点是黑色，并且插入的节点是在父节点的右边
// 因为该情况最后会归一化到case3.2.1的情况，所以需要先执行
if (parent.rightNode === node) {
// 1、以父节点为支点，进行左旋
this.rotateLeft(parent)
// 旋转之后需要重新设置
uncle = parent
parent = node
node = uncle
}
// 上面一种情况最后要归一化到最后的这种情况case3.2.1：叔叔节点不存在或者叔叔节点是黑色的，并且插入
// 的节点是在父节点的左边
// 1、将父节点和祖父节点分别设置为黑红
parent.rbColor = BLACK
gparent.rbColor = RED
// 2、对祖父节点进行右旋
this.rotateRight(gparent)
// 更新父节点
parent = node.parentNode
} else {
// 父节点是祖父节点的右节点，情况和上面完全相反
// 取叔叔节点，也就是父节点的兄弟节点
uncle = gparent.leftNode
// case3.1情况：如果叔叔节点存在并且颜色是红色
if (uncle && uncle.rbColor === RED) {
// 1、将叔叔节点、父节点、祖父节点分别置为黑黑红
uncle.rbColor = BLACK
parent.rbColor = BLACK
gparent.rbColor = RED
// 2、将祖父节点置为当前节点
node = gparent
// 祖父节点变更后，父节点必然也得变更
parent = node.parentNode
continue
}
// case3.3.2、如果叔叔节点不存在或者叔叔节点是黑色，并且插入的节点是在父节点的右边
// 因为该情况最后会归一化到case3.3.1的情况，所以需要先执行
if (parent.leftNode === node) {
// 1、以父节点为支点，进行右旋
this.rotateRight(parent)
// 旋转之后需要重新设置
uncle = parent
parent = node
node = uncle
}
// 上面一种情况最后要归一化到最后的这种情况case3.3.1：叔叔节点不存在或者叔叔节点是黑色的，并且插入
// 的节点是在父节点的右边
// 1、将父节点和祖父节点分别设置为黑红
parent.rbColor = BLACK
gparent.rbColor = RED
// 2、对祖父节点进行左旋
this.rotateLeft(gparent)
// 更新父节点
parent = node.parentNode
}
}
this.root.rbColor = BLACK
}
findNode(data) {
let root = this.root
while (root !== null) {
if (data > root.data) {
root = root.rightNode
} else if (data < root.data) {
root = root.leftNode
} else {
return root
}
}
return null
}
remove(data) {
const node = this.findNode(data)
if (node) {
this.__remove(node)
}
}
// 既然是替换节点，为何不直接将替换节点的值复制到被删除节点后，再将替换节点复制给node？这样代码不是可以省很多吗？周一试一下？
__remove(node) {
let replaceNode = node
// 如果被删除的节点左右节点都不为空
if (node.leftNode && node.rightNode) {
// 先找出被删除节点的后继节点（大于删除结点的最小结点）来当做替换节点
let replaceNode = node.rightNode
while(replaceNode.leftNode) {
replaceNode = replaceNode.leftNode
}
node.data = replaceNode.data
}
const parent = replaceNode.parentNode
const color = replaceNode.rbColor
// 这里有着足够的隐含信息，如果被删除节点不是左右节点都有，那么这里的child是null或者左右节点之一，
// 如果被删除节点左右节点皆有，那么这里的是替换节点，而替换节点的左节点肯定是不存在的，只能是右节点或者null
const child = replaceNode.rightNode || replaceNode.leftNode
if (child) {
child.parentNode = parent
}
if (parent) {
if (parent.leftNode === replaceNode) {
parent.leftNode = child
} else {
parent.rightNode = child
}
} else {
this.root = child
}
if (color === BLACK) {
this.__remove_color(child, parent)
}
replaceNode = null
}
// node表示待修正的节点，即后继节点的子节点（因为后继节点被删除了）
__remove_color(node, parent) {
let brother
while((node === null || node.rbColor === BLACK) && node !== this.root) {
// 场景2.1、替换结点是其父结点的左子结点
if (node == parent.leftNode) {
brother = parent.rightNode // 取兄弟节点
// 场景2.1.1、替换结点的兄弟结点是红结点
if (brother.rbColor === RED) {
brother.rbColor = BLACK
parent.rbColor = RED
this.rotateLeft(parent)
// 归一化到场景2.1.2.3
brother = parent.rightNode
}
// 场景2.1.2、替换结点的兄弟结点是黑结点
// 场景2.1.2.3、替换结点的兄弟结点的子结点都为黑结点
if ((brother.leftNode === null || brother.leftNode.rbColor === BLACK) && (brother.rightNode === null || brother.rightNode.rbColor === BLACK)) {
brother.rbColor = RED
node = parent
parent = node.parentNode
} else {
// 场景2.1.2.2、替换结点的兄弟结点的右子结点为黑结点，左子结点为红结点
if (brother.rightNode === null || brother.rightNode.rbColor === BLACK) {
if (brother.leftNode) {
brother.leftNode.rbColor = BLACK
}
brother.rbColor = RED
// 右旋后归一化到场景2.1.2.1
this.rotateRight(brother)
brother = parent.rightNode
}
// 场景2.1.2.1、替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色
brother.rbColor = parent.rbColor
parent.rbColor = BLACK
if (brother.rightNode) {
brother.rightNode.rbColor = BLACK
}
this.rotateLeft(parent)
node = this.root
break
}
} else {
// 场景2.2、替换结点是其父结点的右子结点
brother = parent.leftNode
// 场景2.2.1、替换结点的兄弟结点是红结点
if (brother.rbColor === RED) {
brother.rbColor = BLACK
parent.rbColor = RED
// 右旋后会进入场景2.2.2.3
this.rotateRight(parent)
brother = parent.leftNode
}
// 场景2.2.2、替换结点的兄弟结点是黑结点
// 场景2.2.2.3、替换结点的兄弟结点的子结点都为黑结点
if ((brother.leftNode === null || brother.leftNode.rbColor === BLACK) && (brother.rightNode === null || brother.rightNode.rbColor === BLACK)) {
brother.rbColor = RED
node = parent
parent = node.parentNode
} else {
// 场景2.2.2.2、替换结点的兄弟结点的左子结点为黑结点，右子结点为红结点
if (brother.leftNode === null || brother.leftNode.rbColor === BLACK) {
if (brother.rightNode) {
brother.rightNode.rbColor = BLACK
}
brother.rbColor = RED
// 左旋后归一化到场景2.2.2.1
this.rotateLeft(brother)
brother = parent.leftNode
}
// 场景2.2.2.1、替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色
brother.rbColor = parent.rbColor
parent.rbColor = BLACK
if (brother.leftNode) {
brother.leftNode.rbColor = BLACK
}
this.rotateRight(parent)
node = this.root
break
}
}
}
if (node) {
node.rbColor = BLACK
}
}
// 销毁二叉树
clear() {
this.destroy(this.root)
this.root = null
}
destroy(node) {
if (node === null) {
return null
}
if (node.leftNode !== null) {
this.destroy(node.leftNode)
}
if (node.rightNode) {
this.destroy(node.rightNode)
}
node = null
}
print() {
return this.root
}
preOrderTraversal(node) {
const result = []
result.push(node.data)
if (node.leftNode) {
this.preOrderTraversal(node.leftNode)
}
if (node.rightNode) {
this.preOrderTraversal(node.rightNode)
}
}
inOrderTraversal(node) {
const result = []
result.push(node.data)
if (node.leftNode) {
this.inOrderTraversal(node.leftNode)
}
if (node.rightNode) {
this.inOrderTraversal(node.rightNode)
}
}
postOrderTraversal(node) {
const result = []
if (node.leftNode) {
this.postOrderTraversal(node.leftNode)
}
if (node.rightNode) {
this.postOrderTraversal(node.rightNode)
}
result.push(node.data)
}
findMinVal() {
const node = this.findMinNode()
if (node) {
return node.data
}
return null
}
findMinNode() {
let node = this.root
while(node.leftNode !== null) {
node = node.leftNode
}
return node
}
findMaxVal() {
const node = this.findMaxNode()
if (node) {
return node.data
}
return null
}
findMaxNode() {
let node = this.root
while (node.rightNode !== null) {
node = node.rightNode
}
return node
}
}
const tree = new RbTree([11, 2, 14, 1, 7, 15, 5, 8, 4, 16])简约版本的debounce
debounce的简单实现
题目详情
实现一个简易版本的debounce，不需要任何配置参数，原型是：
function debounce(fn, delaytime) {}
解法
因为是防抖，所以在触发没有结束之前，回调函数都不会被调用。当触发结束的时候，delaytime之后才会调用回调函数，因此我们在每次触发的时候都重置一下定时器，直到没有被触发。
function debounce(fn, delaytime) {
let timeout = null
let previous = 0
let result
const later = function() {
result = fn.apply(this, arguments)
if (timeout) {
clearTimeout(timeout)
timeout = null
}
previous = Date.now()
}
return function() {
const context = this
const args = arguments
const now = Date.now()
if (!previous) {
previous = Date.now()
}
const remaining = delaytime - (now - previous)
console.log(remaining, timeout, Date())
if (!timeout) {
timeout = setTimeout(later.bind(context, args), delaytime)
} else {
clearTimeout(timeout)
timeout = setTimeout(later.bind(context, args), delaytime)
}
previous = now
return result
}
}该版本因为过多的设置和清空回调函数，性能有点差，可以考虑优化成这样：
记录一个每次触发的时候的时间戳，当超时函数到期的时候，比较二者时间差来决定是否要继续加塞定时器：
function debounce(fn, delaytime) {
let timeout = null
let contetxt
let args
let previous = 0
let result
const later = function() {
const now = Date.now()
const remaining = delaytime - (now - previous)
if (remaining > 0) {
timeout = setTimeout(later.bind(context, args), remaining)
} else {
result = fn.apply(context, args)
if (timeout) {
clearTimeout(timeout)
timeout = null
context = null
args = null
}
}
}
return function() {
context = this
args = arguments
// 只要有触发，那么这里的previous就会一直更新
previous = Date.now()
if (!timeout) {
timeout = setTimeout(later.bind(context, args), delaytime)
}
return result
}
}二叉查找树的简单学习
题目来源：无
题目详情
根据数组实现一个二叉查找树，并实现前序遍历、中序遍历、后序遍历，以及查找某个节点和计算树的深度。
二叉查找树的概念就是根节点的左边节点都比根节点小，右边都比根节点大
解法
const arrays = [10, 20, 9, 15, 35, 99, 100, 11, 27, 76, 10001]
class Node {
constructor(data) {
this.leftNode = null
this.rightNode = null
this.data = data
}
insertLeft(node) {
this.leftNode = node
}
insertRight(node) {
this.rightNode = node
}
}
class Tree {
constructor(array) {
if (array.length === 0) {
this.root = null
return
}
this.root = new Node(array[0])
for(let i = 1; i < array.length; i++) {
this.insertNode(this.root, new Node(array[i]))
}
}
insertNode(rootNode, insertedNode) {
// 插入的节点比根节点大
if (rootNode.data < insertedNode.data) {
if (rootNode.rightNode) {
this.insertNode(rootNode.rightNode, insertedNode)
} else {
rootNode.rightNode = insertedNode
}
} else {
if (rootNode.leftNode) {
this.insertNode(rootNode.leftNode, insertedNode)
} else {
rootNode.leftNode = insertedNode
}
}
}
// 先序遍历
preorderTraversal(node) {
let result = []
if (!node) {
return []
}
result.push(node.data)
if (node.leftNode) {
const temp = this.preorderTraversal(node.leftNode)
result = [...result, ...temp]
}
if (node.rightNode) {
const temp = this.preorderTraversal(node.rightNode)
result = [...result, ...temp]
}
return result
}
// 中序遍历
inorderTraversal(node) {
let result = []
if (!node) {
return []
}
if (node.leftNode) {
const temp = this.inorderTraversal(node.leftNode)
result = [ ...result, ...temp]
}
result.push(node.data)
if (node.rightNode) {
const temp = this.inorderTraversal(node.rightNode)
result = [...result, ...temp]
}
return result
}
postorderTraversal(node) {
let result = []
if (!node) {
return []
}
if (node.leftNode) {
const temp = this.postorderTraversal(node.leftNode)
result = [...result, ...temp]
}
if (node.rightNode) {
const temp = this.postorderTraversal(node.rightNode)
result = [...result, ...temp]
}
result.push(node.data)
return result
}
treeHeight(node) {
if (!node) {
return 0
}
let leftTreeHeight = 1
let rightTreeHeight = 1
if (node.leftNode) {
leftTreeHeight += this.treeHeight(node.leftNode)
}
if (node.rightNode) {
rightTreeHeight += this.treeHeight(node.rightNode)
}
return Math.max(leftTreeHeight, rightTreeHeight)
}
find(node, val) {
if (!node) {
return null
}
if (val === node.data) {
return node
} else if (val < node.data) {
return this.find(node.leftNode, val)
} else {
return this.find(node.rightNode, val)
}
}
}
const tree = new Tree(arrays)
console.log('前序遍历结果是：', tree.preorderTraversal(tree.root))
console.log('中序遍历结果是：', tree.inorderTraversal(tree.root))
console.log('后序遍历结果是：', tree.postorderTraversal(tree.root))
console.log('这棵树的深度是：', tree.treeHeight(tree.root))
console.log('查找节点35：', tree.find(tree.root, 35))如果想用非递归方式遍历的话，可以借助栈模型，比如：
前序非递归遍历是利用了栈，将根结点放入栈中，然后再取出来，将值放入结果数组，然后如果存在左子树，将左子树压入栈，如果存在右子树，将右子树压入栈，然后循环判断栈是否为空，重复上述步骤。
根据压入栈的顺序就可以得到结果了
最长公共前缀
最长公共前缀
题目来源：最长公共前缀
题目详情
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
所有输入只包含小写字母 a-z 。
解法
该题目实现的核心逻辑是这样的，我们通过排序找到长度最短的字符串，从最短的字符串开始下手，将这个字符串去匹配剩余的所有字符串的前缀，能全部匹配上的，就是我们要找的答案
var longestCommonPrefix = function(strs) {
if (strs.length === 0) { return "" }
const sortRes = strs.sort((a, b) => a.length - b.length)
const shortestStr = sortRes[0]
for(let i = shortestStr.length; i > 0; i--) {
const matchStr = shortestStr.slice(0, i)
let isMatch = true
for (j = 1; j < sortRes.length; j++) {
const regx = new RegExp(`^${matchStr}`)
if (!sortRes[j].match(regx)) {
isMatch = false
break;
}
}
if (isMatch) {
return matchStr
}
}
return ""
};无重复字符的最长子串
无重复字符的最长子串
题目来源：无重复字符的最长子串
题目详情
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解法
var lengthOfLongestSubstring = function(s) {
let result = ''
let maxLength = 0
const length = s.length
for(let i = 0; i < length; i += 1) {
result = s[i]
if (length === 1) {
maxLength = 1
}
for (let j = i + 1; j < length; j += 1) {
if (result.includes(s[j])) {
maxLength = result.length > maxLength ? result.length : maxLength
break;
} else {
result += s[j]
maxLength = result.length > maxLength ? result.length : maxLength
}
}
}
return maxLength
};回文解码
回文解码
题目来源：回文解码
题目详情
现在有一个字符串，你要对这个字符串进行 n 次操作，每次操作给出两个数字：(p, l) 表示当前字符串中从下标为 p 的字符开始的长度为 l 的一个子串。你要将这个子串左右翻转后插在这个子串原来位置的正后方，求最后得到的字符串是什么。字符串的下标是从 0 开始的，你可以从样例中得到更多信息。
输入描述:
每组测试用例仅包含一组数据，每组数据第一行为原字符串，长度不超过 10 ，仅包含大小写字符与数字。接下来会有一个数字 n 表示有 n 个操作，再接下来有 n 行，每行两个整数，表示每次操作的(p , l)。
保证输入的操作一定合法，最后得到的字符串长度不超过 1000。
输出描述:
输出一个字符串代表最后得到的字符串。
示例1
输入
ab
2
0 2
1 3
输出
abbaabb
解法
以下解法只能在牛客网上运行，readline这种函数也就只有牛客网才有的方法
记得operation[0]和operation[1]都需要强制写为整数哦，否则字符串相加就全错了
let str = readline()
const operationCounts = readline()
for (let i = 0; i< operationCounts; i++) {
const operation = readline().split(' ')
const start = +operation[0]
const len = +operation[1]
const reverseStr = str.substr(start, len).split('').reverse().join('')
str = str.slice(0, start + len) + reverseStr + str.slice(start+len)
}
print(str)Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.