// 右指针一直动，找到重复的之后左指针会 跳 到指定位置右指针再开始动。 var lengthOfLongestSubstring = function (s) { let m = newMap() // start 是左索引，i 是右索引，start 和 i 之间是无重复的字符 let start = max = 0 for (let i = 0; i < s.length; i++) { if (m.get(s[i])) start = Math.max(m.get(s[i]), start) // 如果Map里有重复的值，把这个值的索引和start作比较，选取大的那个。 m.set(s[i], i + 1) // 如果 map 内没有则会添加，如果 map 内已经有该值则会覆盖。 max = Math.max(i - start + 1, max) // 更新最大值 } return max };
// 右指针先动，直到找到重复的。右指针停止，左指针开始动，直到删除重复的。以此往复，类似于毛毛虫蠕动般丝滑。 var lengthOfLongestSubstring = function (s) { const occ = newSet(); const n = s.length; // rk 是右索引，i 是左索引 let rk = -1, ans = 0; for (let i = 0; i < n; ++i) { if (i != 0) occ.delete(s.charAt(i - 1)); // 配合下面一直删除最左侧，直到删除重复的值才会继续进行下面代码 while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) { // 如果rk后面还有值且这个值不再occ中的话，向occ内添加该值，并将rk向后移动。 occ.add(s.charAt(rk + 1)); ++rk; } ans = Math.max(ans, rk - i + 1); // 更新最大值 } return ans; };
/** * @param {string} s * @return {string} */ // 改进前 var longestPalindrome = function (s) { let result = '' for (let i = 0; i < s.length; i++) { for (let j = i; j < s.length; j++) { let str = s.slice(i, j + 1) if (str == str.split('').reverse().join('') && (j - i + 1) > result.length) result = str } } return result };
// 改进之后 var longestPalindrome = function (s) { let result = '' for (let i = 0; i < s.length; i++) { let l = -1, r = 1 // 处理连续的重复的字符，如aaa,aaaa等 while (true) { if (s[i] == s[i + r]) r++; else { // 如果有重复的字符，直接跳转到这些字符的最后一个，减少检测次数。 if (r != 1) { i += r - 1 l -= r - 1 r = 1 } break } } // 当重复内容都检测完之后，开始向两边检测，如果左右内容一致，则继续向下检测 while (true) { // 超出范围判断 if (r - l > s.length) break if (s[i + l] == s[i + r]) { l--; r++; } elsebreak } // 判断是否比当前result长，长的话赋值 if ((r - l - 1) > result.length) result = s.slice(i + l + 1, i + r) } return result };
/** * @param {string} s * @param {number} numRows * @return {string} */ var convert = function (s, numRows) { // 如果行数为1或者字符少于行数就直接返回原字符串 if (s.length <= numRows || numRows == 1) return s // 创建二维数组 let ls = [] for (let i = 0; i < numRows; i++) { ls.push([]) } let p = 0 for (let i = 0; i < s.length; i++) { ls[p].push(s[i]) // 控制字符串对应的规律，如： // PAYPALISHIRING // 01210121012101 numRows 为 3 时 // 01232101232101 numRows 为 4 时 if (i % (2 * numRows - 2) < numRows - 1) p++ else p-- } // 将数组拼接成字符串 let result = '' ls.forEach(item => { result += item.join('') }) return result }
// 其他解题方法，根据规律依次找出第一行、第二行、第n行的值。 var convert = function (s, numRows) { const n = s.length, r = numRows; if (r === 1 || r >= n) { return s; } const t = r * 2 - 2; const ans = []; for (let i = 0; i < r; i++) { // 枚举矩阵的行 // j < n - i 保证j不会在最后一行 // j每轮位置都是固定的几个值，根据i来添加值 for (let j = 0; j < n - i; j += t) { // 枚举每个周期的起始下标 ans.push(s[j + i]); // 当前周期的第一个字符 if (0 < i && i < r - 1 && j + t - i < n) { ans.push(s[j + t - i]); // 当前周期的第二个字符 } } } return ans.join(''); };
/** * @param {string} s * @return {number} */ // 本人代码 /** * @param {number} x * @return {boolean} */ var isPalindrome = function (x) { if (x < 0) returnfalse if (x < 10) returntrue let str = x.toString() return str == str.split('').reverse().join('') };
// 优质数字运算 /** * @param {number} x * @return {boolean} */ var isPalindrome = function (x) { if (x < 0) returnfalse; if (x < 10) returntrue; let n = 10 ** Math.floor(Math.log10(x)); while (n > 1 && x > 0) { if (Math.floor(x / n) !== x % 10) returnfalse; x = Math.floor((x % n) / 10); n /= 100; } returntrue; };
/** * @param {number[]} height * @return {number} */ // 最初代码 var maxArea = function (height) { let max = 0 for (let i = 0; i < height.length - 1; i++) { for (let j = i + 1; j < height.length; j++) { max = Math.max(max, Math.min(height[i], height[j]) * (j - i)) } } return max };
// 两端方法 var maxArea = function (height) { let max = 0 // 头尾两个指针 let a = 0, b = height.length - 1 while (a < b) { // 计算 max = Math.max(max, Math.min(height[a], height[b]) * (b - a)) // 哪边小移动哪边 if (height[a] < height[b]) a++ else b-- } return max };
/** * @param {string} s * @return {number} */ var romanToInt = function (s) { let result = 0 let m = { '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 } for (let i = 0; i < s.length; i++) { if (m[s.slice(i, i + 2)]) { result += m[s.slice(i, i + 2)] i += 1 } else { result += m[s[i]] } } return result };
// 暴力解法 var longestCommonPrefix = function (strs) { if (strs.length == 1) return strs[0] let last = 0 for (let i = 1; i <= strs[0].length; i++) { let b = strs.every(item => item.slice(0, i) == strs[0].slice(0, i)) if (!b) { last = i - 1 break } last = i } return strs[0].slice(0, last) };
// 自己看过解题思路写的，时间占用较大 var threeSum = function (nums) { let result = [] nums = nums.sort((a, b) => a - b) for (let i = 0; i < nums.length - 2; i++) { let L = i + 1, R = nums.length - 1 while (L < R) { let sum = nums[i] + nums[L] + nums[R] if (sum == 0) { if (!result.find(item => item[0] == nums[i] && item[1] == nums[L] && item[2] == nums[R])) { result.push([nums[i], nums[L], nums[R]]) } R-- L++ } elseif (sum < 0) L++ else R-- } } return result };
// 解题思路的代码 var threeSum = function(nums) { let ans = []; const len = nums.length; if(nums == null || len < 3) return ans; nums.sort((a, b) => a - b); // 排序 for (let i = 0; i < len ; i++) { if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环 if(i > 0 && nums[i] == nums[i-1]) continue; // 去重 let L = i+1; let R = len-1; while(L < R){ const sum = nums[i] + nums[L] + nums[R]; if(sum == 0){ ans.push([nums[i],nums[L],nums[R]]); while (L<R && nums[L] == nums[L+1]) L++; // 去重 while (L<R && nums[R] == nums[R-1]) R--; // 去重 L++; R--; } elseif (sum < 0) L++; elseif (sum > 0) R--; } } return ans; };
/** * @param {number[]} nums * @param {number} target * @return {number} */ // 最初代码 var threeSumClosest = function (nums, target) { let gap = 9999999 let result = 0 nums = nums.sort((a, b) => a - b) let len = nums.length for (let i = 0; i < len - 2; i++) { let L = i + 1, R = len - 1 while (L < R) { let sum = nums[i] + nums[L] + nums[R] let sub = sum - target if (Math.abs(sub) < gap) { result = sum gap = Math.abs(sum - target) } if (sub < 0) L++ elseif (sub == 0) break else R-- } if (gap == 0) break } return result };
// 改进后 var threeSumClosest = function (nums, target) { let result = nums[0] + nums[1] + nums[2] nums = nums.sort((a, b) => a - b) let len = nums.length for (let i = 0; i < len - 2; i++) { let L = i + 1, R = len - 1 while (L < R) { let sum = nums[i] + nums[L] + nums[R] if (Math.abs(sum - target) < Math.abs(result - target)) result = sum if (sum < target) L++ elseif (sum > target) R-- elsereturn result } } return result };
/** * @param {string} s * @return {boolean} */ // 最初 var isValid = function (s) { let a = ['()', '[]', '{}'] let stack = [] for (let i = 0; i < s.length; i++) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') stack.push(s[i]) else { if (a.includes(stack[stack.length - 1] + s[i])) stack.pop() elsereturnfalse } } if (stack.length) returnfalse returntrue }; // 改进版 也没提升性能 var isValid = function (s) { let obj = { '(': ')', '[': ']', '{': '}' } let stack = [] for (let i = 0; i < s.length; i++) { if (obj[s[i]]) stack.push(s[i]) elseif (obj[stack.pop()] != s[i]) returnfalse } if (stack.length) returnfalse returntrue };
// 题解写法 速度快但是内存高了 var isValid = function(s) { const n = s.length; if (n % 2 === 1) { returnfalse; } const pairs = newMap([ [')', '('], [']', '['], ['}', '{'] ]); const stk = []; for (let ch of s){ if (pairs.has(ch)) { if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) { returnfalse; } stk.pop(); } else { stk.push(ch); } }; return !stk.length; };
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var reverseKGroup = function (head, k) { let tmp = [], ls = [] let index = 0 while (head) { if (!(index % k)) { ls = ls.concat(tmp.reverse()) tmp = [] } tmp.push(head.val) index++ head = head.next }
if (tmp.length == k) ls.push(...tmp.reverse()) else ls.push(...tmp)
let res = newListNode(null) for (let i = ls.length - 1; i >= 0; i--) { let temp = newListNode(null) res.val = ls[i] temp.next = res res = temp } return res.next };
赞赏码