Open TinyScript opened 2 years ago
完成算法:https://leetcode-cn.com/problems/shortest-distance-to-a-character/
第一版:
var shortestToChar = function(s, c) {
const len = s.length;
const result = new Array(len);
let mainCur = 0;
let subCur = 0;
let prevSign = 0;
let nextSign = 0;
while(mainCur < len) {
while(!nextSign && subCur < len) {
if(s[subCur] === c) {
if(mainCur === 0) prevSign = subCur
nextSign = subCur;
subCur++;
break;
}
subCur++;
}
const prev = Math.abs(prevSign - mainCur)
const next = Math.abs(nextSign - mainCur)
const currDistance = Math.min(prev, next);
if(!currDistance) {
prevSign = nextSign
nextSign = 0
}
result[mainCur] = currDistance
mainCur++
}
return result
};
第二版:
var shortestToChar = function(s, c) {
const len = s.length;
const arr = [-Infinity];
const result = [];
for(let i = 0; i < len; i++) {
s.charAt(i) === c && arr.push(i);
}
arr.push(Infinity);
for(let i = 0; i < len; i++) {
if(s.charAt(i) === c) {
arr.shift();
result.push(0);
continue;
}
const resNum = Math.min(i - arr[0], arr[1] - i);
result.push(resNum);
}
return result;
};
第三版:
var shortestToChar = function(s, c) {
const len = s.length;
const result = [];
const keyArr = [-Infinity];
for(let i = 0; i < len; i++) {
if(s.charAt(i) === c) keyArr.push(i);
}
keyArr.push(Infinity);
let idx = 1, prev = keyArr[idx - 1], next = keyArr[idx];
for(let i = 0; i < len; i++) {
const dist = Math.min(i - prev, next - i);
result.push(dist);
if(i === next) {
idx++;
prev = next;
next = keyArr[idx];
}
}
return result;
};
Symbol实现,参考:https://gist.github.com/liril-net/4436fb0bdc8f8ddecbdd34bdfa571b14 第一版:
function SymbolPolyfill(description) {
if(this instanceof SymbolPolyfill) throw new TypeError('Symbol is not a constructor');
if(description !== undefined) {
descString = String(description)
}
const symbol = Object.create(SymbolPolyfill.prototype)
Object.defineProperties(symbol, {
__Description__: { value: description },
__Name__: { value: generateName(description) },
})
return symbol
}
var generateName = (function() {
const createdMap = {}
return function (description) {
let suffix = createdMap[description]
if(!suffix) suffix = 0
suffix += 1
createdMap[description] = suffix
return `@@${description}${suffix}`
}
})()
var symbolA = SymbolPolyfill('a')
var symbolA1 = SymbolPolyfill('a')
第二版:
给实例对象添加辨别属性,使用传入的desc入参填充
function SymbolPolyfill(desc) {
if(this instanceof SymbolPolyfill) throw new Error('SymbolPolyfill is not a constructor.');
if (desc) { desc = String(desc); }
const symbol = Object.create(SymbolPolyfill.prototype);
Object.defineProperties(symbol, {
__Name__: defineValue(getName(desc)),
__Description__: defineValue(desc)
})
return symbol;
}
function defineValue(value) { return { value, configurable: true, enumable: false, writable: false } }
var getName = (() => {
const m = new Map();
return value => {
const count = m.get(value) || 0;
m.set(value, count + 1);
return @@${value}_${count + 1}
}
})()
算法:https://leetcode-cn.com/problems/design-a-stack-with-increment-operation/
var CustomStack = function(maxSize) {
this.stack = new Array(maxSize);
this.cur = -1;
this.boundary = maxSize - 1;
};
CustomStack.prototype.push = function(x) {
if(this.cur >= this.boundary) return;
this.cur++;
this.stack[this.cur] = x;
};
CustomStack.prototype.pop = function() {
if(this.cur < 0) return -1;
const pop = this.stack[this.cur]
this.stack[this.cur] = undefined;
this.cur--;
return pop;
};
CustomStack.prototype.increment = function(k, val) {
const minLen = Math.min(this.stack.length, k);
for(let i = 0; i < minLen; i++) {
this.stack[i] += val;
}
};
实现 allSettled:
function allSettled(promises) {
if(!Array.isArray(promises)) {
return Promise.resolve([]);
}
const len = promises.length;
if(!len) return Promise.resolve([]);
const result = new Array(len);
// 原本使用result.length === len,但是这样无法使用new Array(len),后续改用times
let resolve, times = 0;
for(let i = 0; i < len; i++) {
const promise = transferPromise(promises[i]);
promise
.then(value => (result[i] = { status: 'fulfilled', value }))
.catch(reason => (result[i] = { status: 'rejected', reason }))
.finally(() => {
times++;
if(times !== len) return;
resolve(result)
})
}
return new Promise(res => { resolve = res })
}
function transferPromise(target) {
if(target instanceof Promise) return target;
return Promise.resolve(target);
}
第二版:
function allSettled(promises) {
if(!Array.isArray(promises)) throw new TypeError(`${ promises } is not iterable.`)
const len = promises.length;
if(!len) return Promise.resolve([])
const result = new Array(len);
let count = 0, resolve;
for(let i = 0; i < len; i++) {
const promise = Promise.resolve(promises[i]);
promise
.then(value => result[i] = { status: 'fulfilled', value })
.catch(reason => result[i] = { status: 'rejected', reason })
.finally(() => {
if(++count !== len) return;
resolve(result);
})
}
return new Promise(res => resolve = res);
}
实现算法:https://leetcode-cn.com/problems/decode-string/
var decodeString = function(s) {
const stack = [];
for(var char of s) {
if(char !== ']') {
stack.push(char);
continue;
}
let curr = stack.pop();
let str = '';
while(curr !== '[') {
str = curr + str;
curr = stack.pop();
}
curr = stack.pop();
let num = '';
while(!isNaN(curr)) {
num = curr + num;
curr = stack.pop();
}
stack.push(curr);
stack.push(str.repeat(num))
}
return stack.join('');
};
实现is函数:Object.is(value1, value2)
function is(a, b) {
if(a !== a) {
return b !== b;
}
if(a === 0 && b === 0) {
return 1 / a === 1 / b;
}
return a === b
}
实现算法:https://leetcode-cn.com/problems/implement-queue-using-stacks/
var MyQueue = function() {
this.queue = new Array(100);
this.head = 0;
this.cur = 0;
};
/**
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
this.queue[this.cur] = x;
const isBondary = this.cur !== this.queue.length - 1
this.cur = isBondary ? this.cur + 1 : 0;
};
/**
* @return {number}
*/
MyQueue.prototype.pop = function() {
const result = this.queue[this.head];
this.queue[this.head] = undefined;
const isBondary = this.head !== this.queue.length - 1;
this.head = isBondary ? this.head + 1 : 0;
return result;
};
/**
* @return {number}
*/
MyQueue.prototype.peek = function() {
return this.queue[this.head];
};
/**
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
return this.cur === this.head
};
实现时针、分针夹角计算: 请计算出时钟的时针和分针的角度(两个角度的较小者,四舍五入)。时间以HH:mm的格式传入。
取较小差角,判断差角是大于180°时,使用360° - 差角
function angle(time) {
const [hours, minutes] = time.split(':');
const HOUR_ANGLE = 360 / 12;
const MINUTE_ANGLE = 360 / 60;
const hourAngle = hours % 12 * HOUR_ANGLE;
const hourOffsetAngle = minutes / 60 * HOUR_ANGLE;
const minuteAngle = minutes * MINUTE_ANGLE;
const calcAngle = Math.abs(hourAngle + hourOffsetAngle - minuteAngle);
const finalAngle = calcAngle > 180 ? 360 - calcAngle : calcAngle;
return Math.round(finalAngle);
}
angle('01:15') // 53°
待补充
var maxChunksToSorted = function(arr) {
const sortArr = arr.slice().sort();
const map = new Map();
let ans = 0;
let nonzero = 0;
for(let i = 0; i < arr.length; ++i) {
const x = arr[i], y = sortArr[i];
map.set(x, (map.get(x) ?? 0) + 1);
if(map.get(x) === 0) nonzero--;
if(map.get(x) === 1) nonzero++;
map.set(y, (map.get(y) ?? 0) - 1);
if(map.get(y) === -1) nonzero++;
if(map.get(y) === 0) nonzero--;
if(nonzero === 0) ans++;
}
return ans;
};
编程题:实现URLSearchParams。 第一版:未使用map
class MyURLSearchParams {
/**
* @params {string} init
*/
constructor(init) {
const search = this.formatSearchList(init)
this.search = search.reduce((obj, item) => {
if(!obj[item.key]) obj[item.key] = [];
obj[item.key].push(item.value);
return obj;
}, {})
}
formatSearchList(str) {
return str.replace(/^.*\?/, '').split('&').map(s => {
const [k, v] = s.split('=');
return { key: k, value: v }
});
}
/**
* @params {string} name
* @params {any} value
*/
append(name, value) {
if(!this.search[name]) this.search[name] = [];
this.search[name].push(String(value));
}
/**
* @params {string} name
*/
delete(name) {
delete this.search[name];
}
getEntiresBySearch() {
const search = this.search;
return Object.keys(search).reduce((arr, key) => {
const valueArr = search[key].map(v => [key, v]);
return arr.concat(valueArr);
}, [])
}
/**
* @returns {Iterator}
*/
*entries() {
const entries = this.getEntiresBySearch();
for(let i = 0; i < entries.length; i++) {
yield entries[i];
}
}
/**
* @param {(value, key) => void} callback
*/
forEach(callback) {
const entries = this.getEntiresBySearch();
entries.forEach(([k, v]) => {
callback(v, k, this);
})
}
/**
* @param {string} name
* returns the first value of the name
*/
get(name) {
const _name = name.replace(/^.*\?/, '');
const value = this.search[_name];
if(!Array.isArray(value)) return null;
return this.search[_name][0];
}
/**
* @param {string} name
* @return {string[]}
* returns the value list of the name
*/
getAll(name) {
return this.search[name] ?? [];
}
/**
* @params {string} name
* @return {boolean}
*/
has(name) {
return Boolean(this.search[name]);
}
/**
* @return {Iterator}
*/
*keys() {
const entries = this.getEntiresBySearch();
for(let i = 0; i < entries.length; i++) {
yield entries[i][0];
}
}
/**
* @param {string} name
* @param {any} value
*/
set(name, value) {
this.search[name] = [String(value)];
}
// sor all key/value pairs based on the keys
sort() {
const entries = this.getEntiresBySearch();
const newEntries = entries.sort((a,b) => a[0].charCodeAt() - b[0].charCodeAt());
const newSearch = newEntries.reduce((obj, entry) => {
const [k, v] = entry
if(!obj[k]) obj[k] = [];
obj[k].push(v);
return obj;
}, {})
this.search = newSearch;
}
/**
* @return {string}
*/
toString() {
const search = this.search;
return Object.keys(search).reduce((str, k) => {
const serialize = search[k].reduce((_str, v) => {
return _str + `&${k}=${v}`
}, '');
return str + serialize
}, '').substring(1);
}
/**
* @return {Iterator} values
*/
*values() {
const entries = this.getEntiresBySearch();
for(let i = 0; i < entries.length; i++) {
yield entries[i][1];
}
}
}
第二版:使用map
实现算法:https://leetcode-cn.com/problems/rotate-list/
var rotateRight = function(head, k) {
// 1. 取链表长度,因为涉及到长度处理的原因,所以从1开始计算
let n = 1;
let node = head;
if(!head || !head.next || k === 0) return head;
while(node.next) {
node = node.next;
n++;
}
// 2. 取右移k次后,最后一个节点的位置,如果k大于链表长度,取链表长度的模
n = n - k % n;
// 3. 链表首位相接成环
node.next = head;
// 4. 开始计算右移,最终得出来的node为尾部节点
while(n) {
node = node.next;
n--;
}
// 5. 链表去环
const result = node.next;
node.next = null;
return result;
};
实现算法:https://leetcode-cn.com/problems/swap-nodes-in-pairs/
1 -> 2 -> 3
=> 2 -> 1 -> 3
,看上去只是1和2替换,但这里还要注意1和2替换后,还要让1和3链上var swapPairs = function(head) {
let count = 0;
let node = head;
let preNode = null;
if(!head) return head;
while(node.next) {debugger
if(count % 2 === 0) {
const temp1 = node;
const temp2 = node.next.next;
node = node.next;
if(count === 0) head = node;
node.next = temp1;
temp1.next = temp2;
if(preNode) preNode.next = node;
}
preNode = node;
node = node.next;
count++;
}
return head;
};
编程题:实现Object.create。 参考:https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Object/create#polyfill
function myObjectCreate(proto) {
if(typeof proto !== "object" || proto === null) {
throw new Error(`Expected object but received ${proto === null ? "null" : typeof proto}`);
}
const o = new Object();
o.__proto__ = proto;
return o;
}
实现算法:https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
// Definition for singly-linked list.
class ListNode {
val: number
next: ListNode | null
constructor(val?: number, next?: ListNode | null) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
}
// Definition for a binary tree node.
class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
}
function sortedListToBST(head: ListNode | null): TreeNode | null {
const arr: number[] = [];
while(head) {
arr.push(head.val);
head = head.next;
}
const buildBST = (start: number, end: number): TreeNode | null => {
if(start > end) return null;
const mid: number = Math.ceil((start + end) / 2);
const node: TreeNode = new TreeNode(arr[mid]);
node.left = buildBST(start, mid - 1);
node.right = buildBST(mid + 1, end);
return node;
}
return buildBST(0, arr.length - 1);
};
function sortedListToBST(head: ListNode | null): TreeNode | null {
if(head === null) return null;
// 1. 定义快慢指针,慢跑1,快跑2,并记录慢指针的前一个节点
let fast = head;
let slow = head;
let prev = null;
// 2. fast跑完整个list,slow跑完list.length
while(fast && fast.next) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
// 3. 取slow当前位置作为当前层的root节点
const root = new TreeNode(slow.val);
// 4. 处理root.left与root.right
if(prev !== null) {
prev.next = null;
root.left = sortedListToBST(head);
}
root.right = sortedListToBST(slow.next);
return root;
};
根据二叉搜索树中序遍历的结果,还原为遍历前二叉树
function sortedListToBST(head: ListNode | null): TreeNode | null {
// 1. 计算链表长度
let len = 0;
let headNode = head;
while(head) {
len++;
head = head.next;
}
// 2. 递归分治,取数组中央节点mid做为最小二叉树树根
const buildBST = (start, end): TreeNode | null => {
// 6. 递归至start > end时,代表到最底部,开始向上操作
if(start > end) return null;
const mid = Math.ceil((start + end) / 2);
// 3. 左叶节点截取数组0, mid - 1,重复2
const left = buildBST(start, mid - 1);
// 5. 每个最小二叉树左叶节点处理完毕后,建立根节点,且控制链表指针往后挪(按中序遍历顺序挪动)
const root = new TreeNode(headNode.val);
headNode = headNode.next;
root.left = left;
// 4. 右叶节点截取mid + 1, arr.length - 1,重复2
root.right = buildBST(mid + 1, end);
return root;
}
return buildBST(0, len - 1)
};
编程题:实现EventEmitter
实现sub.release,释放订阅
class EventEmitter {
constructor() {
this.eventMap = new Map();
}
subscribe(eventName, callback) {
if(typeof callback !== 'function') return false;
if(!this.eventMap[eventName]) this.eventMap[eventName] = [];
this.eventMap[eventName].push(callback);
return {
release: () => {
const idx = this.eventMap[eventName].indexOf(callback);
this.eventMap[eventName].splice(idx, 1);
}
}
}
emit(eventName, ...args) {
const eventList = this.eventMap[eventName];
if(!Array.isArray(eventList)) return false;
eventList.forEach(callback => {
callback(...args);
})
}
}
实现算法:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
暴力法
时间O(m+n),空间O(m)(m为HeadA)
function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
const set = new Set();
while(headA) {
set.add(headA);
headA = headA.next;
}
while(headB) {
if(set.has(headB)) {
return headB;
}
headB = headB.next;
}
return null;
};
双指针
终上所述,只需要单次循环遍历即可,最终只需要判断指针A或指针B
function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
const headNodeA = headA;
const headNodeB = headB;
while(headA !== headB) {
headA = headA === null ? headNodeB : headA.next;
headB = headB === null ? headNodeA : headB.next;
}
return headA;
};
实现算法:https://leetcode-cn.com/problems/linked-list-cycle-ii/ 暴力法
function detectCycle(head: ListNode | null): ListNode | null {
const set = new Set();
while(head) {
if(set.has(head)) return head;
set.add(head);
head = head.next;
}
return null;
};
双指针
a到入环的距离
,为fast与slow相遇节点到入环节点的距离
+ n - 1圈
function detectCycle(head) {
if(!head || !head.next) return null;
if(head === head.next) return head;
let fast = head;
let slow = head;
while(fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
if(fast === slow) break;
}
while(fast && fast.next) {
if(fast === head) return head;
head = head.next;
fast = fast.next;
}
return null
};
编程题:实现Promise.any
function any(promises) {
// your code here
const len = promises.length;
let resolve, reject, errors = [];
for(let i = 0; i < len; i++) {
promises[i]
.then(resp => resolve(resp))
.catch(error => { errors[i] = error })
.finally(() => {
if(errors.length !== len) return
const rejectInfo = new Error(
'No Promise in Promise.any was resolved',
errors
)
reject(rejectInfo)
})
}
return new Promise((res, rej) => {
resolve = res;
reject = rej;
})
}
实现算法,LRU缓存:https://leetcode-cn.com/problems/lru-cache/submissions/
class DoubleLink {
key: number;
val: number;
prev: DoubleLink | void;
next: DoubleLink | void;
constructor(key: number, val: number) {
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
}
removeNode() {
if(this.prev) {
this.prev.next = this.next;
}
if(this.prev && this.next) {
this.next.prev = this.prev
}
this.prev = null;
this.next = null;
return this;
}
addNode(node) {
this.next = node;
node.prev = this;
}
insertNode(node) {
if(this.prev) {
this.prev.next = node;
node.prev = this.prev;
}
this.prev = node;
node.next = this;
}
}
class LRUCache {
cache: Map<number, DoubleLink> = new Map();
head: DoubleLink = new DoubleLink(0, 0);
tail: DoubleLink = new DoubleLink(0, 0);
capacity: number;
constructor(capacity: number) {
this.capacity = capacity;
this.head.next = this.tail;
this.tail.prev = this.head;
}
get(key: number): number {
const cacheNode = this.cache.get(key);
if(cacheNode) {
cacheNode.removeNode();
this.tail.insertNode(cacheNode);
return cacheNode.val;
}
return -1;
}
put(key: number, value: number): void {
const cacheNode = this.cache.get(key)
const node = new DoubleLink(key, value);
this.cache.set(key, node);
this.tail.insertNode(node);
if(cacheNode) {
cacheNode.removeNode();
return;
}
if(this.cache.size > this.capacity && this.head.next) {
const head = this.head.next.removeNode();
this.cache.delete(head.key);
}
}
}
编程题:实现Promise.race
function race(promises) {
let resolve, reject;
for(let i = 0, len = promises.length; i < len; i++) {
promises[i].then(resolve).catch(reject);
}
return new Promise((res, rej) => {
resolve = res;
reject = rej;
})
}
实现算法:二叉树的最大深度
function maxDepth(root: TreeNode | null): number {
if(!root) return 0;
const left = maxDepth(root.left);
const right = maxDepth(root.right);
return Math.max(left, right) + 1;
};
编程题:实现对象合并时,只更新不相同的值
type ProduceFunc = <T>(base: T, receipe: (draft: T) => any) => void
const state = [ { name: 'BFE', }, { name: '.', } ]
const compare = (base: any, modify: any) => { if(typeof base !== typeof modify) return false; if(typeof base !== 'object') return base === modify; let isEqual = true; for(let key of Object.keys(base)) { if(compare(base[key], modify[key])) { modify[key] = base[key]; continue; } isEqual = false; } return Object.keys(base).length === Object.keys(modify).length && isEqual; }
const produce: ProduceFunc = (base, recipe) => { // your code here const modify = JSON.parse(JSON.stringify(base)) recipe(modify) if(compare(base, modify)) return base; return modify; }
const newState = produce(state, draft => { draft.push({name: 'dev'}) draft[0].name = 'bigfrontend' draft[1].name = '.' // set为相同值。 })
实现算法:相同的树
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if(p === q) return true;
if(p === null || q === null) return false;
if(p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
编程题:实现JSX解析
开标签
,得到标签名<
开头,则可当做文本节点进行字符作为children的收集<
,则在不影响循环字符的索引情况下,向下递归,寻找是否有/
字符,有为闭合标签,结束本次children的收集(这点的逻辑应该后置,一般情况下有嵌套的场景都不会立即遇上闭合标签,都是先逐级递归开放标签,类似括号嵌套算法的思路: [(())])/
,但找到了>
字符,代表需要重复第一点进行标签拆解(开始递归,从第1点开始,直到满足第4点为止)/
字符处理
type JSXOpeningElement = {
tag: string
}
type JSXClosingElement = { tag: string }
type JSXChildren = Array<string | JSXElement>
type JSXElement= { openingElement: JSXOpeningElement children: JSXChildren closingElement: JSXClosingElement }
function checkCloseTag(str: string, i: number): boolean { if(str[i] === '/') return true; if(str[i] === '>') return false; return checkCloseTag(str, i + 1); }
function parseChildren(str: string): [JSXChildren, number] { // 判断当前标签是否结束 // 非结束标签,则进行递归parse函数,并收集文字 // 递归完毕后拿到子元素的内容,存到child数组中备用号 // 如果既不是openTag也不是closeTag,则按文字处理,收集字符文字 const children = []; let text = ''; let i = 0;
for(; i < str.length; i++) { if(str[i] !== '<') { text += str[i]; continue; } // 闭合标签 if(checkCloseTag(str, i)) break; if(text) { children.push(text); text = ''; } const childTag = codeParse(str.slice(i)); children.push(formatJSX(childTag)); i += childTag.closeTagEndIndex; } if(text) children.push(text); return [ children, i ] }
function parseTag(str: string): [number, string, boolean] { const tagEndIndex = str.indexOf('>'); let tagName = str.slice(1, tagEndIndex).trim(); let isClose = false; if(tagName[0] === '/') { tagName = tagName.slice(1).trim(); isClose = true } return [tagEndIndex, tagName, isClose] }
function formatJSX({ openTagName, closeTagName, children }: Record<string, any>) { return { openingElement: { tag: openTagName }, closingElement: { tag: closeTagName }, children } }
function codeParse(code: string) { code = code.trim() if ( (code[0] !== "<" || code[code.length - 1] !== ">") || code.split("<").length !== code.split(">").length ) { throw new Error(""); } // 记录当前字符的位置 let i = 1 // 解析开标签 const [ openTagEndIndex, openTagName ] = parseTag(code); // 去掉开标签字符 code = code.substr(openTagEndIndex + 1, code.length) // 同步字符的索引 i += openTagEndIndex; // 解析子节点 const [ children, skipIndex ] = parseChildren(code) // 去掉子节点的字符 code = code.substr(skipIndex, code.length) // 同步位置 i += skipIndex; // 闭合标签,接下来两个行代码同上 const [ closeTagEndIndex, closeTagName, isClose ] = parseTag(code); code = code.substr(closeTagEndIndex, code.length) i += closeTagEndIndex;
if(!isClose || openTagName !== closeTagName) {
throw new Error(isClose: ${isClose}, openTagName: ${openTagName}, closeTagName: ${closeTagName}
);
}
return {
openTagName,
closeTagName,
children,
closeTagEndIndex: i // 目的是为了子节点碰到标签需要递归时,知道目前位置到哪里了
}
}
function parse(code: string): JSXElement { // your code here const codeJSON = codeParse(code); return formatJSX(codeJSON); }
function generate(ast: JSXElement | string): Record<string, any> | string { if(typeof ast === 'string') return ast; const tagName = ast.openingElement.tag; const type = tagName[0] === tagName[0].toUpperCase() ? Heading : tagName const node = { type, props: { children: ast.children.map(generate) } } return node; }
const str = " < a > bfe.dev < / a > " console.log((parse(str)))
实现算法:129. 求根节点到叶节点数字之和
节点数
=== 树高
=== 栈消耗
(链表)
var sumNumbers = function(root) {
const dfs = (root, prevSum = 0) => {
if(!root) return null;
const sum = prevSum * 10 + root.val;
if(root.left === null && root.right === null) return sum;
return dfs(root.left, sum) + dfs(root.right, sum)
}
return dfs(root);
};
queueNode
与节点对应路径路净值队列:queueNum
var sumNumbers = function(root) {
if(root === null) return 0;
let sum = 0;
// 广度优先的两个队列:记录节点,与当前节点累计的拼接值
const queueNode = [root], queueNum = [root.val];
while(queueNode.length) {
// 取出root,后续存root.left与root.right,以此类推,永远都是把上一层的所有子节点先跑完
const node = queueNode.shift();
// 取出当前节点对应的累计拼接值,思路上一行的node
const num = queueNum.shift();
const left = node.left, right = node.right;
// 场景1:到达叶尾节点场景,因为在下来之前已经把当前节点加上了,这里只需累加至sum变量做统计即可
if(left === null && right === null) {
sum += num;
continue;
}
// 场景2:只有单左叶节点场景
if(left) {
queueNode.push(left);
queueNum.push(num * 10 + left.val);
}
// 场景3:只有单右叶节点场景
if(right) {
queueNode.push(right);
queueNum.push(num * 10 + right.val);
}
}
return sum;
};
编程题: 去除字符
给定只含有a、b 和 c的字符串,请去掉其中的b 和 ac。
removeChars('ab') // 'a'
removeChars('abc') // ''
removeChars('cabbaabcca') // 'caa'
function removeChars(str) {
const arrStr = str.split('');
const stack = [];
let result = ''
for(let i = 0; i < arrStr.length; i++) {
if(str[i] === 'a') {
stack.push(str[i]);
continue;
}
if(str[i] === 'c' && stack.length) {
stack.pop();
continue;
}
if(str[i] === 'b') continue;
result += str[i];
}
result = result + stack.join('')
return result;
}
removeChars('acacabbaabcca')
实现算法:513. 找树左下角的值
var findBottomLeftValue = function(root) {
if(!root) return null;
const queue = [root];
let result = null;
while(queue.length) {
result = queue[0]; // 每层都尝试拿一次最左的值
for(let i = 0, len = queue.length; i < len; i++) {
const node = queue.shift();
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
}
return result.val;
};
var findBottomLeftValue = function(root) {
let maxPath = 0;
let resNode = root;
const dfs = (root, curPath = 1) => {
const isEnd = !Boolean(root.left) && !Boolean(root.right);
console.log(root, maxPath, curPath)
if(isEnd && maxPath < curPath) {
maxPath = curPath;
resNode = root.val;
}
curPath++
if(root.left) dfs(root.left, curPath);
if(root.right) dfs(root.right, curPath);
}
dfs(root);
return resNode;
};
编程题: 实现一个LazyMan
queue
push时,都要激活一次清空队列的命令run
,因为程序并不知道你什么时候才算push完毕,算是一种技巧性思路LazyMan(“Hank”)
// 输出:
// Hi! This is Hank!
LazyMan(“Hank”).sleep(10).eat(“dinner”)
// 输出:
// Hi! This is Hank!
// 等待10秒..
// Wake up after 10
// Eat dinner~
LazyMan(“Hank”).eat(“dinner”).eat(“supper”)
// 输出:
// Hi This is Hank!
// Eat dinner~
// Eat supper~
LazyMan(“Hank”).eat(“supper”).sleepFirst(5)
// 输出:
// 等待5秒
// Wake up after 5
// Hi This is Hank!
// Eat supper
class LazyMan {
constructor(name = 'tiny') {
this.queue = [];
this.timer = null;
this.firstCount = 0;
console.log(`Hi! This is ${name}!`)
}
run() {
if(this.timer) clearTimeout(this.timer);
this.timer = setTimeout(() => {
if(!this.queue.length) return;
const fn = this.queue.shift();
Promise.resolve(fn()).then(this.run.bind(this))
});
return this;
}
eat(str) {
this.queue.push(() => console.log(str))
return this.run();
}
sleep(time) {
const p = () => new Promise(resolve => setTimeout(() => {
console.log(`Wake up after ${time}`)
resolve();
}, time * 1000))
this.queue.push(p)
return this.run()
}
sleepFirst(time) {
const p = () => new Promise(resolve => setTimeout(() => {
console.log(`等待${time}秒`)
resolve();
}, time * 1000))
this.queue.splice(this.firstCount, 0, p)
this.firstCount++;
return this.run()
}
}
var l = new LazyMan();
l.sleep(3).eat('dinner').sleep(3).eat('supper').sleepFirst(1).sleepFirst(2);
实现算法:297. 二叉树的序列化与反序列化
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function(root) {
if(root === null) return null;
const queue = [root];
const result = [];
while(queue.length) {
const node = queue.shift();
result.push(node ? node.val : 'null');
if(!node) continue;
queue.push(node.left ? node.left : null);
queue.push(node.right ? node.right : null);
}
console.log(result.join(','))
return result.join(',');
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
if(!data) return null;
const arr = data.split(',')
const root = new TreeNode(arr.shift());
const queue = [root];
while(queue.length) {
const node = queue.shift();
if(node === 'null') continue;
const left = arr.shift()
if(left !== 'null') {
node.left = new TreeNode(left);
queue.push(node.left);
}
const right = arr.shift()
if(right !== 'null') {
node.right = new TreeNode(right);
queue.push(node.right);
}
}
return root;
};
var serialize = function(root) {
const result = [];
const dfs = (root, result) => {
if(root === null) {
result.push('null')
return 'null';
}
result.push(root.val);
dfs(root.left, result);
dfs(root.right, result);
}
dfs(root, result);
return result.join(',');
};
var deserialize = function(data) {
if(!data) return null;
const arr = data.split(',')
const dfs = (arr) => {
const val = arr.shift();
if(val === 'null') return null;
const root = new TreeNode(val);
root.left = dfs(arr);
root.right = dfs(arr);
return root;
}
return dfs(arr);
};
编程题: 渲染百万条结构简单的大数据时 怎么使用分片思想优化渲染 todo
实现算法:987. 二叉树的垂序遍历
var verticalTraversal = function(root) {
const entries = dfs(root);
entries.sort((a,b) => {
if(a[1] !== b[1]) return a[1] - b[1];
if(a[0] !== b[0]) return a[0] - b[0];
return a[2] - b[2];
})
const result = [];
let maxNum = -Number.MAX_VALUE
for(let arr of entries) {
if(arr[1] !== maxNum) {
maxNum = arr[1];
result.push([arr[2]])
continue;
}
result[result.length - 1].push(arr[2]);
}
return result
};
const dfs = (root, row = 0, col = 0, nodes = []) => {
if(root === null) return null;
nodes.push([row, col, root.val]);
dfs(root.left, row + 1, col - 1, nodes);
dfs(root.right, row + 1, col + 1, nodes);
return nodes;
}
编程题:请实现 DOM2JSON 一个函数,可以把一个 DOM 节点输出 JSON 的格式
function dom2JSON(elem) {
const json = {
nodeType: elem.nodeType
}
if(elem.nodeType === 1) {
json.tagName = elem.tagName.toLowerCase();
json.className = elem.className;
console.log(elem, elem.attributes)
json.attrs = Object.keys(elem.attributes).reduce((obj, key) => {
const attr = elem.attributes[key];
if(attr.name === 'class') return obj;
obj[attr.name] = attr.nodeValue;
return obj;
}, {})
json.children = Array.from(elem.childNodes).map(dom2JSON);
return json;
}
json.children = [elem.nodeValue]
return json
}
实现算法:1. 两数之和
var twoSum = function(nums, target) {
const map = new Map();
for(let i = 0; i < nums.length; i++) {
const t = target - nums[i]
if(map.has(t)) return [map.get(t), i];
map.set(nums[i], i);
}
};
编程题:实现函数柯里化compose
function compose(...fns){
return fns.reduce((a, b) => ...args => a(b(...args)))
}
const multiply20 = (price) => price * 20;
const divide100 = (price) => price / 100;
const normalizePrice = (price) => price.toFixed(2);
const discount = compose(normalizePrice, divide100, multiply20);
discount(200.0); //40.00
实现算法:347. 前 K 个高频元素
时间复杂度:遍历数组O(N) + 堆操作O(logN),即O(N logN)
var topKFrequent = function(nums, k) {
if(!nums.length) return [];
const m = new Map();
nums.sort().forEach(num => {
let count = m.get(num);
if(!count) count = 0;
m.set(num, ++count);
})
const p = new PriorityQueue();
const entries = m.entries()
for(let [num,v] of entries) {
if(p.queue.length < k) {
p.enqueue(v, num)
continue;
}
const head = p.getHead();
console.log(num, v, head.p, p.queue.length)
if(v > head.p) {
p.outqueue();
p.enqueue(v, num);
}
}
return p.queue.sort((a,b) => {
if(a.p !== b.p) return b.p - a.p;
return a.p - b.p;
}).map(({v}) => v);
};
class PriorityQueue { queue = [];
getHead() { return this.queue[0] }
enqueue(p, v) { this.queue[this.queue.length++] = {p, v}; this.upAdjust(); }
upAdjust() { let childIndex = this.queue.length - 1; let parentIndex = Math.floor((childIndex - 1) / 2); let temp = this.queue[childIndex]; while(childIndex > 0 && temp.p < this.queue[parentIndex].p) { this.queue[childIndex] = this.queue[parentIndex]; childIndex = parentIndex; parentIndex = Math.floor((childIndex - 1) / 2); } this.queue[childIndex] = temp; }
outqueue() { if(!this.queue.length) return null; const head = this.queue[0] const last = this.queue.pop(); if(this.queue.length) { this.queue[0] = last; this.downAdjust(); } return head; }
downAdjust(parentIndex = 0) { const temp = this.queue[parentIndex]; let childIndex = 1; while(childIndex < this.queue.length) { const nextChildIndex = childIndex + 1; if( nextChildIndex < this.queue.length && this.queue[nextChildIndex].p < this.queue[childIndex].p ) childIndex++; if(temp.p <= this.queue[childIndex].p) break; this.queue[parentIndex] = this.queue[childIndex]; parentIndex = childIndex; childIndex = 2 * parentIndex + 1; } this.queue[parentIndex] = temp; } }
编程题:请使用vue或者react实现断点续传 todo
```ts
实现算法:447. 回旋镖的数量
点与点的坐标值
之间相减平方。((x1 - x2)^2 + (y1 - y2)^2)var numberOfBoomerangs = function(points) {
let count = 0;
for(let i = 0; i < points.length; i++) {
const m = new Map();
for(let j = 0; j < points.length; j++) {
const [x1,y1] = points[i];
const [x2,y2] = points[j];
const distance = Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2);
const historyDistance = m.get(distance) || 0
m.set(distance, historyDistance + 1);
}
for(let [_, times] of m.entries()) {
count += times * (times - 1);
}
}
return count
};
编程题:实现类型体操Trim
type Ident = ' ' | '\t' | '\n'
type Trim<T extends string> = T extends `${Ident}${infer TL}`
? Trim<TL>
: T extends `${infer TR}${Ident}`
? Trim<TR>
: T;
实现算法:3. 无重复字符的最长子串
// 版本1
var lengthOfLongestSubstring = function(s) {
const set = new Set(), len = s.length;
let pointer = -1, max = 0;
for(let i = 0; i < len; i++) {
if(i !== 0) set.delete(s[i - 1]);
// 判断是否到最后一个字符,如果没到则看有没重复字符
while(pointer + 1 < len && !set.has(s[pointer + 1])) {
pointer++;
set.add(s[pointer]);
}
max = Math.max(max, set.size);
}
return max;
};
// 版本2 var lengthOfLongestSubstring = function(s) { const set = new Set(), len = s.length; let pointer = 0, max = 0; for(let i = 0; i < len; i++) { if(i !== 0) set.delete(s[i - 1]); while(pointer < len && !set.has(s[pointer])) { set.add(s[pointer]); pointer++; } max = Math.max(max, set.size); } return max; }
### 思路二:left、right的while循环双指针滑动窗口
- 大致思路与for循环类似,双指针滑动窗口
- 区别1:可读性更高
- 区别2:right每次都要进行一次计算,for循环只会在右侧边界出现重复时进行max计算
```ts
var lengthOfLongestSubstring = function(s) {
const set = new Set(), len = s.length;
let left = 0, right = 0, max = 0;
while(right < len) {
if(set.has(s[right])) {
set.delete(s[left]);
left++;
continue;
}
set.add(s[right]);
right++;
max = Math.max(max, right - left);
}
return max;
}
实现算法:30. 串联所有单词的子串
var findSubstring = function(s, words) {
const len = s.length;
const wordSize = words[0].length;
const wordTotalLen = wordSize * words.length;
const ans = [];
const wordMap = words.reduce((obj, word) => {
obj[word] = (obj[word] || 0) + 1;
return obj
}, {})
for(let i = 0, actualLen = len - wordTotalLen; i <= actualLen; i++) {
const tempMap = { ...wordMap };
let count = words.length;
for(let j = i; j < i + wordTotalLen; j += wordSize) {
const word = s.slice(j, j + wordSize);
if(!(word in tempMap) || tempMap[word] <= 0) break;
tempMap[word]--;
count--;
}
if(count === 0) ans.push(i);
}
return ans;
};
编程题:手写vuex新版和老版 todo
实现算法:Delete Sublist to Make Sum Divisible By K
class Solution {
solve(nums, k) {
if(!nums.length) return -1;
let target = 0;
target = nums.reduce((a,b) => a+b) % k;
if (target == 0) return 0;
const map = new Map();
map.set(0,0);
let pos = 0, now = 0, ans = nums.length;
for(let num of nums) {
pos++;
now = (now + num) % k;
if(map.has((now + k - target) % k)) {
ans = Math.min(ans, pos - map.get((now + k - target) % k))
}
map.set(now, pos);
}
return ans === nums.length ? -1 : ans;
}
}
编程题:实现类型体操 Partial
interface Demo {
a: string,
b: number
}
// bad type Exclude<T, K> = keyof T extends K ? never : keyof T; Exclude<Demo, 'a'>
// goods type Exclude<T, K> = T extends K ? never : T; Exclude<keyof Demo, 'a'>
5. 最后进行类型合并
```ts
type Merge<T> = { [K in keyof T]: T[K] };
type Exclude<T, K> = T extends K ? never : T;
type Include<T, K> = T extends K ? T : never;
type PartialByKeys<T, K = keyof T> = { [ k in Exclude<keyof T, K> ]: T[k]} & { [ k in Include<keyof T, K> ]?: T[k] }
type Merge<T> = { [ k in keyof T]: T[k] };
type Include<T, K> = T extends K ? T : never;
type Exclude<T, K> = T extends K ? never : T;
type Pick<T, K extends keyof T> = { [ k in K ]: T[k] };
type Omit<T, K> = Pick<T, Exclude<keyof T, K>>;
type Partial<T, K> = Merge<Omit<T, K> & { [ k in keyof Include<keyof T, K> ]?: T[k] }>
实现算法:876. 链表的中间结点
var middleNode = function(head) {
let curr = 0, len = 0, node = head;
while(node) {
len++;
node = node.next;
}
const mid = Math.floor(len/2);
node = head;
while(curr < mid) {
curr++;
node = node.next;
}
return node;
};
思路二:
var middleNode = function(head) {
let node = head;
const arr = [];
while(node) {
arr.push(node);
node = node.next;
}
return arr[Math.floor(arr.length / 2)]
};
编程题:简单实现双向绑定Two-way binding
// 实现model满足下面的逻辑
const input = document.createElement('input')
const state = { value: 'BFE' }
model(state, input)
console.log(input.value) // 'BFE'
state.value = 'dev'
console.log(input.value) // 'dev'
input.value = 'BFE.dev'
input.dispatchEvent(new Event('change'))
console.log(state.value) // 'BFE.dev'
type State = {value: string};
function model(state: State, element: HTMLInputElement) {
Object.keys(state).forEach((_key: string) => {
const key = _key as keyof State ;
element[key] = state[key];
})
// your code here
defineProperty(state, 'value', null, (newVal: any) => {
element.value = newVal;
});
element.addEventListener('change', () => {
state.value = element.value;
})
}
function defineProperty(obj: HTMLInputElement | Record<string, any>, key: string, getter: Function | null, setter: Function | null) {
let value: any;
Object.defineProperty(obj, key, {
get: () => {
getter && getter(value);
return value;
},
set: (newVal: any) => {
setter && setter(newVal);
value = newVal;
}
})
}
实现算法:26. 删除有序数组中的重复项
var removeDuplicates = function(nums) {
const len = nums.length;
let slow = 0, fast = 1;
while(fast < len) {
if(nums[fast] !== nums[fast-1]) {
slow++;
nums[slow] = nums[fast];
}
fast++;
}
// 索引转长度
return slow + 1;
};
编程题:实现类型体操OmitThisParameter
function foo(this: {a: string}) {}
foo() // Error
const bar = foo.bind({a: 'BFE.dev'})
bar() // OK
type Foo = (this: {a: string}) => string
type Bar = MyOmitThisParameter<Foo> // () => string
() => R
函数,否则返回never
type MyOmitThisParameter<T> = T extends (...args: any[]) => infer R ? () => R : never;
实现算法:35. 搜索插入位置
var searchInsert = function(nums, target) {
const len = nums.length;
let left = 0, right = len - 1, ans = len;
while(left <= right) {
const mid = Math.floor((right - left) / 2) + left;
if(nums[mid] < target) {
left = mid + 1;
continue;
}
right = mid - 1;
ans = mid;
}
return ans;
};
编程题:实现React useCallback原理
function _useCallback() {
let lastFn: () => void, lastDeps: DependencyList;
return function (fn: () => void, deps: DependencyList) {
if(lastDeps) {
const notSame = deps.some((item: unknown, i: number) => {
console.log(item, deps[i], 1111)
return item !== lastDeps[i]
});
if(notSame) {
lastFn = fn;
lastDeps = deps;
}
return lastFn;
}
lastFn = fn;
lastDeps = deps;
return lastFn;
}
}
const useCallback = _useCallback();
实现算法:239. 滑动窗口最大值
queue[0] < i - k
var maxSlidingWindow = function(nums, k) {
const result = [];
// anchor1: 单调递减普通队列,用于存储nums索引,存储规则:根据nums值单调递减存储nums
const queue = [];
// 取前3个值的最大值,因为必须跑到3才会出现第一个result,为了保证可读性,所以单独处理
for(let i = 0; i < k; i++) {
// anchor3: 判断队列最后记录的值是否小于当前值nums[i],小于则删除last值
while(queue.length && nums[getArrLastVal(queue)] < nums[i]) queue.pop();
queue.push(i); // 无论如何新值索引总会被记录
}
result.push(nums[queue[0]]);
// 从k开始往后取
for(let i = k, len = nums.length; i < len; i++) {
// anchor2: 先判断queue中有没超出k的值,要始终保持k长度的窗口
if(queue[0] <= i - k) queue.shift();
// anchor3: 如果没有超出,则清除比nums[i]小的值
while(queue.length && nums[getArrLastVal(queue)] < nums[i]) queue.pop();
queue.push(i);
// 除了前三位,后续每移动一次都要得到一个值
result.push(nums[queue[0]]);
}
return result;
};
function getArrLastVal(arr) { return arr[arr.length - 1]; }
编程题: 实现React useMemo原理
### 思路:
- useMemo作用是固化函数返回值,并根据依赖项更新。
- 上下文:fn为`useMemo(fn, deps)`传入的函数`fn`,result为`result = useMemo(fn, deps)`的返回值,deps为`依赖列表`
- 核心思路与useCallback相似,缓存依赖列表`deps`与函数返回值`fn()`(useCallback是函数地址)
- 缓存使用map + 按序的key进行缓存,并且在每次执行完所有useMemo后,把key清零,方便下次update重新计算(不严谨)
- 如果last依赖项与新依赖项不一致,执行函数并返回新的返回值
- 如果一致,返回历史值,不执行,使用以前的result
```ts
function _useMemo() {
let timer: NodeJS.Timeout, key: number = -1;
const m = new Map();
return function(fn: (...args: any[]) => any, deps: DependencyList) {
key++;
const currKey = key;
const { deps: lastDeps } = m.get(currKey) || {};
timer && clearTimeout(timer);
timer = setTimeout(() => { key = -1 });
if(lastDeps!) {
const isChanged = deps.some((item, i) => item !== lastDeps[i])
if(isChanged) {
m.set(currKey, { result: fn(), deps });
}
return m.get(currKey).result;
}
m.set(currKey, { result: fn(), deps });
return m.get(currKey).result;
}
}
const useMemo = _useMemo();
实现算法:997. 找到小镇的法官
编号
, 信任人
],可以做一个出入度的图模型var findJudge = function(n, trust) {
const inDegress = new Array(n + 1).fill(0)
const outDegress = new Array(n + 1).fill(0)
for(let edge of trust) {
const [x, y] = edge;
++inDegress[y];
++outDegress[x];
}
for(let i = 1; i <= n; i++) {
if(inDegress[i] === n - 1 && outDegress[i] === 0) return i;
}
return -1;
};
编程题:实现React useState原理
type UseState = <T>(arg: T) => [T, (newState: T) => void];
function _useState(): UseState {
const stateMap: Map<number, any> = new Map();
let key: number = 0;
let timer: NodeJS.Timeout;
return function<T>(initState: T) {
const state: T = stateMap.has(key) ? stateMap.get(key) : initState;
const currKey: number = key;
const setState = (newState: T) => {
stateMap.set(currKey, newState);
key = 0;
timer && clearTimeout(timer);
timer = setTimeout(update)
}
key++;
return [state, setState];
}
}
const useState = _useState();
实现算法:886. 可能的二分法
var possibleBipartition = function(n, dislikes) {
// 先建图
const graph = new Array(n + 1).fill(0).map(() => []);
for(let edge of dislikes) {
const [ self, other ] = edge;
graph[self].push(other);
graph[other].push(self);
}
// 访问图节点记录表,染色节点记录表
const visited = new Array(n + 1).fill(false);
const colored = new Array(n + 1).fill(false);
let ok = true;
// 开始逐个节点遍历
const traverse = (graph, self) => {
if(!ok) return;
// 标记已访问,防止重复运行
visited[self] = true;
// 访问对立的图节点,即连了边的节点
for(let other of graph[self]) {
// 如果已经被访问过,则判断是否与自己的颜色一致,一致代表非二分图
if(visited[other]) {
if(colored[self] === colored[other]) ok = false;
continue; // continue是为了跑完所有节点,如果单纯为了判断二分图,可以直接break
}
// 未被访问过,需要染色且访问被连线的节点(与自己链接点颜色必须对立,否则不满足二分图)
colored[other] = !colored[self];
// 顺着节点走
traverse(graph, other);
}
}
// 逐个遍历,如果当前的i节点被访问过,则直接跳过
for(let i = 1; i <= n; i++) {
if(!visited[i]) traverse(graph, i);
}
// 返回是否能成二分图
return ok;
};
编程题:请使用你熟悉的语言或技术或框架实现一个autocomplete组件 todo
todo 实现算法:1203. 项目管理 【前置知识】 图论 拓扑排序 BFS & DFS
编程题: 实现Object.assign原理
function objectAssign(...objList) {
const [firstObj, ...restObj] = objList;
for(let obj of restObj) {
Object.keys(obj).forEach(key => {
firstObj[key] = obj[key];
});
}
return firstObj
}
objectAssign({a: 1}, {a:2, b:1}, {a:3,c:2})
// {a: 3, b: 1, c: 2}
实现算法:69. x 的平方根
编程题:实现_.chunk()
chunk([1,2,3,4,5], 1)
// [[1], [2], [3], [4], [5]]
chunk([1,2,3,4,5], 2)
// [[1, 2], [3, 4], [5]]
chunk([1,2,3,4,5], 3)
// [[1, 2, 3], [4, 5]]
chunk([1,2,3,4,5], 4)
// [[1, 2, 3, 4], [5]]
chunk([1,2,3,4,5], 5)
// [[1, 2, 3, 4, 5]]
实现算法:278. 第一个错误的版本
编程题:实现parseToMoney
实现千位分隔符
// 保留三位小数
parseToMoney(1234.56); // return ‘1,234.56’
parseToMoney(123456789); // return ‘123,456,789’
parseToMoney(1087654.321); // return ‘1,087,654.321’
实现算法:三重反转
给定一个整数列表 nums
,返回满足 nums[i] > nums[j] * 3
的对 i < j
的数量。
约束:
n ≤ 100,000
其中 n
是 nums
的长度
编程题:返回DOM tree中”左边“的元素
给定一个DOM tree和目标节点,请找出其左边的节点。
就像上图那样,绿色<a/>
的左边是蓝色的<button/>
。注意它们并不一定需要有共同的父节点。
如果没有的话,返回null
。
你的代码的时间和空间复杂度是多少?
实现算法:最小光半径
给你一个整数列表,代表一维线上房屋的坐标。您有 3
盏路灯,您可以将它们放在坐标线上的任何位置,坐标 x
处的一盏灯照亮了 [x - r, x + r]
中的房屋,包括在内。返回所需的最小 r
,以便我们可以放置 3
盏灯并且所有的房子都被点亮。
约束
n ≤ 100,000
其中 n
是 nums
的长度
实现算法:第K对距离
给定一个整数列表 nums
和一个整数 k
,返回 nums
中每对元素 (x, y)
的第 k
个(0 索引)最小 abs(x - y)
。注意 (x, y)
和 (y, x)
被认为是同一对。
约束:
n ≤ 100,000
其中 n
是 nums
的长度
Day - 01
完成算法:https://leetcode-cn.com/problems/add-to-array-form-of-integer/submissions/
思路:
1. 数组的单位计算处理
2. k值的单位计算处理
3. 进位数处理
4. 最高位数进1处理
5. 如何保证num和k的值被加完
优化版:
思路:
以上3点做加法循环,直到k = 0且num遍历完
实现柯里化:
思路