常见编程题解析
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')
})
