字数
553 字
阅读时间
3 分钟
编辑距离问题
这次秋招笔试中遇到的类型频率最高的算法题就是这种 72. 编辑距离- 力扣（LeetCode）
动态规划总给我一种看上去逻辑并不复杂，可认真推导起来就又是另外一回事了
txt
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符javascript
let l1 = word1.length, l2 = word2.length;
if (l1 * l2 === 0) {
return l1 + l2;
}
let dp = new Array(l1 + 1).fill(0).map(v => new Array(l2 + 1).fill(0));
for (let i = 0; i < l1 + 1; i++) {
dp[i][0] = i;
}
for (let j = 0; j < l2 + 1; j++) {
dp[0][j] = j;
}
for (let i = 0; i <= l1; i++) {
for (let j = 0; j <= l2; j++) {
let left = dp[i - 1][j] + 1;
let right = dp[i][j - 1] + 1;
let replace = dp[i - 1][j - 1];
if (word1[i] === word1[i - 1] && word2[j] === word2[j - 1]) {
replace += 1;
}
dp[i][j] = Math.min(left, right, replace);
}
}
return dp[l1][l2];蚁群算法——最短距离
某厂笔试的一个算法题，第一眼就觉得是用类似图的算法（心里直接 pass），后来听到牛人说回溯能暴力 a 出来 。。（和 solution 就隔着一扇窗，我确以为是堵墙😭
js
function backtracking (points, used, sum, x, y) {
if (path.length === points.length) {
if (sum < res) {
res = sum;
return;
}
}
for (let i = 0; i < points.lenght; i++) {
if (!used[i]) {
path.push(points[i]);
used[i] = true;
backtracking(points, used, sum + Math.abs(points[i][0]-x) + Math.abs(points)[i][1]-y), poinst[i][0], points[i][1]);
used[i] = false;
path.pop();
}
}
}
let used = new Array(points.length).fill(false);
backtracking(points, used, 0, 0, 0);约瑟夫环
javascript
// sum代表多少个人，score代表报什么数组排除
function ring (sum, score) {
var numbers = [];
for (var i = 1; i <= sum; i++) {
numbers.push(i);
}
var flag = 0;
while (numbers.length > 1) {
l = numbers.length;
for (var j = 0; j < l; j++) {
flag++;
// 为3时，用splice方法从numbers数组中去掉，改变元数组
// 因原数组长度-1，所以索引-1，循环的长度-1
// 当编号为100时，flag = 1，重新开始报数是1的flag为2，解决的龙摆尾报数的问题
if (flag == score) {
flag = 0;
numbers.splice(j, 1);
j--;
l--;
}
}
}
return numbers[0];
};贡献者
jiechen