给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
示例
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],输出:[["ate","eat","tea"],["nat","tan"],["bat"]]
思路
我们先遍历数组,把每个字母异位词都进行排序。再将排序后的字符串作为 key,将 key 值一样的字母异位词置于同一个数组中。最后,再按照题目所要求的格式返回数组。
详解
创建个空对象 obj,用于后续将字母异位词分类储存;
创建个空数组 arr,用与后续返回结果;
遍历数组里的元素;
将每个字母异位词进行排序,并将排序后的字符串作为 key,可知 key 值一样的即为字母异位词,将他们置于同一个数组中(即 obj["aet"] = ["ate","eat","tea"]);
待上述遍历结束,再遍历 obj,将 obj 的每一个值,push 到 arr 中。
const groupAnagrams = function (strs) {const obj = {};const arr = [];// 遍历数组for (let i = 0; i < strs.length; i++) {// 将每个字母异位词进行排序,并将排序后的字符串作为 keyconst unit = Array.from(strs[i]).sort().join('');// 将 key 值一样的字母异位词置于同一个数组中if (!obj[unit]) {obj[unit] = [];}obj[unit].push(strs[i]);}for (const i in obj) {arr.push(obj[i]);}return arr;};
复杂度分析
时间复杂度:
外层 strs for 循环为 ,里面根据字符数据进行排序,查资料得排序时间复杂度为 ,k 为字符串长度最大值,即整个时间复杂度为 。
空间复杂度:
代码运行时创建了 obj 对象用于存储 strs 中的字符串,空间与 strs 长度与字符串长度成正比关系,所以空间复杂度为 。
思路
我们先遍历数组,每次都创建一个长度为 26,元素全是 0 的数组,用于记录每个单词中每个字符出现的次数;然后将其转化为字符串作为 key,将 key 值一样的字母异位词置于同一个数组中。最后,再按照题目所要求的格式返回数组。
详解
1.创建个空对象 obj,用于后续将字母异位词分类储存;
2.创建个空数组 arr,用与后续返回结果;
3.遍历数组里的元素;
4.每次遍历都创建一个长度为 26(跟 26 个英文字母对应),元素全是 0 的数组,用于记录每个单词中每个字符出现的次数,然后将该数组转化的字符串作为 key,可知 key 值一样的即为字母异位词,将他们置于同一个数组中;
5.待上述遍历结束,再遍历 obj,将 obj 的每一个值,push 到 arr 中。
代码
const groupAnagrams = function (strs) {const obj = {};const arr = [];// 遍历数组for (let i = 0; i < strs.length; i++) {// 都创建一个长度为 26,元素全是 0 的数组,用于记录每个单词中每个字符出现的次数const unit = new Array(26).fill(0);for (let j = 0; j < strs[i].length; j++) {const index = strs[i].charCodeAt(j) - 97;unit[index] += 1;}// 将每个数组转化的字符串作为 keyconst newUnit = JSON.stringify(unit);// 将 key 值一样的字母异位词置于同一个数组中if (!obj[newUnit]) {obj[newUnit] = [];}obj[newUnit].push(strs[i]);}for (const i in obj) {arr.push(obj[i]);}return arr;};
复杂度分析
时间复杂度:
外层 strs for 循环为 ,内层为对字符串进行 for 循环,时间复杂度为 ,k 为字符串长度最大值,即整个时间复杂度为 。
空间复杂度:
代码运行时创建了 obj 对象用于存储 strs 中的字符串,空间与 strs 长度与字符串长度成正比关系,所以空间复杂度为 。
给定一个包含 n
个整数的数组 nums
,判断 nums
中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],满足要求的三元组集合为:[[-1, 0, 1],[-1, -1, 2]]
思路
我们首先想到的是三重循环,题目中要求三元组不能重复,因此对每次插入数组对三元组做一下简单的记录。
详解
直接对数组进行3重遍历,当三个数的和等于 0 时,插入数组,同时对已经插入对数据做一下记录
const threeSum = function (nums) {const res = [];const uniqueMap = {};nums.sort();for (let i = 0; i < nums.length - 2; i++) {for (let j = i + 1; j < nums.length - 1; j++) {for (let k = j + 1; k < nums.length; k++) {if (nums[i] + nums[j] + nums[k] === 0) {const item = [nums[i], nums[j], nums[k]];if (!uniqueMap[item.join(',')]) {res.push(item);uniqueMap[item.join(',')] = 1;}}}}}return res;};
复杂度分析
时间复杂度:
解法虽然简单,套三重循环,时间复杂度高。
空间复杂度:
额外申请了uniqueMap的空间,复杂度为
思路
首先对数组进行排序,便于在插入的时候去重,进行双指针遍历时,遇到重复的数就可以很方便得跳过。
详解
先将数组排序,令左指针,右指针,当时,进行循环
当 时,将三个数插入数组,同时判断 和 是否重复,去重复解之后,同时将 和 移到下一个位置
若 小于 0,说明 太小, 需要右移,
若 大于 0,说明 太大, 需要左移,
const threeSum = function (nums) {const res = [];nums.sort((a, b) => a - b);const length = nums.length;for (let i = 0; i < length; i++) {let left = i + 1;let right = length - 1;while (left < right) {const sum = nums[i] + nums[left] + nums[right];if (sum === 0) {res.push([nums[i], nums[left], nums[right]]);const leftValue = nums[left];// 这两步是为了去重while (left < length && nums[left] === leftValue) {left++;}const rightValue = nums[right];while (right > left && nums[right] === rightValue) {right--;}} else if (sum < 0) {// 小于 0 说明太小了,需要向右移动left++;} else {// 太大了,把右边的指针向左移动right--;}}while (i + 1 < nums.length && nums[i] === nums[i + 1]) {i++;}}return res;};
复杂度分析
时间复杂度:
数组遍历 ,双指针遍历 ,因此复杂度为 为
空间复杂度:
指针使用常数大小的额外空间
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例1
输入: "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例2
输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例3
输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
维护一个数组,数组里从前到后存放着字符。 在遍历过程中,维持数组中字符不重复,如果重复,则从数组中 shift 出字符, 直到移除那个重复字符为止,并记录下数组的最长长度。
思路
用一个数组来储存当前字符, 在遍历过程中不断地存入不重复字符,遇到重复字符则整理数组达到字符不重复的条件。
详解
初始化一个数组和最大值, 从前向后遍历字符串, 如果该字符不在数组中,则把字符 push 到数组中,并且比较记录下当前最大值。 否则就从头部向外 pop 字符直到该重复字符被移除, 如此循环直到结束。
const lengthOfLongestSubstring = function (s) {let current = 0;let max = 0;const list = [];const len = s.length;for (; current < len; current++) {if (list.indexOf(s[current]) === -1) {list.push(s[current]);} else {do {list.shift();} while (list.indexOf(s[current]) !== -1);list.push(s[current]);}max = Math.max(list.length, max);}return max;};
复杂度分析
时间复杂度:
这样子需要从前向后遍历一遍长度为 的字符串,需要进行 次字符是否重复的比较。
空间复杂度:
在计算比较过程中,数组最长有可能存放 个不重复字符串。
从前到后遍历字符串,维护一个string,记录着不重复字符子串。 每当遇到重复的字符时候,找到string中重复的字符,并截断。 循环往复直到遍历最后一个字符.
思路
记录当前正在遍历的不重复字串的子集 string , 在遍历过程中不断地添加不重复字符,遇到重复字符则截断 string 达到 string 内补字符不重复的条件。
详解
初始化一个 string 和最大值,
从前向后遍历字符串,
如果该字符不在 string 中,则添加字符到 string 中,并记录下最大值。
否则就截断字符串,如此循环直到结束。
const lengthOfLongestSubstring = function (s) {let num = 0;let max = 0;let subString = '';for (char of s) {if (subString.indexOf(char) === -1) {subString += char;num++;max = max < num ? num : max;} else {subString += char;subString = subString.slice(subString.indexOf(char) + 1);num = subString.length;}}return max;};
复杂度分析
时间复杂度:
我们只遍历了包含有 个元素的字符串一次。
空间复杂度:
所需的额外空间取决于子串的长度,子串始终小于等于传入字符串的长度,该子串最多需要存储 个元素。
给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1
输入:[[1,1,1],[1,0,1],[1,1,1]]输出:[[1,0,1],[0,0,0],[1,0,1]]
示例 2
输入:[[0,1,2,0],[3,4,5,2],[1,3,1,5]]输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
进阶
一个直接的解决方案是使用 的额外空间,但这并不是一个好的解决方案。
一个简单的改进方案是使用 的额外空间,但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗?
注意事项
注意边遍历边修改原数组,以免未遍历元素受 0 值的影响。
思路
申请额外空间去记录需要置为 0 的行号和列号
详解
申请 的额外空间,声明两个数组,所占空间最大值分别为 ,,分别存放水平方向、垂直方向应该重置为零的元素下标
从上到下,从左到右依次遍历原数组,记录元素为 0 的横坐标与纵坐标到提前声明的两个需置零的数组
待遍历结束后,再次遍历原数组,按照两个需置零的数组把元素置为零。
const setZeroes = function (matrix) {const len = matrix.length;const width = matrix[0].length;const vertical = [];const horizontal = [];for (let i = 0; i < len; i++) {for (let j = 0; j < width; j++) {if (!matrix[i][j]) {vertical.push(j);horizontal.push(i);}}}for (let i = 0; i < len; i++) {if (horizontal.indexOf(i) > -1) {matrix[i].fill(0, 0, width);}for (let j = 0; j < vertical.length; j++) {matrix[i][vertical[j]] = 0;}}};
时间复杂度:
算法包括两个遍历,运行次数为是 ,所以时间复杂度是
空间复杂度:
额外空间包括若干个常量和两个长度分别为 ,的数组
思路
我们不能再额外创建数组来记录 0 的位置,从原数组本身找突破点,用原数组的第一行和第一列记录该行或该列需不需要置零,再根据首行首列的标识对元素置零
参考图
详解
首先从左到右,从上到下遍历数组中每一个元素(列遍历从第二列开始),若该元素为 0,则同时设置改行首列元素、首行该列元素为 0,若首列存在为 0 元素,则设置标识,意为首列元素会被全部置零,此目的是区分行元素与首列元素置零的标识,
然后,从右到左,从下到上遍历数组,若首行该列或该行首列元素为 0,则置该元素为 0,若存在标识,则置首列元素为 0,为什么不选择从左到右,从上到下遍历?是因为首行首列的先根据标志置零,新的零元素会影响后面的数据。
const setZeroes = function (matrix) {const len = matrix.length;const width = matrix[0].length;let flag = false;for (let i = 0; i < len; i++) {if (!matrix[i][0]) {flag = true;}for (let j = 1; j < width; j++) {if (!matrix[i][j]) {matrix[i][0] = 0;matrix[0][j] = 0;}}}for (let i = len - 1; i >= 0; i--) {for (let j = width - 1; j > 0; j--) {if (!matrix[0][j] || !matrix[i][0]) {matrix[i][j] = 0;}}if (flag) {matrix[i][0] = 0;}}};
复杂度分析:
时间复杂度:
算法包括两个遍历,运行次数都是 ,所以时间复杂度是
空间复杂度:
额外空间包括若干个常量,与 、大小无关
给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1, 使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 ,空间复杂度为 。
示例 1:
输入: [1, 2, 3, 4, 5];输出: true;
示例 2:
输入: [5, 4, 3, 2, 1];输出: false;
思路
使用 one 和 two 两个数。保证 one 小于 two,若遍历到一个数大于 two,则满足3个数递增。返回true
设置两个变量,one 代表三元子序列的第一个,two代表三元子序列的第二个。
例如:
第一个数作为 one,第二个数若比第一个数大,这两个数可以成三元子序列中的前两个,于是可以赋值给two;
第三个数比第二个数小,说明三元子序列可能会从这个数开始
one、two 的初始值为 undefined,任意数与undefined做比较均为 false。
现在,开始循环遍历 num,若:
num > two,说明可以构成三元子序列了,返回 true
num > one,说明 num 比 two 小(或等于),比 one 大,可以将 two 更新为此 num,
num < one,则这个 num 可以成为三元子序列的最小者,更新 one 为 num。
/*** @param {number[]} nums* @return {boolean}*/const increasingTriplet = function (nums) {if (nums.length < 3) return false;let one,two;for (const num of nums) {if (num > two) {return true;} else if (num > one) {two = num;} else {one = num;}}return false;};
复杂度分析
时间复杂度:,遍历了1次含个元素的空间
空间复杂度:,遍历过程没有用到新的空间存储数据
思路
循环遍历数组,不断更新数组内出现的最小值与最大值,如果出现的一个大于最大值的数,则表示存在长度为 3 的递增子序列。
详解
若目标数组 nums 存在递增的三元子序列,设这三个数为 a1,a2,a3,则 a3>a2>a1
。
可以先定义两个变量 small, big (samll < big) 分别用于存放最小的两个数字,在js中使用 Number.MAX_SAFE_INTEGER
常量表示最大的安全整数(maxinum safe integer)(2^53 - 1)。
遍历数组,实时捕获当前最小的两个数,同时判断在这两个数后方是否存在一个数字a3>small && a3>big
,若存在,即该数组存在长度为3的递增的子序列。
/*** @param {number[]} nums* @return {boolean}*/const increasingTriplet = function (nums) {let small = Number.MAX_SAFE_INTEGER;let big = Number.MAX_SAFE_INTEGER;for (let i = 0; i < nums.length; i++) {if (nums[i] <= small) {small = nums[i];} else if (nums[i] <= big) {big = nums[i];} else {return true;}}return false;};
复杂度分析
时间复杂度:
遍历了 1 次含 个元素的空间
空间复杂度:
遍历过程没有用到新的空间存储数据