leetCode算法第二天

好好刷刷算法题，提高自己的编码能力。

将整数转为罗马数字

leetcode链接：https://leetcode.cn/problems/integer-to-roman/

解题思路： 我们将几种特殊规则，也定义在罗马数字与字符的map中，这样就让所有的规则都变成了从左向右，大的在左，小的在右。每一次都从多往少匹配，只要number大于对应的数值，就匹配上对应的字符串，然后从左往右加起来即可。

另外罗马数字还有很大的数，这道题只要求实现3000以内的数字。

var intToRoman = function (num) {const romanNumeralMap = {M: 1000,CM: 900,D: 500,CD: 400,C: 100,XC: 90,L: 50,XL: 40,X: 10,IX: 9,V: 5,IV: 4,I: 1,};let result = "";while (num > 0) {for (let key in romanNumeralMap) {if (num >= romanNumeralMap[key]) {result += key;console.log(result);num -= romanNumeralMap[key];break;}}}return result;
};

将罗马数字转为整数

leetcode链接：https://leetcode.cn/problems/roman-to-integer/

解题思路： 我们将几种特殊规则，也定义在罗马数字与字符的map中，这样就让所有的规则都变成了从左向右，大的在左，小的在右。每一次都从多往少匹配，只要字符匹配到了字符串，并且index为0，就将对应的number加上，剩下的字符串再继续从大到小匹配。

/* @param {string} s* @return {number}*/
var romanToInt = function (s) {const romanNumeralMap = {M: 1000,CM: 900,D: 500,CD: 400,C: 100,XC: 90,L: 50,XL: 40,X: 10,IX: 9,V: 5,IV: 4,I: 1,};let num = 0;while (s.length) {for (let key in romanNumeralMap) {const index = s.indexOf(key);if (index === 0) {s = s.slice(key.length);num += romanNumeralMap[key];break;}}}return num;
};

编写一个函数来查找字符串数组中的最长公共前缀

leetcode链接：https://leetcode.cn/problems/longest-common-prefix/

解题思路：最长公共前缀，顶多是数组里面最短的某个字符串，所以我们先找到最短字符串，然后再依次减少它的长度，去判断是否是数组里面其它元素字符串的前缀，如果最后当最短的字符串长度缩减为1时还不满足，就没有公共前缀。

/* @param {string[]} strs* @return {string}*/
var longestCommonPrefix = function (strs) {let minStr = "";strs.forEach((item) => {if (!minStr || item.length < minStr.length) {minStr = item;}});while (minStr) {const length = minStr.length;for (const value of strs) {console.log(value);if (value.indexOf(minStr) !== 0) {minStr = minStr.slice(0, minStr.length - 1) || "";break;}}if (minStr.length < length) {continue;} else {return minStr;}}return "";
};

电话号码的字母组合

leetcode链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

解题思路：循环回溯。digits的长度就决定了我们要循环多少次，每一次循环的次数，由数字对应的数组长度决定，每循环一次，就判断剩余的digits长度是否为1，如果为1就是最后一次循环，退出递归，否则就继续递归。

/* @param {string} digits* @return {string[]}*/
var letterCombinations = function (digits) {let NumberMap = {2: ["a", "b", "c"],3: ["d", "e", "f"],4: ["g", "h", "i"],5: ["j", "k", "l"],6: ["m", "n", "o"],7: ["p", "q", "r", "s"],8: ["t", "u", "v"],9: ["w", "x", "y", "z"],};let result = [];function numberToCharCode(ReminDigits = digits, str = "") {console.log(ReminDigits, str);if (ReminDigits.length === 1) {for (const value of NumberMap[ReminDigits]) {let newStr = str + value;result.push(newStr);}} else if(ReminDigits.length > 1) {const newReminDigits = ReminDigits.slice(1);for (const value of NumberMap[ReminDigits[0]]) {let newStr = str + value;numberToCharCode(newReminDigits, newStr);}}}numberToCharCode();return result;
};