前言
春招要來了，大三的我目标找到一家實習公司，趁着這段空閑時間，來溫習溫習資料結構與算法吧。來看數組篇吧。
數組知識點回顧
這裡是在刷題過程中一些小的知識點的總結
- Array的正常方法
- 疊代方法:
every()
some()
forEach()
map()
filter()
(item,index,arr)
- 縮小方法:
reduce()
reduceRight()
(prev,cur,index,arr)
- Array的
includes
方法
用于檢測數組中是否包含某一項
- ES6引入的
Set()
- 求數組中最大值的幾種方法
- 方法一：ES6的拓展運算符
var array = [1,2,3,4]
return Math.max(...array)
- 方法二：ES5的
apply
var array = [1,2,3,4]
return Math.max.apply(null,array)
- 方法三：
reduce
var array = [1,2,3,4]
return arr.reduce((prev,cur,arr)=>{
return prev > cur ? prev:cur;
})
- 方法四、五
for
sort
- 數組的
concat
slice
splice
var arr1 = [1,2,3,4]
var arr2 = [5]
var arr3 = arr1.concat(arr2) //[1,2,3,4,5]
return arr1 //[1,2,3,4]
arr1.slice(0,1)
return arr1 //[1,2,3,4]
arr1.splice(0,1)
return arr1 //[2,3,4]
6.
find()
函數
查詢數組中某一項
let age = [1,2,3]
age.find(item => 1) //1
age.find(item > 2) //3
- 一些小問題
[1,2,3] === [1,2,3] //false
[1,2,3] == "1,2,3" //true
new Set([1,1,2,[1,2],[1,2]])//{1,2,[1,2],[1,2]}
兩個數組的交集_簡單
給定兩個數組：編寫一個函數來計算它們的交集。 示例 1: 輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出:[2] 示例 2: 輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 輸出: [9,4]
說明:輸出結果中的每個元素一定是唯一的。我們可以不考慮輸出結果的順序。
1. 使用
filter()
函數暴力求解
兩次周遊數組，将相同項
push
進結果數組中，再使用
filter()
函數進行重複元素過濾。
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
var tempArray = [];
for(var i of nums1){
for(var j of nums2){
if(i===j){
tempArray.push(i);
}
}
}
var returnNum = [];
returnNum = tempArray.filter(function(item, index, arr){
return index === arr.indexOf(item);
})
return returnNum;
};
- 使用ES6的
Set()
filter()
Set()
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
return [...new Set(nums1.filter((item) => {
return nums2.includes(item);
}))]
};
3. 排序後雙指針查找
傳統解法，對數組分别排序後，進行雙指針周遊。
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
nums1 = nums1.sort((a,b) => a-b);
nums2 = nums2.sort((a,b) => a-b);
let returnArray = new Set();
let i=0;
let j=0;
while(i<nums1.length&&j<nums2.length){
if(nums1[i]<nums2[j]){
i++;
}else if(nums1[i]>nums2[j]){
j++;
}else{
returnArray.add(nums1[i]);
i++;
j++;
}
}
return [... returnArray]
};
合并區間_簡單
給出一個區間的集合，請合并所有重疊的區間.
示例 1: 輸入: [[1,3],[2,6],[8,10],[15,18]] 輸出:[[1,6],[8,10],[15,18]] 解釋: 區間[1,3] 和 [2,6] 重疊, 将它們合并為 [1,6].
示例 2: 輸入:[[1,4],[4,5]] 輸出: [[1,5]] 解釋: 區間 [1,4] 和 [4,5] 可被視為重疊區間。
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
if(intervals.length===0||intervals.length===1){
return intervals;
}
let returnArray = [];
intervals = intervals.sort((a,b) => a[0]-b[0]);
returnArray.push(intervals.reduce((pre,cur) =>{
if(pre[1]>=cur[0]){
if(pre[1]<=cur[1]){
pre[1]=cur[1];
}
return pre;
}else{
returnArray.push(pre);
return cur;
}
}));
return returnArray;
};
将數組分成和相等的三個部分_簡單
給定一個整數數組 A，隻有我們可以将其劃分為三個和相等的非空部分時才傳回 true，否則傳回 false。
形式上，如果我們可以找出索引i+1 < j 且滿足 (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … +A[j-1] == A[j] + A[j-1] + … + A[A.length - 1]) 就可以将數組三等分。
示例 1：輸出：[0,2,1,-6,6,-7,9,1,2,0,1] 輸出：true 解釋：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1= 2 + 0 + 1
示例 2： 輸入：[0,2,1,-6,6,7,9,-1,2,0,1] 輸出：false 示例 3： 輸入[3,3,6,5,-2,2,5,1,-9,4] 輸出：true 解釋：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 -
9 + 4
提示： 3 <= A.length <= 50000
-10000 <= A[i] <= 10000
/**
* @param {number[]} A
* @return {boolean}
*/
var canThreePartsEqualSum = function (A) {
if (A.forEach(item => item === 0)) return true
let sum = A.sum()
let avg = sum / 3
let ins = 0, count = 0
for (const i of A) {
ins = ins + i
if (ins === avg) {
count++
ins = 0
}
}
return count === 3
};
Array.prototype.sum = function () {
return this.reduce((pre, cur) => pre + cur)
}
兩數之和_簡單
給定一個整數數組 nums 和一個目标值 target，請你在該數組中找出和為目标值的那 兩個 整數，并傳回他們的數組下标。
你可以假設每種輸入隻會對應一個答案。但是，你不能重複利用這個數組中同樣的元素。 示例: 給定 nums = [2, 7, 11, 15],
target = 9 因為 nums[0] + nums[1] = 2 + 7 = 9 是以傳回 [0, 1]
解法如下，可以兩次周遊暴力求解；同樣也可以根據數組中值與索引的關系建立
Map()
字典。
1. 暴力求解
最好的辦法莫過于暴力梭哈，兩次周遊數組，滿足條件時傳回結果。
時間複雜度:O(n)=n²
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for(var i=0;i<nums.length;i++){
for(var j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]===target){
return [i,j]
}
}
}
};
2. HashMap求解
根據數組中數值和索引的關系建立
Map()
這一資料結構，可以省去一次周遊，通過檢查
Map
中待比對兩數的索引是否存在即可求解。
時間複雜度O(n)=n
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
var resultArray = [];
var hashSet = new Map();
for(var i=0;i<nums.length;i++){
var tempValue = target - nums[i];
var tempIndex = hashSet.get(tempValue);
if(hashSet.has(tempValue) && tempIndex != i){
resultArray.push(tempIndex);
resultArray.push(i);
return resultArray;
}else{
hashSet.set(nums[i],i);
}
}
return resultArray;
};
買股票的最佳時機_簡單
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
如果你最多隻允許完成一筆交易（即買入和賣出一支股票），設計一個算法來計算你所能擷取的最大利潤。 注意你不能在買入股票前賣出股票。
示例1:輸入: [7,1,5,3,6,4] 輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 =6）的時候賣出，最大利潤 = 6-1 = 5 。注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。
示例 2: 輸入: [7,6,4,3,1] 輸出: 0
解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。
可使用對數組兩輪周遊得到每種情況的買賣數值，進而求最大值。更好的辦法在于動态規劃，周遊數組得到最小值，并比較得出後續數組元素與最小值的內插補點利潤的最大值。
1. 暴力求解
兩次周遊數組，将每次買賣情況的利潤均存入另一數組中，最後取得數組中最大值。
時間複雜度O(n)=n²
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
var maxArray = [0];
var length = prices.length;
for(var i=0;i<length;i++){
for(var j=i+1;j<length;j++){
if(prices[j]>prices[i]){
maxArray.push(prices[j]-prices[i])
}
}
}
return Math.max(...maxArray)
};
2. 動态規劃
單次周遊數組，找到最小值。然後比較後續數組與最小值的內插補點的最大值。
/**
* @param {number[]} prices
* @return {number}
*/
//curMin表示目前最小值
//max表示每次買賣利潤中的最大值
var maxProfit = function(prices) {
var curMin = prices[0];
var max = 0;
for(const i of prices){
if(curMin > i){
curMin = i;
continue;
}
max = Math.max(max,i-curMin);
}
return max;
};
最大子序和_簡單
給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。
示例: 輸入:[-2,1,-3,4,-1,2,1,-5,4], 輸出: 6 解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。
1. 動态規劃
與上題相似，周遊一次數組，若目前累計值為正值可繼續保留，否則将目前周遊值設為累計值。最後比較得出所有周遊過程中的最大值。
/**
* @param {number[]} nums
* @return {number}
*/
//sum表示目前周遊累計值
//ins表示周遊過程中最大值
var maxSubArray = function(nums) {
var sum=0;
var ins=nums[0];
for(const num of nums){
if(sum < 0){
sum = num;
}else{
sum = sum + num;
}
ins = Math.max(sum,ins);
}
return ins;
};
合并兩個有序數組_簡單
給定兩個有序整數數組 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成為一個有序數組。
說明: 初始化 nums1 和 nums2 的元素數量分别為 m 和 n。 你可以假設 nums1 有足夠的空間（空間大小大于或等于 m + n）來儲存nums2 中的元素。
示例: 輸入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n =3
輸出: [1,2,2,3,5,6]
關鍵在于要對數組本身進行操作，而不是生成一個副本數組。是以直接在數組上進行
slice
和
concat
等方法均無效
1. 重新指派。
将數組去除無效值并重新排序後，循環數組，進行重新指派。
時間複雜度O(n)=n
/**
* @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) {
var tempArray = nums1.splice(0,m).concat(nums2)
tempArray.sort((a,b)=>a-b);
for(var i=0;i<tempArray.length;i++){
nums1[i]=tempArray[i]
}
};
2. 直接操作原數組
直接向原數組中多餘位指派，進而重新排序。
時間複雜度:O(n)=n²
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var me
var merge = function(nums1, m, nums2, n) {
for(var i=0;i<n;i++){
nums1[m+i]=nums2[i];
}
nums1.sort((a,b)=>a-b);
};
盛水最多的容器_中等
給定 n 個非負整數 a1，a2，…，an，每個數代表坐标中的一個點 (i, ai) 。在坐标内畫 n 條垂直線，垂直線 i的兩個端點分别為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。
說明：你不能傾斜容器，且 n 的值至少為2。
關于數組那些事前言 圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。
示例:輸入: [1,8,6,2,5,4,8,3,7] 輸出: 49
本題可暴力求解，兩次周遊數組；同樣也可以使用雙指針隻周遊一次，得到最大值。
-
暴力求解
通過兩次周遊數組中元素，得到每次所盛水的數值，進而比較出其中最大值。
時間複雜度:O(n)=n²
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
function calAre(a,b){
var temp = Math.abs(a-b);
return Math.min(temp*height[a],temp*height[b]);
}
var len = height.length;
var ins = calAre(0,1);
for(var i=0;i<len;i++){
for(var j=i+1;j<len;j++){
if(calAre(i,j) > ins){
ins = calAre(i,j);
}
}
}
return ins;
};
2. 雙指針求解
可簡化為單次周遊，左側指針從左向右周遊，右側指針從右向左周遊。進而得到最大值。
時間複雜度:O(n)=n²
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
var left = 0;
var right = height.length-1;
var ins = 0;
var maxArea = calAre(left,right);
while(left < right){
if(height[left] < height[right]){
ins = calAre(left,right);
left++;
}else{
ins = calAre(left,right);
right--
}
maxArea = Math.max(maxArea,ins);
}
return maxArea;
function calAre(i,j){
var temp = j-i;
return Math.min(temp*height[i],temp*height[j]);
}
};
會議室_中等
給定一個會議時間安排的數組，每個會議時間都會包括開始和結束的時間 [[s1,e1],[s2,e2],…] (si < ei)，為避免會議沖突，同時要考慮充分利用會議室資源，請你計算至少需要多少間會議室，才能滿足這些會議安排。
示例 1:輸入: [[0, 30],[5, 10],[15, 20]] 輸出: 2
示例 2: 輸入: [[7,10],[2,4]] 輸出: 1
1. 雙重周遊
現将數組排序，再排序後對數組兩次周遊，第二次周遊中首元素周遊至目前元素，若兩個比較元素可共享會議室，即
splice
前一進制素。同時将目前數組的第一位元素置為0。
時間複雜度:O(n)=n²
/**
* @param {number[][]} intervals
* @return {number}
*/
var minMeetingRooms = function(intervals) {
if (!intervals.length) return 0
if (intervals.length==1) return 1;
intervals = intervals.sort((a,b)=>a[0]-b[0]);
for(var i=1;i<intervals.length;i++){
const tempNow = intervals[i];
for(j=0;j<i;j++){
const tempLast = intervals[j]
if(tempNow[0]>=tempLast[1]){
intervals.splice(j,1)
tempNow[0]=0
i--;
}
}
}
return intervals.length
};
接雨水_困難
給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之後能接多少雨水。
關于數組那些事前言 上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6
個機關的雨水（藍色部分表示雨水）。 示例: 輸入: [0,1,0,2,1,0,1,3,2,1,2,1] 輸出: 6
本題主要在于分析所求位置雨水量與左右最大高度的關系。所求位置雨水量是左側高度最大值和右側高度最大值中較小者與本身高度的內插補點。為此兩次循環或是雙指針均可求解。
-
暴力求解
根據分析，我們能夠看出，每個數組元素的接水量等于其左側高度最大值與右側高度最大值中的最小值與該數組元素高度的內插補點。
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
var ins = 0;
for(var i=0;i<height.length;i++){
var lMax = 0;//左側高度最大值
var rMax = 0;//右側高度最大值
for(var j=i;j>=0;j--){
lMax = Math.max(lMax,height[j]);
}
for(var k=i;k<height.length;k++){
rMax = Math.max(rMax,height[k])
}
ins += Math.min(lMax,rMax) - height[i];
}
return ins;
};
2. 雙指針
使用雙指針将兩次周遊數組轉化為一次周遊。
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
var left=0;
var right=height.length-1;
var lMax = 0;
var rMax = 0;
var ins = 0;
while(left < right){
lMax = Math.max(lMax,height[left]);
rMax = Math.max(rMax,height[right]);
if(lMax < height[right]){
ins += lMax - height[left];
left++;
}else{
ins += rMax - height[right];
right--;
}
}
return ins;
};
三數之和
- 雙指針，先排除特殊情況
給定一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0
？找出所有滿足條件且不重複的三元組。 注意：答案中不可以包含重複的三元組。 示例： 給定數組 nums = [-1, 0, 1, 2,
-1, -4]， 滿足要求的三元組集合為： [ [-1, 0, 1], [-1, -1, 2] ]
/**
* @param {number[]} nums
* @return {number[][]}
*/
// 3.07
var threeSum = function (nums) {
if (nums === null || nums.length < 3) return []
let res = []
const len = nums.length - 1
nums.sort((a, b) => a - b)
for (let i = 0; i < len + 1; i++) {
if (nums[0] > 0 || nums[len] < 0) break
if (i > 0 && nums[i] === nums[i - 1]) continue
let left = i + 1, right = len
while (left < right) {
let sum = nums[left] + nums[i] + nums[right]
if (sum === 0) {
res.push([nums[left], nums[i], nums[right]])
while (left < right && nums[left] === nums[left+1]) left++
while (left < right && nums[right] === nums[right-1]) right--
left++
right--
}
else if (sum < 0) left++
else if (sum > 0) right--
}
}
return res
}