Count the triples
You are given an array of integers, arr, and a, B, and C. Please count the number of good triples.
A triple (arr[I], arr[j], arr[k]) is considered a good triple if it satisfies all of the following conditions.
0 <= i < j < k < arr.length
|arr[i] – arr[j]| <= a
|arr[j] – arr[k]| <= b
|arr[i] – arr[k]| <= c
The absolute value of x | | x said.
Returns the number of good triples
Example:
Input: arr = [3,0,1,1,9,7], A = 7, b = 2, c = 3
Output: 4
Explanation: a total of four good triples: [(3, 1), (3, 1), (3,1,1), (0,1,1)].
The subscripts of three numbers must not be the same.
Time O(n^3), space 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;
};
Copy the code
Find the winner of the array game
You are given an integer array of different integers arr and an integer k.
Each turn is played between the first two elements of the array (arR [0] and ARR [1]). Compare the size of arr[0] with arr[1], the larger integer wins the round and remains at position 0, and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds, and the integer is the winner of the match.
Returns the integer that won the race.
Title data guarantees a winner in the game.
Example:
Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds in a row.
In the process of iterating through the array, compare the size of the first two numbers and record the number of winning turns for the larger number. When the number of winning turns equals k, return the larger number.
One thing to note is that when k is greater than the length of the array, the number of rounds that can be won can only be the maximum of the current array.
In this way, the time complexity can be optimized to 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];
};
Copy the codeIn the above solution, splice and push methods are used to exchange array elements so as to update the first two digits.
But you don’t really need to update the first two digits here, because you can get the result in one walk, so just record the subscripts of the current two numbers.
By using double Pointers to record the subscripts of the current two numbers, the time complexity caused by splice can be optimized, so that the overall time complexity can be optimized to 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;
};
Copy the code
The minimum number of switches for arranging a binary grid
You are given an N x N binary grid, and in each operation, you can select two adjacent rows of the grid to swap.
A proper grid requires all the cells above the main diagonal to be zeros.
Return the minimum number of operations required to make the grid fit, or -1 if not.
The main diagonal is the grid from (1, 1) to (n, n).
Example:
Input: grid = [[0,0,1],[1,0,0]]
Output: 3
What is the basis for the exchange of two adjacent rows?
And finally, we want to complete the main diagonal with zeros all over the top right, so the purpose of the swap is to move the row with the most consecutive zeros to the top.
First, we need to record the number of consecutive zeros to the right of each row, and then swap according to the relationship between the number of consecutive zeros and the number of rows.
Time order n^3.
const minSwaps = function(grid) {
const row = grid[0].length;
// Count the number of consecutive zeros to the right of each row
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; // You cannot fill the upper right corner with zeros
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;
};
Copy the code
Maximum score
You have two ordered arrays with different elements, nums1 and nums2.
A valid path is defined as follows:
Select the array nums1 or nums2 to begin traversal (starting at subscript 0).
Traverses the current array from left to right.
If you encounter a value that exists in both nums1 and nums2, you can switch paths to the corresponding number in the other array and continue traversing (although duplicate numbers are counted only once in legal paths).
A score is defined as the sum of different numbers in a legal path.
Return the maximum score of all possible legal paths.
Since the answer may be large, you can return it mod 10^9 + 7.
Example:
Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths include:
,4,5,8,9,4,5,8,10 [2], [2], [2,4,6,8,9], [2,4,6,8,10], (since nums1 traversal)
,5,8,10,6,8,9 [4], [4], [4,5,8,9], [4,6,8,10] (since nums2 traversal)
The maximum score is the green path shown above [2,4,6,8,10].
Don’t make this problem too complicated, keep the local path maximum score, then the final legal path maximum score.
Use the double pointer to traverse two arrays and record the scores of two branches at the same time. When the same node is encountered, take the largest score in the branch and start scoring again. The sum of the maximum score of each branch is the result.
Time complexity 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);
};
Copy the code
Highlights from the past
-
LeetCode Tour for front End Engineers – Week 185
-
Front End Engineer’s LeetCode Journey — Week 184
-
LeetCode Tour for front End Engineers – Week 183
-
LeetCode Tour for front End Engineers — Week 182
-
JavaScript AC solutions to problems on LeetCode
