# 21-30
# 21、手写防抖节流-京东
function debounce(fn, delay) {
let timer = null;
return function () {
if (timer) clearTimeout(timer);
timer = setTimeout(() => fn.apply(this, arguments), delay);
}
}
window.addEventListener(
"scroll",
debounce(() => {
console.log(111);
}, 1000)
);
function throttle(fn, delay) {
let isFlag = false;
return function () {
if (isFlag) return;
isFlag = true;
setTimeout(() => {
fn();
isFlag = false;
}, delay);
}
}
window.addEventListener(
"scroll",
throttle(() => {
console.log(111);
}, 1000)
);
# 22、手写，将虚拟Dom转为真是Dom（类似的递归题-必考）；
{
tag: 'DIV',
attrs:{
id:'app'
},
children: [
{
tag: 'SPAN',
children: [
{ tag: 'A', children: [] }
]
},
{
tag: 'SPAN',
children: [
{ tag: 'A', children: [] },
{ tag: 'A', children: [] }
]
}
]
}
把上诉虚拟Dom转化成下方真实Dom
<div id="app">
<span>
<a></a>
</span>
<span>
<a></a>
<a></a>
</span>
</div>
function _render(vnode) {
if (typeof vnode === "number") {
vnode = String(vnode);
}
if (typeof vnode === "string") {
return document.createTextNode(vnode);
}
const dom = document.createElement(vnode.tag);
if (vnode.attrs) {
// for(let key in vnode.attrs) {
// dom.setAttribute(vnode.attrs[key]);
// }
Object.keys(vnode.attrs).forEach(key => {
dom.setAttribute(key, vnode.attrs[key]);
});
}
vnode.child.forEach(children => {
dom.appedChild(_render(children));
})
return dom;
}
# 23、手写实现一个flatten方法-阿里
const obj = {
a: {
b: 1,
c: 2,
d: {e: 5}
},
b: [1, 3, {a: 2, b: 3}],
c: 3
}
flatten(obj) 结果返回如下
// {
// 'a.b': 1,
// 'a.c': 2,
// 'a.d.e': 5,
// 'b[0]': 1,
// 'b[1]': 3,
// 'b[2].a': 2,
// 'b[2].b': 3
// c: 3
// }
function isObject(val) {
return typeof val === 'object' && val !== null;
}
function flatten(obj) {
if (!isObject(obj)) return;
let res = {};
function dfs(cur, prefix) {
if (isObject(cur)) {
if (Array.isArray(cur)) {
cur.forEach((item, index) => {
dfs(item, `${prefix}[${index}]`)
})
} else {
for (let key in cur) {
dfs(cur[key], `${prefix}${prefix ? '.' : ''}${key}`)
}
}
} else {
res[prefix] = cur;
}
}
dfs(obj, "");
return res;
}
# 24、手写判读字符串是否有效 - 小米
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
function isValid(str) {
if (!str || str.length % 2 === 1) return false;
const obj = {
'(': ')',
'[': ']',
'{': '}'
}
const queue = [];
for (let i = 0; i < str.length; i++) {
if (obj[str[i]]) {
queue.push(str[i])
} else {
const cur = queue.shift();
if (obj[cur] !== str[i]) {
return false;
}
}
}
if (queue.length) return false;
return true;
}
# 25、查找数组公共前缀-美团
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
function longestCommonPrefix(strArr) {
const str = strs[0];
let index = 0;
while (index < strArr.length) {
const strCur = str.slice(0, index + 1);
for (let i = 0; i < strArr.length; i++) {
if (!strs[i] && !strArr[i].startsWith(strCur)) {
return str.slice(0, index);
}
}
index++;
}
return str;
}
# 26、手写-字符串最长的不重复子串
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
function lengMax(s) {
if (!s.length) return 0;
let left = 0, map = new Map(), max = 0;
for (let i = 0; i < s.length; i++) {
if (map.has(s[i])) {
left = Math.max(left, map.get(s[i]) + 1);
}
map.set(s[i], i);
max = Math.max(max, i - left + 1);
}
return max;
}
# 27、手写-如何找到数组中第一个没出现的最小正整数 怎么优化（字节）
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
时间空间均为 O(n)
function firstMissingPositive(nums) {
const set = new Set();
for (let i = 0; i < nums.length; i++) {
set.add(nums[i])
}
for (let i = 0; i < set.size; i++) {
if (!set.has(i)) {
return i;
}
}
return set.size;
}
最终版 时间复杂度为 O(n) 并且只使用常数级别空间
function firstMissingPositive(nums) {
for (let i = 0; i < nums.length; i++) {
// 对1~nums.length范围内的元素进行安排 // 已经出现在理想位置的，就不用交换
while (nums[i] > 0 && nums[i] < nums.length && nums[nums[i] - 1] !== nums[i]) {
[nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
}
}
// 现在期待的是 [1,2,3,...]，如果遍历到不是放着该放的元素
for (let i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1; // 发现元素 1~nums.length 占满了数组，一个没缺
}
28、手写-怎么在制定数据源里面生成一个长度为 n 的不重复随机数组 能有几种方法 时间复杂度多少（字节）
第一版 标记法 / 自定义属性法 时间复杂度为 O(n)
function getNums(testArray, n) {
const map = new Map();
for(let i = 0; i< n; i++) {
const index = Math.floor(Math.random() * testArray.length);
if(map.has(testArray[index])){
i--;
continue;
}
map.set(testArray[index], true);
}
return [...map.keys()];
}
第二版 交换法 时间复杂度为 O(n)
function getTenNum(testArray, n) {
const cloneArr = [...testArray];
let result = [];
for (let i = 0; i < n; i++) {
debugger;
const ran = Math.floor(Math.random() * (cloneArr.length - i));
result.push(cloneArr[ran]);
cloneArr[ran] = cloneArr[cloneArr.length - i - 1];
}
return result;
}
const testArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
const resArr = getTenNum(testArray, 14);
最终版 边遍历边删除 时间复杂度为 O(n)
function getTenNum(testArray, n) {
const cloneArr = [...testArray];
let result = [];
for (let i = 0; i < n; ++i) {
const random = Math.floor(Math.random() * cloneArr.length);
const cur = cloneArr[random];
result.push(cur);
cloneArr.splice(random, 1);
}
return result;
}
const testArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
const resArr = getTenNum(testArray, 14);