最近几天做的js笔试题，整理了一下，虽然前端通常不会涉及到太复杂的算法，但是在做题的过程中算法思路还是非常重要的，cc觉得刷题主要是锻炼个人的思维能力~ 不是只在乎数量
一、钉钉前端笔试题目
1. 实现模板函数 render(template,data)
要求实现HTML的模板内置函数，示例如下：
let template = ‘我是，年龄，性别’; let data = { name:‘姓名’, age: 18}
Output：我是姓名，年龄18，性别undefined
考察点：String,正则式匹配
思路：实际上，使用正则匹配模板中的内容，并代替data中的内容十分简单
Tips: 1) String对象的一些方法只会返回新对象，如replace(),slice(),toUpperCase()等，都不是在原数组上进行修改的2)模板中可能出现空格3)不可以从data出发考虑，因为data的某些属性并不存在，如示例中的sex
var render = function(template, data){
var tempStr = template.replace(/\s+/g,'')
var resStr = tempStr.replace(/\{\{([\s\S]+?)\}\}/g,function($key, $value){
return data[$value]
})
return resStr
}
2. 比较版本号的大小 compareVersion(version1, version2)
要求：实现一个方法，用于比较两个版本号（类似1.0.1 / 1.2.0 / 1.2 / 0.1）
如果version1 > version2，返回1；如果version1 < version2，返回-1，其他情况返回0
版本号规则x.y.z，x、y、z均为大于等于0的整数，至少有x位
思路： 1）先比较前两位 ，再比较后一位 2）将版本号split成为一个数组对象，之后设置优先级比较，cc最初设置的优先级利用数值，相邻两位的优先级比例100：1，但这样会出现bug，造成1.2.101 > 1.3.0，所以推荐第一种方法
var compareVersion = function(version1,version2){
var v1Pre = parseFloat(version1)
var v2Pre = parseFloat(version2)
if(v1Pre > v2Pre) return 1
if(v1Pre < v2Pre) return -1
//前两位版本号相同，比较最后一位
var v1Next = version1.replace(v1pre+'.','')
var v2Next = version2.replace(v2pre+'.','')
if(v1Next > v2Next) return 1
if(v1Next < v2Next) return -1
return 0
}
下面是cc自己想的设置权重优先级的数值判大小的方法（版本号很大的情况不适用）
var valueOfVersion = function(version){
verArr = version.split('.')
var value = 0
var weight = 10000
for(var item in verArr){
value += weight * verArr[item]
weight /= 100
}
return value
}
var compareVersion = function(version1, version2){
var v1 = valueOfVersion(version1)
var v2 = valueOfVersion(version2)
if(v1 < v2){
return -1
}
return v1>v2?1:0
}
3. 实现随机字符串生成函数 randomStr()
要求如下：
生成的随机的字符串应该以字母开头，并包含 [a-z][0-9] 这些字符。
生成的字符串长度为 8。
生成的字符串不能够在程序运行的生命周期中存在重复的情形。
思路: 从字符池中选择，设置生成随机的索引，生成重复字符串的几率很小p = 1/(26*36^7)
var randomStr = function(len = 8){
var resStr = ''
var letterList = 'abcdefghijklmnopqrstuvwxyz'
var strList = '0123456789abcdefghijklmnopqrstuvwxyz'
var firstIndex = Math.floor(Math.random()*26)
resStr += letterList[firstIndex]
while(len-- > 1){
var index = Math.floor(Math.random()*36)
resStr += strList[index]
}
return resStr
}
二、LeetCode题目
1. Leetcode 26：删除排序数组的重复项
关于JS中的数组去重，有很多方法，在排序数组中，重复的元素必然是相邻的
1.1 不考虑额外空间的情况
- 利用indexOf() === -1，将不重复的元素放入新数组中
var removeDuplicates = function(nums){
var newArr = []
nums.map(function(item){
if(newArr.indexOf(item) == -1)
newArr.push(item)
})
return newArr
}
- 利用元素的indexOf()值与自身的index相同，筛选非重复项
（如果是重复元素，indexOf的返回值是前面出现过的重复值，不是它本身）
var removeDuplicates = function(nums){
var newArr = []
for(var i in nums){
if(nums.indexOf(nums[i]) === i)
newArr.push(nums[i])
}
return newArr
}
- 不用indexOf，比较当前元素与newArr的尾元素（因为是有序数组，如果当前遍历项是重复项，那么必然和新数组的最后一项相同，不同才放入新数组）
var removeDuplicates = function(nums){
var newArr = []
nums.map(function(item){
if(item !== newArr[-1])
newArr.push(item)
})
return newArr
}
1.2 如果规定不能申请额外空间，那么我们只能在本数组上进行移动，和删除,空间复杂度O(1)
- 利用重复的元素必然相邻，把重复元素的前一个删除，这种做法数组的长度也发生了变化
var removeDuplicates = function(nums){
for(var i = 0; i < nums.length - 1; i++){
if(nums[i] === nums[i+1]){
nums.splice(i, 1)
i --
}
}
}
- 双指针,i利用索引记录需要改变的位置，j记录后一位，不相等就重新赋值新数组，指针i与j会因为重复元素的出现渐行渐远，这种做法数组的长度不变，只保证了新数组前面不重复元素的顺序，不关注后面的元素
var removeDuplicates = function(nums){
if(nums.length === 0)
return 0
var i = 0
for(var j = 1; j < nums.length; j++){
if(nums[i] != nums[j]){
nums[++i] = nums[j]
}
}
return i+1
}
2. Leetcode 125： 判断回文字符串（忽略其他所有非数字和非字母的字符，忽略大小写差异）
思路：使用正则匹配式，找出字母数字的元素，验证字符串与自身反转之后的串的值是否相同
var isPalindrome = function(s){
var reg = /[a-zA-Z0-9]/g
var t = s.match(reg).join('').toLowerCase()
var s = t.split('').reverse().join()
return t===s
}
3. 剑指Offer面试题 10.01：合并排序的数组
思路: 将两个数组的前面部分都拿出来，拼在一起再进行排序
var mergeSortedArray = function(arr1, m, arr2, n){
A = A.slice(0,m)
B = B.slice(0,n)
return A.concat(B).sort()
}
4. 剑指Offer面试题 45：把数组排成最小数
思路：对数组中的元素按照一定的规则排序，排序规则不是传统上数值意义的大小，而是若mn < nm 则认为m < n，为了防止数值拼接造成的大数范围溢出问题，在做比较的时候使用字符串作比较
var minNumver = function(nums){
var arrs = nums.sort(compareNum)
return arrs.join('')
}
// 利用字符串拼接比较两个数据的排序优先级
var compareNum = function(num1, num2){
var str1 = num1.toString() + num2.toString()
var str2 = num2.toString() + num1.toString()
if(str1 < str2){
return -1
}
return 1
}
5. Leetcode 994: 烂橘子问题
思路：第一遍遍历，记录好橘子的个数和坏橘子的坐标（用栈的形式）
第二次遍历，模拟腐烂传递的过程（在好橘子个数大于0且烂橘子坐标栈非空的时候，依次从烂橘子栈中弹出，传染周围的好橘子，更新新变坏的橘子的坐标栈，作为下一次循环的坏橘子栈，minutes ++ ）
var orangesRotting = function(grid){
var minutues = 0
var freshCount = 0
let badQue = []
// 统计好橘子的数目和坏橘子的坐标
for(var i = 0; i < grid.length; i++){
for(var j = 0; j < grid[0].length; j++){
if(grid[i][j] === 1)
freshCount ++;
else if(grid[i][j] === 2)
badQue.push([i,j])
}
}
// 腐烂蔓延的过程
while(badQue.length && newFresh){
let newBadQue = []
while(badQue.length){
let badOrange = badQue.shift()
let rottedOrange = oneRotting(newBadQue,badOrange[0],badOrange[1],grid)
freshOrange -= rottedOrange
}
mintues ++
badQue = newBadQue
}
if(newFresh === 0)
return mintues
return -1
}
// 一个坐标（i,j）的坏橘子的腐烂传染过程，rottingQue为被它感染的好橘子栈
// 函数返回新感染的橘子数目
var oneRotting = function(rottingQue,i,j,grid){
var rottedCount = 0
if(i - 1 > 0 && grid[i-1][j] === 1){
rottingQue.push([i-1,j])
rottedCount ++
grid[i-1][j] = 2
}
if(i + 1< grid.length && grid[i+1][j] === 1){
rottingQue.push([i+1,j])
rottedCount ++
grid[i+1][j] = 2
}
if(j - 1 > 0 && grid[i][j-1] === 1){
rottingQue.push([i,j-1])
rottedCount ++
grid[i][j-1] = 2
}
if(j + 1 < grid[i].length && grid[i][j+1] === 1){
rottingQue.push([i,j+1])
rottedCount ++
grid[i][j+1] = 2
}
return rottedCount
}
6. Leetcode 1103：分糖果
思路：记录剩余的糖果数目和实际应该发的糖果数，发放的坐标根据当前手中的糖果数目决定
var distributeCandies = function(candies, num_people){
var candiesList = new Array(num_people)
candiesList.fill(0, 0, num_people)
if(candies === 0){
return candiesList
}
// 初始化剩余的糖果和当前发放的糖果
var leftCandies = candies
var disCandies = 1
while(leftCandies > 0){
var index = disCandies % num_people !== 0? disCandies%num_people - 1 : num_people-1
if(leftCandies >= disCandies){
candiesList[index] += disCandies
leftCandies -= disCandies
disCandies ++
} else { // 糖果不足，全部给当前小盆友
candiesList[index] += leftCandies
leftCandies = 0
}
}
return candiesList
}
7. 剑指Offer面试题 57-Ⅱ：和为s的连续正数序列
思路一：使用滑动窗口的方法，记录坐标在【left, right】窗口范围内的数据，比较窗口内数据和sum与target的关系决定窗口的范围：
1）sum < target，右边界向右滑一格 → 【left, right+1】
2）sum > target，左边界向右滑一格 → 【left+1, right】
3）sum = target，当前窗口【】符合要求，继续右滑寻找下一窗口
滑动条件：窗口最右边界right小于 target/2+1
var findContinuousSequence = function(target){
let res = []
if(target < 3) return res
// 初始化窗口[1,2]以及窗口内数据和sum
let left = 1
let right = 2
let sum = left + right
while(right < target/2 + 1){
if(sum < target){
right++
sum += right
}else if(sum > target){
sum -= left
left ++
}else{
res.push(numWindow(left,right))
right ++
sum += right
}
}
return res
}
// 滑动窗口的内容
var numWindow = function(left, right){
let res = []
for(var i = left; i <= right; i++)
res.push(i)
return res
}
思路二：使用暴力法，寻找连续的数列
var findContinuousSequence = function(target){
let res = []
// ES6定义内部函数，寻找以cur开始的、和为value的连续序列
const findArr = ((cur, value)=>{
let arr = []
while(value > 0){
if(curr < value){
arr.push(cur)
value -= cur
cur ++
}else{
return;
}
}
return arr
})
// 暴力寻找数组
for(let i = 1; i < target/2; i++){
let resArr = findArr(i, target)
if(resArr)
res.push(resArr)
}
return res
}
三、阿里CBU在线笔试题
1. 换硬币函数coinChange(coins, amount):
说明：给定不同面额的硬币 coins 和一个总金额 amount，
- 编写一个函数来计算可以凑成总金额所需的最少的硬币个数，
- 如果没有任何一种硬币组合能组成总金额，返回 -1，
- 你可以认为每种硬币的数量是无限的。
- 示例： coinsChange([1,2,5], 11); //3 coinChange([2, 4], 3); // -1
思路一： 完全背包问题，cc使用的是经典的动态规划法,记录在0-amount内，每种金额所需要的最少的硬币数目。其中，状态转移方程如下：
var coinChange = function(coins, amount){
var counts = [0]
for(var i = 1; i <= amount; i++){
counts[i] = amount + 1
coins.map(function(item){
if(i >= item){
counts[i] = Math.min(counts[i], counts[i-item]+1)
}
})
}
return counts[amount]>amount ? -1 : counts[amount]
}
同样是动态规划，还可以采用如下解法，两者相差不大：
var coinChange = function(coins, amount){
if(amount < 0) return -1
else if(amount === 0) return 0
// 对硬币数目数组赋初值
const counts = new Array(amount+1)
counts.fill(0, 0, amount+1)
coins.map(function(item){
if(item <= amount && item != 0){
counts[item] = 1
}
})
// 根据状态转移方程，更新不同金额下的最少硬币数目
for(let i = 0; i < amount+1; i++){
counts[i] = -1
coins.map(function(item){
if(i >= item && counts[i-item] !== -1){
if(counts[i-item]+1 < counts[i] || counts[i] === -1){
counts[i] = counts[i-item] + 1
}
}
})
}
return counts[amount] // 金额为amount,所需的最少硬币数目
}
思路二：除了动态规划法，网上对本题还可以使用递归+回溯法、DFS，先将硬币面额按照大小排序，从每个不同面额的硬币开始DFS，而且可以通过剪枝来提高代码速度
2. 字符串隐藏部分内容函数mask(str, char):
说明：实现一个方法，接收一个字符串和一个符号，将字符串中间四位按指定符号隐藏
1. 符号无指定时使用星号（*）
2. 接收的字符串小于或等于四位时，返回同样长度的符号串，等同于全隐藏，如 123，隐藏后是、***
3. 字符串长度是大于四位的奇数时，如 123456789，隐藏后是 12789，奇数多出来的一位在末尾
示例： * mask(‘alibaba’, ‘#’); // a####ba * mask(‘85022088’); //85**88 * mask(‘hello’); // ****o * mask(‘abc’, ‘?’); //???
var mask = function(str, char='*'){
let lenStr = str.length
let resStr = ''
while(lenStr >= 1 && lenStr <= 4){
resStr += char
lenStr --
}
if(lenStr === 0) return resStr
let index = Math.floor((lenStr-4)/2)
resStr = str.replace(str.slice(index,index+4),char+char+char+char)
returen resStr
}
3. 购物打折——价格数组转文本序列函数rangeStringify(input):
说明：我们在网上购物时常常会见到购买较多时有额外打折，这题就是把这种阶梯价给展示出来。本题即最少买5件，5到15件是12.85元，15件以上时11.36元。这种阶梯可能有多级
示例：
var input = [{
“moqPe”: 5,
“pricePe”: 12.85
}, {
“moqPe”: 15,
“pricePe”: 11.36
}]
var output = rangeStringify(input);
// output: “¥12.85 (5-15); ¥11.36 (≥15个)”
var rangeStringify = function(input){
var output = ''
for (var i = 0; i < input.length; i++){
output += '¥'+input[i].pricePe
if(i !== input.length-1){
output += ' ('+input[i].moqPe+'-'+input[i+1].moqPe+');'
}else{
output += ' (≥'+input[i].moqPe+'个)'
}
}
return output
}
4. 平铺节点数组转嵌套树函数depthArray2Tree(input):
说明：将一个包含深度信息的节点数组转换成一棵树，要求只能遍历一次该数组
输入值：TreeNode数组 TreeNode为包含title, depth(正整数，深度不限)字段的Object
输出值：组装好的嵌套树，子节点挂载在对应父节点的children字段上
下面是网络上学习的大佬的做法，cc真的无能
function depthArray2Tree(depthArray) {
const res = []
for(var obj of arr){
var keyName = ''
for(var key in obj){
if(key !== 'depth'){
keyName = key;
break;
}
}
var level = obj[keyName]
depthArray2TreeHelper(res, obj,keyName,level)
}
return res
}
var depthArray2TreeHelper = function(res,obj,keyName,level){
if(level.length === 1){
var pos = 0
var currentTitle = ''
for(var key in res[pos]){
if(key !== "depth" && key!== "children"){
currentTitle = res[pos][key]
break
}
}
while(pos < res.length && obj[keyName] >= currentTitle){
if(obj[keyName] === currentTitle){
res[pos] = {children: res[pos].children, ...obj}
return
}
pos ++
for(var key in res[pos]){
if(key !== "depth" && key!== "children"){
currentTitle = res[pos][key]
break
}
}
}
res.splice(pos,0,obj)
return
}
const currentLevel = parseInt(level.charAt(0)) - 1
if(res[currentLevel] === null|| res[currentLevel] ===undefined){
res[currentLevel] = {children:[]}
res[currentLevel][keyName] = obj[keyName].slice(0,obj[keyName].length-level.length+1)
}
if(res[currentLevel].hasOwnProperty("children")){
depthArray2TreeHelper(res[currentLevel].children,obj,keyName,level.slice(2))
}else{
const children = []
res[currentLevel]["children"] = children
depthArray2TreeHelper(children,obj,keyName,level.slice(2))
}
}
这段时间的题大概就是
这些了，后续还会整理的，加油啊，我爱学习，我爱刷题
