leetcode刷题记录(11)

技术2022-07-10 143

1.存在重复元素 *简单

题目：

给定一个整数数组，判断是否存在重复元素。

如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

思路：首先是用map来记录

/** * @param {number[]} nums * @return {boolean} */ var containsDuplicate = function(nums) { let map={} for(let i=0,l=nums.length;i<l;i++){ if(map[nums[i]]){ return true }else{ map[nums[i]]=1 } }; return false };

还可以利用Set对象的特点

/** * @param {number[]} nums * @return {boolean} */ var containsDuplicate = function(nums) { return new Set(nums).size!==nums.length };

借助indexOf方法（这种方法最慢，并且慢得多）

var containsDuplicate = function(nums) { for(let i=0,l=nums.length;i<l;i++){ if(nums.indexOf(nums[i])!==i)return true }; return false };

还是用Set

/** * @param {number[]} nums * @return {boolean} */ var containsDuplicate = function(nums) { const set=new Set(); for(let i=0,l=nums.length;i<l;i++){ if(set.has(nums[i]))return true set.add(nums[i]) }; return false }

2.存在重复元素 II *简单

题目：

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值至多为 k。

思路：还是先来简单的，用map记录

/** * @param {number[]} nums * @param {number} k * @return {boolean} */ var containsNearbyDuplicate = function(nums, k) { let map = {}; for (let i = 0, l = nums.length; i < l; i++) { if (map[nums[i]] !== undefined) { if (i - map[nums[i]] <= k) return true; } map[nums[i]] = i; } return false; };

另一个思路：设想一滑动窗口，窗口宽度固定，然后往左滑，判断新添加的元素是否是k，如果是k且窗口已有，则返回true，如果窗口宽度大于k，则删除set的第一个元素

/** * @param {number[]} nums * @param {number} k * @return {boolean} */ var containsNearbyDuplicate = function(nums, k) { const set = new Set(); for(let i = 0; i < nums.length; i++) { if(set.has(nums[i])) { return true; } set.add(nums[i]); if(set.size > k) { set.delete(nums[i - k]); } } return false; };

3.翻转二叉树 *简单

题目：翻转一棵二叉树。

思路：递归，或者用数组迭代，很简单，无非是遍历顺序的不同

/** * @param {TreeNode} root * @return {TreeNode} */ var invertTree = function(root) { if(root === null) return null; invertTree(root.left); invertTree(root.right); [root.left,root.right] = [root.right,root.left]; return root; }; /** * @param {TreeNode} root * @return {TreeNode} */ var invertTree = function(root) { if (root && (root.left || root.right)) { let temp = root.left; root.left = invertTree(root.right); root.right = invertTree(temp); } return root; }; */ /** * @param {TreeNode} root * @return {TreeNode} */ var invertTree = function(root) { let queue = [root]; while(queue.length > 0){ let cur = queue.pop(); if(cur === null) continue; [cur.left,cur.right] = [cur.right,cur.left]; queue.unshift(cur.left); queue.unshift(cur.right); } return root; };

4.两数相加 *中等

题目：

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

思路：动态规划，用尾递归的方式实现，按照同样的顺序去遍历两个链表的每一个节点，如果是null则值为0，然后后前一位是否要进1

然后把flag去掉，直接给l1的下一个节点+1，就只需要一个函数递归完成

迭代实现，思路一样

/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function (l1, l2) { let flag = false; let res = null; let cur = null; while (l1 || l2 || flag) { let v1 = 0; let v2 = 0; if (l1) { v1 = l1.val; l1 = l1.next; } if (l2) { v2 = l2.val; l2 = l2.next; } const v = (flag ? 1 : 0) + v1 + v2; flag = v > 9; const cv = new ListNode(v % 10); if (!res) { res = cur = cv; } else { cur.next = cv; cur = cv; } } return res; };

5.无重复字符的最长子串 *中等

题目：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

思路：最简单的思路，用一个数组记录之前的字符，二层嵌套的循环，遍历每一个可能的字符，然后比较最大值

/** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function(s) { let stack = []; let res = 0; for (let i = 0, l = s.length; i < l; i++) { for (let j = i; j < l && l - i > res; j++) { if (stack.includes(s[j])) { res = stack.length > res ? stack.length : res; stack = []; break; } else { stack.push(s[j]); } } res = stack.length > res ? stack.length : res; stack = []; } return res; };

优化：当我们遇到重复的字符串时，找到重复的那个字符的下标，然后从它的下一个下标开始遍历，这样就不会重复遍历了

/** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function(s) { let stack = []; let res = 0; for (let i = 0, l = s.length; i < l; i++) { if (stack.includes(s[i])) { res = stack.length > res ? stack.length : res; const x = stack.indexOf(s[i]); stack.splice(0, x + 1); stack.push(s[i]); } else { stack.push(s[i]); } } res = stack.length > res ? stack.length : res; return res; };

优化：类用一个map记录每个字符出现的位置，遇到重复的就比较长度，然后更新该字符的值

/** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function(s) { let map = new Map(), max = 0 for(let i = 0, j = 0; j < s.length; j++) { if(map.has(s[j])) { i = Math.max(map.get(s[j]) + 1, i) } max = Math.max(max, j - i + 1) map.set(s[j], j) } return max };

6.最长回文子串 *中等

思路：暴力解法，双重遍历，找到最长的那个

/** * @param {string} s * @return {string} */ var isStr = (s) => { while (s.length > 1) { if (s[0] == s[s.length - 1]) { s = s.substring(1, s.length - 1); } else { return false; } } return true; }; var longestPalindrome = function (s) { let res = ""; let end = s.length; for (let i = 0; i < end; i++) { for (let j = end; j > res.length + i; j--) { if (isStr(s.substring(i, j))) { if (j - i > res.length) { res = s.substring(i, j); } } } } return res; };

优化：动态规划。

如果一个字符串是回文串，那么它去掉首尾两个字符也是回文串。同理，一个回文串如果首尾各扩展1个字符，且扩展的字符相同，那么新

的字符串也是回文串

优化：我们用遇到的第一个回文串向两边扩展，同时记录最长字符串，最后得到结果

/** * @param {string} s * @return {string} */ var longestPalindrome = function (s) { let result = s[0] || ""; for (let i = 0; i < s.length; i++) { for (let j = 1; j <= 2; j++) { let left = i, right = i + j; while(left >= 0 && right < s.length && s[left] === s[right]) { left--, right++; }; let length = right - left - 1; //(right - 1) - (left + 1) + 1 if (length > result.length) { result = s.substr(left + 1, length); } } } return result; };

Processed: 0.014, SQL: 9