01 統計的に良い三項
説明簡単
整数の配列 arr と3つの整数 a, b, c が与えられます．良い三つ組の数を数えなさい。 次の条件をすべて満たすとき、三項対立はよい三項対立とみなされます。 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つ： [, , ].
時間の複雑さ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 配列ゲームの勝者を見つける
説明中
異なる整数からなる整数の配列 arr と整数 k が与えられます。 ゲームの各ラウンドは、配列の最初の2つの要素の間で行われます。arr[0]とarr[1]の大きさを比較し、大きい方の整数がラウンドに勝ち、0の位置に留まり、小さい方の整数は配列の末尾に移動します。整数が k 回連続で勝ったとき、ゲームは終了し、その整数がゲームの勝者となります。 ゲームに勝った整数を返します。 トピックデータは、ゲームの勝者がいることを保証します。 例: 入力: arr = [3,2,1], k = 10 出力: 3 解説: 最初の 10 ラウンド連続で 3 が勝ちます。
配列を繰り返しながら、最初の2つの数字の大きさを比較し、大きい方の数字が勝ったラウンド数を記録し続け、勝ったラウンド数が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 メソッドを使用して配列の要素を入れ替え、最初の 2 桁を更新しています。
しかし、1 回の走査で結果を見つけることができるため、ここでは最初の 2 桁を更新する必要はなく、現在の 2 桁の添え字を記録するだけで十分です。
現在の2桁の添え字を記録するためにダブルポインタを使用することで、 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 2進グリッドを配置するための最小スワップ数
説明Medium
n×nの2進格子が与えられ、各操作で隣り合う2行を選んで入れ替えることができます。 満足なグリッドは、主対角線より上のすべてのセルが0であることを必要とします。 グリッドを適合させるための最小の操作回数、またはグリッドを適合させることができない場合は -1 を返すように求められます。 主対角線は、.から.までのグリッドを指します。 例: 入力: grid = [[0,0,1],[1,1,0],[1,0,0]] 出力: 3
この問題の難しさは、問題の意味を理解し、隣接する2つの行がどのような根拠で交換されるのか？
最終的なゴールは、右上にすべてのゼロがある主対角線を完成させることなので、入れ替えの目的は、右側の連続するゼロが最も多い行を最上位に移動させることです。
まず、各行の右側に連続するゼロの数を記録し、連続するゼロの数と行数の関係に従ってスワップ操作を行う必要があります。
時間の複雑さは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 最大スコア
説明難しい
異なる要素を持つ2つの順序付き配列nums1とnums2があります。 nums1 か nums2 のどちらかを選択し、探索を開始します。 現在の配列を左から右に走査します。 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]、 [4,6,8,9]、[4,5,8,10]、[4,58,9]、[4,6,8,10] スコアが最大になるのは、上図の緑色のパス[2,4,6,8,10]です。
この問題は考えすぎず、ローカルパスのスコアを最大にしておけば、最終的に合法的なパスのスコアが最大になります。
ダブルポインタを使って2つの配列を走査し、2つの枝のスコアを同時に記録し、同じノードに出会ったら、枝の中で最大のスコアを取り、スコアリングを再開します。
計算量は 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 前のレビュー
