目录

前言

一、合并两个有序数组

二、移除元素

三、删除有序数组的重复项

四、删除有序数组的重复项Ⅱ

五、取数组中出现次数大于数组长度/2的元素

六、移动数组元素

七、计算数组中相差最大的值

八、字母异位词分组

九、最长连续序列

十、移动0

十一、盛水最多的容器

---

前言

自己的算法层面较为薄弱，希望能通过尝试做力扣的题能提升下自己，以下都是根据自己的方法做出来的，比较繁琐，有的方法结合了力扣里比较优秀的解答。

一、合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

//方法一
function merge(nums1: number[], m: number, nums2: number[], n: number): void {//拿到nums2裁剪后的数组nums2.splice(n);//裁剪掉只需要m个元素nums1.splice(m);nums2.forEach(number => {//给原数组后新增数据nums1.splice(m + 1, 0, number);});//给原数组排序nums1.sort((a,b)=>a-b);
};//方法二
function merge(nums1: number[], m: number, nums2: number[], n: number): void {//从索引m开始(包括m)删除n个元素，然后添加nums2中的元素nums1.splice(m, n, ...nums2);//**注意:如果直接使用sort()不加函数体，此时如果有负数则会出现排序错误，因为默认是按照Unicode字符编码进行排序的。nums1.sort((a, b) => a - b);}

二、移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

  //删除后会立即改变数组，所以原来索引为3的会变成索引为2，但由于循环已经执行了为2的所以会直接跳过，导致错误function removeElement(nums: number[], val: number): number {for (let j = 0; j < nums.length; j++) {if (nums[j] === val) {nums.splice(j, 1);//这一步是防止splice修改数组后能再次判断当前索引j的元素是否与val相等，如果被删除的元素后也是和val一致的值就会被跳过，则删除不全j--;}}return nums.length;}

三、删除有序数组的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

ps:发现for循环真是万能的= = 

function removeDuplicates(nums: number[]): number {for (let i = 0; i < nums.length; i++) {if (nums[i] === nums[i + 1]) {nums.splice(i, 1);//防止后面还有重复的i--;}}return nums.length;
}

四、删除有序数组的重复项Ⅱ

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

ps:这一题需要连续重复起码3次及以上才会删除元素，所以可以根据这点结合快慢指针得到

function removeDuplicates(nums: number[]): number {//数组元素只有2个及以下时，此时直接返回数组长度if (nums.length <= 2) {return nums.length;} else {let slow = 2;for (let i = 2; i < nums.length; i++) {//如果连续三个或者三个以上相同则会存在索引-2值还一样if (nums[i] === nums[i - 2]) {nums.splice(i, 1);i--;//如果不一样，则说明不存在连续3个以上的数，则将索引值复制给slow} else {nums[slow] = nums[i];slow++;}}return slow;}
};

五、取数组中出现次数大于数组长度/2的元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 function majorityElement(nums: number[]): any {//次数超过数组长度/2也就是排序后出现次数最多的元素的索引需要为数组长度/2//先排序确保元素按照顺序排列nums.sort((a, b) => a - b);//向下取整 如7/2则为3，索引值为3的地方就是数组中出现次数最多的元素return nums[Math.floor(nums.length / 2)];}const a = majorityElement([1, 1, 1, 1, 1, 5, 5, 5]); //最终返回 1console.log(a);

六、移动数组元素

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

ps:刚开始实际上我使用的是时间复杂度为n平方的算法，但报超出时间限制，所以学习了他人的提交答案得到以下:

 function rotate(nums: number[], k: number): void {//k%nums.length 可以得到每一次需要移动到的实际位置，如k=1，则移动一次，如k=5，实际上和k=1移动到的位置一致，所以是整除数组长度//而实际上i%arr.length也得到每个索引值，所以移动后的索引值可以使用(i+k)%nums.length得到const arr = [...nums];for (let i = 0; i < arr.length; i++) {nums[(i + k) % arr.length] = arr[i];}}

七、计算数组中相差最大的值

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

 //找到两者差最大的两个元素function maxProfit(prices: number[]): number {//最低买入let min = prices[0];//最大利润let max = 0;for (let i = 1; i < prices.length; i++) {//找到两者之间较小的值min = Math.min(min, prices[i]);//找到两者之间较大的利润max = Math.max(max, prices[i] - min);}return max;}//第一轮prices[0]为4,4<5,min=4,max1=5-4=1//第二轮prices[0]为4,4<7,min=4,max1=7-4=3//第一轮prices[0]为4,4>1,min=1,max0=1-1=0,3>0,max1=3//第一轮prices[0]为4,1<2,min=1,max0=2-1=1,3>1,max1=3

八、字母异位词分组

‌字母异位词‌是指由相同的字母组成，但字母排列顺序不同的单词。例如，"cat"和"act"就是一对字母异位词

 //字母异位词:字符串组合的字母都是相同的，只是顺序不同。如abc,cba,bac，互为字母异位词function groupAnagrams(strs: string[]): string[][] {const map = new Map();//遍历出数组中的每一项for (let str of strs) {//将字符串转换为数组后将数组排序，如果位异位词那么得到的数组一定是相同的const arr = Array.from(str);arr.sort();let key = arr.toString();if (map.has(key)) {map.set(key, map.get(key).concat([str]));} else {map.set(key, [str]);}}//获取可迭代对象的值转换为数组const list = [...map.values()];return list;}groupAnagrams(['abc', 'cba', 'abs']);//[['abc','cba'],['abs']]

九、最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

 //求有序列的最大连续值，其实就是先去重，再判断每个数是不是有序列的第一个值，如果不是，则说明他前面还有其他的值，如果是，则往后走//这道题首先，先将数组去重，因为重复的值是没有意义的，其次遍历去重后的数组，对遍历出的每个值都进行判断，//这个值是否为序列最开始，也就是没有当前值 - 1，如果是则最长序列为当前值，且判断当前值 + 1是否存在这个数组内，如果存在则最长序列再 + 1，这样循环判断function longestConsecutive(nums: number[]): number {const setList = new Set(nums);let max = 0;for (let num of setList) {//如果去重后的数组中不存在当前值-1，说明当前值就是序列开头,如果存在则不进入，直到找到当前序列的最小if (!setList.has(num - 1)) {let currentNum = num;let cureentLength = 1;//赋值当前值，防止while循环重复循环，需要有个跳出循环的条件//如果存在当前值后面的值，则说明序列还能增加while (setList.has(currentNum + 1)) {currentNum++;cureentLength++;}//找到每一次循环时较长的序列max = Math.max(max, cureentLength);}}return max;}longestConsecutive([9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6]); // [3,4,5,6,7,8,9] //最长序列为7

十、移动0

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

 自己想的一个不规范的方法，用到了删除：

/**Do not return anything, modify nums in-place instead.*/
function moveZeroes(nums: number[]): void {let count = 0;for (let i = 0; i < nums.length; i++) {//如果数值为0就计数if (!nums[i]) {//删除当前0nums.splice(i, 1);//删除后后面的元素会往前移，所以需要i--重新遍历当前元素i--;count++;}}//删除了多少个0就在末尾加多少个0nums.push(...new Array(count).fill(0));
};

规范的方法： 

 //所有0移动到数组末尾，其余数按照原始顺序排列//使用双指针，fast快指针遍历数组，slow慢指针用于储存不为0的数，当fast指针指向的值不为0，则赋值给slow，最后slow前的值都不为0，slow后的都为0function moveZeroes(nums: number[]): void {let fast = 0;let slow = 0;while (fast < nums.length) {//所有不为0的都位于[0,slow-1]中if (nums[fast] !== 0) {nums[slow] = nums[fast];//最后一个不为0的值的索引值为slow-1slow++;}fast++;}//第一个while循环执行完后，再执行第二个while循环//这个while循环用于判断除去不为0的数的索引其余都应该填充为0while (slow < nums.length) {nums[slow] = 0;slow++;}console.log(nums);}moveZeroes([0, 0, 3, 1, 5, 2, 8, 0]); //[3,1,5,2,8,0,0,0]

十一、盛水最多的容器

ps:其实这道题的重点 //其实这道题就是找到（索引值相减*索引值对应整数的较小值）得到的最大值，遍历两次拿到每一次的较大者，最终输出最大值

 这个方法在力扣上不对：超出时间执行范围了

 //其实这道题就是找到（索引值相减*索引值对应整数的较小值）得到的最大值function maxArea(height: number[]): number {let max = 0;//j永远是i的下一个索引开头，索引为i+1for (let i = 0; i < height.length; i++) {for (let j = i + 1; j < height.length; j++) {const num = (j - i) * Math.min(height[i], height[j]);//每次比较取到最大值max = Math.max(max, num);}}return max;}maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]);//49

使用官方方法：重点是左右两个指针，左指针指向开头索引为0，右指针指向末尾，比较左右两个指针对应的值的大小，如果左指针指向的值偏小则左指针偏右，如果右指针指向的值偏小则右指针偏左，这样可以确保是找最大面积 **注意：如果左指针指向的值偏小移动右指针此时宽度是减小1的且高度也只会比原来小或者不变，因为是以小的值为准，一个桶能装多少水,取决于短板

 function maxArea(height: number[]): number {//使用双指针，左指针指向索引为0，右指针指向height.length-1,此时如果height[i]>height[j]，则移动较小者，因为最大面积就是高度的较小者决定的//如果移动较高者，不管怎么移动在宽度变小的情况下，结果只会比原来小或者不变，所以我们来移动较小者let left = 0;let right = height.length - 1;let maxArea = 0;while (left < right) {let currentArea = (right - left) * Math.min(height[left], height[right]);maxArea = Math.max(maxArea, currentArea);//移动值较小者，才有可能得到较大面积if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;}maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]);//49