前端刷题用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常用代码模板"}
}
可以。力扣针对扣友作为企业的重要技术成员，满足日常工作中的人员管理、能力测评、远程面试等一系列需求，创建一场随到随测测评，你可以自由组卷，编辑题目，并邀请企业内外部成员加入这场测评，力扣将记录形成绩档案并帮助你进行能力排名与分析。面试功能将帮助您进行高效的远程面试，支持音视频通话，代码协同与编辑、追踪模式，最后会生成一份力扣专属的面试报告供您进行分析与决策。升级为企业版后，你可以在通过力扣组建内部的竞赛，支持自由组卷、多人竞赛、系统自动判卷和排名。
题目描述
给你一个大小为 m x n 的二进制矩阵 grid，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1：
示例 2：
提示：
根据飞地的定义，如果从一个陆地单元格出发无法移动到网格边界，则这个陆地单元格是飞地。因此可以将所有陆地单元格分成两类：第一类陆地单元格和网格边界相连，这些陆地单元格不是飞地；第二类陆地单元格不和网格边界相连，这些陆地单元格是飞地。
我们可以从网格边界上的每个陆地单元格开始深度优先搜索，遍历完边界之后，所有和网格边界相连的陆地单元格就都被访问过了。然后遍历整个网格，如果网格中的一个陆地单元格没有被访问过，则该陆地单元格不和网格的边界相连，是飞地。
代码实现时，由于网格边界上的单元格一定不是飞地，因此遍历网格统计飞地的数量时只需要遍历不在网格边界上的单元格。
代码
Java
C#
C++
C
Python3
Golang
JavaScript
复杂度分析
也可以通过广度优先搜索判断每个陆地单元格是否和网格边界相连。
首先从网格边界上的每个陆地单元格开始广度优先搜索，访问所有和网格边界相连的陆地单元格，然后遍历整个网格，统计飞地的数量。
代码
Java
C#
C++
C
Python3
Golang
JavaScript
复杂度分析
除了深度优先搜索和广度优先搜索的方法以外，也可以使用并查集判断每个陆地单元格是否和网格边界相连。
并查集的核心思想是计算网格中的每个陆地单元格所在的连通分量。对于网格边界上的每个陆地单元格，其所在的连通分量中的所有陆地单元格都不是飞地。如果一个陆地单元格所在的连通分量不同于任何一个网格边界上的陆地单元格所在的连通分量，则该陆地单元格是飞地。
并查集的做法是，遍历整个网格，对于网格中的每个陆地单元格，将其与所有相邻的陆地单元格做合并操作。由于需要判断每个陆地单元格所在的连通分量是否和网格边界相连，因此并查集还需要记录每个单元格是否和网格边界相连的信息，在合并操作时更新该信息。
在遍历网格完成并查集的合并操作之后，再次遍历整个网格，通过并查集中的信息判断每个陆地单元格是否和网格边界相连，统计飞地的数量。
代码
Java
C#
C++
C
Python3
Golang
JavaScript
复杂度分析
BY /
本文作者：力扣
