常见编程题解析
list数据转成tree结构
实现 convert 方法，把原始 list 转换成树形结构，要求尽可能降低时间复杂度
以下数据结构中，id 代表部门编号，name 是部门名称，parentId 是父部门编号，为 0 代表一级部门，现在要求实现一个 convert 方法，把原始 list 转换成树形结构，parentId 为多少就挂载在该 id 的属性 children 数组下
// 原始 list 如下
let list = [
{ id: 1, name: '部门A', parentId: 0 },
{ id: 2, name: '部门B', parentId: 0 },
{ id: 3, name: '部门C', parentId: 1 },
{ id: 4, name: '部门D', parentId: 1 },
{ id: 5, name: '部门E', parentId: 2 },
{ id: 6, name: '部门F', parentId: 3 },
{ id: 7, name: '部门G', parentId: 2 },
{ id: 8, name: '部门H', parentId: 4 },
];
// 转换后的结果如下
let needResult = [
{
id: 1,
name: '部门A',
parentId: 0,
children: [
{
id: 3,
name: '部门C',
parentId: 1,
children: [
{
id: 6,
name: '部门F',
parentId: 3,
},
{
id: 16,
name: '部门L',
parentId: 3,
},
],
},
{
id: 4,
name: '部门D',
parentId: 1,
children: [
{
id: 8,
name: '部门H',
parentId: 4,
},
],
},
],
},
{
// id 2 的
},
// ···
];
最优解，时间复杂度O(n)：
function convert(list) {
const res = []
const map = list.reduce((res, v) => (res[v.id] = v, res), {})
for (const item of list) {
if (item.parentId === 0) {
res.push(item)
continue
}
if (item.parentId in map) {
const parent = map[item.parentId]
parent.children = parent.children || []
parent.children.push(item)
}
}
return res
}
递归：
function convert(list) {
let arr = list.filter(obj => obj.parentId === 0);
handleChildren(arr, list);
return arr;
}
function handleChildren(arr, list) {
arr.forEach(obj => {
let childArr = list.filter(childObj => childObj.parentId === obj.id);
if (childArr.length) {
obj.children = childArr;
handleChildren(childArr, list);
}
})
}
实现一个new函数
function new (fn, ...args) {
const obj = {};
obj._proto_ = fn.prototype; // obj = Object.create(fn.prototype)
const res = fn.apply(obj, args);
return (typeof res === 'object' && res !== null) ? res : obj;
}
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1: 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2: 输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3: 输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
最优解，时间复杂度O(n)：
var lengthOfLongestSubstring = function (str) {
const len = str.length;
if (!len) {
return 0;
}
let left = 0;
let right = 1;
let max = 1;
while (right < len) {
const temp = str.slice(left, right);
if (temp.includes(str.charAt(right))) {
left++;
} else {
max = Math.max(max, right - left + 1);
right++;
}
}
return max;
};
梯度计费
请用尽可能少的代码实现一个函数，用于计算用户一个月共计交费多少港元。（代码请写的尽量清晰简洁，我们希望能够看到你的编码风格和习惯） 用户在的平台上进行交易，需要交平台使用费。平台使用费的梯度收费方案如下： 每月累计订单数 每笔订单（港元） 梯度1：1-5笔 => 30.00 梯度2：6-20笔 => 15.00 梯度3：21-50笔 => 10.00 梯度4：51笔及以上 => 1.00 假设一个用户，一个月交易了6笔订单，则在梯度1交费共计： 30港元*5=150港元，在梯度二交费：15港元，一共交费165港元。
const level = [
{ min: 1, max: 5, fee: 30 },
{ min: 6, max: 20, fee: 15 },
{ min: 21, max: 50, fee: 10 },
{ min: 51, max: 0, fee: 1 },
]
function calcAmount(orderCount) {
let amount = 0;
level.forEach(({ min, max, fee }) => {
if (orderCount >= min) {
if (orderCount <= max || max === 0) {
amount += (orderCount - min + 1) * fee;
} else {
amount += (max - min + 1) * fee;
}
}
})
return amount;
}
实现jsonp
使用方法：
jsonp({
url: 'url',
data: {
key1: 'value1'
},
callback (data) {
// data 是服务端返回的数据
}
})
常规实现
function objectToQuery(obj) {
const arr = [];
for ( var i in obj) {
arr.push(encodeURIComponent(i)+ '=' +encodeURIComponent(obj[i]));
}
return arr.join('&');
}
function jsonp ({url, data, callback}) {
const container = document.getElementsByTagName('head')[0];
const fnName = `jsonp_${new Date().getTime()}`;
const script = document.createElement('script');
script.src = `${url}?${objectToQuery(data)}&callback=${fnName}`;
script.type = 'text/javascript';
container.appendChild(script);
window[fnName] = function (res) {
callback && callback(res);
// 很多候选人漏掉clean这块
container.removeChild(script);
delete window[fnName];
}
script.onerror = function() { // 异常处理，也是很多人漏掉的部分
window[fnName] = function() {
callback && callback(
'something error hanppend!'
)
container.removeChild(script);
delete window[fnName];
}
}
}
Promise实现
function jsonp ({url, data, callback}) {
const container = document.getElementsByTagName('head')[0];
const fnName = `jsonp_${new Date().getTime()}`;
const script = document.createElement('script');
script.src = `${url}?${objectToQuery(data)}&callback=${fnName}`;
script.type = 'text/javascript';
container.appendChild(script);
return new Promise((resolve, reject) => {
window[fnName] = function (res) {
// 很多候选人漏掉clean这块
container.removeChild(script);
delete window[fnName];
resolve(res);
}
script.onerror = function() { // 异常处理，也是很多人漏掉的部分
container.removeChild(script);
delete window[fnName];
reject('something error hanppend!');
}
}
})
}
服务端
const Koa = require('koa')
const app = new Koa()
app.use( async ( ctx ) => {
// 如果jsonp 的请求为GET
if ( ctx.method === 'GET' && ctx.url.split('?')[0] === '/getData.jsonp') {
// 获取jsonp的callback
let callbackName = ctx.query.callback || 'callback'
let returnData = {
success: true,
data: {
text: 'this is a jsonp api',
time: new Date().getTime(),
}
}
// jsonp的script字符串
let jsonpStr = `;${callbackName}(${JSON.stringify(returnData)})`
// 用text/javascript，让请求支持跨域获取
ctx.type = 'text/javascript'
// 输出jsonp字符串
ctx.body = jsonpStr
} else {
ctx.body = 'hello jsonp'
}
})
app.listen(3000, () => {
console.log('[demo] jsonp is starting at port 3000')
})
HardMan
实现HardMan函数：
HardMan('lilei')
//> i'm lilei
HardMan('lilei').rest(10).learn('chinese')
//> i'm lilei
// 等待10秒
//> start learning after 10s
//> learning chinese
HardMan('lilei').restFirst(5).learn('chinese')
// 等待5s
//> start learning after 5s
//> i'm lilei
//> learning chinese
代码：
function HardMan(name) {
const task = []; // 任务容器
// 这边执行next() 相当于调用task数组中的第一个函数，并删除它
function next() {
// 任务执行器
if (task.length) {
task.shift()(); // shift 用于把数组的第一个元素从其中删除，并返回第一个元素的值
}
}
// 延时器
function sleep(time) {
return function () {
setTimeout(function () {
console.log(`start learning after ${time}s`);
next(); // 执行完执行下一个
}, time * 1000);
};
}
// 提供外部方法
const fn = function () {};
fn.prototype.rest = function (time) {
task.push(sleep(time)); // 任务中加入sleep返回的函数
return this; // 返回当前this 用于链式调用
};
fn.prototype.restFirst = function (time) {
task.unshift(sleep(time)); // unshift() 方法可向数组的开头添加一个或更多元素 。 这边是加入到数组前面最先调用 。
return this;
};
fn.prototype.learn = function (sub) {
task.push(function () {
console.log(`learn ${sub}`);
next(); // 执行完执行下一个
});
return this;
};
task.push(function () {
console.log(`i"m ${name}`);
next();
});
// 第一个
setTimeout(next, 0);
return new fn(); // 返回 实例对象 可调用它的内部方法 例：HardMan (name).rest(time)
}
有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
3、每个右括号都有一个对应的相同类型的左括号。
输入：s = "()"
输出：true
输入：s = "()[]{}"
输出：true
输入：s = "(]"
输出：false
代码：
var isValid = function(s) {
const n = s.length;
if (n % 2 === 1) {
return false;
}
const pairs = new Map([
[')', '('],
[']', '['],
['}', '{']
]);
const stk = [];
for (let ch of s){
if (pairs.has(ch)) {
if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {
return false;
}
stk.pop();
}
else {
stk.push(ch);
}
};
return !stk.length;
};
长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
代码：
function minSubArrayLen(s, nums) {
if (nums.length === 0) {
return 0;
}
let left = 0;
let right = 0;
let sum = 0;
let minLength = Infinity;
while (right < nums.length) {
sum += nums[right];
while (sum >= s) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return minLength === Infinity ? 0 : minLength;
}
