leetCode算法第一天
今天开始刷算法题,提升自己的算法思维和代码能力,加油!
无重复字符的最长子串
leetCode链接 https://leetcode.cn/problems/longest-substring-without-repeating-characters/
解题思路有两种。
- 扩散算法
从i开始,分别尝试i (i + 1)和i(i - 1) 然后是(i - 1)i(i + 1) 以此类推,从中间扩散的方式进行判断是否无重复字符串。 - 从最长的开始适配
先判断整个字符串是否满足,然后是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/
解题思路有两种。
- 扩散算法
从i开始,分别尝试i (i + 1)和i(i - 1) 然后是(i - 1)i(i + 1) 以此类推,从中间扩散的方式进行判断是否无重复字符串。 - 从最长的开始适配
先判断整个字符串是否满足,然后是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;}
};