447. 回旋镖的数量 [01/08]
题目
给定平面上 n 对 互不相同 的点 points ,其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ,其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等(需要考虑元组的顺序)。
返回平面上所有回旋镖的数量。
题解
/**
* @param {number[][]} points
* @return {number}
*/
var numberOfBoomerangs = function (points) {
let ans = 0; // 回旋镖数量
const distanceCounts = new Map(); // 固定点到其他点的距离
for (let [x1, y1] of points) {
distanceCounts.clear(); //端点变化,重新记忆
// 固定点坐标
for (let [x2, y2] of points) {
// 端点到固定点距离
const dis = (x1 - x2) ** 2 + (y1 - y2) ** 2;
// 端点到固定点距离相同 点数量
const c = distanceCounts.get(dis) ?? 0;
// [i, x , y] [i, y, x] 顺序算两个
ans += c * 2;
// 距离相同点数+1
distanceCounts.set(dis, c + 1);
}
}
return ans;
};
2707. 字符串中的额外字符 [01/09]
题目
给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串,每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。
请你采取最优策略分割 s ,使剩下的字符 最少 。
题解
/**
* @param {string} s
* @param {string[]} dictionary
* @return {number}
*/
var minExtraChar = function (s, dictionary) {
// dp表 每个字符对应剩余字符的最优解
const dpMap = new Array(s.length + 1).fill(0);
//循环字符串找到每一个字符串的最优解
for (let i = 0; i < s.length; i++) {
// 当前字符串
const cur = s.slice(0, i + 1);
// 剩余字符串默认+1
dpMap[i + 1] = dpMap[i] + 1;
for (let item of dictionary) {
// 循环单词字典找到包含在cur字符串的
if (cur.endsWith(item)) {
// 此时最优剩余字符 就是当前的剩余 和 当前匹配字符初始前字符剩余长度 对比
dpMap[i + 1] = Math.min(dpMap[i + 1], dpMap[i - item.length + 1]);
}
}
}
return dpMap[dpMap.length - 1];
};
2696. 删除子串后的字符串最小长度 [01/10]
题解
给你一个仅由 大写 英文字符组成的字符串 s 。
你可以对此字符串执行一些操作,在每一步操作中,你可以从 s 中删除 任一个 “AB” 或 “CD” 子字符串。
通过执行操作,删除所有 “AB” 和 “CD” 子串,返回可获得的最终字符串的 最小 可能长度。
注意,删除子串后,重新连接出的字符串可能会产生新的 “AB” 或 “CD” 子串。
题目
/**
* @param {string} s
* @return {number}
*/
var minLength = function (s) {
let stack = []; //栈
for (let key of s) {
stack.push(key);
if (stack.length >= 2) {
const newStr = stack[stack.length - 2] + stack[stack.length - 1];
if (newStr === "AB" || newStr === "CD") {
stack.pop();
stack.pop();
}
}
}
return stack.length;
};