前端框架Web开发 移动 前端 Python Android Java

前端面试题全面整理

2020-11-19  本文已影响0人  宁_Yi

css相关

1. 万能居中

1.margin: 0 auto;水平
2.text-align: center;水平
3.行高，垂直
4.表格，center,middle；水平垂直
5.display:table-cell；模拟表格，all
6.绝对定位，50%减自身宽高
7.绝对定位，上下左右全0，margin:auto
8.绝对定位加相对定位。不需要知道宽高
9.IE6，IE7：给父元素设一个font-size:高度/1.14,vertical-align:middle

2. BFC优化

块格式化上下文, 特性:

3. 盒模型哪两种模式？什么区别？如何设置

4. 常用清除浮动的方法，如不清除浮动会怎样？

当父元素不给高度的时候，内部元素不浮动时会撑开, 而浮动的时候，父元素变成一条线, 造成塌陷.

5. 删格化的原理

比如antd的row和col, 将一行等分为24份, col是几就占几份, 底层按百分比实现; 结合媒体查询, 可以实现响应式

6. 纯css实现三角形

// 通过设置border
.box {            
  width:0px;            
  height:0px;            
  border-top:50px solid rgba(0,0,0,0);            
  border-right:50px solid  rgba(0,0,0,0);            
  border-bottom:50px solid green;            
  border-left:50px solid  rgba(0,0,0,0);            
}

7. 高度不定，宽100%，内一div高不确定，如何实现垂直居中？

8. 至少两种方式实现自适应搜索

9. 设置一段文字的大小为6px

10. css菊花图

四个小圆点一直旋转

// 父标签
animation: antRotate 1.2s infinite linear;
// 子标签
animation: antSpin 1s infinite linear;
@keyframe antSpin {  to {    opacity: 1   }}
@keyframe antRotate {  to {    transform: rotate(405)  }}
// animation-delay: 逐个延迟0.4s

11. 关于em

 <div style="font-size: 20px">
      123
      <div style="font-size: 2em;width: 2em">456</div>
 </div>
// 此时子元素的font-size为40px, 宽度为80px(还要乘以子元素font-size的系数)

12. 关于vh, vw

vw：viewpoint width，视窗宽度，1vw等于视窗宽度的1%。
vh：viewpoint height，视窗高度，1vh等于视窗高度的1%。
vmin：vw和vh中较小的那个。
vmax：vw和vh中较大的那个。

13. Flex布局

14. overflow原理

15. 实现自适应的正方形:

16. 标准模式和怪异模式

17. CSS3实现环形进度条

两个对半矩形遮罩, 使用rotate以及overflow: hidden进行旋转

18. css优先级

选择器的特殊性值表述为4个部分，用0,0,0,0表示。

JS相关

1. ES5和ES6继承方式区别

2. Generator了解

ES6 提供的一种异步编程解决方案, Generator 函数是一个状态机，封装了多个内部状态。

function* helloWorldGenerator() {
  yield 'hello';
  yield 'world';
  return 'ending';
}

var hw = helloWorldGenerator();

调用后返回指向内部状态的指针, 调用next()才会移向下一个状态, 参数:

hw.next()
// { value: 'hello', done: false }

hw.next()
// { value: 'world', done: false }

hw.next()
// { value: 'ending', done: true }

hw.next()
// { value: undefined, done: true }

3. 手写Promise实现

var myPromise = new Promise((resolve, reject) => {
  // 需要执行的代码
  ...
  if (/* 异步执行成功 */) {
    resolve(value)
  } else if (/* 异步执行失败 */) {
    reject(error)
  }
})

myPromise.then((value) => {
  // 成功后调用, 使用value值
}, (error) => {
  // 失败后调用, 获取错误信息error
})

4. Promise优缺点

function promise () {
  this.msg = '' // 存放value和error
  this.status = 'pending'
  var that = this
  var process = arguments[0]

  process (function () {
    that.status = 'fulfilled'
    that.msg = arguments[0]
  }, function () {
    that.status = 'rejected'
    that.msg = arguments[0]
  })
  return this
}

promise.prototype.then = function () {
  if (this.status === 'fulfilled') {
    arguments[0](this.msg)
  } else if (this.status === 'rejected' && arguments[1]) {
    arguments[1](this.msg)
  }
}

5. 观察者模式

又称发布-订阅模式, 举例子说明.
实现: 发布者管理订阅者队列, 并有新消息推送功能. 订阅者仅关注更新就行

6. 手写实现bind

Function.prototype.bind = function () {
   // 保存原函数
  var self = this
  // 取出第一个参数作为上下文, 相当于[].shift.call(arguments)
  var context = Array.prototype.shift.call(arguments)
  // 取剩余的参数作为arg; 因为arguments是伪数组, 所以要转化为数组才能使用数组方法
  var arg = Array.prototype.slice.call(arguments)
  // 返回一个新函数
  return function () {
    // 绑定上下文并传参
    self.apply(context, Array.prototype.concat.call(arg, Array.prototype.slice.call(arguments)))
  }
}

7. 手写实现4种继承

function Father () {}
function Child () {}
// 1. 原型继承
Child.prototype = new Father()
// 2. 构造继承
function Child (name) {
  Father.call(this, name)
}
// 3. 组合继承
function Child (name) {
  Father.call(this, name)
}
Child.prototype = new Father()
// 4. 寄生继承
function cloneObj (o) {
  var clone = object.create(o)
  clone.sayName = ...
  return clone
}
// 5. 寄生组合继承
// 6. ES6 class extend继承

8. css菊花图

四个小圆点一直旋转

// 父标签
animation: antRotate 1.2s infinite linear;
// 子标签
animation: antSpin 1s infinite linear;
@keyframe antSpin {
  to {
    opacity: 1 
  }
}
@keyframe antRotate {
  to {
    transform: rotate(405)
  }
}
// animation-delay: 逐个延迟0.4s

9. http状态码

10. Object.create实现（原型式继承，特点：实例的proto指向构造函数本身）

11. async和await：

12. 算法和数据结构：

13. 封装JSONP

image

jsonp

function jsonp ({url, param, callback}) {
  return new Promise((resolve, reject) => {
    var script = document.createElement('script')
    window.callback = function (data) {
      resolve(data)
      document.body.removeChild('script')
    }
    var param = {...param, callback}
    var arr = []
    for (let key in param) {
      arr.push(`${key}=${param[key]}`)
    }
    script.src = `${url}?${arr.join('&')}`
    document.body.appendChild(script)
  })
}

14. 手动实现map(forEach以及filter也类似)

// for循环实现
Array.prototype.myMap = function () {
  var arr = this
  var [fn, thisValue] = Array.prototype.slice.call(arguments)
  var result = []
  for (var i = 0; i < arr.length; i++) {
    result.push(fn.call(thisValue, arr[i], i, arr))
  }
  return result
}
var arr0 = [1, 2, 3]
console.log(arr0.myMap(v => v + 1))

// forEach实现(reduce类似)
Array.prototype.myMap = function (fn, thisValue) {
  var result = []
  this.forEach((v, i, arr) => {
    result.push(fn.call(thisValue, v, i, arr))
  })
  return result
}
var arr0 = [1, 2, 3]
console.log(arr0.myMap(v => v + 1))

15. js实现checkbox全选以及反选

<body>
    <button id="other">反选</button>
    <input type="checkbox" id="all" />全选
    <input type="checkbox" class="check" />1
    <input type="checkbox" class="check" />2
    <input type="checkbox" class="check" />3
    <script>
      var checkbox = document.getElementsByClassName('check')
      var checkAll = document.getElementById('all')
      var checkOther = document.getElementById('other')
      checkAll.onclick = function() {
        var flag = true
        for (var i = 0; i < checkbox.length; i++) {
          if (!checkbox[i].checked) flag = false
        }
        if (flag) {
          for (var i = 0; i < checkbox.length; i++) {
            checkbox[i].checked = false
          }
        } else {
          for (var i = 0; i < checkbox.length; i++) {
            checkbox[i].checked = true
          }
        }
      }
      checkOther.onclick = function() {
        for (var i = 0; i < checkbox.length; i++) {
          checkbox[i].checked = !checkbox[i].checked
        }
      }
    </script>
  </body>

16. 对原型链的理解？prototype上都有哪些属性

17. 为什么使用继承

通常在一般的项目里不需要,因为应用简单,但你要用纯js做一些复杂的工具或框架系统就要用到了,比如webgis、或者js框架如jquery、ext什么的,不然一个几千行代码的框架不用继承得写几万行,甚至还无法维护

18. setTimeout时间延迟为何不准

单线程, 先执行同步主线程, 再执行异步任务队列

19. 事件循环述，宏任务和微任务有什么区别？

20. let const var作用域

块级作用域, 暂时性死区

21. 节流和防抖

// 函数节流   滚动条滚动
var canRun = true;
document.getElementById("throttle").onscroll = function(){
    if(!canRun){
        // 判断是否已空闲，如果在执行中，则直接return
        return;
    }

    canRun = false;
    setTimeout(function(){
        console.log("函数节流");
        canRun = true;
    }, 300);
};

// 函数防抖
var timer = false;
document.getElementById("debounce").onscroll = function(){
    clearTimeout(timer); // 清除未执行的代码，重置回初始化状态

    timer = setTimeout(function(){
        console.log("函数防抖");
    }, 300);
};

22. 实现一个sleep函数

// 这种实现方式是利用一个伪死循环阻塞主线程。因为JS是单线程的。所以通过这种方式可以实现真正意义上的sleep()。
function sleep(delay) {
  var start = (new Date()).getTime();
  while ((new Date()).getTime() - start < delay) {
    continue;
  }
}

function test() {
  console.log('111');
  sleep(2000);
  console.log('222');
}

test()

23. 闭包

24. Immutable.js

Facebook出品, 倡导数据的不可变性, 用的最多就是List和Map.

25. js实现instanceof

// 检测l的原型链（__proto__）上是否有r.prototype，若有返回true，否则false
function myInstanceof (l, r) {
  var R = r.prototype
  while (l.__proto__) {
    if (l.__proto__ === R) return true
  }
  return false
}

27. ES6的模块引入和CommonJs区别

28. 严格模式

// 严格模式下, 隐式绑定丢失后this不会指向window, 而是指向undefined
      'use strict'
      var a = 2
      var obj = {
        a: 1,
        b: function() {
          // console.log(this.a)
          console.log(this)
        }
      }
      var c = obj.b
      c() // undefined

29. fetch, axios区别

30. typescript缺点

31. 构造函数实现原理

// 模拟构造函数实现
var Book = function(name) {
          this.name = name;
        };
 
        //正常用法
        var java = new Book(‘Master Java’);
        
        //使用代码模拟，在非IE浏览器中测试，IE浏览器不支持
        var python = {};
        python.__proto__ = Book.prototype;
        Book.call(python, 'Master Python');

32. for in 和 for of区别

33. JS实现并发控制:

使用消息队列以及setInterval或promise进行入队和出队

34. ajax和axios、fetch的区别

35. promise.finally实现

Promise.prototype.finally = function (callback) {
  let P = this.constructor;
  return this.then(
    value  => P.resolve(callback()).then(() => value),
    reason => P.resolve(callback()).then(() => { throw reason })
  );
};

浏览器网络相关

1. reflow(回流)和repaint(重绘)优化

image

render

2.一个页面从输入 URL 到页面加载显示完成，这个过程中都发生了什么？

3.localStorage 与 sessionStorage 与cookie的区别总结

4.浏览器如何阻止事件传播，阻止默认行为

5.虚拟DOM方案相对原生DOM操作有什么优点，实现上是什么原理？

虚拟DOM可提升性能, 无须整体重新渲染, 而是局部刷新.
JS对象, diff算法

6.浏览器事件机制中事件触发三个阶段

7.什么是跨域？为什么浏览器要使用同源策略？你有几种方式可以解决跨域问题？了解预检请求嘛？

8.了解浏览器缓存机制吗？

9.为什么操作 DOM 慢?

DOM本身是一个js对象, 操作这个对象本身不慢, 但是操作后触发了浏览器的行为, 如repaint和reflow等浏览器行为, 使其变慢

10.什么情况会阻塞渲染？

11.如何判断js运行在浏览器中还是node中？

判断有无全局对象global和window

12.关于web以及浏览器处理预加载有哪些思考？

图片等静态资源在使用之前就提前请求
资源使用到的时候能从缓存中加载, 提升用户体验
页面展示的依赖关系维护

13.http多路复用

14. http和https：

  1. https相对于http加入了ssl层, 加密传输, 身份认证;

  2. 需要到ca申请收费的证书;

  3. 安全但是耗时多，缓存不是很好;

  4. 注意兼容http和https;

  5. 连接方式不同, 端口号也不同, http是80, https是443

15. CSRF和XSS区别及防御

16. cookie可设置哪些属性？httponly?

chrome控制台的application下可查看:

image

cookie

17. 登录后，前端做了哪些工作，如何得知已登录

18. http状态码

19. # Http请求头缓存设置方法

Cache-control, expire, last-modify

20. 实现页面回退刷新

21. 正向代理和反向代理

22. 关于预检请求

在非简单请求且跨域的情况下，浏览器会自动发起options预检请求。

23. 三次握手四次挥手

24. TCP和UDP协议

25. 进程和线程的区别

vue相关

1. 生命周期

image

生命周期

2 .双向数据绑定v-model。这个最好也是自己实现一下 理解更深

通过v-model
VUE实现双向数据绑定的原理就是利用了 Object.defineProperty() 这个方法重新定义了对象获取属性值(get)和设置属性值(set)的操作来实现的。

// 依赖收集
// 简化版
var obj = { }
var name
//第一个参数：定义属性的对象。
//第二个参数：要定义或修改的属性的名称。
//第三个参数：将被定义或修改的属性描述符。
Object.defineProperty(obj, "data", {
  //获取值
  get: function () {
    return name
  },
  //设置值
  set: function (val) {
    name = val
    console.log(val)
  }
})
//赋值调用set
obj.data = 'aaa'
//取值调用get
console.log(obj.data)

// 详细版
 myVue.prototype._obverse = function (obj) { // obj = {number: 0}
    var value;
    for (key in obj) {  //遍历obj对象
      if (obj.hasOwnProperty(key)) {
        value = obj[key]; 
        if (typeof value === 'object') {  //如果值是对象，则递归处理
          this._obverse(value);
        }
        Object.defineProperty(this.$data, key, {  //关键
          enumerable: true,
          configurable: true,
          get: function () {
            console.log(`获取${value}`);
            return value;
          },
          set: function (newVal) {
            console.log(`更新${newVal}`);
            if (value !== newVal) {
              value = newVal;
            }
          }
        })
      }
    }
  }

3.vue父子组件传递参数

4.vue传递参数方法

// 1. 新建eventBus.js
import Vue from 'vue'
export default new Vue
// 或直接在main.js中初始化EventBus(全局)
Vue.prototype.$EventBus = new Vue()

// 2. 发射与接收
// 如果是定义在eventBus.js中
import eventBus from 'eventBus.js'
eventBus.$emit()
eventBus.$on()

// 如果是定义在main.js中
this.bus.$emit()
this.bus.$on()

// 3. 移除监听
eventBus.$off()

5.vue自定义组件

可以使用独立可复用的自定义组件来构成大型应用, 采用帕斯卡命名法或横线连接, 通过以上方式进行组件间通信. 每一个组件都是Vue实例, 可以使用生命周期钩子.

6. vue自定义指令

7.vuex组成和原理

8.vue-router的原理，例如hashhistory和History interface这些东西要弄明白。其实看一下源码就好了，看不懂可以直接看解析的相关技术博客。

9.vue的seo问题

seo关系到网站排名, vue搭建spa做前后端分离不好做seo, 可通过其他方法解决:

10.预渲染和ssr
以上

11.生命周期内create和mounted的区别

12.监听watch

对应一个对象，键是观察表达式，值是对应回调。值也可以是methods的方法名，或者是对象，包含选项。在实例化时为每个键调用 $watch()

13.登录验证拦截(通过router)

routes = [
    {
        name: 'detail',
        path: '/detail',
        meta: {
            requireAuth: true
        }
    },
    {
        name: 'login',
        path: '/login'
    }
]

router.beforeEach((from, to, next) => {
    if (to.meta.requireAuth) { // 判断跳转的路由是否需要登录
        if (store.state.token) { // vuex.state判断token是否存在
            next() // 已登录
        } else {
            next({
                path: '/login',
                query: {redirect: to.fullPath} // 将跳转的路由path作为参数，登录成功后跳转到该路由
            })
        }
    } else {
       next()
    }
})

14. v-for key值

不写key值会报warning, 和react的array渲染类似. 根据diff算法, 修改数组后, 写key值会复用, 不写会重新生成, 造成性能浪费或某些不必要的错误

15. vue3.0的更新和defineProperty优化

15. vue使用this获取变量

正常要通过vm.[图片上传失败...(image-bd2cdd-1605778364068)]

root传参取值

16. jQuery的优缺点，与vue的不同，vue的优缺点？

17. vue解除双向绑定

let obj = JSON.parse(JSON.stringify(this.temp1));

18. vue异步组件

为了简化，Vue 允许你以一个工厂函数的方式定义你的组件，这个工厂函数会异步解析你的组件定义。Vue 只有在这个组件需要被渲染的时候才会触发该工厂函数，且会把结果缓存起来供未来重渲染

Vue.component(
  'async-webpack-example',
  // 这个 `import` 函数会返回一个 `Promise` 对象。
  () => import('./my-async-component')
)

19. MVC与MVVM

20. vue渐进式

小到可以只使用核心功能，比如单文件组件作为一部分嵌入；大到使用整个工程，vue init webpack my-project来构建项目；VUE的核心库及其生态系统也可以满足你的各式需求（core+vuex+vue-route）

react相关

1. 新旧生命周期

2. react核心

3. fiber核心(react 16)

4. 渲染一个react

5. 高阶组件

高阶组件就是一个函数，且该函数(wrapper)接受一个组件作为参数，并返回一个新的组件。
高阶组件并不关心数据使用的方式和原因，而被包裹的组件也不关心数据来自何处.

6. hook(v16.7测试)

在无状态组件(如函数式组件)中也能操作state以及其他react特性, 通过useState

7. redux和vuex以及dva：

8. react和vue的区别

9. react单向数据流怎么理解

React是单向数据流，数据主要从父节点传递到子节点（通过props）。如果顶层（父级）的某个props改变了，React会重渲染所有的子节点。

10. React算法复杂度优化

react树对比是按照层级去对比的， 他会给树编号0,1,2,3,4.... 然后相同的编号进行比较。所以复杂度是n，这个好理解。

关键是传统diff的复杂度是怎么算的？传统的diff需要出了上面的比较之外，还需要跨级比较。他会将两个树的节点，两两比较，这就有n2的复杂度了。然后还需要编辑树，编辑的树可能发生在任何节点，需要对树进行再一次遍历操作，因此复杂度为n。加起来就是n3了。

11. React优点

声明式, 组件化, 一次学习, 随处编写. 灵活, 丰富, 轻巧, 高效

移动端相关

1. 移动端兼容适配

2. flexible如何实现自动判断dpr

判断机型, 找出样本机型去适配. 比如iphone以6为样本, 宽度375px, dpr是2

3. 为什么以iPhone6为标准的设计稿的尺寸是以750px宽度来设计的呢？

iPhone6的满屏宽度是375px，而iPhone6采用的视网膜屏的物理像素是满屏宽度的2倍，也就是dpr(设备像素比)为2, 并且设计师所用的PS设计软件分辨率和像素关系是1:1。所以为了做出的清晰的页面，设计师一般给出750px的设计图，我们再根据需求对元素的尺寸设计和压缩。

4. 如何处理异形屏iphone X

5. 移动端首屏优化

6. PWA全称Progressive Web App，即渐进式WEB应用

一个 PWA 应用首先是一个网页, 可以通过 Web 技术编写出一个网页应用. 随后添加上 App Manifest 和 Service Worker 来实现 PWA 的安装和离线等功能
解决了哪些问题？

7. 离线包方案

现在 web 页面在移动端的地位越来越高，大部分主流 App 采用 native + webview 的 hybrid 模式，加载远程页面受限于网络，本地 webview 引擎，经常会出现渲染慢导致的白屏现象，体验很差，于是离线包方案应运而生。动态下载的离线包可以使得我们不需要走完整的 App 审核发布流程就完成了版本的更新

8. 自适应和响应式布局的区别

  1. 自适应布局通过检测视口分辨率，来判断当前访问的设备是：pc端、平板、手机，从而请求服务层，返回不同的页面；响应式布局通过检测视口分辨率，针对不同客户端在客户端做代码处理，来展现不同的布局和内容。

  2. 自适应布局需要开发多套界面，而响应式布局只需要开发一套界面就可以了。

  3. 自适应对页面做的屏幕适配是在一定范围：比如pc端一般要大于1024像素，手机端要小于768像素。而响应式布局是一套页面全部适应。

  4. 自适应布局如果屏幕太小会发生内容过于拥挤。而响应式布局正是为了解决这个问题而衍生出的概念，它可以自动识别屏幕宽度并做出相应调整的网页设计。

插件及工具相关

1. babel和polyfill

2. jpg, jpeg和png区别

3. git rebase和merge区别

image

git rebase

image

git merge

前端性能优化

  1. 减少HTTP请求（合并css、js，雪碧图/base64图片）

  2. 压缩（css、js、图片皆可压缩,使用webpack uglify和 svg）

  3. 样式表放头部，脚本放底部

  4. 使用CDN（这部分，不少前端都不用考虑，负责发布的兄弟可能会负责搞好）

  5. http缓存

  6. bosify图片压缩: 根据具体情况修改图片后缀或格式 后端根据格式来判断存储原图还是缩略图

  7. 懒加载, 预加载

  8. 替代方案: 骨架屏, SSR

  9. webpack优化

原生通信

1.JSBridge通信原理, 有哪几种实现的方式？

JsBridge给JavaScript提供了调用Native功能，Native也能够操控JavaScript。这样前端部分就可以方便使用地理位置、摄像头以及登录支付等Native能力啦。JSBridge构建 Native和非Native间消息通信的通道，而且是 双向通信的通道。

2.实现一个简单的 JSBridge，设计思路？

算法相关

1. 二分查找和冒泡排序

2. 快速排序

function quickSort (arr) {
  if (arr.length < 2) return arr
  var middle = Math.floor(arr.length / 2)
  var flag = arr.splice(middle, 1)[0]
  var left = [],
        right = []
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < flag) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([flag], quickSort(right))

3. 最长公共子串

function findSubStr(str1, str2) {
        if (str1.length > str2.length) {
          [str1, str2] = [str2, str1]
        }
        var result = ''
        var len = str1.length
        for (var j = len; j > 0; j--) {
          for (var i = 0; i < len - j; i++) {
            result = str1.substr(i, j)
            if (str2.includes(result)) return result
          }
        }
      }
      console.log(findSubStr('aabbcc11', 'ppooiiuubcc123'))

4. 最长公共子序列(LCS动态规划)

另一篇

// dp[i][j] 计算去最大长度，记住口诀：相等左上角加一，不等取上或左最大值
function LCS(str1, str2){
        var rows =  str1.split("")
        rows.unshift("")
        var cols =  str2.split("")
        cols.unshift("")
        var m = rows.length
        var n = cols.length
        var dp = []
        for(var i = 0; i < m; i++){ 
            dp[i] = []
            for(var j = 0; j < n; j++){ 
                if(i === 0 || j === 0){
                    dp[i][j] = 0
                    continue
                }
              
                if(rows[i] === cols[j]){ 
                    dp[i][j] = dp[i-1][j-1] + 1 //对角＋1
                }else{
                    dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) //对左边，上边取最大
                }
            }
            console.log(dp[i].join(""))//调试
        } 
        return dp[i-1][j-1]
    }
//!!!如果它来自左上角加一，则是子序列，否则向左或上回退。
//findValue过程，其实就是和 就是把T[i][j]的计算反过来。
// 求最长子序列
function findValue(input1,input2,n1,n2,T){
    var i = n1-1,j=n2-1;
    var result = [];//结果保存在数组中
    console.log(i);
    console.log(j);
    while(i>0 && j>0){
        if(input1[i] == input2[j]){
            result.unshift(input1[i]);
            i--;
            j--;
        }else{
            //向左或向上回退
            if(T[i-1][j]>T[i][j-1]){
                //向上回退
                i--;
            }else{
                //向左回退
                j--;
            }
        }

    }

    console.log(result);
}

5. 数组去重，多种方法

6. 实现一个函数功能：sum(1,2,3,4..n)转化为 sum(1)(2)(3)(4)…(n)

// 使用柯里化 + 递归
function curry ( fn ) {
  var c = (...arg) => (fn.length === arg.length) ? 
          fn (...arg) : (...arg1) => c(...arg, ...arg1)
  return c
}

7. 反转二叉树

var invertTree = function (root) {
  if (root !== null) {
    [root.left, root.right] = [root.right, root.left]
    invertTree(root.left)
    invertTree(root.right)
  }
  return root
}

8. 贪心算法解决背包问题

var items = ['A','B','C','D']
var values = [50,220,60,60]
var weights = [5,20,10,12]
var capacity = 32 //背包容积

greedy(values, weights, capacity) // 320

function greedy(values, weights, capacity) {
        var result = 0
        var rest = capacity
        var sortArray = []
        var num = 0
        values.forEach((v, i) => {
          sortArray.push({
            value: v,
            weight: weights[i],
            ratio: v / weights[i]
          })
        })
        sortArray.sort((a, b) => b.ratio - a.ratio)
        sortArray.forEach((v, i) => {
          num = parseInt(rest / v.weight)
          rest -= num * v.weight
          result += num * v.value
        })
        return result
      }

9. 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

function FindNumbersWithSum(array, sum)
{
    var index = 0
    for (var i = 0; i < array.length - 1 && array[i] < sum / 2; i++) {
        for (var j = i + 1; j < array.length; j++) {
            if (array[i] + array[j] === sum) return [array[i], array[j]]
        }
        //index = array.indexOf(sum - array[i], i + 1)
       // if (index !== -1) {
       //     return [array[i], array[index]]
        //}
    }
    return []

10. 二叉树各种(层序)遍历

深度广度遍历

// 根据前序和中序重建二叉树
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    var result = null
    if (pre.length === 1) {
        result = {
            val: pre[0],
            left: null,
            right: null
        }
    } else if (pre.length > 1) {
        var root = pre[0]
        var vinRootIndex = vin.indexOf(root)
        var vinLeft = vin.slice(0, vinRootIndex)
        var vinRight = vin.slice(vinRootIndex + 1, vin.length)
        pre.shift()
        var preLeft = pre.slice(0, vinLeft.length)
        var preRight = pre.slice(vinLeft.length, pre.length)
        result = {
            val: root,
            left: reConstructBinaryTree(preLeft, vinLeft),
            right: reConstructBinaryTree(preRight, vinRight)
        }
    }
    return result
}

// 递归
// 前序遍历
function prevTraverse (node) {
  if (node === null) return;

  console.log(node.data);
  prevTraverse(node.left);
  prevTraverse(node.right);
}

// 中序遍历
function middleTraverse (node) {
  if (node === null) return;

  middleTraverse(node.left);
  console.log(node.data);
  middleTraverse(node.right);
}

// 后序遍历
function lastTraverse (node) {
  if (node === null) return;

  lastTraverse(node.left);
  lastTraverse(node.right);
  console.log(node.data);
}

// 非递归
// 前序遍历
function preTraverse(tree) {
        var arr = [],
          node = null
        arr.unshift(tree)
        while (arr.length) {
          node = arr.shift()
          console.log(node.root)
          if (node.right) arr.unshift(node.right)
          if (node.left) arr.unshift(node.left)
        }
      }

// 中序遍历
function middleTraverseUnRecursion (root) {
  let arr = [],
      node = root;

  while (arr.length !== 0 || node !== null) {
    if (node === null) {
      node = arr.shift();
      console.log(node.data);
      node = node.right;
    } else {
      arr.unshift(node);
      node = node.left;
    }
  }

}

// 广度优先-层序遍历
// 递归
var result = []
var stack = [tree]
var count = 0
var bfs = function () {
  var node = stack[count]
  if (node) {
    result.push(node.value)
    if (node.left) stack.push(node.left)
    if (node.right) stack.push(node.right)
    count++
    bfs()
  }
}
bfs()
console.log(result)
// 非递归
function bfs (node) {
  var result = []
  var queue = []
  queue.push(node)
  while (queue.length) {
    node = queue.shift()
    result.push(node.value)
    node.left && queue.push(node.left)
    node.right && queue.push(node.right)
  }
  return result
}

11. 各种排序

// 插入排序
function insertSort(arr) {
        var temp
        for (var i = 1; i < arr.length; i++) {
          temp = arr[i]
          for (var j = i; j > 0 && temp < arr[j - 1]; j--) {
            arr[j] = arr[j - 1]
          }
          arr[j] = temp
        }
        return arr
      }
      console.log(insertSort([3, 1, 8, 2, 5]))

// 归并排序
function mergeSort(array) {
        var result = array.slice(0)
        function sort(array) {
          var length = array.length
          var mid = Math.floor(length * 0.5)
          var left = array.slice(0, mid)
          var right = array.slice(mid, length)
          if (length === 1) return array
          return merge(sort(left), sort(right))
        }
        function merge(left, right) {
          var result = []

          while (left.length || right.length) {
            if (left.length && right.length) {
              if (left[0] < right[0]) {
                result.push(left.shift())
              } else {
                result.push(right.shift())
              }
            } else if (left.length) {
              result.push(left.shift())
            } else {
              result.push(right.shift())
            }
          }
          return result
        }
        return sort(result)
      }
      console.log(mergeSort([5, 2, 8, 3, 6]))

// 二分插入排序
function twoSort(array) {
        var len = array.length,
          i,
          j,
          tmp,
          low,
          high,
          mid,
          result
        result = array.slice(0)
        for (i = 1; i < len; i++) {
          tmp = result[i]
          low = 0
          high = i - 1
          while (low <= high) {
            mid = parseInt((high + low) / 2, 10)
            if (tmp < result[mid]) {
              high = mid - 1
            } else {
              low = mid + 1
            }
          }
          for (j = i - 1; j >= high + 1; j--) {
            result[j + 1] = result[j]
          }
          result[j + 1] = tmp
        }
        return result
      }
      console.log(twoSort([4, 1, 7, 2, 5]))

12. 使用尾递归对斐波那契优化

递归非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生“栈溢出”错误（stack overflow）。但对于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误。

// 传统递归斐波那契, 会造成超时或溢出
function Fibonacci (n) {
  if ( n <= 1 ) {return 1};

  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10) // 89
Fibonacci(100) // 超时
Fibonacci(500) // 超时

// 使用尾递归优化, 可规避风险
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};

  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity

13. 两个升序数组合并为一个升序数组

function sort (A, B) {
  var i = 0, j = 0, p = 0, m = A.length, n = B.length, C = []
  while (i < m || j < n) {
    if (i < m && j < n) {
      C[p++] = A[i] < B[j] ? A[i++] : B[j++]
    } else if (i < m) {
      C[p++] = A[i++]
    } else {
      C[p++] = B[j++]
    }
  }
  return C
}

node相关

1. node的router是什么

2. 数据库索引是啥

3. 浏览器的事件循环和node事件循环有什么区别？

上一篇 下一篇

猜你喜欢

热点阅读