d-kylin / interview Goto Github PK
View Code? Open in Web Editor NEWJust do it, and do more better
Just do it, and do more better
实现一个 sum 函数,能满足以下情况调用时返回正确的结果。
sum(1,2,3,4).sumOf() //10
sum(1)(2)(3)(4).sumOf() //10
sum(1)(2,3)(4).sumOf() //10
sum()(2)()()()()().sumOf() //2
按照惯例,先上题目分析。链式调用的情况,可以通过返回对象本身,这样只要是对象的方法都能一直调用返回值,最容易想到的就是 JQuery 的链式调用。
var rootjQuery = null,
jQuery = function( selector, context ) {
return new jQuery.fn.init( selector, context, rootjQuery );
};
jQuery.fn = jQuery.prototype = {
init: function( selector, context, rootjQuery ) {
console.log("jQuery.init");
return this;
},
toArray: function() {
console.log("jquery.toArray");
return this;
}
};
jQuery.fn.init.prototype = jQuery.fn;
jQuery().init().init().toArray().init().toArray();
//控制台打印的结果如下:
//jQuery.init
//jQuery.init
//jQuery.init
//jquery.toArray
//jQuery.init
//jquery.toArray
另一种就是通过返回函数。
下面直接上结果:
function sum(...args){
let arr = args
let fn = function(...args) {
arr.push(...args)
return fn
}
fn.sumOf = function() {
return arr.reduce((re, cu) => {
return re + cu
})
}
return fn
}
1、一个长度为 N 的数组,元素为 1 时为正常值,元素为 2 时为异常值,并且有个约束,从第一个出现 2 以后的所有元素都只能是 2,如何用最少的查找次数找到第一个出现的 2 索引。
测试用例:
let a = [1,1,1,1,1,2,2];
let b = [2,2,2,2,2,2,2];
let c = [1,1,1,1,1,1,2];
最坏时间复杂度 O(n2)
最优时间复杂度 O(n)
平均时间复杂度 O(n2)
最坏空间复杂度 总共 O(n),需要辅助空间 O(1)
function bubble(arr) {
let i, j, temp;
for (i = 0; i < arr.length - 1; i++) {
for (j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
return arr
}
}
最坏时间复杂度 O(n2)
最优时间复杂度 O(n)
平均时间复杂度 O(n2)
最坏空间复杂度 总共 O(n),需要辅助空间 O(1)
function insertion(arr) {
let i, j
for (i = 1; i < arr.length; i++) {
for (j = 0; j < i; j++) {
if (arr[j] > arr[i]) {
arr.splice(j, 0, arr[i])
arr.splice(i + 1, 1)
break
}
}
}
return arr
}
最坏时间复杂度 O(n2)
最优时间复杂度 O(n)
平均时间复杂度 O(n + k)
最坏空间复杂度 总共 O(n + k)
function bucketSort(arr, num) {
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
const max = Math.max(...arr)
const min = Math.min(...arr)
const buckets = []
const bucketsSize = Math.floor((max - min) / num) + 1
for (let i = 0; i < arr.length; i++) {
let index = ~~(arr[i] / bucketsSize)
!buckets[index] && (buckets[index] = [])
buckets[index].push(arr[i])
let l = buckets[index].length
while(l > 0) {
buckets[index][l] < buckets[index][l - 1] && swap(buckets[index], l, l - 1)
l--
}
}
let wrapBuckets = []
for (let i = 0; i < buckets.length; i++) {
buckets[i] && (wrapBuckets = wrapBuckets.concat(buckets[i]))
}
return wrapBuckets
}
最坏时间复杂度 O(n + k)
最优时间复杂度 O(n + k)
平均时间复杂度 O(n + k)
最坏空间复杂度 O(n + k)
function countingSort(arr) {
let i, j
let C = []
let result = []
for (i = 0; i < arr.length; i++) {
C[arr[i]] >= 1 ? C[arr[i]]++ : (C[arr[i]] = 1)
}
for (j = 0; j < C.length; j++) {
if (C[j]) {
while (C[j] > 0) {
result.push(j)
C[j]--
}
}
}
return result
}
最坏时间复杂度 O(nlogn)
最优时间复杂度 O(nlogn)
平均时间复杂度 O(nlogn)
最坏空间复杂度 O(n)
function merge(left, right) {
let result = []
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
return result.concat(left, right)
}
function mergeSort(arr) {
if (arr.length <= 1) {
return arr
}
let middle = Math.floor(arr.length / 2)
let left = arr.slice(0, middle)
let right = arr.slice(middle)
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
let result = []
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
return result.concat(left, right)
}
function mergeSort(arr) {
let result = []
}
高频触发优化方式
,可用于对页面中一些高频触发的操作进行性能优化。function debounce(fn, wait = 0, immediate = false) {
let timer = null
return function() {
let args = arguments
let context = this
if (immediate && !timer) {
fn.apply(conext, args)
}
if (timer) clearTimeout(timer)
timer = setTimeout(() => {
fn.apply(context, args)
}, wait)
}
}
function throttle(fn, wait, immediate) {
let timer = null
let callNow = immediate
return function() {
let args = arguments
let context = this
if (callNow) {
fn.apply(context, args)
callNow = false
}
if (!timer) {
timer = setTimeout(() => {
fn.apply(context, args)
timer = null
}, wait)
}
}
}
实现一个 Queue 构造函数,包含 task 和 start 方法,可以使用 start(time, cb) 方法添加延时任务,使用 start 方法执行所有添加的方法。例如 Queue().task(1000, ()=>{ console.log(1000) }).task(2000, ()=>{ console.log(2000) }).start()
class Queue {
constructor() {
this.queue = []
}
task(time, cb) {
this.queue.push({
time,
cb
})
// 返回实例,就可以链式调用task来添加定时任务
return this
}
start() {
this._run(this._generator())
}
_generator() {
const _this = this
return function* gen() {
for (let i = 0; i < _this.queue.length; i++) {
const { time, cb } = _this.queue[i]
// 利用promise生成异步函数
yield new Promise((resolve, reject) => {
setTimeout(() => {
resolve(cb())
}, time)
})
}
}
}
_run(generator) {
const g = generator()
function next(data) {
let result = g.next(data)
if (result.done) return
// result 的 value 值就是 generator 函数体内的 promise 函数的返回值
result.value.then(function(data) {
next(data)
})
}
next()
}
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.