10
You are given an array of non-negative integers numbers. You are allowed to choose any number from this array and swap any two digits in it. If after the swap operation the number contains leading zeros, they can be omitted and not considered (eg: 010 will be considered just 10).
Your task is to check whether it is possible to apply the swap operation at most once, so that the elements of the resulting array are strictly increasing.
Example
For numbers = [1, 5, 10, 20], the output should be makeIncreasing(numbers) = true.
The initial array is already strictly increasing, so no actions are required.
For numbers = [1, 3, 900, 10], the output should be makeIncreasing(numbers) = true.
By choosing numbers[2] = 900 and swapping its first and third digits, the resulting number 009 is considered to be just 9. So the updated array will look like [1, 3, 9, 10], which is strictly increasing.
For numbers = [13, 31, 30], the output should be makeIncreasing(numbers) = false.
The initial array elements are not increasing.
By swapping the digits of numbers[0] = 13, the array becomes [31, 31, 30] which is not strictly increasing;
By swapping the digits of numbers[1] = 31, the array becomes [13, 13, 30] which is not strictly increasing;
By swapping the digits of numbers[2] = 30, the array becomes [13, 31, 3] which is not strictly increasing;
So, it's not possible to obtain a strictly increasing array, and the answer is false.
Input/Output
[execution time limit] 4 seconds (php)
[input] array.integer numbers
An array of non-negative integers.
Guaranteed constraints:
1 ≤ numbers.length ≤ 103,
0 ≤ numbers[i] ≤ 103.
[output] boolean
Return true if it is possible to obtain a strictly increasing array by applying the digit-swap operation at most once, and false otherwise.
function makeIncreasing($numbers) {
$hasChanged = false;
for($i=1; $i< count($numbers); $i++){
if($numbers[$i] > $numbers[$i-1]){
continue;
}
if($numbers[$i] < 10 && $numbers[$i-1]< 10){
return false;
}
$before = $i >= 2 ? $numbers[$i-2] : 0;
if(swapNumberSuccess($before, $numbers[$i-1], $numbers[$i]) && (!$hasChanged)){
$hasChanged = true;
continue;
}else{
return false;
}
}
return true;
}
function swapNumberSuccess($number0, $number1, $number2){
echo $number1,',', $number2, PHP_EOL;
if($number1 == 1000){
$min_1 = 1;
}elseif($number1/100 > 1){
$d1=floor($number1/100);
$d2=(floor($number1/10)%10);
$d3=$number1%10;
$d_min = min($d1, $d2, $d3);
$d_max = max($d1, $d2, $d3);
$d_mid = mid($d1, $d2, $d3, $d_min, $d_max);
$min_1 = 100 * $d_min + 10 * $d_mid + $d_max;
echo $d_min,',', $d_mid,',',$d_max, PHP_EOL;
}elseif($number1/10 > 1){
$d1= floor($number1/10);
$d2= $number1%10;
$min_1 = min($d1, $d2)*10 + max($d1, $d2);
}else{
$min_1 = $number1;
}
echo $min_1, PHP_EOL;
if($min_1 < $number2 && $min_1 > $number0){
return true;
}
if($number2 == 1000){
$max2 = 1000;
}elseif($number2/100 > 1){
$d1=floor($number2/100);
$d2=(floor($number2/10)%10);
$d3=$number2%10;
$d_min = min($d1, $d2, $d3);
$d_max = max($d1, $d2, $d3);
$d_mid = mid($d1, $d2, $d3, $d_min, $d_max);
$max_2 = 100 * $d_max + 10 * $d_mid + $d_min;
}elseif($number2/10 > 1){
$d1= floor($number2/10);
$d2= $number2%10;
$max_2 = max($d1, $d2)*10 + min($d1, $d2);
}else{
$max_2 = $number2;
}
echo $max_2, PHP_EOL;
if($max_2 > $number1){
return true;
}
return false;
}
function mid($n1, $n2, $n3, $d_min, $d_max){
if($n1 < $d_max && $n1 > $d_min){
return $n1;
}
if($n2 < $d_max && $n2 > $d_min){
return $n2;
}
return $n3;
}
11
You are given a matrix of integers field of size n × m representing a game field, and also a matrix of integers figure of size 3 × 3 representing a figure. Both matrices contain only 0s and 1s, where 1 means that the cell is occupied, and 0 means that the cell is free.
You choose a position at the top of the game field where you put the figure and then drop it down. The figure falls down until it either reaches the ground (bottom of the field) or lands on an occupied cell, which blocks it from falling further. After the figure has stopped falling, some of the rows in the field may become fully occupied.
demonstration
Your task is to find the dropping position such that at least one full row is formed. As a dropping position you should consider the column index of the cell in game field which matches the top left corner of the figure 3 × 3 matrix. If there are multiple dropping positions satisfying the condition, feel free to return any of them. If there are no such dropping positions, return -1.
Note: When falling, the 3 × 3 matrix of the figure must be entirely inside the game field, even if the figure matrix is not totally occupied.
Example
For
field = [[0, 0, 0],
[0, 0, 0],
[0, 0, 0],
[1, 0, 0],
[1, 1, 0]]
and
figure = [[0, 0, 1],
[0, 1, 1],
[0, 0, 1]]
the output should be findFullLine(field, figure) = 0.
The figure can be dropped only from position 0. When the figure stops falling, two fully occupied rows are formed, so dropping position 0 satisfies the condition.
example 1
For
field = [[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 1, 0, 1, 0],
[1, 0, 1, 0, 1]]
and
figure = [[1, 1, 1],
[1, 0, 1],
[1, 0, 1]]
the output should be findFullLine(field, figure) = 2.
The figure can be dropped from three positions - 0, 1, and 2. As you can see below, a fully occupied row will be formed only when dropping from position 2:
example 2
For
field = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[1, 0, 0, 1],
[1, 1, 0, 1]]
and
figure = [[1, 1, 0],
[1, 0, 0],
[1, 0, 0]]
the output should be findFullLine(field, figure) = -1.
The figure can be dropped from two positions - 0 and 1, and in both cases, a fully occupied line won't be obtained:
example 3
Note that the figure could technically form a full row if it was dropped one position further to the right, but in that case the figure matrix wouldn't be fully contained with the field.
Input/Output
[execution time limit] 4 seconds (php)
[input] array.array.integer field
A matrix of integers representing the game field. It's guaranteed that at the beginning there are no fully occupied rows on the game field and that the top three rows are fully free.
Guaranteed constraints:
4 ≤ field.length ≤ 100,
3 ≤ field[i].length ≤ 100,
0 ≤ field[i][j] ≤ 1.
[input] array.array.integer figure
A matrix of integers representing the figure. It's guaranteed that the figure's occupied cells are pairwise connected and there is at least one occupied cell at the bottom row of the figure.
Guaranteed constraints:
figure.length = 3,
figure[i].length = 3,
0 ≤ figure[i][j] ≤ 1.
[output] integer
The dropping position such that a full row is formed. If there are multiple possible positions, return any of them. If there is no such position, return -1.
12
You are given three arrays of integers a, b, and c. Your task is to find the longest contiguous subarray of a containing only elements that appear in b but do not appear in c.
Return this longest subarray. If there is more than one longest subarray satisfying these conditions, return any of these possible subarrays.
Example
For a = [2, 1, 7, 1, 1, 5, 3, 5, 2, 1, 1, 1], b = [1, 3, 5], and c = [2, 3], the output can be longestInversionalSubarray(a, b, c) = [1, 1, 5].
There is no contiguous subarray of length 4 satisfying all the requirements:
a[0..3] = [2, 1, 7, 1] contains the number a[2] = 7, which doesn't appear in b;
a[1..4] = [1, 7, 1, 1] contains the number a[2] = 7, which doesn't appear in b;
a[2..5] = [7, 1, 1, 5] contains the number a[2] = 7, which doesn't appear in b;
a[3..6] = [1, 1, 5, 3] contains the number a[6] = 3, which does appear in c (which is prohibited);
a[4..7] = [1, 5, 3, 5] contains the number a[6] = 3, which does appear in c;
a[5..8] = [5, 3, 5, 2] contains the number a[6] = 3, which does appear in c;
a[6..9] = [3, 5, 2, 1] contains the number a[6] = 3, which does appear in c;
a[7..10] = [5, 2, 1, 1] contains the number a[8] = 2, which doesn't appear in b;
a[8..11] = [2, 1, 1, 1] contains the number a[8] = 2, which doesn't appear in b.
There are two possible contiguous subarrays of length 3 satisfying all the requirements:
a[3..5] = [1, 1, 5]: both numbers 1 and 5 appear in b, and both of these numbers don't appear in c.
a[9..11] = [1, 1, 1]: the number 1 appears in b, and doesn't appear in c.
example
As you can see, the longest consecutive subarrays of a that fulfill the conditions are a[3..5] = [1, 1, 5] and a[9..11] = [1, 1, 1]. Both of these answers are acceptable.
For a = [1, 2, 3], b = [], and c = [], the output should be longestInversionalSubarray(a, b, c) = [].
Since b is empty, there are no elements that appear in b and not c. So the answer is [].
Input/Output
[execution time limit] 4 seconds (php)
[input] array.integer a
The first array of integers.
Guaranteed constraints:
0 ≤ a.length ≤ 105,
-109 ≤ a[i] ≤ 109.
[input] array.integer b
The second array of integers.
Guaranteed constraints:
0 ≤ b.length ≤ 105,
-109 ≤ b[i] ≤ 109.
[input] array.integer c
The third array of integers.
Guaranteed constraints:
0 ≤ c.length ≤ 105,
-109 ≤ c[i] ≤ 109.
[output] array.integer
Any of the longest contiguous subarrays of a which consists only of elements from b that don't appear in c.
