In a string s of lowercase letters, these letters form consecutive groups of the same character.
For example, a string like s = "abbxxxxzyy " has the groups "a ", "bb ", "xxxx ", "z ", and "yy ".
A group is identified by an interval [start, end], where start and end denote the start and end indices (inclusive) of the group. In the above example, "xxxx " has the interval [3,6].
A group is considered large if it has 3 or more characters.
Return the intervals of every large group sorted in increasing order by start index.
Example 1:
Input: s = "abbxxxxzzy "
Output: [[3,6]]
Explanation: "xxxx " is the only large group with start index 3 and end index 6.
Example 2:
Input: s = "abc " Output: [] Explanation: We have groups "a ", "b ", and "c ", none of which are large groups.
Example 3:
Input: s = "abcdddeeeeaabbbcd " Output: [[3,5],[6,9],[12,14]] Explanation: The large groups are "ddd ", "eeee ", and "bbb ".
Constraints:
1 <= s.length <= 1000s contains lowercase English letters only.program main
implicit none
integer :: i, j, n
character(len=1000) :: s
integer, allocatable :: starts(:), ends(:)
do i = 1, size(examples)
write (*, '(A)') 'Example ', i
s = examples(i)
call solve(s, starts, ends)
n = size(starts)
write (*, '(A, I0)') 'Number of large groups: ', n
do j = 1, n
write (*, '(A, I0, A, I0)') 'Large group ', j, ': ', starts(j), '-', ends(j)
end do
write (*, *)
end do
contains
subroutine solve(s, starts, ends)
implicit none
character(len=*), intent(in) :: s
integer, allocatable, intent(out) :: starts(:), ends(:)
integer :: i, j, k, n
logical :: found_large
! Initialize arrays
allocate(starts(0))
allocate(ends(0))
! Loop over characters in the string
do i = 1, len(s)
! Check if current character is part of a large group
found_large = .false.
do j = 1, size(starts)
if (s(i:i) == s(starts(j):starts(j))) then
found_large = .true.
exit
end if
end do
! If current character is part of a large group, update the end index
if (found_large) then
k = size(ends)
ends(k+1) = i
end if
! If current character is not part of any large group, create a new one
if (.not. found_large) then
n = size(starts) + 1
allocate(starts(n))
allocate(ends(n))
starts(n) = i
ends(n) = i
end if
end do
! Sort the large groups by start index
call sort(starts, ends)
end subroutine solve
function sort(starts, ends) result(sorted)
implicit none
integer, intent(in) :: starts(:), ends(:)
integer, allocatable :: sorted(:, :)
integer :: i, j, k, m
! Allocate temporary arrays
allocate(sorted(size(starts), 2))
! Copy the input arrays into the temporary arrays
do i = 1, size(starts)
sorted(i, 1) = starts(i)
sorted(i, 2) = ends(i)
end do
! Bubble sort the temporary arrays
do while (any(sorted(:, 1) /= starts))
do i = 1, size(starts)-1
if (sorted(i, 1) > sorted(i+1, 1)) then
m = sorted(i, 1)
sorted(i, 1) = sorted(i+1, 1)
sorted(i+1, 1) = m
m = sorted(i, 2)
sorted(i, 2) = sorted(i+1, 2)
sorted(i+1, 2) = m
end if
end do
end do
! Copy the sorted arrays back into the output arrays
do i = 1, size(starts)
starts(i) = sorted(i, 1)
ends(i) = sorted(i, 2)
end do
end function sort
character(len=1000), parameter :: examples(3) = ["abbxxxxzzy ", &
"abc ", &
"abcdddeeeeaabbbcd "]
end program maintemp.f95:100:67:
100 | character(len=1000), parameter :: examples(3) = ["abbxxxxzzy ", &
| 1
Error: Different CHARACTER lengths (11/4) in array constructor at (1)
temp.f95:95:12:
95 | starts(i) = sorted(i, 1)
| 1
Error: Dummy argument ‘starts’ with INTENT(IN) in variable definition context (assignment) at (1)
temp.f95:96:12:
96 | ends(i) = sorted(i, 2)
| 1
Error: Dummy argument ‘ends’ with INTENT(IN) in variable definition context (assignment) at (1)
temp.f95:64:4:
61 | call sort(starts, ends)
| 2
......
64 | function sort(starts, ends) result(sorted)
| 1
Error: ‘sort’ at (1) has a type, which is not consistent with the CALL at (2)
temp.f95:10:12:
10 | s = examples(i)
| 1
Error: Function ‘examples’ at (1) has no IMPLICIT type
temp.f95:8:27:
8 | do i = 1, size(examples)
| 1
Error: Symbol ‘examples’ at (1) has no IMPLICIT type
program large_groups
implicit none
character(len=1000) :: s
integer :: start, end
integer :: i, j
! read input
read (*, *) s
! initialize variables
start = 1
end = 1
! loop through the string
do i = 2, len(s)
! if the current character is the same as the previous character
if (s(i:i) == s(i-1:i-1)) then
! increment the end index of the current group
end = end + 1
! if the current character is not the same as the previous character
else
! if the current group is large
if (end - start + 1 >= 3) then
! add the interval of the current group to the output
write (*, *) "[", start, ",", end, "]"
end if
! reset the start and end indices of the current group
start = i
end = i
end if
end do
! if the last group is large
if (end - start + 1 >= 3) then
! add the interval of the last group to the output
write (*, *) "[", start, ",", end, "]"
end if
end program
At line 9 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x7be8ceca8960 in ??? #1 0x7be8ceca94d9 in ??? #2 0x7be8ceefd17b in ??? #3 0x7be8ceef6684 in ??? #4 0x7be8ceef72aa in ??? #5 0x56b05ab7f21c in MAIN__ #6 0x56b05ab7f4bf in main
from itertools import combinations
def largestTriangleArea(points):
return max(0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) for (x1, y1), (x2, y2), (x3, y3) in combinations(points, 3))
The algorithm computes the area of the triangle formed by any three different points in the input array. To do this, the algorithm performs the following steps:
The algorithm has a time complexity of O(n^3), where n is the number of points in the input array.
#include <vector>
#include <algorithm>
using namespace std;
double largestTriangleArea(vector<vector<int>>& points) {
double max_area = 0.0;
for (int i = 0; i < points.size(); ++i) {
for (int j = i + 1; j < points.size(); ++j) {
for (int k = j + 1; k < points.size(); ++k) {
max_area = max(max_area, 0.5 * abs(points[i][0] * (points[j][1] - points[k][1])
+ points[j][0] * (points[k][1] - points[i][1])
+ points[k][0] * (points[i][1] - points[j][1])));
}
}
}
return max_area;
}
The algorithm computes the area of the triangle formed by any three different points in the input array. To do this, the algorithm performs the following steps:
The algorithm has a time complexity of O(n^3), where n is the number of points in the input array.