Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcf205af

Browse files
authored
Added tasks 3451-3459
1 parenteb8b465 commitcf205af

File tree

27 files changed

+1228
-0
lines changed

27 files changed

+1228
-0
lines changed
Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
3451\. Find Invalid IP Addresses
2+
3+
Hard
4+
5+
Table:`logs`
6+
7+
+-------------+---------+
8+
| Column Name | Type |
9+
+-------------+---------+
10+
| log_id | int |
11+
| ip | varchar |
12+
| status_code | int |
13+
+-------------+---------+
14+
log_id is the unique key for this table.
15+
Each row contains server access log information including IP address and HTTP status code.
16+
17+
Write a solution to find**invalid IP addresses**. An IPv4 address is invalid if it meets any of these conditions:
18+
19+
* Contains numbers**greater than**`255` in any octet
20+
* Has**leading zeros** in any octet (like`01.02.03.04`)
21+
* Has**less or more** than`4` octets
22+
23+
Return_the result table__ordered by_`invalid_count`,`ip`_in**descending** order respectively_.
24+
25+
The result format is in the following example.
26+
27+
**Example:**
28+
29+
**Input:**
30+
31+
logs table:
32+
33+
+--------+---------------+-------------+
34+
| log_id | ip | status_code |
35+
+--------+---------------+-------------+
36+
| 1 | 192.168.1.1 | 200 |
37+
| 2 | 256.1.2.3 | 404 |
38+
| 3 | 192.168.001.1 | 200 |
39+
| 4 | 192.168.1.1 | 200 |
40+
| 5 | 192.168.1 | 500 |
41+
| 6 | 256.1.2.3 | 404 |
42+
| 7 | 192.168.001.1 | 200 |
43+
+--------+---------------+-------------+
44+
45+
**Output:**
46+
47+
+---------------+--------------+
48+
| ip | invalid_count|
49+
+---------------+--------------+
50+
| 256.1.2.3 | 2 |
51+
| 192.168.001.1 | 2 |
52+
| 192.168.1 | 1 |
53+
+---------------+--------------+
54+
55+
**Explanation:**
56+
57+
* 256.1.2.3 is invalid because 256 > 255
58+
* 192.168.001.1 is invalid because of leading zeros
59+
* 192.168.1 is invalid because it has only 3 octets
60+
61+
The output table is ordered by invalid\_count, ip in descending order respectively.
Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
# Write your MySQL query statement below
2+
# #Hard #Database #2025_02_18_Time_393_ms_(79.56%)_Space_0.0_MB_(100.00%)
3+
WITH cte_invalid_ipAS (
4+
SELECT log_id, ip
5+
FROM logs
6+
WHERE NOT regexp_like(ip,'^(?:[1-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])(?:[.](?:[1-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])){3}$')
7+
),
8+
cte_invalid_ip_countAS (
9+
SELECT ip,count(log_id)as invalid_count
10+
FROM cte_invalid_ip
11+
GROUP BY ip
12+
)
13+
SELECT ip, invalid_count
14+
FROM cte_invalid_ip_count
15+
ORDER BY invalid_countDESC, ipDESC;
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg3401_3500.s3452_sum_of_good_numbers;
2+
3+
// #Easy #Array #2025_02_18_Time_1_ms_(99.99%)_Space_44.75_MB_(7.31%)
4+
5+
publicclassSolution {
6+
publicintsumOfGoodNumbers(int[]nums,intk) {
7+
inttotalSum =0;
8+
intn =nums.length;
9+
for (inti =0;i <n;i++) {
10+
booleanisGood =i -k <0 ||nums[i] >nums[i -k];
11+
if (i +k <n &&nums[i] <=nums[i +k]) {
12+
isGood =false;
13+
}
14+
if (isGood) {
15+
totalSum +=nums[i];
16+
}
17+
}
18+
returntotalSum;
19+
}
20+
}
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
3452\. Sum of Good Numbers
2+
3+
Easy
4+
5+
Given an array of integers`nums` and an integer`k`, an element`nums[i]` is considered**good** if it is**strictly** greater than the elements at indices`i - k` and`i + k` (if those indices exist). If neither of these indices_exists_,`nums[i]` is still considered**good**.
6+
7+
Return the**sum** of all the**good** elements in the array.
8+
9+
**Example 1:**
10+
11+
**Input:** nums =[1,3,2,1,5,4], k = 2
12+
13+
**Output:** 12
14+
15+
**Explanation:**
16+
17+
The good numbers are`nums[1] = 3`,`nums[4] = 5`, and`nums[5] = 4` because they are strictly greater than the numbers at indices`i - k` and`i + k`.
18+
19+
**Example 2:**
20+
21+
**Input:** nums =[2,1], k = 1
22+
23+
**Output:** 2
24+
25+
**Explanation:**
26+
27+
The only good number is`nums[0] = 2` because it is strictly greater than`nums[1]`.
28+
29+
**Constraints:**
30+
31+
*`2 <= nums.length <= 100`
32+
*`1 <= nums[i] <= 1000`
33+
*`1 <= k <= floor(nums.length / 2)`
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
packageg3401_3500.s3453_separate_squares_i;
2+
3+
// #Medium #Array #Binary_Search #2025_02_18_Time_60_ms_(99.96%)_Space_88.58_MB_(26.92%)
4+
5+
publicclassSolution {
6+
publicdoubleseparateSquares(int[][]squares) {
7+
longhi =0L;
8+
longlo =1_000_000_000L;
9+
for (int[]q :squares) {
10+
lo =Math.min(lo,q[1]);
11+
hi =Math.max(hi,q[1] + (long)q[2]);
12+
}
13+
while (lo <=hi) {
14+
longmid = (lo +hi) /2;
15+
if (diff(mid,squares) <=0) {
16+
hi =mid -1;
17+
}else {
18+
lo =mid +1;
19+
}
20+
}
21+
doublediff1 =diff(hi,squares);
22+
doublediff2 =diff(lo,squares);
23+
returnhi +diff1 / (diff1 -diff2);
24+
}
25+
26+
privatedoublediff(longmid,int[][]squares) {
27+
double[]res =newdouble[2];
28+
for (int[]q :squares) {
29+
res[0] +=Math.min(q[2],Math.max(0,mid -q[1])) *q[2];
30+
res[1] +=Math.min(q[2],Math.max(0,q[1] +q[2] -mid)) *q[2];
31+
}
32+
returnres[1] -res[0];
33+
}
34+
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
3453\. Separate Squares I
2+
3+
Medium
4+
5+
You are given a 2D integer array`squares`. Each <code>squares[i] =[x<sub>i</sub>, y<sub>i</sub>, l<sub>i</sub>]</code> represents the coordinates of the bottom-left point and the side length of a square parallel to the x-axis.
6+
7+
Find the**minimum** y-coordinate value of a horizontal line such that the total area of the squares above the line_equals_ the total area of the squares below the line.
8+
9+
Answers within <code>10<sup>-5</sup></code> of the actual answer will be accepted.
10+
11+
**Note**: Squares**may** overlap. Overlapping areas should be counted**multiple times**.
12+
13+
**Example 1:**
14+
15+
**Input:** squares =[[0,0,1],[2,2,1]]
16+
17+
**Output:** 1.00000
18+
19+
**Explanation:**
20+
21+
![](https://assets.leetcode.com/uploads/2025/01/06/4062example1drawio.png)
22+
23+
Any horizontal line between`y = 1` and`y = 2` will have 1 square unit above it and 1 square unit below it. The lowest option is 1.
24+
25+
**Example 2:**
26+
27+
**Input:** squares =[[0,0,2],[1,1,1]]
28+
29+
**Output:** 1.16667
30+
31+
**Explanation:**
32+
33+
![](https://assets.leetcode.com/uploads/2025/01/15/4062example2drawio.png)
34+
35+
The areas are:
36+
37+
* Below the line:`7/6 * 2 (Red) + 1/6 (Blue) = 15/6 = 2.5`.
38+
* Above the line:`5/6 * 2 (Red) + 5/6 (Blue) = 15/6 = 2.5`.
39+
40+
Since the areas above and below the line are equal, the output is`7/6 = 1.16667`.
41+
42+
**Constraints:**
43+
44+
* <code>1 <= squares.length <= 5 * 10<sup>4</sup></code>
45+
* <code>squares[i] =[x<sub>i</sub>, y<sub>i</sub>, l<sub>i</sub>]</code>
46+
*`squares[i].length == 3`
47+
* <code>0 <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>9</sup></code>
48+
* <code>1 <= l<sub>i</sub> <= 10<sup>9</sup></code>
Lines changed: 155 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,155 @@
1+
packageg3401_3500.s3454_separate_squares_ii;
2+
3+
// #Hard #Array #Binary_Search #Segment_Tree #Line_Sweep
4+
// #2025_02_18_Time_156_ms_(80.18%)_Space_79.96_MB_(64.32%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.List;
9+
10+
@SuppressWarnings("java:S1210")
11+
publicclassSolution {
12+
privatestaticclassEventimplementsComparable<Event> {
13+
doubley;
14+
intx1;
15+
intx2;
16+
inttype;
17+
18+
Event(doubley,intx1,intx2,inttype) {
19+
this.y =y;
20+
this.x1 =x1;
21+
this.x2 =x2;
22+
this.type =type;
23+
}
24+
25+
publicintcompareTo(Eventother) {
26+
returnDouble.compare(this.y,other.y);
27+
}
28+
}
29+
30+
privatestaticclassSegment {
31+
doubley1;
32+
doubley2;
33+
doubleunionX;
34+
doublecumArea;
35+
36+
Segment(doubley1,doubley2,doubleunionX,doublecumArea) {
37+
this.y1 =y1;
38+
this.y2 =y2;
39+
this.unionX =unionX;
40+
this.cumArea =cumArea;
41+
}
42+
}
43+
44+
privatestaticclassSegmentTree {
45+
int[]count;
46+
double[]len;
47+
intn;
48+
int[]x;
49+
50+
SegmentTree(int[]x) {
51+
this.x =x;
52+
n =x.length -1;
53+
count =newint[4 *n];
54+
len =newdouble[4 *n];
55+
}
56+
57+
voidupdate(intidx,intl,intr,intql,intqr,intval) {
58+
if (qr <l ||ql >r) {
59+
return;
60+
}
61+
if (ql <=l &&r <=qr) {
62+
count[idx] +=val;
63+
}else {
64+
intmid = (l +r) /2;
65+
update(2 *idx +1,l,mid,ql,qr,val);
66+
update(2 *idx +2,mid +1,r,ql,qr,val);
67+
}
68+
if (count[idx] >0) {
69+
len[idx] =x[r +1] - (double)x[l];
70+
}else {
71+
if (l ==r) {
72+
len[idx] =0;
73+
}else {
74+
len[idx] =len[2 *idx +1] +len[2 *idx +2];
75+
}
76+
}
77+
}
78+
79+
voidupdate(intql,intqr,intval) {
80+
update(0,0,n -1,ql,qr,val);
81+
}
82+
83+
doublequery() {
84+
returnlen[0];
85+
}
86+
}
87+
88+
publicdoubleseparateSquares(int[][]squares) {
89+
intn =squares.length;
90+
Event[]events =newEvent[2 *n];
91+
intidx =0;
92+
List<Integer>xList =newArrayList<>();
93+
for (int[]s :squares) {
94+
intx =s[0];
95+
inty =s[1];
96+
intl =s[2];
97+
intx2 =x +l;
98+
inty2 =y +l;
99+
events[idx++] =newEvent(y,x,x2,1);
100+
events[idx++] =newEvent(y2,x,x2, -1);
101+
xList.add(x);
102+
xList.add(x2);
103+
}
104+
Arrays.sort(events);
105+
intm =xList.size();
106+
int[]xCords =newint[m];
107+
for (inti =0;i <m;i++) {
108+
xCords[i] =xList.get(i);
109+
}
110+
Arrays.sort(xCords);
111+
intuniqueCount =0;
112+
for (inti =0;i <m;i++) {
113+
if (i ==0 ||xCords[i] !=xCords[i -1]) {
114+
xCords[uniqueCount++] =xCords[i];
115+
}
116+
}
117+
int[]x =Arrays.copyOf(xCords,uniqueCount);
118+
SegmentTreesegTree =newSegmentTree(x);
119+
List<Segment>segments =newArrayList<>();
120+
doublecumArea =0.0;
121+
doublelastY =events[0].y;
122+
intiEvent =0;
123+
while (iEvent <events.length) {
124+
doublecurrentY =events[iEvent].y;
125+
doubledelta =currentY -lastY;
126+
if (delta >0) {
127+
doubleunionX =segTree.query();
128+
segments.add(newSegment(lastY,currentY,unionX,cumArea));
129+
cumArea +=unionX *delta;
130+
}
131+
while (iEvent <events.length &&events[iEvent].y ==currentY) {
132+
Evente =events[iEvent];
133+
intleft =Arrays.binarySearch(x,e.x1);
134+
intright =Arrays.binarySearch(x,e.x2);
135+
if (left <right) {
136+
segTree.update(left,right -1,e.type);
137+
}
138+
iEvent++;
139+
}
140+
lastY =currentY;
141+
}
142+
doubletotalArea =cumArea;
143+
doubletarget =totalArea /2.0;
144+
doubleanswer;
145+
for (Segmentseg :segments) {
146+
doublesegArea =seg.unionX * (seg.y2 -seg.y1);
147+
if (seg.cumArea +segArea >=target) {
148+
doubleneeded =target -seg.cumArea;
149+
answer =seg.y1 +needed /seg.unionX;
150+
returnanswer;
151+
}
152+
}
153+
returnlastY;
154+
}
155+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp