分享20个遇到的大厂算法题和手写题
站长
· 阅读数 13
前言
下面20道题是笔者最近在面试里遇到的和在牛客看到的，希望对大家有帮助~
1. LRU算法（快手）
var LRUCache = function (capacity) {
this.catch = new Map() //初始化map数据结构
this.capacity = capacity //容量
};
LRUCache.prototype.get = function (key) {
if (this.catch.has(key)) { //map中有这个元素
let value = this.catch.get(key); //调用map的get方法获取元素
//更新key=>value
this.catch.delete(key); //删除之前的元素
this.catch.set(key, value); //将新获取的相同的元素以键值对推入map中
return value //返回关键字的值
}
return -1 //map中没有这个元素返回-1
};
LRUCache.prototype.put = function (key, value) {
if (this.catch.has(key)) { //有这个元素
this.catch.delete(key); //删除
}
//判断有没有达到存储的阈值
if (this.catch.size >= this.capacity) {
//移除谁 再放新值
//m.keys().next()拿到首位的键值对
this.catch.delete(this.catch.keys().next().value)
}
this.catch.set(key, value);
};
//验证
let lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
实现思路：
- 构造函数内定义一个
Map数据类型存放catch和capacity设置最大存放数 put方法是进行存放，如果已经存放了这个key和value，那么进行删除，再判断有没有超过阈值，如果超出了，进行删除首个元素，再存放，没有超过，那么进行直接存放get方法是进行catch的获取，如果有这个元素，那么进行先删除后存放，如果没有，直接返回-1表示不存在
2. 版本号排序（字节）
const versions = ["1.2.1", "1.0.2", "1.3.2", "1.1", "1.2", "1", "1.10.0"];
// 升序排序
versions.sort(compareVersion);
console.log(versions); // ["1", "1.0.2", "1.1", "1.2", "1.2.1", "1.3.2", "1.10.0"]
// 降序排序
versions.sort((a, b) => compareVersion(b, a));
console.log(versions); // ["1.10.0", "1.3.2", "1.2.1", "1.2", "1.1", "1.0.2", "1"]
const compareVersion = function(version1, version2){
const arr1 = version1.split('.');// 得到的是字符串数组
const arr2 = version2.split('.');
// 获取最大长度，进行比较
const len = Math.max(arr1.length, arr2.length);
for(let i = 0; i < len; i++){
// 要进行长度的比较判断
const num1 = i > arr1.length ? 0 : parseInt(arr1[i]);
const num2 = i > arr2.length ? 0 : parseInt(arr2[i]);
if(num1 > num2){
return 1;
}else if(num1 < num2){
return -1;
}
}
return 0;
}
实现思路：
- 进行sort方法的重构，升序还是降序，调换参数的顺序即可
3. 最长公共前缀（快手）
function longestCommonPrefix(strs){
if(strs.length === '') return '';
// 先赋值，后不断缩小
const prefix = strs[0];
for(let i = 0; i < strs.length; i++) {
while(strs[i].indexOf(prefix) !== 0){
prefix.slice(0, prefix.length - 1);
if(prefix = '') return '';
}
}
return prefix;
}
- 关键在于
String.prototype.indexOf()的理解，如果在其中，则返回0
4.大数相加（快手）
function addStrings(num1, num2){
let i = num1.length - 1; // 初始化指向 num1 的末位的指针 i
let j = num2.length - 1; // 初始化指向 num2 的末位的指针 j
let carry = 0; // 初始化进位为 0
let result = ''; // 初始化结果字符串为空字符串
while (i >= 0 || j >= 0 || carry !== 0) { // 当还有数字或者存在进位时，继续执行循环
// parseInt() 函数来将字符串转换为数字
const digit1 = i >= 0 ? parseInt(num1[i]) : 0; // 取出 num1 当前位上的数字，如果越界了就用 0 补齐
const digit2 = j >= 0 ? parseInt(num2[j]) : 0; // 取出 num2 当前位上的数字，如果越界了就用 0 补齐
const sum = digit1 + digit2 + carry; // 计算当前位上的数字和
result = (sum % 10).toString() + result; // 将该位上的数字插入到结果字符串的最前面
carry = Math.floor(sum / 10); // 计算进位
i--; // 将指针 i 向前移动一位
j--; // 将指针 j 向前移动一位
}
return result; // 返回结果字符串
}
思路：
- 处理两个字符串相加后的结果
- 需要两个指针i,j进行指向，对每一位的字符进行加减，carry变量进行处理进位，res存储结果
- 进入循环，当存在进位或者指针存在则继续循环
- 拿到字符(可能已经超出了，给0)
- 进行相加并且要带上上次的进位数字
- 将个位数进行插入到前面（记得toString()）
- 更新进位数，移动指针
5.手撕开平方（商汤科技）
function sqrt(s, precision = 16){
if(s === 0 || s === 1){
return s;
}
// 计算精度值
const percisionValue = Math.pow(10, -precision)
// 二分查找进行匹配
let low = 0;
let hight = s;
while(hight - low >= precisionValue){
let mid = (hight + low) / 2;
if(mid * mid === s){
// 当可以开整数平方时
return mid;
}else if(mid * mid < hight){
hight = mid;
}else {
low = mid;
}
}
// 当无法开整数平方时
return low.toFixed(precision);
}
实现关键：
- 计算精度：Math.pow(10, -n)
- 处理小数：.toFixed(n)
6.前k个频率高的元素（滴滴）
const toKFrequent = function(nums, k){
const Map = new Map();
for(let num of nums){
Map.set(num, (Map.get(num) || 0) + 1)
}
// 插入桶里
const bucket = [];
for(let [key, value] of Map){
if(!bucket[value]){
bucket[value] = [];
}
bucket[value].push(num);
}
// 从桶里拔出来
const res = [];
for(let i = bucket.length - 1; i > 0 && res.length < k; i++){
if(bucket[i]){
res.push(...bucket[i]);
}
}
return res;
}
7.三数之和（字节）
function threeSum(nums) {
const result = [];
if (nums.length < 3) {
return result;
}
nums.sort((a, b) => a - b); // 排序
for (let i = 0; i < nums.length - 2; i++) {
if(nums[i] > 0) return result;
if (i > 0 && nums[i] === nums[i - 1]) {
continue; // 跳过重复的元素
}
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
left++;
right--;
while (left < right && nums[left] === nums[left - 1]) {
left++; // 跳过重复的元素
}
while (left < right && nums[right] === nums[right + 1]) {
right--; // 跳过重复的元素
}
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
8.用栈实现队列
function MyQueue(){
// 定义的两个栈
this.stackIn = [];
this.stackOut = [];
}
// 入列
MyQueue.prototype.push = function(x){
this.stackIn.push(x);
}
// 出列
MyQueue.prototype.pop = function(x){
// 检测出栈的内容
const size = this.stackOut.length;
if(size) return this.stack.pop();
while(this.stackIn.length){
// 把入栈的元素都放入出栈里面
this.stackOut.push(this.stackIn.pop());
}
// 返回出栈的元素
return this.stackOut.pop()
}
// 获取列首位置
MyQueue.prototype.peek = function(){
const x = this.pop();
this.stackOut.push(x);
return x;
}
// 判断是否为空
MyQueue.prototype.empty(){
return !this.stackIn.length && !this.stackOut.length;
}
9.用队列实现栈
function MyStack(){
this.queue = [];
}
// 入栈
MyStack.prototype.push = function(){
this.queue.push(x);
}
// 出栈
MyStack.prototype.pop = function(){
let size = this.queue.length;
// 倒转过来
while(size-- > 1){
this.queue.push(this.queue.shift())
}
return this.queue.shift();
}
// 拿到栈顶元素
MyStack.prototype.top = function() {
// 弹出再压进去
const x = this.pop();
this.queue.push(x);
return x;
};
MyStack.prototype.empty = function() {
return !this.queue.length;
};
10.队列的最大值（蔚来）
class MaxQueue{
constuctor(){
this.queue = [];
this.max = [];
}
enqueue(el){
this.queue.push(el);
while(this.max.length && this.max[this.length - 1] < el){
this.max.pop()
}
this.max.push(el);
}
dequeue(){
if(this.queue.length === 0) return -1;
const el = this.queue.shift();
if(el === this.max[0]){
this.max.shift();
}
return el;
}
getMax(){
return max.length > 0 ? max[0] : -1
}
}
11.千分位分隔（字节）
// input：-123456.123
// output：-123,456.123
function thousandSeparator(n) {
let nStr = n.toString();
let [integerPart, decimalPart = ''] = nStr.split('.');
if(integerPart[0] === '-'){
integerPart = integerPart.slice(1);// 切割索引为1后面的字符串，并返回，slice是不会改动原来字符串的
}
// 定义变量，进行存储添加,后的结果
let formattedIntegerPart = '';
// 进行反转添加
for (let i = integerPart.length - 1, count = 0; i >= 0; i--, count++) {
if (count === 3) {
formattedIntegerPart = ',' + formattedIntegerPart;
count = 0;
}
formattedIntegerPart = integerPart[i] + formattedIntegerPart;
}
return (n < 0 ? '-' : '') + formattedIntegerPart + (decimalPart ? '.' + decimalPart : '');
}
12.带并发限制的异步调度器Scheduler（百度）
// JS实现一个带并发限制的异步调度器Scheduler
// 保证同时运行的任务最多有两个
// 完善代码中Scheduler类
// 使得以下程序能正确输出
class Scheduler {
constructor() {
this.count = 2
this.queue = []
this.run = []
}
add(task) {
}
}
const timeout = (time) => new Promise(resolve => {
setTimeout(resolve, time)
})
const scheduler = new Scheduler()
const addTask = (time, order) => {
scheduler.add(() => timeout(time)).then(() => console.log(order))
}
addTask(1000, '1')
addTask(500, '2')
addTask(300, '3')
addTask(400, '4')
// output: 2 3 1 4
// 一开始，1、2两个任务进入队列
// 500ms时，2完成，输出2，任务3进队
// 800ms时，3完成，输出3，任务4进队
// 1000ms时，1完成，输出1
// 1200ms时，4完成，输出4
解答：
class Scheduler {
constructor() {
this.count = 0
this.queue = []
}
add(task) {
return new Promise((resolve) => {
const runTask = async() => {
this.count++;
await task();
reslove();// 任务完成，执行下面的
this.count--;
if(this.queue.length > 0){
const nextTask = this.queue.shift();
nextTask();
}
};
if(this.count < 2){
runtask();
}esle{
this.queue.push(runTask);
}
})
}
}
13.BFS和DFS实现document.querySelectAll('.a')(百度)
DFS:
const dfsFindNode = () => {
const res = [];
if(node && node.nodeType === 1){ // 判断当前节点是否为元素节点
if(/\ba\b/.test(node.className)){
res.push(node);
}
const children = node.children;// 获取当前节点的子节点元素列表
for(let i = 0; i < children.length; i++){
const child = children[i];
res.push(...dfsFindNode(child))
}
}
return res;
}
const Nodes = dfsFindNode(document.body); // 查找 document.body 下所有 class 为 a 的元素节点
BFS:
function bfsFindNode(node) {
const res = []; // 存放符合条件的节点的数组
const queue = [node]; // 定义一个队列，初始值为根节点
while (queue.length > 0) { // 当队列不为空时进行遍历
const cur = queue.shift(); // 取出队头元素，并作为当前处理的节点
if (cur.nodeType === 1 && /\ba\b/.test(cur.className)) { // 判断当前节点是否为元素节点，并且其 class 属性是否包含 a
res.push(cur); // 如果符合条件，则将当前节点加入结果数组中
}
const children = cur.children; // 获取当前节点的所有子元素
for (let i = 0; i < children.length; i++) { // 遍历每个子元素
const child = children[i];
queue.push(child); // 将子元素加入队列尾部，等待被处理
}
}
return res; // 返回所有符合条件的节点组成的数组
}
const Nodes = bfsFindNode(document.body); // 查找 document.body 下所有 class 为 a 的元素节点
14.数组去重(百度)
// api方法
const arr = [1,2,2,6,6]
const uniqueArr = [...new Set(arr)];
const uniqueArr = arr.filter((index, item) => {
return arr.indexOf(item) === index
})
// 原生实现
function deduplicateArray(arr) {
const res = [];
for(let i = 0;i < arr.length;i++){
let isDuplicate = false;// 标记是否重复
for(let j = 0; j < arr.length; j++){
if(arr[i] === res[j]){
isDuplicate = ture;
break;
}
}
if(!isDuplicate){
res.push(arr[i]);
}
}
return res;
}
15.两数相加（快手）
本地idle实现所有功能：
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
function arrayToLinkedList(arr) {
if (!Array.isArray(arr)) {
console.log("Input is not an array.");
return null;
}
if (arr.length === 0) {
console.log("Array is empty.");
return null;
}
let head = new Node(arr[0]);
let currentNode = head;
for (let i = 1; i < arr.length; i++) {
const newNode = new Node(arr[i]);
currentNode.next = newNode;
currentNode = newNode;
}
return head;
}
var addTwoNumbers = function (l1, l2) {
// 创建虚拟头结点
const dummy = new Node(0);
let cur = dummy;
let carry = 0;
while (l1 || l2) {
const value1 = l1 ? l1.value : 0;
const value2 = l2 ? l2.value : 0;
// 相加
let sum = value1 + value2 + carry;
carry = Math.floor(sum / 10);
sum %= 10;
cur.next = new Node(sum);
cur = cur.next;
if (l1) l1 = l1.next;
if (l2) l2 = l2.next;
}
if (carry) {
cur.next = new Node(carry);
}
return dummy.next;
}
- 最长回文子序列 （小米）
/**
* @param {string} s
* @return {number}
*/
const longestPalindromeSubseq = (s) => {
const strLen = s.length;
let dp = Array.from(Array(strLen), () => Array(strLen).fill(0));
for(let i = 0; i < strLen; i++) {
dp[i][i] = 1;
}
for(let i = strLen - 1; i >= 0; i--) {
for(let j = i + 1; j < strLen; j++) {
if(s[i] === s[j]) {
dp[i][j] = dp[i+1][j-1] + 2;
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][strLen - 1];
};
- 实现 promise.all （滴滴、蔚来）
const promiseAll = (promises) => {
if(typeof promises[Symbol.interator] === 'function'){
let count = 0;
let result = [];
return new Promise((reslove, reject) => {
for(const [index, item] of promises){
// 保存每次执行的结果
Promise.resolve(item).then((res) => {
result[index] = res;
count++;
if(count === promises.lenth){
return reslove(result);
}
}).catch(err => {
reject(err);
})
}
})
}
}
- 实现 Promise.allSettled （快手）
function allSettled(promises){
return new Promise((reslove, reject) => {
const result = [];
let count = 0;
if(promises.length === 0){
resolve(result);
return;
}
promises.forEach((promise, index) => {
Promise.resolve(promise)
.then((value) => {
result[index] = { status: 'fulfilled', value }
})
.catch((reson) => {
result[index] = { status: 'rejected', reason }
})
.fianlly(() => {
count++;
if(count === promise.length){
resolve(results)
}
})
})
})
}
- call、apply、bind（快手）
// call 方法的参数：对象，多个参数
Function.prototype.call = function(context, ...args){
if(typeof this !== 'function')
return new TypeError('error');
// 确保不为空
context = context || window;
const fn = Symbol('fn');
context[fn] = this;
const res = context[fn](...args);
delete context[fn];
return res;
}
// apply方法的参数：对象，一个参数数组
Function.prototype.apply = (context, args) => {
if(typeof this !== 'function'){
return new TypeError('error');
}
context = context || window;
const fn = Symbol('fn');
context[fn] = this;
const res = context[fn](...args);
delete context[fn]
return res;
}
// bind 是会返回一个函数,考虑到可能多次调用，那么就不进行删除
Function.prototype.bind = function(target, ...outArgs) {
if(typeof this !== 'function'){
return new TypeError('error');
}
target = target || window;
const fn = Symbol();
target[fn] = this;
return function(...moreArgs) {
const res = target[fn](...outArgs, ...moreArgs);
return res;
}
}
- 将下划线或中划线命名转换为驼峰命名（字节）
function toCamelCase(str){
// 首先对于一个字符串的下划线或者中划线进行split(/[-_]/)分割成数组
let words = str.split(/[-_]/);
let res = str[0];// 给个初始值
for(let i = 1; i < words.length; i++){// 从 i = 1开始遍历即可
// 拿到每个单词的第一个值，后面的切一刀连起来
// toUpperCase()
res += word[i][0].toUpperCase() + word[i].slice(1);
}
return res;
}
转载自:https://juejin.cn/post/7273775338421452834