leetCode算法第一天

今天开始刷算法题，提升自己的算法思维和代码能力，加油！

无重复字符的最长子串

leetCode链接 https://leetcode.cn/problems/longest-substring-without-repeating-characters/
解题思路有两种。

1. 扩散算法
   从i开始，分别尝试i (i + 1)和i（i - 1） 然后是（i - 1）i（i + 1） 以此类推，从中间扩散的方式进行判断是否无重复字符串。
2. 从最长的开始适配
   先判断整个字符串是否满足，然后是length - 1 的字符串（有两个），然后是（length - 2）的字符串，有三个，以此类推，只要找到了，就退出循环，返回结果。

是否有重复字符串很好判断，只需要将字符串遍历一遍，检查是否已经有存在过的字符。

/*** @param {string} s* @return {number}*/
var lengthOfLongestSubstring = function (s) {if (typeof s === "string" && s.length >= 1) {const length = s.length;let now = "";for (let i = length; i >= 1; i--) {for (let j = 0; j + i <= length; j++) {now = s.slice(j, j + i);if (isRepeat(now)) {return now.length;}}}} else {return 0;}function isRepeat(str) {const array = [];for (const i of str) {if (array.includes(i)) {return false;} else {array.push(i);}}if (array.length === str.length) {return true;}}
};

最长回文子串

leetCode链接 https://leetcode.cn/problems/longest-palindromic-substring/
解题思路有两种。

1. 扩散算法
   从i开始，分别尝试i (i + 1)和i（i - 1） 然后是（i - 1）i（i + 1） 以此类推，从中间扩散的方式进行判断是否无重复字符串。
2. 从最长的开始适配
   先判断整个字符串是否满足，然后是length - 1 的字符串（有两个），然后是（length - 2）的字符串，有三个，以此类推，只要找到了，就退出循环，返回结果。

是否是回文字符串也比较容易判断，只需要将字符串转为数组，再将数组倒序，拼为一个新的字符串，如果新字符串与一开始相等，就是回文字符串。

/*** @param {string} s* @return {string}*/
var longestPalindrome = function (s) {function isPalindrome(str) {return str.split("").reverse().join("") === str;}const length = s.length;if (typeof s === "string" && s.length > 0) {for (let i = length; i >= 1; i--) {for (let j = 0; j <= length - i; j++) {const now = s.substring(j, j + i);console.log(now);if (isPalindrome(now)) {return now;}}}} else {return "";}
};

N形变换

leetCode链接 https://leetcode.cn/problems/zigzag-conversion/

解题思路： N行变换，说白了就是找规律，比如当行数为4行的时候，字符串下标为i的字符分别所在的位置，我们按照这个位置保存到一个二维数组中，然后遍历这个二维数组，将字符串重新组合。

规律如下： 字符串下标 i % 2n - 2 求余， n是要求的行数，如果余数小于n - 1，那余数就是该字符所在的行数，如果余数大于等于 n - 1，那就用2n - 2 - 余数，对应的值就是该字符串所在的行数。

0     6      12        18
1   5 7   11 13    17
2 4   8 10   14 16
3     9      15

/*** @param {string} s* @param {number} numRows* @return {string}*/
var convert = function (s, numRows) {const array = s.split("");if (numRows <= 1) {return s;}const resultArray = [];const num = numRows * 2 - 2;array.forEach((item, index) => {let rows = (index % num) - num / 2;if (rows >= 0) {rows = num - (index % num);} else {rows = index % num;}if (typeof resultArray[rows] === "object") {resultArray[rows].push(item);} else {resultArray[rows] = [item];}});let result = "";for (let i = 0; i < resultArray.length; i++) {result += resultArray[i].join("");}return result;
};

字符串转换整数

leetCode链接 https://leetcode.cn/problems/string-to-integer-atoi/

这个题其实没啥意思，就是要读懂题目要求
空格只能出现在字符串的最面，可以是连续的，否则就终止。
±符号只能出现一次或者零次，并且±符号最多总共只能出现一个，否则就终止。
±符号只可能出现在空格的后面和数字的前面，否则就终止。
除了前面的空格和前面的±符号可能出现外，其余的地方只能出现数字，否则就终止。

如果终止后没有得到一个合理的数字，就返回 0。
如果数字超出了设置的最大最小的范围，就返回范围边界的数字即可。

/*** @param {string} s  https://leetcode.cn/problems/string-to-integer-atoi/submissions/* @return {number}*/
var myAtoi = function (str) {let sign = 1;let i = 0;let result = 0;const max = Math.pow(2, 31) - 1;const min = -Math.pow(2, 31);while (i < str.length) {// 去除最前面的空格if (str[i] === " ") {i++;continue;} else {break;}}if (str[i] === "-") {sign = -1;i++;} else if (str[i] === "+") {i++;}while (i < str.length) {const charCode = str.charCodeAt(i);if (charCode >= 48 && charCode <= 57) {result = result * 10 + Number(str[i]);} else {break;}const nextCharCode = str.charCodeAt(i + 1);if (nextCharCode < 48 || nextCharCode > 57) {break;} else {i++;continue;}}result = sign * result;if (result > max) {return max;} else if (result < min) {return min;} else {return result;}
};