算法学习（JavaScript实现） #50
Comments
二、KNN （k-nearest neighbors，K最近邻算法）从一个很简单的例子来理解KNN。 假设我们有一堆橙子和一堆柚子，通常情况下，柚子比橙子更大，更红；现在有一个水果，我们怎么判断它是橙子还是柚子？肯定是比较它的大小和颜色，与橙子/柚子哪个更接近。怎么判断接近？我们可以把之前的橙子/柚子画到二维点图上，X轴为颜色，Y轴为大小，然后来看看离这个水果最近的3个点，结果这3个点里，有2个是橙子，那么我们大概率可以确定，这个水果就是橙子。 这里运用到的就是 KNN 算法：给定一个（训练）数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。 KNN 算法是一种基本分类和回归方法，是机器学习中最简单的算法之一。 由于给定的数据集都带有label（即是橙子还是柚子），并且新输入的实例也会明确确定label，所以KNN属于监督学习。 下面讲一些KNN算法的注意点： K 的选取
距离计算
特征归一化假设我们通过两个维度（身高和脚长）来判断性别，很显然，计算距离时，结果会偏向于身高。 所以很容易理解，我们需要对特征归一化。即取每个维度的最大值减去最小值，然后该维度计算时首先除以这个值来进行归一化。 |
三、动态规划背包问题首先我们从背包问题开始。 一个背包可以装4kg的物品，现有物品音响（3000元|4kg）笔记本电脑（2000元|3kg）、吉他（1500元|1kg），那么我们怎么拿可以使物品价值最高？ 1、 最简单的方法：罗列所有组合，选取符合条件的最高的那个。 物品是1个的时候，我们可以拿或不拿，即2种选择；物品3个的时候，我们有8种选择；物品n种时，我们有 2^n 种选择——时间复杂度 O(2^n)! 2、动态规划
动态规划的核心在于合并两个子问题的解来得到更大问题的解。 那么它的难度就在于怎么把大问题分解成子问题。 在这里的例子里，装入背包的物品价值取决于物品类型和背包容量两个因素，以这两个因素为维度，利用网格来得到问题的解（本质上是当容量更小、物品更少时更容易得到解）。
|
1. 核心观点动态规划并不难，通常是通过流程 递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法 一步步铺垫而来，动态规划的核心是化递归（自顶向下）为循环迭代（自底向上）。 如上面流程所示，在动态规划中，得到暴力解（即如何穷举所有可能性，也即得到“状态转移方程”）是最困难的一步。为什么说困难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不容易穷举完整。 2. 凑零钱Demo演示
假设 n 总是可以被凑出来的，那么这个问题其实非常简单，我们只需要先从最大币值的硬币开始凑就可以了。然而这个假设并不总是成立，所以事实上我们需要穷举所有可能性——典型的可以采用动态规划方法来解决的问题。 下面我们按流程来解题： 1）暴力解（即状态转移方程）：如上，可以理解为原问题的解可以通过子问题的最优解来得到，即 f(11) 是可以分解为：
3种情形的最优解即为最终解，而 好了，给这个暴力解一个程序表达： // 暴力递归
function assembleCoin(coins, amount) {
if (amount === 0) {
return 0;
}
let ans = Number.MAX_SAFE_INTEGER;
for(let c of coins.values()) {
// 剩余金额
let value = amount - c;
// 币值大于总金额，说明是无效的
if (value < 0) continue;
// 计算剩余金额可能的最少组合次数
const sub = assembleCoin(coins, value);
// 次数小于0，说明无效
if (sub < 0) continue;
// 该次组合有效，更新最少次数
ans = Math.min(ans, 1 + sub);
}
return ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
}2）带备忘录的递归暴力解有太多的重复子问题（比如多个 f(5) 的求解）,如果重复子问题的求解结果被缓存了，那同一个子问题就只用计算一次了： // 带备忘录的递归
function assembleCoinWithMemo(coins, amount) {
const memo = {};
return coinHelper(memo, coins, amount);
}
function coinHelper(memo, coins, amount) {
if (amount === 0) {
return 0;
}
if (memo[amount] !== undefined) {
return memo[amount];
}
let ans = Number.MAX_SAFE_INTEGER;
for (let c of coins.values()) {
// 剩余金额
let value = amount - c;
// 币值大于总金额，说明是无效的
if (value < 0) continue;
// 计算剩余金额可能的最少组合次数
const sub = coinHelper(memo, coins, value);
// 次数-1，说明无效
if (sub === -1) continue;
// 该次组合有效，取最少次数
ans = Math.min(ans, 1 + sub);
}
memo[amount] = ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
return memo[amount];
}3）动态规划：递归 --> 循环动态规划其实和上面的备忘录法已经相当接近了，把备忘录换成 DP 表，从而自底向上求解替代自顶向下，就是动态规划： // 动态规划
function assembleCoinDP(coins, amount) {
// dp 表最多包含 amount + 1 种情况（包括0）
const dp = Array(amount + 1).fill(amount + 1);
// 最简单（自底向上的底）的情况：
dp[0] = 0;
// 从 1 开始填充 dp 表的过程即自底向上逐渐求解的过程
for(let i = 1; i < dp.length; i++) {
// 内层 for 循环求所有子问题 + 1（种硬币） 的最小值
// 比如 i = 1，我们即求解：1元+dp[0]，2元+dp[-1]，5元+dp[-4] 等3种情况，
// 其中后两种被 continue 直接过滤了，所以 dp[1] 很容易得到为 1；
// 随着 i 增大，我们最终总可以得到所有的 d[i]，且必然 d[x]（x < i）是已经计算
// 有结果的（保持 amount + 1的最大值即代表amount 为该值时无可用的硬币排布，返回 -1）
for (let c of coins.values()) {
if (i - c < 0) {
continue;
}
dp[i] = Math.min(dp[i], 1 + dp[i - c]);
}
}
return dp[amount] === amount + 1 ? -1 : dp[amount];
}时间复杂度最后顺便给一组实际测试时不同方式的用时： 可以看到，相比带备忘录的递归和动态规划，暴力递归的用时太可怕了：
如上，希望通过例子可以对动态规划更容易理解一些。 |
四、KMP（Knuth-Morris-Pratt ） 算法KMP 是著名的字符串匹配算法，效率高但比较难理解（一看就懂的请勿代入 😂 ）。 字符串匹配问题是指从一段已有的文本串（记为 暴力匹配function directSearch(pat, txt) {
if (!pat || !txt) return -1;
const txtLen = txt.length;
const patLen = pat.length;
for (let i = 0; i < txtLen - patLen + 1; i++) {
let j;
for (j = 0; j < patLen; j++) {
if (pat[j] !== txt[i + j]) {
break;
}
}
// j 等于 patLen，代表比较过程全部走完，即全部匹配
if (j === patLen) {
return i;
}
}
return -1;
}如上，暴力匹配即从文本串第一位开始，每次都遍历整个模式串来一一比较，简单直接，时间复杂度为 但暴力匹配有个问题：它不够智能，每次都需要从头开始重新一一比较，之前比较过程中匹配的部分没法利用，做了很多无用功。那么有没有方法可以利用之前比较的结果？有，这就是KMP。 从 PMT （部分匹配表 Partial Match Table）开始来理解 KMP这里为什么不从 KMP 的概念开始学习 KMP（正如我们以前学习一般算法那样）？因为从概念开始，最后讲到 PMT 真的不容易理解，所以干脆反其道而行之，先来理解 KMP 的核心概念：部分匹配表PMT。 1) 字符串的前缀、后缀到 PMT理解PMT的前置要求就是理解字符串的前缀、后缀。假设字符串A、B、S，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。后缀同理。 PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。 举例描述，对 假设模式串 pat 是
2) PMT可以帮助到暴力匹配什么现在我们已经有了 PMT 了，那它可以用来优化暴力匹配吗？当然可以，这里也就是 KMP 理解的难点。 暴力匹配被认为效率低的地方在于一旦不匹配，就只能从头开始比较，之前的比较结果无法利用。但当我们有了 PMT ，我们就再也不用从头比较了！ 我们尝试来在暴力匹配中加入 PMT ：
如上就是借助 PMT 之后的比较过程（即KMP），它可以保证 i 不回退，可以尽量不重新比较整个模式串（j 设置为合理的值而不像暴力匹配那样直接重置为 0）。 但为什么可以比暴力匹配更聪明？即为什么 i 不回退， j 是 5？
KMP 的实现/**
* 定义 “k-前缀” 为一个字符串的前 k 个字符； “k-后缀” 为一个字符串的后 k 个字符。k 必须小于字符串长度。
* next[x] 定义为： pat[0]~pat[x]这一段字符串，使得k-前缀等于k-后缀的最大的k。
* 对字符串pat的求解并返回next数组。
*
* @demo 'aa' => [0,1]
* @demo 'abababc' => [0,0,1,2,3,4,0]
*/
function getPMT(pat) {
// 所有元素填充为 0，且next[0]=0不用再计算。
const next = Array(pat.length).fill(0);
let curr = 1; // 指针（从1开始），用于指定当前需要计算的next数组元素next[curr]
let len = 0; // 长度，理解为next[curr-1]的值，即前一位（next[curr-1]）的最长相等前后缀长度
while (curr < pat.length) {
console.log('start',len, curr, next)
// 如果字符相等，则说明最长相等前后缀长度加1（即len+1）
if (pat[curr] === pat[len]) {
next[curr++] = ++len; // 同时 curr 往右移动一位继续计算过程
}
// 如果不等，则根据情况设置 len / curr
else {
// 如果len是0，即前一位的最长相等前后缀长度是0，现在又不相等，next[curr] 只能继续0；
// curr往右移动一位继续
if (len === 0) {
curr++;
}
// 如果 len > 0，即前一位的最长相等前后缀长度大于 0，那么我们需要怎么缩短 len，然后重新比较 pat[curr] 和 pat[len]。
// ---
// 先假设 pat[0,...,len-1] 为字符串 A，pat[curr-len,...,curr-1] 为字符串 B，很显然，我们当前比较的就是
// [...A,pat[len]] 和 [...B,pat[curr]]，只可惜 pat[curr] 和 pat[len] 不等；
// 那么 A 和 B 的最长相等前后缀长度是多少呢？是 next[len-1]，注意到这里有A和B相等。
// 回到上面的问题，怎么缩短 len 是最有效的（尽可能让len最大）？
// 显然 curr 是不用变的，因为 curr 就是用来指示当前需要计算的 next[curr];
// 所以缩短len到len1，本质上就是尽可能取A的左半部分（长度len1），尽可能取B的右半部分（长度len1），让两者相等；
// 巧合的是，A和B相等，那么，这个len1，正好就是 next[len-1]
else {
len = next[len - 1];
}
}
console.log('end',len, curr, next)
}
return next;
}
function kmpSearch(txt, pat) {
let i = 0;
let j = 0;
const next = getPMT(pat);
while (i < txt.length && j < pat.length) {
if (txt[i] === pat[j]) {
i++;
j++;
if (j === pat.length) {
return i - j;
}
} else {
if (j > 0) {
j = next[j - 1];
} else {
i++;
}
}
}
return -1;
} |
五、位操作实现加法等特殊需求怎么不用加号实现加法？ 这里考虑两个特殊位操作符：
const a = 5; // 00000000000000000000000000000101
const b = 3; // 00000000000000000000000000000011
console.log(a & b); // 00000000000000000000000000000001
// Expected output: 1
console.log(a ^ b); // 00000000000000000000000000000110
// Expected output: 6那么我们怎么借助这两个位操作实现加法？ function bitAdd(a, b) {
// 对应位都是1才返回1，所以这是a和b的和的需要进位的部分
const carry = a & b;
// 对应位只有不一样才返回1（去除了对应位都是1的部分），所以这是a和b的和的不需要进位的部分
const noCarrySum = a ^ b;
// 需要进位，那么进位的部分先进位（<<1），然后递归调用bitAdd
if (carry) {
return bitAdd(carry << 1, noCarrySum);
}
// 如果不需要进位，直接返回就好
else {
return noCarrySum;
}
}更进一步，借助bitAdd实现乘法，比如数字✖️7: const bitMultiply7 = (a) => bitAdd(a << 2, bitAdd(a << 1, a)); |
|
已收到,稍候会处理best wish~
|
一、HashTable （哈希函数，哈希表的简单实现）
这一章节内容主要是 HashTable，中文即哈希表，散列表等等。HashTable 是编程中日常使用，不可或缺的一个数据结构，本章节最终会代码实现一个简单哈希表，来解释哈希表相关的重要概念。
对前端同学而言，哈希表是个每天用但说起来可能陌生的概念。说每天用，是因为在 JavaScript 中，对象（
{}）的底层实现即哈希表，我们也经常用对象来做缓存等各种用法，利用其查找时间复杂度为 O(1) 的特性。1. 为什么需要 hash table （元素查找的时间复杂度）
对若干个元素（key-value对），如果我们想通过 key 来找到对应的 value，通常情况下，我们需要遍历所有元素，一一比较 key，来找到对应的 value。这个时间复杂度是 O(n) 。
然后我们假设这些元素是有序的，那么通过二分查找，时间复杂度可以降到 O(log n) 。
那么有没有更好的方法呢？这就是 hash table 出现的原因，它可以达到 O(1) 的时间复杂度。
2. 什么是 hash table？
哈希表是一种用于存储键值对（key-value pairs）的数据结构，它可以实现key到value的映射，一般情况下查找的时间复杂度是O(1) 。
3. 哈希表的简单实现
以上是一个简单的哈希表实现，还有很多细节没有考虑，比如：
填装因子
（填装因子 = 哈希表的元素数量 / 哈希表的位置总数）。根据经验，一旦填装因子大于 0.7，我们就需要调整哈希表的长度。buckets 数组这里没有规定长度，如果考虑 buckets 的长度，那么我们就要对哈希函数返回的值进行取余操作。
参考：
The text was updated successfully, but these errors were encountered: