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

Commit6f08d34

Browse files
authored
Added tasks 3461-3464
1 parent0cd2a8a commit6f08d34

File tree

12 files changed

+509
-0
lines changed

12 files changed

+509
-0
lines changed
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
packageg3401_3500.s3461_check_if_digits_are_equal_in_string_after_operations_i;
2+
3+
// #Easy #String #Math #Simulation #Number_Theory #Combinatorics
4+
// #2025_02_25_Time_2_ms_(96.71%)_Space_42.26_MB_(97.03%)
5+
6+
publicclassSolution {
7+
publicbooleanhasSameDigits(Strings) {
8+
char[]ch =s.toCharArray();
9+
intk =ch.length -1;
10+
while (k !=1) {
11+
for (inti =0;i <k;i++) {
12+
inta =ch[i] -48;
13+
intb =ch[i +1] -48;
14+
intd = (a +b) %10;
15+
charc = (char) (d +'0');
16+
ch[i] =c;
17+
}
18+
k--;
19+
}
20+
returnch[0] ==ch[1];
21+
}
22+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
3461\. Check If Digits Are Equal in String After Operations I
2+
3+
Easy
4+
5+
You are given a string`s` consisting of digits. Perform the following operation repeatedly until the string has**exactly** two digits:
6+
7+
* For each pair of consecutive digits in`s`, starting from the first digit, calculate a new digit as the sum of the two digits**modulo** 10.
8+
* Replace`s` with the sequence of newly calculated digits,_maintaining the order_ in which they are computed.
9+
10+
Return`true` if the final two digits in`s` are the**same**; otherwise, return`false`.
11+
12+
**Example 1:**
13+
14+
**Input:** s = "3902"
15+
16+
**Output:** true
17+
18+
**Explanation:**
19+
20+
* Initially,`s = "3902"`
21+
* First operation:
22+
*`(s[0] + s[1]) % 10 = (3 + 9) % 10 = 2`
23+
*`(s[1] + s[2]) % 10 = (9 + 0) % 10 = 9`
24+
*`(s[2] + s[3]) % 10 = (0 + 2) % 10 = 2`
25+
*`s` becomes`"292"`
26+
* Second operation:
27+
*`(s[0] + s[1]) % 10 = (2 + 9) % 10 = 1`
28+
*`(s[1] + s[2]) % 10 = (9 + 2) % 10 = 1`
29+
*`s` becomes`"11"`
30+
* Since the digits in`"11"` are the same, the output is`true`.
31+
32+
**Example 2:**
33+
34+
**Input:** s = "34789"
35+
36+
**Output:** false
37+
38+
**Explanation:**
39+
40+
* Initially,`s = "34789"`.
41+
* After the first operation,`s = "7157"`.
42+
* After the second operation,`s = "862"`.
43+
* After the third operation,`s = "48"`.
44+
* Since`'4' != '8'`, the output is`false`.
45+
46+
**Constraints:**
47+
48+
*`3 <= s.length <= 100`
49+
*`s` consists of only digits.
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
packageg3401_3500.s3462_maximum_sum_with_at_most_k_elements;
2+
3+
// #Medium #Array #Sorting #Greedy #Matrix #Heap_(Priority_Queue)
4+
// #2025_02_25_Time_62_ms_(99.82%)_Space_78.09_MB_(20.19%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publiclongmaxSum(int[][]grid,int[]limits,intk) {
10+
intl =0;
11+
for (inti =0;i <limits.length;i++) {
12+
l +=limits[i];
13+
}
14+
int[]dp =newint[l];
15+
inta =0;
16+
for (inti =0;i <grid.length;i++) {
17+
intlim =limits[i];
18+
Arrays.sort(grid[i]);
19+
for (intj =grid[i].length -lim;j <grid[i].length;j++) {
20+
dp[a] =grid[i][j];
21+
a++;
22+
}
23+
}
24+
Arrays.sort(dp);
25+
longsum =0L;
26+
for (inti =l -1;i >=l -k;i--) {
27+
sum +=dp[i];
28+
}
29+
returnsum;
30+
}
31+
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
3462\. Maximum Sum With at Most K Elements
2+
3+
Medium
4+
5+
You are given a 2D integer matrix`grid` of size`n x m`, an integer array`limits` of length`n`, and an integer`k`. The task is to find the**maximum sum** of**at most**`k` elements from the matrix`grid` such that:
6+
7+
* The number of elements taken from the <code>i<sup>th</sup></code> row of`grid` does not exceed`limits[i]`.
8+
9+
10+
Return the**maximum sum**.
11+
12+
**Example 1:**
13+
14+
**Input:** grid =[[1,2],[3,4]], limits =[1,2], k = 2
15+
16+
**Output:** 7
17+
18+
**Explanation:**
19+
20+
* From the second row, we can take at most 2 elements. The elements taken are 4 and 3.
21+
* The maximum possible sum of at most 2 selected elements is`4 + 3 = 7`.
22+
23+
**Example 2:**
24+
25+
**Input:** grid =[[5,3,7],[8,2,6]], limits =[2,2], k = 3
26+
27+
**Output:** 21
28+
29+
**Explanation:**
30+
31+
* From the first row, we can take at most 2 elements. The element taken is 7.
32+
* From the second row, we can take at most 2 elements. The elements taken are 8 and 6.
33+
* The maximum possible sum of at most 3 selected elements is`7 + 8 + 6 = 21`.
34+
35+
**Constraints:**
36+
37+
*`n == grid.length == limits.length`
38+
*`m == grid[i].length`
39+
*`1 <= n, m <= 500`
40+
* <code>0 <= grid[i][j] <= 10<sup>5</sup></code>
41+
*`0 <= limits[i] <= m`
42+
*`0 <= k <= min(n * m, sum(limits))`
Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
packageg3401_3500.s3463_check_if_digits_are_equal_in_string_after_operations_ii;
2+
3+
// #Hard #String #Math #Number_Theory #Combinatorics
4+
// #2025_02_25_Time_43_ms_(99.64%)_Space_49.40_MB_(10.02%)
5+
6+
publicclassSolution {
7+
privateintpowMod10(inta,intn) {
8+
intx =1;
9+
while (n >=1) {
10+
if (n %2 ==1) {
11+
x = (x *a) %10;
12+
}
13+
a = (a *a) %10;
14+
n /=2;
15+
}
16+
returnx;
17+
}
18+
19+
privateint[]f(intn) {
20+
int[]ns =newint[n +1];
21+
int[]n2 =newint[n +1];
22+
int[]n5 =newint[n +1];
23+
ns[0] =1;
24+
for (inti =1;i <=n; ++i) {
25+
intm =i;
26+
n2[i] =n2[i -1];
27+
n5[i] =n5[i -1];
28+
while (m %2 ==0) {
29+
m /=2;
30+
n2[i]++;
31+
}
32+
while (m %5 ==0) {
33+
m /=5;
34+
n5[i]++;
35+
}
36+
ns[i] = (ns[i -1] *m) %10;
37+
}
38+
int[]inv =newint[10];
39+
for (inti =1;i <10; ++i) {
40+
for (intj =0;j <10; ++j) {
41+
if (i *j %10 ==1) {
42+
inv[i] =j;
43+
}
44+
}
45+
}
46+
int[]xs =newint[n +1];
47+
for (intk =0;k <=n; ++k) {
48+
inta =0;
49+
ints2 =n2[n] -n2[n -k] -n2[k];
50+
ints5 =n5[n] -n5[n -k] -n5[k];
51+
if (s2 ==0 ||s5 ==0) {
52+
a = (ns[n] *inv[ns[n -k]] *inv[ns[k]] *powMod10(2,s2) *powMod10(5,s5)) %10;
53+
}
54+
xs[k] =a;
55+
}
56+
returnxs;
57+
}
58+
59+
publicbooleanhasSameDigits(Strings) {
60+
intn =s.length();
61+
int[]xs =f(n -2);
62+
int[]arr =newint[n];
63+
for (inti =0;i <n;i++) {
64+
arr[i] =s.charAt(i) -'0';
65+
}
66+
intnum1 =0;
67+
intnum2 =0;
68+
for (inti =0;i <n -1;i++) {
69+
num1 = (num1 +xs[i] *arr[i]) %10;
70+
num2 = (num2 +xs[i] *arr[i +1]) %10;
71+
}
72+
returnnum1 ==num2;
73+
}
74+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
3463\. Check If Digits Are Equal in String After Operations II
2+
3+
Hard
4+
5+
You are given a string`s` consisting of digits. Perform the following operation repeatedly until the string has**exactly** two digits:
6+
7+
* For each pair of consecutive digits in`s`, starting from the first digit, calculate a new digit as the sum of the two digits**modulo** 10.
8+
* Replace`s` with the sequence of newly calculated digits,_maintaining the order_ in which they are computed.
9+
10+
Return`true` if the final two digits in`s` are the**same**; otherwise, return`false`.
11+
12+
**Example 1:**
13+
14+
**Input:** s = "3902"
15+
16+
**Output:** true
17+
18+
**Explanation:**
19+
20+
* Initially,`s = "3902"`
21+
* First operation:
22+
*`(s[0] + s[1]) % 10 = (3 + 9) % 10 = 2`
23+
*`(s[1] + s[2]) % 10 = (9 + 0) % 10 = 9`
24+
*`(s[2] + s[3]) % 10 = (0 + 2) % 10 = 2`
25+
*`s` becomes`"292"`
26+
* Second operation:
27+
*`(s[0] + s[1]) % 10 = (2 + 9) % 10 = 1`
28+
*`(s[1] + s[2]) % 10 = (9 + 2) % 10 = 1`
29+
*`s` becomes`"11"`
30+
* Since the digits in`"11"` are the same, the output is`true`.
31+
32+
**Example 2:**
33+
34+
**Input:** s = "34789"
35+
36+
**Output:** false
37+
38+
**Explanation:**
39+
40+
* Initially,`s = "34789"`.
41+
* After the first operation,`s = "7157"`.
42+
* After the second operation,`s = "862"`.
43+
* After the third operation,`s = "48"`.
44+
* Since`'4' != '8'`, the output is`false`.
45+
46+
**Constraints:**
47+
48+
* <code>3 <= s.length <= 10<sup>5</sup></code>
49+
*`s` consists of only digits.
Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
packageg3401_3500.s3464_maximize_the_distance_between_points_on_a_square;
2+
3+
// #Hard #Array #Greedy #Binary_Search #2025_02_25_Time_18_ms_(98.51%)_Space_49.78_MB_(46.27%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicintmaxDistance(intside,int[][]pts,intk) {
9+
intn =pts.length;
10+
long[]p =newlong[n];
11+
for (inti =0;i <n;i++) {
12+
intx =pts[i][0];
13+
inty =pts[i][1];
14+
longc;
15+
if (y ==0) {
16+
c =x;
17+
}elseif (x ==side) {
18+
c =side + (long)y;
19+
}elseif (y ==side) {
20+
c =2L *side + (side -x);
21+
}else {
22+
c =3L *side + (side -y);
23+
}
24+
p[i] =c;
25+
}
26+
Arrays.sort(p);
27+
longc =4L *side;
28+
inttot =2 *n;
29+
long[]dArr =newlong[tot];
30+
for (inti =0;i <n;i++) {
31+
dArr[i] =p[i];
32+
dArr[i +n] =p[i] +c;
33+
}
34+
intlo =0;
35+
inthi =2 *side;
36+
intans =0;
37+
while (lo <=hi) {
38+
intmid = (lo +hi) >>>1;
39+
if (check(mid,dArr,n,k,c)) {
40+
ans =mid;
41+
lo =mid +1;
42+
}else {
43+
hi =mid -1;
44+
}
45+
}
46+
returnans;
47+
}
48+
49+
privatebooleancheck(intd,long[]dArr,intn,intk,longc) {
50+
intlen =dArr.length;
51+
int[]nxt =newint[len];
52+
intj =0;
53+
for (inti =0;i <len;i++) {
54+
if (j <i +1) {
55+
j =i +1;
56+
}
57+
while (j <len &&dArr[j] <dArr[i] +d) {
58+
j++;
59+
}
60+
nxt[i] = (j <len) ?j : -1;
61+
}
62+
for (inti =0;i <n;i++) {
63+
intcnt =1;
64+
intcur =i;
65+
while (cnt <k) {
66+
intnx =nxt[cur];
67+
if (nx == -1 ||nx >=i +n) {
68+
break;
69+
}
70+
cur =nx;
71+
cnt++;
72+
}
73+
if (cnt ==k && (dArr[i] +c -dArr[cur]) >=d) {
74+
returntrue;
75+
}
76+
}
77+
returnfalse;
78+
}
79+
}

0 commit comments

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