283. 移動(dòng)零 - 力扣（LeetCode） (leetcode-cn.com)
數(shù)組nums， 把0移動(dòng)到末尾，同時(shí)保持非零元素的相對(duì)順序
輸入: [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)
一個(gè)數(shù)組
nums和一個(gè)值val躏升，你需要 原地 移除所有數(shù)值等于val的元素，并返回移除后數(shù)組的新長度贞绳。
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
思路：從后向前遍歷，splice(索引, 刪除的個(gè)數(shù))
/**
* @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. 刪除有序數(shù)組中的重復(fù)項(xiàng) - 力扣（LeetCode） (leetcode-cn.com)
一個(gè)有序數(shù)組
nums致稀，請(qǐng)你 原地 刪除重復(fù)出現(xiàn)的元素冈闭，使每個(gè)元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度抖单。
輸入：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. 刪除有序數(shù)組中的重復(fù)項(xiàng) II - 力扣（LeetCode） (leetcode-cn.com)
一個(gè)有序數(shù)組
nums萎攒，請(qǐng)你 原地 刪除重復(fù)出現(xiàn)的元素，使每個(gè)元素 最多出現(xiàn)兩次 矛绘，返回刪除后數(shù)組的新長度耍休。
輸入：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)
給定一個(gè)包含紅色、白色和藍(lán)色货矮，一共 n 個(gè)元素的數(shù)組羊精，原地對(duì)它們進(jìn)行排序，使得相同顏色的元素相鄰囚玫，并按照紅色喧锦、白色、藍(lán)色順序排列抓督。
此題中裸违，我們使用整數(shù) 0、 1 和 2 分別表示紅色本昏、白色和藍(lán)色。
輸入：nums = [2,0,2,1,1,0]
輸出：[0,0,1,1,2,2]
思路：三路快排(本質(zhì)是交換)
/**
* @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, 注意是前閉區(qū)間后閉區(qū)間
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. 合并兩個(gè)有序數(shù)組 - 力扣（LeetCode） (leetcode-cn.com)
兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2枪汪，請(qǐng)你將 nums2 合并到 nums1 中涌穆，使 nums1 成為一個(gè)有序數(shù)組怔昨。
輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
思路：歸并排序
歸并排序會(huì)開辟一個(gè)長度為nums1 + nums2的數(shù)組
從后向前遍歷
/**
* @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. 數(shù)組中的第K個(gè)最大元素 - 力扣（LeetCode） (leetcode-cn.com)
在未排序的數(shù)組中找到第 k 個(gè)最大的元素
需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素宿稀。
/**
* @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. 兩數(shù)之和 II - 輸入有序數(shù)組 - 力扣（LeetCode） (leetcode-cn.com)
給定一個(gè)已按照 升序排列 的整數(shù)數(shù)組 numbers 趁舀，請(qǐng)你從數(shù)組中找出兩個(gè)數(shù)滿足相加之和等于目標(biāo)數(shù) target
輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等于目標(biāo)數(shù) 9 。因此 index1 = 1, index2 = 2 祝沸。
思路：對(duì)撞指針
/**
* @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開始計(jì)算
return res;
} else if(numbers[l] + numbers[r] < target) {
l++;
} else{
r--;
}
}
}
125. 驗(yàn)證回文串 - 力扣（LeetCode） (leetcode-cn.com)
給定一個(gè)字符串矮烹，驗(yàn)證它是否是回文串，只考慮字母和數(shù)字字符罩锐，可以忽略字母的大小寫
輸入: "A man, a plan, a canal: Panama"
輸出: true
思路：對(duì)撞指針
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
// 匹配1-9a-zA-Z,正則所有大寫轉(zhuǎn)小寫
// 替換所有與范圍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. 反轉(zhuǎn)字符串 - 力扣（LeetCode） (leetcode-cn.com)
編寫一個(gè)函數(shù)奉狈，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 char[] 的形式給出涩惑。
原地修改輸入數(shù)組仁期、使用 O(1) 的額外空間解決這一問題。
輸入：["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
對(duì)撞指針
/**
* @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. 反轉(zhuǎn)字符串中的元音字母 - 力扣（LeetCode） (leetcode-cn.com)
編寫一個(gè)函數(shù)竭恬，以字符串作為輸入跛蛋，反轉(zhuǎn)該字符串中的元音字母
思路： 對(duì)撞指針
/**
* @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('') // 字符串轉(zhuǎn)數(shù)組
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)
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下痊硕，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49
思路：對(duì)撞指針
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;
}
