01
統計好三元組
題目描述【Easy】
給你一個整數數組 arr ，以及 a、b 、c 三個整數。請你統計其中好三元組的數量。
如果三元組 (arr[i], arr[j], arr[k]) 滿足下列全部條件，則認為它是一個 好三元組 。
0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
其中 |x| 表示 x 的絕對值。
傳回 好三元組的數量
輸入：arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
輸出：4
解釋：一共有 4 個好三元組：[(3,0,1), (3,0,1), (3,1,1), (0,1,1)] 。
本道題主要考察數組的周遊，需要特别注意三個數字的下标是不能相同的。
時間複雜度 O(n^3)，空間複雜度 O(1)。
const countGoodTriplets = function(arr, a, b, c) {
const max = arr.length;
let ans = 0;
for (let i = 0; i < max - 2; i++) {
for (let j = i + 1; j < max - 1; j++) {
for (let k = j + 1; k < max; k++) {
if (Math.abs(arr[i] - arr[j]) <= a && Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] -arr[k]) <= c) {
ans++;
}
}
}
}
return ans;
};
02
找出數組遊戲的赢家
題目描述【Medium】
給你一個由 不同 整數組成的整數數組 arr 和一個整數 k 。
每回合遊戲都在數組的前兩個元素（即 arr[0] 和 arr[1] ）之間進行。比較 arr[0] 與 arr[1] 的大小，較大的整數将會取得這一回合的勝利并保留在位置 0 ，較小的整數移至數組的末尾。當一個整數赢得 k 個連續回合時，遊戲結束，該整數就是比賽的 赢家 。
傳回赢得比賽的整數。
題目資料 保證 遊戲存在赢家。
示例：
輸入：arr = [3,2,1], k = 10
輸出：3
解釋：3 将會在前 10 個回合中連續獲勝。
題目非常容易了解，在數組疊代的過程中，不斷比較前兩個數的大小，并且記錄較大數的獲勝回合數，當獲勝回合數等于 k 時，傳回較大的數。
需要注意的一點就是：當 k 大于數組長度時，能夠赢得這麼多回合的數隻能是目前數組的最大值。
這樣可以将時間複雜度優化為 O(min(arr.length, k) * arr.length)。
const getWinner = function(arr, k) {
const len = arr.length;
let max = Number.MIN_SAFE_INTEGER;
let count = 0;
let temp = 0;
while (count < k) {
const first = arr[0];
const next = arr[1] || Number.MIN_SAFE_INTEGER;
if (first > next) {
count++;
arr.splice(1, 1);
arr.push(next);
} else {
count = 1;
arr.splice(0, 1);
arr.push(first);
}
max = Math.max(first, next);
temp++;
if (temp >= len) {
return max;
}
}
return arr[0];
};
上述解法中利用 splice 和 push 方法進行數組元素的交換，進而達到更新前兩位數的目的。
但是這裡其實沒有必要更新前兩位數，因為一次周遊就能知道結果，是以隻要記錄目前兩個數的下标即可。
利用雙指針記錄目前兩個數的下标，即可優化掉 splice 帶來的時間複雜度，進而整體時間複雜度優化為 O(n)。
const getWinner = function(arr, k) {
let preIndex = 0;
let nextIndex = 1;
let count = 0;
let maxNum = Number.MIN_SAFE_INTEGER;
while (nextIndex < arr.length) {
if (arr[nextIndex] < arr[preIndex]) {
count++;
} else {
count = 1;
preIndex = nextIndex;
}
if (count === k) {
return arr[preIndex];
}
maxNum = Math.max(maxNum, arr[nextIndex], arr[preIndex]);
nextIndex++;
}
return maxNum;
};
03
排布二進制網格的最少交換次數
題目描述【Medium】
給你一個 n x n 的二進制網格 grid，每一次操作中，你可以選擇網格的 相鄰兩行 進行交換。
一個符合要求的網格需要滿足主對角線以上的格子全部都是 0 。
請你傳回使網格滿足要求的最少操作次數，如果無法使網格符合要求，請你傳回 -1 。
主對角線指的是從 (1, 1) 到 (n, n) 的這些格子。
示例：
輸入：grid = [[0,0,1],[1,1,0],[1,0,0]]
輸出: 3
本道題的難點在于了解題意，明白依據什麼進行相鄰兩行的交換？
最終是要完成主對角線右上方全是零，那麼交換的目的就是将右邊連續 0 最多的行移動到最高層。
首先需要記錄每一行右邊連續 0 的個數，然後根據連續 0 個數與行數的關系進行交換操作。
時間複雜度 O(n^3)。
const minSwaps = function(grid) {
const row = grid[0].length;
// 統計每一行右邊連續 0 的個數
const record = Array(row).fill(0);
for (let i = 0; i < row; i++) {
for (let j = row - 1; j >= 0; j--) {
if (grid[i][j] == 0) {
record[i]++;
} else {
break;
}
}
}
let step = 0;
for (let i = 0; i < row - 1; i++) {
const currentMinZero = row - 1 - i;
if (record[i] >= currentMinZero) {
continue;
}
let isFlag = true; // 不可以将右上角全部填充成 0
for (let j = i + 1; j < row; j++) {
if (record[j] >= currentMinZero) {
step += (j - i);
const temp = record[j];
record.splice(j, 1);
record.splice(i, 0, temp);
isFlag = false;
break;
}
}
if (isFlag) {
return -1;
}
}
return step;
};
04
最大得分
題目描述【Hard】
你有兩個 有序 且數組内元素互不相同的數組 nums1 和 nums2 。
一條 合法路徑 定義如下：
選擇數組 nums1 或者 nums2 開始周遊（從下标 0 處開始）。
從左到右周遊目前數組。
如果你遇到了 nums1 和 nums2 中都存在的值，那麼你可以切換路徑到另一個數組對應數字處繼續周遊（但在合法路徑中重複數字隻會被統計一次）。
得分定義為合法路徑中不同數字的和。
請你傳回所有可能合法路徑中的最大得分。
由于答案可能很大，請你将它對 10^9 + 7 取餘後傳回。
示例：
輸入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
輸出：30
解釋：合法路徑包括：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（從 nums1 開始周遊）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10] （從 nums2 開始周遊）
最大得分為上圖中的綠色路徑 [2,4,6,8,10] 。
不要把本道題想得太複雜，保持局部路徑得分最大，那麼最終的合法路徑的得分就最大。
利用雙指針周遊兩個數組，同時記錄兩個分支的得分，當遇到相同節點時，取分支中最大的得分，并且重新開始計分，最終各分支的最大得分和即為結果。
時間複雜度 O(n)。
const maxSum = function(nums1, nums2) {
let sum1 = 0;
let sum2 = 0;
let maxSum = 0;
let startNums1Index = 0;
let startNums2Index = 0;
while (startNums1Index < nums1.length && startNums2Index < nums2.length) {
if (nums1[startNums1Index] === nums2[startNums2Index]) {
maxSum += (Math.max(sum1, sum2) + nums1[startNums1Index]);
sum1 = 0;
sum2 = 0;
startNums1Index++;
startNums2Index++;
} else if (nums1[startNums1Index] < nums2[startNums2Index]) {
sum1 += nums1[startNums1Index];
startNums1Index++;
} else {
sum2 += nums2[startNums2Index];
startNums2Index++;
}
}
while(startNums1Index < nums1.length) {
sum1 += nums1[startNums1Index];
startNums1Index++;
}
while(startNums2Index < nums2.length) {
sum2 += nums2[startNums2Index];
startNums2Index++;
}
maxSum += Math.max(sum1, sum2);
return maxSum % (10 ** 9 + 7);
};
05
往期精彩回顧
- 前端工程師的 LeetCode 之旅 -- 周賽 185
- 前端工程師的 LeetCode 之旅 -- 周賽 184
- 前端工程師的 LeetCode 之旅 -- 周賽 183
- 前端工程師的 LeetCode 之旅 -- 周賽 182
你點的每個贊，我都認真當成了喜歡