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

Commitaf3063f

Browse files
authored
Added tasks 3264-3267
1 parent695b7b9 commitaf3063f

File tree

12 files changed

+484
-0
lines changed

12 files changed

+484
-0
lines changed
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg3201_3300.s3264_final_array_state_after_k_multiplication_operations_i;
2+
3+
// #Easy #2024_08_28_Time_1_ms_(100.00%)_Space_44.9_MB_(31.20%)
4+
5+
publicclassSolution {
6+
publicint[]getFinalState(int[]nums,intk,intmultiplier) {
7+
while (k-- >0) {
8+
intmin =nums[0];
9+
intindex =0;
10+
for (inti =0;i <nums.length;i++) {
11+
if (min >nums[i]) {
12+
min =nums[i];
13+
index =i;
14+
}
15+
}
16+
nums[index] =nums[index] *multiplier;
17+
}
18+
returnnums;
19+
}
20+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
3264\. Final Array State After K Multiplication Operations I
2+
3+
Easy
4+
5+
You are given an integer array`nums`, an integer`k`, and an integer`multiplier`.
6+
7+
You need to perform`k` operations on`nums`. In each operation:
8+
9+
* Find the**minimum** value`x` in`nums`. If there are multiple occurrences of the minimum value, select the one that appears**first**.
10+
* Replace the selected minimum value`x` with`x * multiplier`.
11+
12+
Return an integer array denoting the_final state_ of`nums` after performing all`k` operations.
13+
14+
**Example 1:**
15+
16+
**Input:** nums =[2,1,3,5,6], k = 5, multiplier = 2
17+
18+
**Output:**[8,4,6,5,6]
19+
20+
**Explanation:**
21+
22+
| Operation| Result|
23+
|---------------------|------------------|
24+
| After operation 1|[2, 2, 3, 5, 6]|
25+
| After operation 2|[4, 2, 3, 5, 6]|
26+
| After operation 3|[4, 4, 3, 5, 6]|
27+
| After operation 4|[4, 4, 6, 5, 6]|
28+
| After operation 5|[8, 4, 6, 5, 6]|
29+
30+
**Example 2:**
31+
32+
**Input:** nums =[1,2], k = 3, multiplier = 4
33+
34+
**Output:**[16,8]
35+
36+
**Explanation:**
37+
38+
| Operation| Result|
39+
|---------------------|-------------|
40+
| After operation 1|[4, 2]|
41+
| After operation 2|[4, 8]|
42+
| After operation 3|[16, 8]|
43+
44+
**Constraints:**
45+
46+
*`1 <= nums.length <= 100`
47+
*`1 <= nums[i] <= 100`
48+
*`1 <= k <= 10`
49+
*`1 <= multiplier <= 5`
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
packageg3201_3300.s3265_count_almost_equal_pairs_i;
2+
3+
// #Medium #2024_08_28_Time_5_ms_(100.00%)_Space_44.7_MB_(91.23%)
4+
5+
publicclassSolution {
6+
publicintcountPairs(int[]nums) {
7+
intans =0;
8+
for (inti =0;i <nums.length -1;i++) {
9+
for (intj =i +1;j <nums.length;j++) {
10+
if (nums[i] ==nums[j]
11+
|| ((nums[j] -nums[i]) %9 ==0 &&check(nums[i],nums[j]))) {
12+
ans++;
13+
}
14+
}
15+
}
16+
returnans;
17+
}
18+
19+
privatebooleancheck(inta,intb) {
20+
int[]ca =newint[10];
21+
int[]cb =newint[10];
22+
intd =0;
23+
while (a >0 ||b >0) {
24+
if (a %10 !=b %10) {
25+
d++;
26+
if (d >2) {
27+
returnfalse;
28+
}
29+
}
30+
ca[a %10]++;
31+
cb[b %10]++;
32+
a /=10;
33+
b /=10;
34+
}
35+
returnd ==2 &&areEqual(ca,cb);
36+
}
37+
38+
privatebooleanareEqual(int[]a,int[]b) {
39+
for (inti =0;i <10;i++) {
40+
if (a[i] !=b[i]) {
41+
returnfalse;
42+
}
43+
}
44+
returntrue;
45+
}
46+
}
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
3265\. Count Almost Equal Pairs I
2+
3+
Medium
4+
5+
You are given an array`nums` consisting of positive integers.
6+
7+
We call two integers`x` and`y` in this problem**almost equal** if both integers can become equal after performing the following operation**at most once**:
8+
9+
* Choose**either**`x` or`y` and swap any two digits within the chosen number.
10+
11+
Return the number of indices`i` and`j` in`nums` where`i < j` such that`nums[i]` and`nums[j]` are**almost equal**.
12+
13+
**Note** that it is allowed for an integer to have leading zeros after performing an operation.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[3,12,30,17,21]
18+
19+
**Output:** 2
20+
21+
**Explanation:**
22+
23+
The almost equal pairs of elements are:
24+
25+
* 3 and 30. By swapping 3 and 0 in 30, you get 3.
26+
* 12 and 21. By swapping 1 and 2 in 12, you get 21.
27+
28+
**Example 2:**
29+
30+
**Input:** nums =[1,1,1,1,1]
31+
32+
**Output:** 10
33+
34+
**Explanation:**
35+
36+
Every two elements in the array are almost equal.
37+
38+
**Example 3:**
39+
40+
**Input:** nums =[123,231]
41+
42+
**Output:** 0
43+
44+
**Explanation:**
45+
46+
We cannot swap any two digits of 123 or 231 to reach the other.
47+
48+
**Constraints:**
49+
50+
*`2 <= nums.length <= 100`
51+
* <code>1 <= nums[i] <= 10<sup>6</sup></code>
Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
packageg3201_3300.s3266_final_array_state_after_k_multiplication_operations_ii;
2+
3+
// #Hard #2024_08_28_Time_26_ms_(100.00%)_Space_47_MB_(51.94%)
4+
5+
importjava.util.Arrays;
6+
importjava.util.PriorityQueue;
7+
8+
publicclassSolution {
9+
privatestaticfinalintMOD =1_000_000_007;
10+
11+
publicint[]getFinalState(int[]nums,intk,intmultiplier) {
12+
if (multiplier ==1) {
13+
returnnums;
14+
}
15+
intn =nums.length;
16+
intmx =0;
17+
for (intx :nums) {
18+
mx =Math.max(mx,x);
19+
}
20+
long[]a =newlong[n];
21+
intleft =k;
22+
booleanshouldExit =false;
23+
for (inti =0;i <n && !shouldExit;i++) {
24+
longx =nums[i];
25+
while (x <mx) {
26+
x *=multiplier;
27+
if (--left <0) {
28+
shouldExit =true;
29+
break;
30+
}
31+
}
32+
a[i] =x;
33+
}
34+
if (left <0) {
35+
PriorityQueue<long[]>pq =
36+
newPriorityQueue<>(
37+
(p,q) ->
38+
p[0] !=q[0]
39+
?Long.compare(p[0],q[0])
40+
:Long.compare(p[1],q[1]));
41+
for (inti =0;i <n;i++) {
42+
pq.offer(newlong[] {nums[i],i});
43+
}
44+
while (k-- >0) {
45+
long[]p =pq.poll();
46+
p[0] *=multiplier;
47+
pq.offer(p);
48+
}
49+
while (!pq.isEmpty()) {
50+
long[]p =pq.poll();
51+
nums[(int)p[1]] = (int) (p[0] %MOD);
52+
}
53+
returnnums;
54+
}
55+
56+
Integer[]ids =newInteger[n];
57+
Arrays.setAll(ids,i ->i);
58+
Arrays.sort(ids, (i,j) ->Long.compare(a[i],a[j]));
59+
k =left;
60+
longpow1 =pow(multiplier,k /n);
61+
longpow2 =pow1 *multiplier %MOD;
62+
for (inti =0;i <n;i++) {
63+
intj =ids[i];
64+
nums[j] = (int) (a[j] %MOD * (i <k %n ?pow2 :pow1) %MOD);
65+
}
66+
returnnums;
67+
}
68+
69+
privatelongpow(longx,intn) {
70+
longres =1;
71+
for (;n >0;n /=2) {
72+
if (n %2 >0) {
73+
res =res *x %MOD;
74+
}
75+
x =x *x %MOD;
76+
}
77+
returnres;
78+
}
79+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
3266\. Final Array State After K Multiplication Operations II
2+
3+
Hard
4+
5+
You are given an integer array`nums`, an integer`k`, and an integer`multiplier`.
6+
7+
You need to perform`k` operations on`nums`. In each operation:
8+
9+
* Find the**minimum** value`x` in`nums`. If there are multiple occurrences of the minimum value, select the one that appears**first**.
10+
* Replace the selected minimum value`x` with`x * multiplier`.
11+
12+
After the`k` operations, apply**modulo** <code>10<sup>9</sup> + 7</code> to every value in`nums`.
13+
14+
Return an integer array denoting the_final state_ of`nums` after performing all`k` operations and then applying the modulo.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[2,1,3,5,6], k = 5, multiplier = 2
19+
20+
**Output:**[8,4,6,5,6]
21+
22+
**Explanation:**
23+
24+
| Operation| Result|
25+
|-------------------------|------------------|
26+
| After operation 1|[2, 2, 3, 5, 6]|
27+
| After operation 2|[4, 2, 3, 5, 6]|
28+
| After operation 3|[4, 4, 3, 5, 6]|
29+
| After operation 4|[4, 4, 6, 5, 6]|
30+
| After operation 5|[8, 4, 6, 5, 6]|
31+
| After applying modulo|[8, 4, 6, 5, 6]|
32+
33+
**Example 2:**
34+
35+
**Input:** nums =[100000,2000], k = 2, multiplier = 1000000
36+
37+
**Output:**[999999307,999999993]
38+
39+
**Explanation:**
40+
41+
| Operation| Result|
42+
|-------------------------|----------------------|
43+
| After operation 1|[100000, 2000000000]|
44+
| After operation 2|[100000000000, 2000000000]|
45+
| After applying modulo|[999999307, 999999993]|
46+
47+
**Constraints:**
48+
49+
* <code>1 <= nums.length <= 10<sup>4</sup></code>
50+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
51+
* <code>1 <= k <= 10<sup>9</sup></code>
52+
* <code>1 <= multiplier <= 10<sup>6</sup></code>
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
packageg3201_3300.s3267_count_almost_equal_pairs_ii;
2+
3+
// #Hard #2024_08_28_Time_353_ms_(99.78%)_Space_45.8_MB_(56.64%)
4+
5+
importjava.util.Arrays;
6+
importjava.util.HashMap;
7+
importjava.util.HashSet;
8+
importjava.util.Map;
9+
importjava.util.Set;
10+
11+
publicclassSolution {
12+
publicintcountPairs(int[]nums) {
13+
intpairs =0;
14+
Map<Integer,Integer>counts =newHashMap<>();
15+
Arrays.sort(nums);
16+
for (intnum :nums) {
17+
Set<Integer>newNums =newHashSet<>();
18+
newNums.add(num);
19+
for (intunit1 =1,remain1 =num;remain1 >0;unit1 *=10,remain1 /=10) {
20+
intdigit1 =num /unit1 %10;
21+
for (intunit2 =unit1 *10,remain2 =remain1 /10;
22+
remain2 >0;
23+
unit2 *=10,remain2 /=10) {
24+
intdigit2 =num /unit2 %10;
25+
intnewNum1 =
26+
num -digit1 *unit1 -digit2 *unit2 +digit2 *unit1 +digit1 *unit2;
27+
newNums.add(newNum1);
28+
for (intunit3 =unit1 *10,remain3 =remain1 /10;
29+
remain3 >0;
30+
unit3 *=10,remain3 /=10) {
31+
intdigit3 =newNum1 /unit3 %10;
32+
for (intunit4 =unit3 *10,remain4 =remain3 /10;
33+
remain4 >0;
34+
unit4 *=10,remain4 /=10) {
35+
intdigit4 =newNum1 /unit4 %10;
36+
intnewNum2 =
37+
newNum1
38+
-digit3 *unit3
39+
-digit4 *unit4
40+
+digit4 *unit3
41+
+digit3 *unit4;
42+
newNums.add(newNum2);
43+
}
44+
}
45+
}
46+
}
47+
for (intnewNum :newNums) {
48+
pairs +=counts.getOrDefault(newNum,0);
49+
}
50+
counts.put(num,counts.getOrDefault(num,0) +1);
51+
}
52+
returnpairs;
53+
}
54+
}

0 commit comments

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