前端刷题用js还是java_用JavaScript刷LeetCode的正确姿势
韦桂超
原创
关注
0点赞·1164人阅读
虽然很多人都觉得前端算法弱，但其实 JavaScript 也可以刷题啊！最近两个月断断续续刷完了 leetcode 前 200 的 middle + hard ，总结了一些刷题常用的模板代码。走过路过发现 bug 请指出，拯救一个辣鸡(但很帅)的少年就靠您啦！
常用函数
包括打印函数和一些数学函数。
const _max =Math.max.bind(Math)
const _min=Math.min.bind(Math)
const _pow=Math.pow.bind(Math)
const _floor=Math.floor.bind(Math)
const _round=Math.round.bind(Math)
const _ceil=Math.ceil.bind(Math)
const log=console.log.bind(console)//const log = _ =>{}
log 在提交的代码中当然是用不到的，不过在调试时十分有用。但是当代码里面加了很多 log 的时候，提交时还需要一个个注释掉就相当麻烦了，只要将 log 赋值为空函数就可以了。
举一个简单的例子，下面的代码是可以直接提交的。
//计算 1+2+...+n//const log = console.log.bind(console)
const log = _ =>{}functionsumOneToN(n) {
let sum= 0for (let i = 1i <= ni++) {
sum+=i
log(`i=${i}: sum=${sum}`)
}returnsum
}
sumOneToN(10)
位运算的一些小技巧
判断一个整数 x 的奇偶性： x &1 = 1 (奇数) ， x &1 = 0 (偶数)
求一个浮点数 x 的整数部分： ~~x ，对于正数相当于 floor(x) 对于负数相当于 ceil(-x)
计算 2 ^ n ： 1 <<n 相当于 pow(2, n)
计算一个数 x 除以 2 的 n 倍： x >>n 相当于 ~~(x / pow(2, n))
判断一个数 x 是 2 的整数幂(即 x = 2 ^ n ): x &(x - 1) = 0
※注意※：上面的位运算只对32位带符号的整数有效，如果使用的话，一定要注意数！据！范！围！
记住这些技巧的作用：
提升运行速度 ❌
提升逼格 ✅
举一个实用的例子，快速幂(原理自行google)
//计算x^n n为整数
functionqPow(x, n) {
let result= 1while(n) {if (n &1) result *= x//同 if(n%2)
x = x *x
n>>= 1//同 n=floor(n/2)
}returnresult
}
链表
刚开始做 LeetCode 的题就遇到了很多链表的题。恶心心。最麻烦的不是写题，是调试啊！！于是总结了一些链表的辅助函数。
/**
* 链表节点
* @param {*} val
* @param {ListNode} next*/
function ListNode(val, next = null) {this.val =valthis.next =next
}/**
* 将一个数组转为链表
* @param {array} a
* @return {ListNode}*/const getListFromArray= (a) =>{
let dummy= newListNode()
let pre=dummy
a.forEach(x=>pre = pre.next = newListNode(x))returndummy.next
}/**
* 将一个链表转为数组
* @param {ListNode} node
* @return {array}*/const getArrayFromList= (node) =>{
let a=[]while(node) {
a.push(node.val)
node=node.next
}returna
}/**
* 打印一个链表
* @param {ListNode} node*/const logList= (node) =>{
let str= 'list: 'while(node) {
str+= node.val + '->'
node=node.next
}
str+= 'end'
log(str)
}
还有一个常用小技巧，每次写链表的操作，都要注意判断表头，如果创建一个空表头来进行操作会方便很多。
let dummy = newListNode()//返回
return dummy.next
使用起来超爽哒~举个例子。@leetcode 82。题意就是删除链表中连续相同值的节点。
/** @lc app=leetcode id=82 lang=javascript
*
* [82] Remove Duplicates from Sorted List II*/
/**
* @param {ListNode} head
* @return {ListNode}*/
var deleteDuplicates = function(head) {//空指针或者只有一个节点不需要处理
if (head === null || head.next === null) returnhead
let dummy= newListNode()
let oldLinkCurrent=head
let newLinkCurrent=dummywhile(oldLinkCurrent) {
let next=oldLinkCurrent.next//如果当前节点和下一个节点的值相同 就要一直向前直到出现不同的值
if (next &&oldLinkCurrent.val ===next.val) {while (next &&oldLinkCurrent.val ===next.val) {
next=next.next
}
oldLinkCurrent=next
}else{
newLinkCurrent= newLinkCurrent.next =oldLinkCurrent
oldLinkCurrent=oldLinkCurrent.next
}
}
newLinkCurrent.next= null//记得结尾置空~
logList(dummy.next)returndummy.next
}
deleteDuplicates(getListFromArray([1,2,3,3,4,4,5]))
deleteDuplicates(getListFromArray([1,1,2,2,3,3,4,4,5]))
deleteDuplicates(getListFromArray([1,1]))
deleteDuplicates(getListFromArray([1,2,2,3,3]))
本地运行结果
list: 1->2->5->end
list:5->end
list: end
list:1->end
是不是很方便！
矩阵(二维数组)
矩阵的题目也有很多，基本每一个需要用到二维数组的题，都涉及到初始化，求行数列数，遍历的代码。于是简单提取出来几个函数。
/**
* 初始化一个二维数组
* @param {number} r 行数
* @param {number} c 列数
* @param {*} init 初始值*/const initMatrix= (r, c, init = 0) =>new Array(r).fill().map(_ =>newArray(c).fill(init))/**
* 获取一个二维数组的行数和列数
* @param {any[][]} matrix
* @return [row, col]*/const getMatrixRowAndCol= (matrix) =>matrix.length === 0 ? [0, 0] : [matrix.length, matrix[0].length]/**
* 遍历一个二维数组
* @param {any[][]} matrix
* @param {Function} func*/const matrixFor= (matrix, func) =>{
matrix.forEach((row, i)=>{
row.forEach((item, j)=>{
func(item, i, j, row, matrix)
})
})
}/**
* 获取矩阵第index个元素 从0开始
* @param {any[][]} matrix
* @param {number} index*/
functiongetMatrix(matrix, index) {
let col= matrix[0].length
let i= ~~(index /col)
let j= index - i *colreturnmatrix[i][j]
}/**
* 设置矩阵第index个元素 从0开始
* @param {any[][]} matrix
* @param {number} index*/
functionsetMatrix(matrix, index, value) {
let col= matrix[0].length
let i= ~~(index /col)
let j= index - i *colreturn matrix[i][j] =value
}
找一个简单的矩阵的题示范一下用法。@leetcode 566。题意就是将一个矩阵重新排列为r行c列。
/** @lc app=leetcode id=566 lang=javascript
*
* [566] Reshape the Matrix*/
/**
* @param {number[][]} nums
* @param {number} r
* @param {number} c
* @return {number[][]}*/
var matrixReshape = function(nums, r, c) {//将一个矩阵重新排列为r行c列
//首先获取原来的行数和列数
let [r1, c1] =getMatrixRowAndCol(nums)
log(r1, c1)//不合法的话就返回原矩阵
if (!r1 || r1 * c1 !== r * c) returnnums//初始化新矩阵
let matrix =initMatrix(r, c)//遍历原矩阵生成新矩阵
matrixFor(nums, (val, i, j) =>{
let index= i * c1 + j//计算是第几个元素
log(index)
setMatrix(matrix, index, val)//在新矩阵的对应位置赋值
})returnmatrix
}
let x= matrixReshape([[1],[2],[3],[4]], 2, 2)
log(x)
二叉树
当我做到二叉树相关的题目，我发现，我错怪链表了，呜呜呜这个更恶心。
当然对于二叉树，只要你掌握先序遍历，后序遍历，中序遍历，层序遍历，递归以及非递归版，先序中序求二叉树，先序后序求二叉树，基本就能AC大部分二叉树的题目了(我瞎说的)。
二叉树的题目 input 一般都是层序遍历的数组，所以写了层序遍历数组和二叉树的转换，方便调试。
function TreeNode(val, left = null, right = null) {this.val =valthis.left =leftthis.right =right
}/**
* 通过一个层次遍历的数组生成一棵二叉树
* @param {any[]} array
* @return {TreeNode}*/
functiongetTreeFromLayerOrderArray(array) {
let n=array.lengthif (!n) return null
let index= 0
let root= new TreeNode(array[index++])
let queue=[root]while(index
let top=queue.shift()
let v= array[index++]
top.left= v == null ? null : newTreeNode(v)if (index
let v= array[index++]
top.right= v == null ? null : newTreeNode(v)
}if(top.left) queue.push(top.left)if(top.right) queue.push(top.right)
}returnroot
}/**
* 层序遍历一棵二叉树 生成一个数组
* @param {TreeNode} root
* @return {any[]}*/
functiongetLayerOrderArrayFromTree(root) {
let res=[]
let que=[root]while(que.length) {
let len=que.lengthfor (let i = 0i <leni++) {
let cur=que.shift()if(cur) {
res.push(cur.val)
que.push(cur.left, cur.right)
}else{
res.push(null)
}
}
}while (res.length >1 &&res[res.length - 1] == null) res.pop()//删掉结尾的 null
returnres
}
一个例子，@leetcode 110，判断一棵二叉树是不是平衡二叉树。
/**
* @param {TreeNode} root
* @return {boolean}*/
var isBalanced = function(root) {if (!root) return true//认为空指针也是平衡树吧
//获取一个二叉树的深度
const d = (root) =>{if (!root) return 0return _max(d(root.left), d(root.right)) + 1
}
let leftDepth=d(root.left)
let rightDepth=d(root.right)//深度差不超过 1 且子树都是平衡树
if (_min(leftDepth, rightDepth) + 1 >=_max(leftDepth, rightDepth)&&isBalanced(root.left) &&isBalanced(root.right)) return truereturn false
}
log(isBalanced(getTreeFromLayerOrderArray([3,9,20,null,null,15,7])))
log(isBalanced(getTreeFromLayerOrderArray([1,2,2,3,3,null,null,4,4])))
二分查找
参考 C++ STL 中的 lower_bound 和 upper_bound 。这两个函数真的很好用的！
/**
* 寻找>=target的最小下标
* @param {number[]} nums
* @param {number} target
* @return {number}*/
functionlower_bound(nums, target) {
let first= 0
let len=nums.lengthwhile (len >0) {
let half= len >>1
let middle= first +halfif (nums[middle]
first= middle + 1
len= len - half - 1
}else{
len=half
}
}returnfirst
}/**
* 寻找>target的最小下标
* @param {number[]} nums
* @param {number} target
* @return {number}*/
functionupper_bound(nums, target) {
let first= 0
let len=nums.lengthwhile (len >0) {
let half= len >>1
let middle= first +halfif (nums[middle] >target) {
len=half
}else{
first= middle + 1
len= len - half - 1
}
}returnfirst
}
照例，举个例子，@leetcode 34。题意是给一个排好序的数组和一个目标数字，求数组中等于目标数字的元素最小下标和最大下标。不存在就返回 -1。
/** @lc app=leetcode id=34 lang=javascript
*
* [34] Find First and Last Position of Element in Sorted Array*/
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}*/
var searchRange = function(nums, target) {
let lower=lower_bound(nums, target)
let upper=upper_bound(nums, target)
let size=nums.length//不存在返回 [-1, -1]
if (lower >= size || nums[lower] !== target) return [-1, -1]return [lower, upper - 1]
}
在 VS Code 中刷 LeetCode
前面说的那些模板，难道每一次打开新的一道题都要复制一遍么？当然不用啦。
首先配置代码片段 选择 Code ->Preferences ->User Snippets ，然后选择 JavaScript
然后把文件替换为下面的代码：
{"leetcode template": {"prefix": "@lc","body": ["const _max = Math.max.bind(Math)","const _min = Math.min.bind(Math)","const _pow = Math.pow.bind(Math)","const _floor = Math.floor.bind(Math)","const _round = Math.round.bind(Math)","const _ceil = Math.ceil.bind(Math)","const log = console.log.bind(console)","// const log = _ =>{}","/**************** 链表 ****************/","/**"," * 链表节点"," * @param {*} val"," * @param {ListNode} next"," */","function ListNode(val, next = null) {"," this.val = val"," this.next = next","}","/**"," * 将一个数组转为链表"," * @param {array} array"," * @return {ListNode}"," */","const getListFromArray = (array) =>{"," let dummy = new ListNode()"," let pre = dummy"," array.forEach(x =>pre = pre.next = new ListNode(x))"," return dummy.next","}","/**"," * 将一个链表转为数组"," * @param {ListNode} list"," * @return {array}"," */","const getArrayFromList = (list) =>{"," let a = []"," while (list) {"," a.push(list.val)"," list = list.next"," }"," return a","}","/**"," * 打印一个链表"," * @param {ListNode} list "," */","const logList = (list) =>{"," let str = 'list: '"," while (list) {"," str += list.val + '->'"," list = list.next"," }"," str += 'end'"," log(str)","}","/**************** 矩阵(二维数组) ****************/","/**"," * 初始化一个二维数组"," * @param {number} r 行数"," * @param {number} c 列数"," * @param {*} init 初始值"," */","const initMatrix = (r, c, init = 0) =>new Array(r).fill().map(_ =>new Array(c).fill(init))","/**"," * 获取一个二维数组的行数和列数"," * @param {any[][]} matrix"," * @return [row, col]"," */","const getMatrixRowAndCol = (matrix) =>matrix.length === 0 ? [0, 0] : [matrix.length, matrix[0].length]","/**"," * 遍历一个二维数组"," * @param {any[][]} matrix "," * @param {Function} func "," */","const matrixFor = (matrix, func) =>{"," matrix.forEach((row, i) =>{"," row.forEach((item, j) =>{"," func(item, i, j, row, matrix)"," })"," })","}","/**"," * 获取矩阵第index个元素 从0开始"," * @param {any[][]} matrix "," * @param {number} index "," */","function getMatrix(matrix, index) {"," let col = matrix[0].length"," let i = ~~(index / col)"," let j = index - i * col"," return matrix[i][j]","}","/**"," * 设置矩阵第index个元素 从0开始"," * @param {any[][]} matrix "," * @param {number} index "," */","function setMatrix(matrix, index, value) {"," let col = matrix[0].length"," let i = ~~(index / col)"," let j = index - i * col"," return matrix[i][j] = value","}","/**************** 二叉树 ****************/","/**"," * 二叉树节点"," * @param {*} val"," * @param {TreeNode} left"," * @param {TreeNode} right"," */","function TreeNode(val, left = null, right = null) {"," this.val = val"," this.left = left"," this.right = right","}","/**"," * 通过一个层次遍历的数组生成一棵二叉树"," * @param {any[]} array"," * @return {TreeNode}"," */","function getTreeFromLayerOrderArray(array) {"," let n = array.length"," if (!n) return null"," let index = 0"," let root = new TreeNode(array[index++])"," let queue = [root]"," while(index <n) {"," let top = queue.shift()"," let v = array[index++]"," top.left = v == null ? null : new TreeNode(v)"," if (index <n) {"," let v = array[index++]"," top.right = v == null ? null : new TreeNode(v)"," }"," if (top.left) queue.push(top.left)"," if (top.right) queue.push(top.right)"," }"," return root","}","/**"," * 层序遍历一棵二叉树 生成一个数组"," * @param {TreeNode} root "," * @return {any[]}"," */","function getLayerOrderArrayFromTree(root) {"," let res = []"," let que = [root]"," while (que.length) {"," let len = que.length"," for (let i = 0i <leni++) {"," let cur = que.shift()"," if (cur) {"," res.push(cur.val)"," que.push(cur.left, cur.right)"," } else {"," res.push(null)"," }"," }"," }"," while (res.length >1 &&res[res.length - 1] == null) res.pop()// 删掉结尾的 null"," return res","}","/**************** 二分查找 ****************/","/**"," * 寻找>=target的最小下标"," * @param {number[]} nums"," * @param {number} target"," * @return {number}"," */","function lower_bound(nums, target) {"," let first = 0"," let len = nums.length",""," while (len >0) {"," let half = len >>1"," let middle = first + half"," if (nums[middle] <target) {"," first = middle + 1"," len = len - half - 1"," } else {"," len = half"," }"," }"," return first","}","","/**"," * 寻找>target的最小下标"," * @param {number[]} nums"," * @param {number} target"," * @return {number}"," */","function upper_bound(nums, target) {"," let first = 0"," let len = nums.length",""," while (len >0) {"," let half = len >>1"," let middle = first + half"," if (nums[middle] >target) {"," len = half"," } else {"," first = middle + 1"," len = len - half - 1"," }"," }"," return first","}","$1"],"description": "LeetCode常用代码模板"}
}
1、将军视JS-AP131无线wifi摄像头通电，然后扫描盒子上面的二维码直接下载PP软件，通过手机号注册一个帐号就可以登录账号，登录进去后点击设备右上角的+号，点击智能联机。
2、按照操作提示进行安装，安装步骤完成后，等摄像头发出连接提示音后点击下一步。
3、完成上述步骤之后点击添加新设备按钮，输入WIFI账号和密码。
4、将手机声音调大，靠近设备，让手机跟无线摄像头能够更好的连接在一起，完成后点击下一步。
5、完成上述步骤后，手机跟无线摄像头开始连接，连接完成后输入摄像头的密码，即可完成军视JS-AP131无线wifi摄像头的安装工作。
131.用原生 JavaScript 的实现过什么功能吗？
参考答案：轮播图、手风琴、放大镜、3D动画效果等，切记，所答的一定要知道实现原理！，不知道还不如不说！
参与互动
132.javascript 代码中的"use strict"是什么意思 ? 使用它区别是什么？
参考答案：意思是使用严格模式，使用严格模式，一些不规范的语法将不再支持
参与互动
133.简述创建函数的几种方式
参考答案：
参与互动
134.window.location.search() 返回的是什么？
参考答案：查询(参数)部分。除了给动态语言赋值以外，我们同样可以给静态页面, 并使用 javascript 来获得相信应的参数值 返回值：?ver=1.0&id=timlq 也就是问号后面的！
参与互动
135.window.location.hash 返回的是什么？
参考答案：锚点 ， 返回值：#love ；
参与互动
136.window.location.reload() 作用？
参考答案：刷新当前页面
参与互动
137.为什么不能定义 1px 左右的 p 容器？
参考答案： IE6 下这个问题是因为默认的行高造成的，解决的方法也有很多，例如： overflow:hidden | zoom:0.08 | line-height:1px
参与互动
138.BOM 对象有哪些，列举 window 对象？
参考答案：
参与互动
139.简述 readonly 与 disabled 的区别
参考答案：
参与互动
140.为什么扩展 javascript 内置对象不是好的做法？
参考答案：
参与互动
141.什么是三元表达式？“三元”表示什么意思？
参考答案：三元如名字表示的三元运算符需要三个操作数。
语法是 条件 ? 结果1 : 结果2.这里你把条件写在问号(?)的前面后面跟着用冒号(:)分隔的结果1和结果2。满足条件时结果1否则结果2。
参与互动
142.我们给一个 dom 同时绑定两个点击事件，一个用捕获，一个用冒泡，你来说下会执行几次事件，然后会先执行冒泡还是捕获
参考答案：所有事件的顺序是：其他元素捕获阶段事件 ->本元素代码顺序事件 ->其他元素冒泡阶段事件 。
参考
参与互动
144.简述一下 Handlebars 的基本用法？
参考答案：没有用过的话说出它是干什么的即可
参与互动
143.简述一下 Handlerbars 的对模板的基本处理流程， 如何编译的？如何缓存的？
参考答案：
参与互动
145.前端 templating(Mustache, underscore, handlebars)是干嘛的, 怎么用?
参考答案：
参与互动
146.知道什么是 webkit 么? 知道怎么用浏览器的各种工具来调试和 debug 代码么?
参考答案：Webkit 是浏览器引擎，包括 html 渲染和 js 解析功能，手机浏览器的主流内核，与之相对应的引擎有 Gecko（Mozilla Firefox 等使用）和 Trident（也称 MSHTML，IE 使用）。 对于浏览器的调试工具要熟练使用，主要是页面结构分析，后台请求信息查看，js 调试工具使用，熟练使用这些工具可以快速提高解决问题的效率
参与互动
147.如何测试前端代码? 知道 BDD, TDD, Unit Test 么? 知道怎么测试你的前端工程么(mocha, sinon, jasmin, qUnit..)?
参考答案：了解 BDD 行为驱动开发与 TDD 测试驱动开发已经单元测试相关概念
参与互动
148.JavaScript 的循环语句有哪些？
参考答案：while for do while forEach
参与互动
149.作用域-编译期执行期以及全局局部作用域问题
参考答案：js 执行主要的两个阶段：预解析和执行期
参与互动
150.如何添加 html 元素的事件，有几种方法？请列举
参考答案：直接在标签里添加；在元素上添加、使用事件注册函数添加
参与互动
151.列举浏览器对象模型 BOM 里常用的至少 4 个对象，并列举 window 对象的常用方法至少 5 个
参考答案：
对象：Window document location screen history navigator
方法：Alert() confirm() prompt() open() close()
参与互动
152.事件绑定的方式
参考答案：
参与互动
153.事件循环
参考答案：事件循环是一个单线程循环，用于监视调用堆栈并检查是否有工作即将在任务队列中完成。如果调用堆栈为空并且任务队列中有回调函数，则将回调函数出队并推送到调用堆栈中执行。
参与互动
154.事件模型
参考答案：
解析：参考
参与互动
155.如何自定义事件
参考答案：
1.原生提供了 3 个方法实现自定义事件 2.createEvent，设置事件类型，是 html 事件还是 鼠标事件 3.initEvent 初始化事件，事件名称，是否允许冒泡，是否阻止自定义事件 4.dispatchEvent 触发事件
MDN
参与互动
156.target 和 currentTarget 区别
参考答案：
参与互动
157.prototype 和__proto__的关系是什么
参考答案：
所有的对象都拥有__proto__属性，它指向对象构造函数的 prototype 属性
所有的函数都同时拥有__proto__和 protytpe 属性 函数的__proto__指向自己的函数实现 函数的 protytpe 是一个对象 所以函数的 prototype 也有__proto__属性 指向 Object.prototype
Object.prototype.__proto__指向 null
参与互动
158.什么是原型属性？
参考答案：从构造函数的prototype属性出发找到原型，这时候就把原型称之为构造函数的原型属性
参与互动
159.什么是原型对象？
参考答案：从实例的__proto__出发，找到原型，这时候就把原型称之为实例的原型对象。
参与互动
160.使用 let、var 和 const 创建变量有什么区别
参考答案：
let 和 const 的区别在于：let 允许多次赋值，而 const 只允许一次。
