Given an array of integers arr, replace each element with its rank.
The rank represents how large the element is. The rank has the following rules:
Example 1:
Input: arr = [40,10,20,30] Output: [4,1,2,3] Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.
Example 2:
Input: arr = [100,100,100] Output: [1,1,1] Explanation: Same elements share the same rank.
Example 3:
Input: arr = [37,12,28,9,100,56,80,5,12] Output: [5,3,4,2,8,6,7,1,3]
Constraints:
0 <= arr.length <= 105-109 <= arr[i] <= 109- Every time you are in a cell you will collect all the gold in that cell. - From your position, you can walk one step to the left, right, up, or down. - You can't visit the same cell more than once. - Never visit a cell with 0 gold. - You can start and stop collecting gold from any position in the grid that has some gold.
program main
implicit none
integer, parameter :: n = 4
integer :: arr(n) = [40, 10, 20, 30]
integer :: i, j, k
do i = 1, n
write (*, '(I0)') arr(i)
end do
end program main40 10 20 30
! This program solves the problem of replacing each element in an array with its rank.
! The rank represents how large the element is. The rank has the following rules:
!
! * Rank is an integer starting from 1.
! * The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
! * Rank should be as small as possible.
program rank_elements
implicit none
! Declare variables
integer, allocatable :: arr(:)
integer :: i, j, n
! Read the number of elements in the array
read(*,*) n
! Allocate memory for the array
allocate(arr(n))
! Read the elements of the array
do i = 1, n
read(*,*) arr(i)
end do
! Sort the array in descending order
call sort(arr)
! Initialize the rank of each element
do i = 1, n
arr(i) = i
end do
! Update the rank of each element based on its position in the sorted array
do i = 1, n
do j = i + 1, n
if (arr(i) == arr(j)) then
arr(j) = arr(i)
end if
end do
end do
! Print the ranks of the elements
do i = 1, n
write(*,*) arr(i)
end do
end program rank_elements
! This subroutine sorts an array in descending order using the quicksort algorithm.
subroutine sort(arr)
implicit none
! Declare variables
integer, intent(inout) :: arr(:)
integer :: pivot, left, right, temp
! Base case: If the length of the array is 1 or less, it is already sorted
if (size(arr) <= 1) then
return
end if
! Choose a pivot element
pivot = arr(1)
! Partition the array around the pivot
left = 1
right = size(arr)
do while (left < right)
do while (arr(right) >= pivot)
right = right - 1
end do
do while (arr(left) < pivot)
left = left + 1
end do
if (left < right) then
temp = arr(left)
arr(left) = arr(right)
arr(right) = temp
end if
end do
! Recursively sort the subarrays
call sort(arr(1:left-1))
call sort(arr(right+1:))
end subroutine sort
temp.f95:87:24:
87 | call sort(arr(1:left-1))
| 1
Error: SUBROUTINE ‘sort’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:88:24:
88 | call sort(arr(right+1:))
| 1
Error: SUBROUTINE ‘sort’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:28:9:
28 | call sort(arr)
| 1
Error: Explicit interface required for ‘sort’ at (1): assumed-shape argument
def getMaximumGold(grid):
m, n, max_gold = len(grid), len(grid[0]), 0
def getMaximumGoldHelper(x, y):
if not (0 <= x < m) or not (0 <= y < n) or grid[x][y] == 0:
return 0
original_gold = grid[x][y]
grid[x][y] = 0
max_gold = 0
max_gold = max(max_gold, getMaximumGoldHelper(x + 1, y))
max_gold = max(max_gold, getMaximumGoldHelper(x - 1, y))
max_gold = max(max_gold, getMaximumGoldHelper(x, y + 1))
max_gold = max(max_gold, getMaximumGoldHelper(x, y - 1))
grid[x][y] = original_gold
return max_gold + original_gold
for i in range(m):
for j in range(n):
if grid[i][j] != 0:
max_gold = max(max_gold, getMaximumGoldHelper(i, j))
return max_gold
We use a depth-first search (DFS) algorithm to calculate the maximum gold that can be collected in one DFS run, which we do starting from each cell with gold. This algorithm keeps track of the visited cells by changing the gold amount to 0 in the original grid temporarily as part of its recursive computations. As we go through the grid, we store the maximum gold found so far to be returned at the end. Note that the algorithm itself is relatively simple, but the actual implementation varies slightly between languages.
#include <vector>
#include <algorithm>
using namespace std;
int getMaximumGoldHelper(vector<vector<int>> &grid, int x, int y, int m, int n) {
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) return 0;
int originalGold = grid[x][y];
grid[x][y] = 0;
int maxGold = 0;
maxGold = max(maxGold, getMaximumGoldHelper(grid, x + 1, y, m, n));
maxGold = max(maxGold, getMaximumGoldHelper(grid, x - 1, y, m, n));
maxGold = max(maxGold, getMaximumGoldHelper(grid, x, y + 1, m, n));
maxGold = max(maxGold, getMaximumGoldHelper(grid, x, y - 1, m, n));
grid[x][y] = originalGold;
return maxGold + originalGold;
}
int getMaximumGold(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), maxGold = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) {
maxGold = max(maxGold, getMaximumGoldHelper(grid, i, j, m, n));
}
}
}
return maxGold;
}
We use a depth-first search (DFS) algorithm to calculate the maximum gold that can be collected in one DFS run, which we do starting from each cell with gold. This algorithm keeps track of the visited cells by changing the gold amount to 0 in the original grid temporarily as part of its recursive computations. As we go through the grid, we store the maximum gold found so far to be returned at the end. Note that the algorithm itself is relatively simple, but the actual implementation varies slightly between languages.