[失业前端恶补算法]JavaScript leetcode刷题top100（六）：字母异位词分组、最长连续序列、找到字符串中所有字母异位词、最大子数组和、除自身以外数组的乘积 |
您所在的位置：网站首页 › js数组字母排序 › [失业前端恶补算法]JavaScript leetcode刷题top100（六）：字母异位词分组、最长连续序列、找到字符串中所有字母异位词、最大子数组和、除自身以外数组的乘积 |
|
专栏声明：只求用最简单的，容易理解的方法通过，不求优化，不喜勿喷 49. 字母异位词分组 题面给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 知识点：哈希表、排序 思路这里用了 js 语言的一个小技巧，我们可以使用 split 这个 api 将字符串变成字符的数组，之后我们对得到的数组进行排序，这样字母异位词得到了结果字符串的一致的，之后我们哈希表将结果字符串对应的数组在输出的二位数组中的下标保存下来，我们根据这个下标找到每一个字符串应该插入的位置即可 代码 /** * @param {string[]} strs * @return {string[][]} */ var groupAnagrams = function (strs) { var obj = { }; let re = []; for (var i = 0; i re.push([strs[i]]); obj[key] = re.length - 1; } else { re[obj[key]].push(strs[i]); } } return re; }; 128. 最长连续序列 题面给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 知识点：哈希表、Set 思路遍历两次，第一次将数据存到 set 中，目的的为了去除重复的元素，之后对 set 进行遍历，如果当前元素 -1 的元素不在数组中，说明当前元素一个序列最左侧的元素，那么以它为起点向前寻找按顺序递增的序列，直到找不到下一位位置，记录其长度，输出最长的长度即可。 代码 /** * @param {number[]} nums * @return {number} */ var longestConsecutive = function (nums) { let num_set = new Set(); for (var i = 0; i if (!num_set.has(num - 1)) { let s = 0; while (num_set.has(num + s)) { s++; } re = Math.max(re, s); } } return re; }; 438. 找到字符串中所有字母异位词 题面给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。 知识点：哈希表、滑动窗口 思路我们先开一个 26 位的哈希表用于存储每个字符的出现次数，之后先对目标字符串 p 进行哈希 这个用到一个 js 语言的小技巧，如果我们对数组使用 toString 方法，那么它会返回一个由 , 分割的每一个数组元素组成的字符串，那么如果我们对两个哈希表使用 toString 方法，如果他们相同，得到的字符串也相同，我们可以用这个方法快速判定异位词 之后我们对 s 字符串进行滑动窗口操作，现在选择其中第一个和 p 大小相同的区域，将其中的每一个字符处理到哈希表中，如果此时哈希表和 p 哈希结果一样则记录这个下标，之后我们向后移动一位，在哈希表中去除上轮结果的第一个字符并且添加下一个新字符，之后再进行相等比较，直到遍历完整个 s 字符串，最后输出结果即可： 代码 /** * @param {string} s * @param {string} p * @return {number[]} */ var findAnagrams = function (s, p) { let h1 = new Array(26).fill(0); let h2 = new Array(26).fill(0); for (var i = 0; i h1[s.charCodeAt(i) - "a".charCodeAt(0)]++; now++; if(now == p.length){ if(h1.toString() == h2.toString()){ re.push(i - p.length + 1); } h1[s.charCodeAt(i - p.length + 1) - "a".charCodeAt(0)]--; now--; } } return re; }; 53. 最大子数组和 题面给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 。是数组中的一个连续部分。 知识点：动态规划 思路典型的动态规划题：对于每一位，如果它上一位的连续子数组最大和加是负数，那么应该加上它肯定比不加上它更小，所以直接从当前位开始重新计算子数组是最优解，否则它上一位的连续子数组最大和加上当前位是当前位的连续子数组最大和。我们按照这个思路依次处理每一位，每次更新出现的最大值，最后输出即可： 代码 /** * @param {number[]} nums * @return {number} */ var maxSubArray = function (nums) { var dp = []; dp[0] = 0; let re = -10000; for (var i = 1; i let head = new Array(nums.length).fill(1); let back = new Array(nums.length).fill(1); for (var i = 1; i back[i] = back[i + 1] * nums[i + 1]; } for (var i = 0; i |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |