算法| ss 逻辑问题

本文主要是介绍算法| ss 逻辑问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

14.最长公共前缀
605.种花问题
165.比较版本号
6.Z 字形变换
853.车队
318.最大单词长度乘积
146.LRU 缓存
299.猜数字游戏

14. 最长公共前缀

/*** @param {string[]} strs* @return {string}*/
var longestCommonPrefix = function (strs) {let ans = strs[0];for (let i = 1; i < strs.length; i++) {let j = 0;for (; j < strs[i].length && j < ans.length; j++) {if (ans[j] !== strs[i][j]) {break;}}ans = ans.slice(0, j);if (ans === "") return ans;}//   console.log(ans);return ans;
};
longestCommonPrefix(["flower", "flow", "flight"]);
longestCommonPrefix(["dog", "racecar", "car"]);
longestCommonPrefix(["ab", "a"]);
// 输入：strs = ["flower","flow","flight"]
// 输出："fl"

605.种花问题

/*** @param {number[]} flowerbed* @param {number} n* @return {boolean}*/
// 思路
// 在数组的前后补0，这样不用考虑边界了
// 遍历数组， 连续有3个0的 种花count++
var canPlaceFlowers = function (arr, n) {arr.push(0);arr.unshift(0);let count = 0;for (let i = 0; i < arr.length; i++) {if (arr[i] == 0 && arr[i - 1] == 0 && arr[i + 1] === 0) {count += 1;arr[i] = 1;}}console.log(count);return n <= count;
};
canPlaceFlowers([1, 0, 0, 0, 1], 1);
// 输入：flowerbed = [1,0,0,0,1], n = 1
// 输出：true

165. 比较版本号

/*** @param {string} version1* @param {string} version2* @return {number}*/
// 思路
// 分割字符串得到对应的数组
// while循环  shift拿出头个元素，比较大小
// 若arr1 arr2有剩余则分别判断是否都是为0 还是1 或-1
var compareVersion = function (version1, version2) {const arr1 = version1.split(".").map(Number);const arr2 = version2.split(".").map(Number);while (arr1.length && arr2.length) {let a1 = arr1.shift();let a2 = arr2.shift();if (a1 > a2) return 1;if (a1 < a2) return -1;}if (arr1.length) {return arr1.every((item) => item === 0) ? 0 : 1;}if (arr2.length) {return arr2.every((item) => item === 0) ? 0 : -1;}return 0;
};console.log(compareVersion("1.01", "1.001"));

6.Z 字形变换

/*** @param {string} s* @param {number} numRows* @return {string}*/
// 思路
// 边界直接返回s
// 构建存储数组，默认空字符串
// 定义数组下标及方向
// for遍历字符串， 将字符串加入到对应的下标中， 根据方向及到顶或者到底了， 更新下一个num和方向
// 结果输出
var convert = function (s, numRows) {if (s.length <= numRows || numRows === 1) return s;const arr = Array(numRows).fill("");//   对应行let num = 0;//   true 向下 false向上let plus = true;for (let i = 0; i < s.length; i++) {// 字符串拼接arr[num] += s[i];// 向下行+1if (plus) num += 1;// 向上行-1else num -= 1;// 再次到 0 说明到顶了要向下了，为trueif (num === 0) plus = true;// 再次到 底部 说明要向上了，为falseif (num === numRows - 1) plus = false;}return arr.join("");
};
convert("PAYPALISHIRING", 3);
// 输入：s = "PAYPALISHIRING", numRows = 3
// 输出："PAHNAPLSIIGYIR"
// [ 'P', '', '' ]
// [ 'P', 'A', '' ]
// [ 'P', 'A', 'Y' ]
// [ 'P', 'AP', 'Y' ]
// [ 'PA', 'AP', 'Y' ]
// [ 'PA', 'APL', 'Y' ]
// [ 'PA', 'APL', 'YI' ]
// [ 'PA', 'APLS', 'YI' ]
// [ 'PAH', 'APLS', 'YI' ]
// [ 'PAH', 'APLSI', 'YI' ]
// [ 'PAH', 'APLSI', 'YIR' ]
// [ 'PAH', 'APLSII', 'YIR' ]
// [ 'PAHN', 'APLSII', 'YIR' ]
// [ 'PAHN', 'APLSIIG', 'YIR' ]

853.车队

/*** @param {number} target* @param {number[]} position* @param {number[]} speed* @return {number}*/
// 思路
// 利用Map存在位置（map排序不会乱）
// for循环 从末尾开始
// 如果该位置有人， 则计算他的时间和 最大时间比，t= 距离/速度
// 如果该位置时间大于最大时间技术+1，更新最大值
var carFleet = function (target, position, speed) {const map = new Map();position.forEach((p, idx) => map.set(p, idx));let max = -Infinity;let count = 0;for (let i = target; i >= 0; i--) {// 如果当前车到达终点的时间 > 前面所有车辆中到达终点所需最多时间// 说明这辆车永远不会赶上前面的车/车队, 因此车队数量加一：也就是这辆车会形成自己的车队// 如果当前车到达终点的时间 <= 前面所有车辆中到达终点所需最多时间// 说明这辆车会赶上前面的车/车队, 因此车队数量不用加一：也就是说这辆车会合并到前面的车队去if (map.has(i)) {const t = (target - i) / speed[map.get(i)];if (t > max) {count += 1;}max = Math.max(max, t);}}//   console.log(count);return count;
};
carFleet(12, [10, 8, 0, 5, 3], [2, 4, 1, 1, 3]);// 输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
// 输出：3
// 解释：
// 从 10 和 8 开始的车会组成一个车队，它们在 12 处相遇。
// 从 0 处开始的车无法追上其它车，所以它自己就是一个车队。
// 从 5 和 3 开始的车会组成一个车队，它们在 6 处相遇。
// 请注意，在到达目的地之前没有其它车会遇到这些车队，所以答案是 3。

318. 最大单词长度乘积

/*** @param {string[]} words* @return {number}*/
/*** @param {string[]} words* @return {number}*/
// 思路 二进制换算
// 这题还需要好好理解， 不熟悉
function getCharCodeSet(word) {let num = 0;for (let i = 0; i < word.length; i++) {const bit = 1 << (word[i].charCodeAt() - 97);num |= bit;}return num;
}var maxProduct = function (words) {const nums = words.map(getCharCodeSet);let ans = 0;for (let i = 0; i < nums.length; i++) {for (let j = i + 1; j < nums.length; j++) {if ((nums[i] & nums[j]) === 0) {ans = Math.max(ans, words[i].length * words[j].length);}}}return ans;
};

146.LRU 缓存

/*** @param {number} capacity*/
// 思路 利用map进行操作
// 读： 拿起 (删除) 放到最上面
// 放： 如果有该书，拿起 (删除) 放到最上面,如果没有， 判断是否到最大值， 到了则删除最早的那个，再存入
var LRUCache = function (capacity) {this.capacity = capacity;this.map = new Map();
};/*** @param {number} key* @return {number}*/
LRUCache.prototype.get = function (key) {if (this.map.has(key)) {const value = this.map.get(key);this.map.delete(key);this.map.set(key, value);return value;}return -1;
};/*** @param {number} key* @param {number} value* @return {void}*/
LRUCache.prototype.put = function (key, value) {if (this.map.has(key)) {this.map.delete(key);this.map.set(key, value);} else {this.map.size == this.capacity? this.map.delete(this.map.keys().next().value): null;this.map.set(key, value);}
};/*** Your LRUCache object will be instantiated and called as such:* var obj = new LRUCache(capacity)* var param_1 = obj.get(key)* obj.put(key,value)*/const map = new Map();map.set("a", 1);
map.set("b", 2);
map.set("c", 3);
const mapIter = map.keys();
console.log(mapIter); // [Map Iterator] { 'a', 'b', 'c' }
console.log(mapIter.next().value); // a
console.log(mapIter.next().value); // b

299.猜数字游戏

/*** @param {string} secret* @param {string} guess* @return {string}*/
// 不能改变数组
// 考虑过改变数组元素值是对的， 想到-1 没想到 null
// 总体思路是对的， 两次遍历
// 先遍历一次完全匹配的 统计A
// 再遍历一次guess，统计B， 若A包含， 则把A对应的值设为null
// 统计B的时候有点绕， 需要secret对应的值设为nullvar getHint = function (secret, guess) {let m = secret.length;let aCount = 0;let bCount = 0;let arra = secret.split("").map(Number);let arrb = guess.split("").map(Number);for (let i = 0; i < m; i++) {if (arra[i] === arrb[i]) {aCount += 1;arra[i] = null;arrb[i] = null;}}//   遍历guessfor (let i = 0; i < arra.length; i++) {if (arrb[i] === null) continue;// secret 包含了 guess中的元素let ch = arrb[i];if (arra.indexOf(ch) !== -1) {bCount++;arra[arra.indexOf(ch)] = null;}}let ans = aCount + "A" + bCount + "B";console.log(ans);return ans;
};
getHint("1807", "7810");
// getHint("1123", "0111");
// getHint("11", "10");
// 输入：secret = "1807", guess = "7810"
// 输出："1A3B"
// 107 710// 1
// 0