关于前端:前端面试资料整理算法篇

29次阅读

共计 9071 个字符，预计需要花费 23 分钟才能阅读完成。

排序与查找

排序

参考

稳固排序：两个相等的记录，排序前 A,A’，排序后依然是 A,A’
不稳固排序：与下面构造相斥

10 个常见的排序：

冒泡排序
稳固排序，O(n)

function bubble(array) {if (typeof array === 'object' && array.length) {for (let i = 0; i < array.length; i ++) {for (let j = i; j < array.length - i - 1; j++) {if (array[j] > array[j + 1]) {let tmp = array[j]
                    array[j] = array[i + 1]
                    array[j+1] = tmp;
                }
            }
        }
    }
}

快排

  1. 最左边为基值
  2. pos 记录指标地位
  3. 一一遍历，当遇到索引为 i 的值小于基值时，产生 i 与 pos 为产生替换。
  4. 此时 pos 为基值的正确地位，以 pos 划分，右边是小于基值的，左边是大于基值的。
function quick(array, left = 0, right = array.length - 1) {if (left < right) {
    // 标识基数正确的地位
    let pos = left - 1;
    // 基数
    const rightVal = array[right];

    for (let i = left; i <= right; i++) {if (array[i] <= rightVal) {
        pos++;

        // 如果地位正当，是本人替换本人，如果不地位不合理，pos 记录的是替换的地位
        [array[i], array[pos]] = [array[pos], array[i]]
      }
    }
    quick(array, left, pos -1)
    quick(array, pos + 1, right)
  }
  return array
}
quick([2, 1, 4, 5, 3])

PS. 实现一个 quickSortByDESC

抉择排序
简略，了解就是，找到后放到相应地位，而后再次反复

function select(array) {for (let i = 0; i < array.length; i++) {
    min = i;
    for (let j = i; j < array.length -j; j++) {if (array[min] > array[j]) {min = j;}
      [array[min], array[i]] = [array[i], array[min]];
    }
  }
}

插入排序

归并排序
采纳分治法

function mergeSort(array) {if (array.length < 2) {return array;}

  const mid = Math.floor(array.length / 2);
  const left = array.slice(0, mid);
  const right = array.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {const result = [];
  
  while(left.length && right.length) {if (left[0] > right[0]) {result.push(right.shift());
    } else {result.push(left.shift());
    }
  }

  while(left.length) {result.push(left.shift());
  }

  while(right.length) {result.push(right.shift());
  }

  return result;
}

mergeSort([23, 5, 6, 1, 75, 7])

查找

参考

7 个常见的查找：

1. 程序查找

略

2. 二分查找

function search(array, target) {if (!array.length) {return -1;}
    let left = 0;
    let right = array.length -1;


    while(left <= right) {let mid = Math.floor(((right - left) / 2) + left);

        if (array[mid] === target) {return mid;}
        if (array[mid] < target) {left = mid + 1} else if (array[mid] > target) {right = mid -1}
    }
    return -1;
}

3. 差值查找
待补充

4. 斐波那契查找
待补充

5. 树表查找
待补充

6. 分块查找
待补充

7. hash 查找
待补充

算法题

数组

数组去重

// Set

// 暴力，for 双循环

// 暴力，用 Array api 代替，[].indexOf，[].includes，[].fliter

// 排序 + 双指针

// 转化成对象，存在向字符串转化的问题。

数组交加
待补充

平铺数组 flat

function flat (array) {
    // 健壮性判断
    let r = []
    array.forEach((item) => {if (item.length){r = r.concat(flat(item))
        } else {r.push(item)        
        }
    }) 
    return r;

    // es6
    // return array.join().split(',')
    // 
    // array.reduce 也能够
}

console.log(flat([1, [2], [[3]], 4, [5]]))

合并两个有序的数组

给出两个有序的整数数组 A 和 B，将数组 B 合并到 A，变成一个有序数组。假如 A 数组有足够的空间寄存 B 数组元素，A 和 B 中初始元素数别离为 m 和 n


function mergeArray(arrayA, arrayB) {
  // 健壮性查看：数据类型，数组长度
  const m = arrayA.length;
  const n = arrayB.length;
  let posA = 0;
  let posB = 0;
  let array = [];
  for (let i = 0; i < Math.max(m, n); i++) {if (arrayA[i] === undefined || arrayB[i] === undefined) {break;}
    if (arrayA[posA] >= arrayB[posB]) {array.push(arrayB[posB++])
      array.push(arrayA[posA++])
    } else {array.push(arrayA[posA++])
      array.push(arrayB[posB++])
    }
  }
  if (posB < n) {array = array.concat(arrayB.slice(posB, n))
  }
  if (posA < m) {array = array.concat(arrayA.slice(posA, m))
  }
  return array;
}
const A = [1, 3, 5, 7, 9];
const B = [2, 4]
mergeArray(A, B)

给出一组数字，给出所有数字的所有排列

例如输出 [1, 2, 3]，输入 [[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2]]，按数字在数组中的地位为排列根据，按字典排序输入

// 回溯
function permute(array) {
    const length = array.length;

    if (length === 0) {return array;}

    
    const result = []; // 后果数组 [[], ...]
    const used = []; // 曾经应用过的数组
    const path = []; // 以后生成的组合
    dfs(array, length, 0, path, used, result)
    return result
}

/**
 * dfs 深度优先遍历
 * @param  {array}  array   原始数组
 * @param  {number} len     原始数组长度，代表进行遍历
 * @param  {number} depth   以后遍历深度
 * @param  {array}  used 以后遍历的后果
 * @param  {array}  result     存储所有合乎的后果
 */
function dfs(array, len, depth, path, used, result) {if (depth === len) {result.push([].concat(path))
        return;
    }
    
    for (let i = 0; i < len; i++) {if (!used[i]) {path.push(array[i]);
            used[i] = true;

            dfs(array, len, depth + 1, path, used, result)

            // 回溯
            used[i] = false;
            path.pop();}
    }
}

permute([1, 2, 3])

数组之和为零

给你一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0？请你找出所有和为 0 且不反复的三元组。

留神：答案中不能够蕴含反复的三元组。

字符串

最长回文子串【双指针】

给你一个字符串 s，找到 s 中最长的回文子串。
输出：s = “babad”
输入：”bab”
解释：”aba” 同样是合乎题意的答案。

// 暴力，工夫复杂度  O(n^3) 空间复杂度 O(1)
function longestPalindrome(s) {if (s.length < 2) {return s;}

    let maxLength = 0;
    let begin = 0;
    for (let i = 0; i < s.length; i++) {for(let j = i; j < s.length; j++) {if (j - i + 1 > maxLength & validPalindromic(s, i, j)) {
                maxLength = j - i +1;
                begin = i
            } 
        }
    }
    return s.substring(begin, maxLength)
} 

// 验证是否回文
function validPalindromic(s, left, right) {while(left < right) {if (s[left++] != s[right--]) {return false;}
    }
    return true
}

longestPalindrome('babad') // bab
longestPalindrome('babaaaaa') // aa，有问题，应该是 aaaa

// 核心扩大算法，工夫复杂度  O(n^2) 空间复杂度 O(1)
function longestPalindrome(s) {if (s.length < 2) {return s;}
    const len = s.length;
    let start = 0;
    let end = 0;

    for (let i = 0; i < s.length; i++) {
        // 奇数对称
        let len1 = entendAroundCenter(s, i, i);
        // 偶数对称
        let len2 = entendAroundCenter(s, i, i+1);
        let len = Math.max(len1, len2);
        // 获取最长回文长度，大于目前起始位，更新，i 是核心位
        if (len > end - start && len1 > len2) {
            // 奇数
            start = i - ((len - 1) / 2);
            end = i + ((len - 1) / 2);
        } else if (len > end - start && len2 > len1) {
            // 偶数
            start = i - (len / 2);
            end = i + (len / 2);
        }
    }
    return s.substring(start, end + 1) // end + 1 是因为要蕴含 end 处
} 

// 由核心向外扩大
function entendAroundCenter(s, left, right) {
    // 开始扩散
    while(left > 0 && right < s.length && s[left] === s[right]) {
        left--;
        right++;
    }
    // right 和 left 多扩了 1 位
    return (right - 1) - (left + 1) + 1; // 合并计算 right - left -1;
}

longestPalindrome('babaaaaa')

无反复字符的最长子串【双指针】
滑动窗口，有反复的就右边出，左边进

var lengthOfLongestSubstring = function(str) {if (!str.length) return 0
    let tmpStr = ''   // 每次循环找到的不含反复字符的子字符串
    let maxStrLen = 0   // 最大不含反复字符的子字符串的长度
    let len = str.length   
    let left = 0  // 不含反复字符的子字符串的左游标
    for (let i = 0; i < len; i++) {if (tmpStr.indexOf(str[i]) !== -1) {left += (str.slice(left, i).indexOf(str[i]) + 1)
            continue
        }
        tmpStr = str.slice(left, i + 1)
        maxStrLen = Math.max(maxStrLen, tmpStr.length)
    }
    return maxStrLen
};

最长无反复子串

例如 abcabcbb 后果 abc

利用平移窗口

var lengthOfLongestSubstring = function(str) {if (!str.length) return 0
    let tmpStr = ''   // 每次循环找到的不含反复字符的子字符串
    let maxStrLen = 0   // 最大不含反复字符的子字符串的长度
    let len = str.length   
    let left = 0  // 不含反复字符的子字符串的左游标
    for (let i = 0; i < len; i++) {if (tmpStr.indexOf(str[i]) !== -1) {left += (str.slice(left, i).indexOf(str[i]) + 1)
            continue
        }
        tmpStr = str.slice(left, i + 1)
        maxStrLen = Math.max(maxStrLen, tmpStr.length)
    }
    return maxStrLen
};

动静布局

全副布局门路数

仅返回数即可。

输出 m = 3, n = 2
输入 3

var uniquePaths = function(m, n) {let dp = new Array(m)
    for(let i = 0; i < dp.length; i++) {dp[i] = new Array(n).fill(1)
    }

    for(let i = 1; i < dp.length; i++) {for(let j = 1; j < dp[0].length; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
};

uniquePaths(3, 2)

背包问题本

假如咱们有 5 个物品，分量别离为 2,2,4,6,3，背包总容量为 9 Kg。

最短门路

假如咱们有一个 n*n 的矩阵，矩阵中每个元素都是负数。

var shortestPath = function(array) {const len = array[0].length;

    for (let i = 1; i < len; i++) {for(let j = 1; j < len; j++) {array[i][j] += Math.min(array[i - 1][j], array[i][j - 1])
        }

    }
    return array[len - 1][len - 1];
}

shortestPath(
    [[1, 3, 5, 9],
        [2, 1, 3, 4],
        [5, 2, 6, 7],
        [6, 8, 4, 3]
    ]
)

其余

菲波那切数列

要求输出一个整数 n，输入菲波那切数列数列的第 n 项，第 0 项为 0，第 1 项为 1。

// 最耗性能的递归写法。function fibonacci(n) {if (n < 2) {return n;}
    return fibonacci(n-1) + fibonacci(n-2)
}


function fibonacci(n) {if (n < 2) {return n;}
    let a = 0; // 初始 0 位
    let b = 1; // 初始 1 位
    let c = 0; // fibonacci 数
    for (let i = 2; i <= n; i++) {
        c = a + b;
        // 不能间接用 i，会变成 c = 2i - 3
        a = b;
        b = c;
    }
    return c;
}

反转链表
参考

// 迭代法 空间复杂度：O(1) 工夫复杂度：O(n)
function reverseList(head) {if (!head || !head.next) {return head;}

  let prev = null;
  let cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return head;
}

// 尾递归 空间复杂度：O(n) 工夫复杂度：O(n)
// 从头节点开始，递归反转它的每一个节点，直到 null
function reversList(head) {if (!head || !head.next) {return head;}
  head = reverse(null, head)
  return read;
}

function reverse(prev, cur) {if (!cur) return prev;
  const next = cur.next;
  cur.next = prev
  return reverse(cur, next);
}

// 递归
// 依据 head.next 推入栈中，反复：next = head.next, head = stach.pop(), next.next = head, head.next = null, 跳出 head.next === null
function reversList(head) {if (!head || !head.next) {return head;}
  const next = head.next;
  const head = reversList(next);
  
  next.next = head;
  next.next = null;

  return head;
}

递归的逻辑图示

并行申请

未实现，未测试

const f = (url) => new Promise((resolve) => {console.log('f:', url)
  setTimeout(() => resolve({ code: 200}), 500)
})


// 并发管制
function createRequest(num){
  // 健壮性查看
  const queue = [];
  let count = 0; // 正在执行的申请数

  const create = (url, opitons) => () =>
    f(url, opitons).then((res) => {
      count++;
      return res
    }).catch(() => {// 保护个谬误队列}).finally(() => {
      count--;
      if (queue.length) {queue.shift()()}
    })

  

  return function(url, options) {const stack = create(url, options)
    // 排队
    if (count >= num) {queue.push(stack)
    } else {
      // 0, 1, 2
      return stack()}
  }
}

// ---->
// ---->
// ---->
//   ---->
//   ---->
const request = createRequest(3);


// 利用 webmessage 实现并发
request('/a').then((r) => console.log('res', r))
request('/b').then((r) => console.log('res', r))
request('/c').then((r) => console.log('res', r))
request('/e').then((r) => console.log('res', r))
request('/f').then((r) => console.log('res', r))

// -----

// 模仿 fetch
const f = (url) => new Promise((resolve) => {const time = Math.random() * 1000
    setTimeout(() => {console.log(url, time)
      resolve({time})
    }, time)
  })

function createlimitRequest(limit) {const waitQueue = [];
  let requestintCount = 0;
  const r = (url) => {
    requestintCount++;
    return f(url)
      .then((res) => res).finally(() => {if (waitQueue.length) {
          requestintCount++;
          return waitQueue.shift();}
      })
  }
  return function (url) {if (requestintCount > limit) {waitQueue.push(r)
    }
    return r(url)
  } 
}

const request = createlimitRequest(4);

function requestAll(urls) {const results = []
  let count = 0;
  return new Promise((resolve) => {urls.forEach((url, index) => 
      request(url).then((res) => {results[index] = res
      }).catch((err) => {results[index] = err
      }).finally(() => {
        count++;
        if (count === urls.length) {resolve(results)
        }
      })
    )
  })
}


requestAll([
  '/a',
  '/b',
  '/c',
  '/d',
  '/e',
  '/f',
])

还原 IP 地址

给定一个只蕴含数字的字符串，用以示意一个 IP 地址，返回所有可能从 s 取得的 无效 IP 地址。你能够按任何程序返回答案。

无效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：”0.1.2.201″ 和 “192.168.1.1” 是 无效 IP 地址，然而 “0.011.255.245”、”192.168.1.312″ 和 “192.168@1.1” 是 有效 IP 地址。

输出：s = “25525511135”
输入：[“255.255.11.135″,”255.255.111.35”]

待补充

买股票机会

假如你有个数组，第 i 个元素是股票第 i 天的价格。你有一次买入和卖出的机会。（只有买入后能力卖出）。求最大收益。

待补充

正文完
前端
发表至： 前端
2022-04-23
 0
关于前端:微信小程序用户信息授权
关于前端:分享一些有趣的-Web-APIs
关于前端:自己做一个2048游戏来玩吧
关于前端:vuecli3x-及以上版本建议使用的目录结构规范