算法：数组(二)
283. 移动零 - 力扣（LeetCode） (leetcode-cn.com)
数组nums， 把0移动到末尾，同时保持非零元素的相对顺序
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
思路：双指针
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function (nums){
key = 0; // 0-key非零元素
for(let i = 0; i < nums.length; i++) {
if(nums[i]){
nums[key] = nums[i];
key++
}
}
for(let i = key; i < nums.length; i++) {
nums[i] = 0
}
}
27. 移除元素 - 力扣（LeetCode） (leetcode-cn.com)
一个数组
nums和一个值val，你需要 原地 移除所有数值等于val的元素，并返回移除后数组的新长度。
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
思路：从后向前遍历，splice(索引, 删除的个数)
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
for(let i=nums.length-1; i>=0; i--) {
if(nums[i] === val) {
nums.splice(i, 1)
}
}
return nums.length
}
26. 删除有序数组中的重复项 - 力扣（LeetCode） (leetcode-cn.com)
一个有序数组
nums，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
输入：nums = [1,1,2]
输出：2, nums = [1,2]
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
for(let i=nums.length-1; i>= 0; i--) {
if(nums[i]===nums[i-1]){
nums.splice(i, 1)
}
}
return nums.length
}
80. 删除有序数组中的重复项 II - 力扣（LeetCode） (leetcode-cn.com)
一个有序数组
nums，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function (nums){
if(nums.length <= 2) return nums.length;
let count = 0;
for(let i = nums.length-1; i >= 0;) {
if(nums[i] === nums[i-1]) {
count++
if(count > 1) {
nums.splice(i, 1);
count = 0;
} else{
i--
}
} else {
i--;
count = 0
}
}
return nums.length
}
75. 颜色分类 - 力扣（LeetCode） (leetcode-cn.com)
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
思路：三路快排(本质是交换)
三路快排.png
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
function swap(nums, i, j){
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp
}
var sortColors = function(nums) {
let zero = -1; // nums[0...zero] === 0, 注意是前闭区间后闭区间
let two = nums.length; // nums[two...n-1] === 2
for(let i=0; i < two;) {
if(nums[i] === 1) {
i++
} else if(nums[i] === 2) {
swap(nums, i, --two)
} else { // 为0的情况
swap(nums, ++zero, i++)
}
}
}
88. 合并两个有序数组 - 力扣（LeetCode） (leetcode-cn.com)
两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
思路：归并排序
归并排序会开辟一个长度为nums1 + nums2的数组
从后向前遍历
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
m--;
n--;
let l = nums1.length -1 // nums1的长度
while(m >= 0 && n >= 0) {
if(nums1[m] > nums2[n]) {
nums1[l] = nums1[m];
l--;
m--;
} else {
nums1[l] = nums2[n];
l--;
n--;
}
}
while(n >= 0) nums1[l--] = nums2[n--]
return nums1;
}
215. 数组中的第K个最大元素 - 力扣（LeetCode） (leetcode-cn.com)
在未排序的数组中找到第 k 个最大的元素
需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
for(let i=0; i< nums.length; i++){
for(let j=i+1; j<nums.length; j++){
if(nums[j]>nums[i]){
const temp = nums[j]
nums[j] = nums[i]
nums[i] = temp
}
}
}
return nums[k-1]
};
167. 两数之和 II - 输入有序数组 - 力扣（LeetCode） (leetcode-cn.com)
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
思路：对撞指针
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let l = 0, r = number.length - 1;
while(l < r) {
if(numbers[l] + numbers[r] === target) {
let res = [l+1, r+1] // 题目索引要求从1开始计算
return res;
} else if(numbers[l] + numbers[r] < target) {
l++;
} else{
r--;
}
}
}
125. 验证回文串 - 力扣（LeetCode） (leetcode-cn.com)
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写
输入: "A man, a plan, a canal: Panama"
输出: true
思路：对撞指针
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
// 匹配1-9a-zA-Z,正则所有大写转小写
// 替换所有与范围a-zA-Z0-9不匹配的字符
let sArray = s.replace(/[^0-9a-zA-Z]/g,'').toLowerCase()
let l = 0, r = sArray.length - 1;
while(l < r) {
if(sArray[l] === sArray[r]) {
l++;
r--;
} else{
return false;
}
}
return true
}
344. 反转字符串 - 力扣（LeetCode） (leetcode-cn.com)
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
对撞指针
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
function swap(array, l_index, r_index) {
let temp = array[l_index];
array[l_index] = array[r_index];
array[r_index] = temp
}
var reverseString = function(s) {
let l = 0, r = s.length - 1
while(l < r) {
swap(s, l, r)
l++;
r--;
}
return s
}
345. 反转字符串中的元音字母 - 力扣（LeetCode） (leetcode-cn.com)
编写一个函数，以字符串作为输入，反转该字符串中的元音字母
思路： 对撞指针
/**
* @param {string} s
* @return {string}
*/
function swap(array, l_index, r_index){
let temp = array[l_index];
array[l_index] = array[r_index];
array[r_index] = temp
}
var reverseVowels = function(s) {
let vowel = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
s = s.split('') // 字符串转数组
let l = 0, r = s.length - 1
while(l < r) {
if(vowel.includes(s[l])){
l = l
} else {
l++
}
if(vowel.includes(s[r])){
r = r
} else {
r--
}
if(vowel.indexOf(s[l]) != -1 && vowel.indexOf(s[r]) != -1) {
swap(s, l, r)
l++;
r--;
}
}
return s.join("")
}
11. 盛最多水的容器 - 力扣（LeetCode） (leetcode-cn.com)
image.png
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49
思路：对撞指针
var maxArea = function(height) {
let l = 0, r = height.length - 1;
let max = 0;
while(l < r) {
let area = Math.min(height[l], height[r]) * (r - l)
let max = 0;
if( area > max) {
max = area
}
if(height[r] < height[l]) {
const lastl = height[l]
l++;
while(height[l] <= lastl && l < r) {
l++;
}
} else {
const lastr = height[r]
r--;
while(lastr >= height[r] && l < r) {
r--;
}
}
}
return max;
}
