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

Commit7cf0adb

Browse files
authored
Added tasks 2843-2848
1 parent83b7c21 commit7cf0adb

File tree

15 files changed

+607
-0
lines changed

15 files changed

+607
-0
lines changed
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
packageg2801_2900.s2843_count_symmetric_integers;
2+
3+
// #Easy #Math #Enumeration #2023_12_13_Time_26_ms_(80.87%)_Space_43.9_MB_(8.49%)
4+
5+
publicclassSolution {
6+
publicintcountSymmetricIntegers(intlow,inthigh) {
7+
intcount =0;
8+
for (inti =low;i <=high;i++) {
9+
if (isSymmetric(i)) {
10+
count++;
11+
}
12+
}
13+
returncount;
14+
}
15+
16+
privatebooleanisSymmetric(intnum) {
17+
Stringstr =String.valueOf(num);
18+
intn =str.length();
19+
if (n %2 !=0) {
20+
returnfalse;
21+
}
22+
intleftSum =0;
23+
intrightSum =0;
24+
for (inti =0,j =n -1;i <j;i++,j--) {
25+
leftSum +=str.charAt(i) -'0';
26+
rightSum +=str.charAt(j) -'0';
27+
}
28+
returnleftSum ==rightSum;
29+
}
30+
}
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
2843\. Count Symmetric Integers
2+
3+
Easy
4+
5+
You are given two positive integers`low` and`high`.
6+
7+
An integer`x` consisting of`2 * n` digits is**symmetric** if the sum of the first`n` digits of`x` is equal to the sum of the last`n` digits of`x`. Numbers with an odd number of digits are never symmetric.
8+
9+
Return_the**number of symmetric** integers in the range_`[low, high]`.
10+
11+
**Example 1:**
12+
13+
**Input:** low = 1, high = 100
14+
15+
**Output:** 9
16+
17+
**Explanation:** There are 9 symmetric integers between 1 and 100: 11, 22, 33, 44, 55, 66, 77, 88, and 99.
18+
19+
**Example 2:**
20+
21+
**Input:** low = 1200, high = 1230
22+
23+
**Output:** 4
24+
25+
**Explanation:** There are 4 symmetric integers between 1200 and 1230: 1203, 1212, 1221, and 1230.
26+
27+
**Constraints:**
28+
29+
* <code>1 <= low <= high <= 10<sup>4</sup></code>
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
packageg2801_2900.s2844_minimum_operations_to_make_a_special_number;
2+
3+
// #Medium #String #Math #Greedy #Enumeration #2023_12_13_Time_1_ms_(100.00%)_Space_41_MB_(68.09%)
4+
5+
publicclassSolution {
6+
publicintminimumOperations(Stringnum) {
7+
char[]number =num.toCharArray();
8+
intn =number.length;
9+
intzero =0;
10+
intfive =0;
11+
for (inti =n -1;i >=0;i--) {
12+
if (number[i] =='0') {
13+
if (zero ==1) {
14+
returnn -i -2;
15+
}else {
16+
zero++;
17+
}
18+
}elseif (number[i] =='5') {
19+
if (zero ==1) {
20+
returnn -i -2;
21+
}
22+
if (five ==0) {
23+
five++;
24+
}
25+
}elseif ((number[i] =='2' ||number[i] =='7') &&five ==1) {
26+
returnn -i -2;
27+
}
28+
}
29+
if (zero ==1) {
30+
returnn -1;
31+
}
32+
returnn;
33+
}
34+
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
2844\. Minimum Operations to Make a Special Number
2+
3+
Medium
4+
5+
You are given a**0-indexed** string`num` representing a non-negative integer.
6+
7+
In one operation, you can pick any digit of`num` and delete it. Note that if you delete all the digits of`num`,`num` becomes`0`.
8+
9+
Return_the**minimum number of operations** required to make_`num`_special_.
10+
11+
An integer`x` is considered**special** if it is divisible by`25`.
12+
13+
**Example 1:**
14+
15+
**Input:** num = "2245047"
16+
17+
**Output:** 2
18+
19+
**Explanation:** Delete digits num[5] and num[6]. The resulting number is "22450" which is special since it is divisible by 25. It can be shown that 2 is the minimum number of operations required to get a special number.
20+
21+
**Example 2:**
22+
23+
**Input:** num = "2908305"
24+
25+
**Output:** 3
26+
27+
**Explanation:** Delete digits num[3], num[4], and num[6]. The resulting number is "2900" which is special since it is divisible by 25. It can be shown that 3 is the minimum number of operations required to get a special number.
28+
29+
**Example 3:**
30+
31+
**Input:** num = "10"
32+
33+
**Output:** 1
34+
35+
**Explanation:** Delete digit num[0]. The resulting number is "0" which is special since it is divisible by 25. It can be shown that 1 is the minimum number of operations required to get a special number.
36+
37+
**Constraints:**
38+
39+
*`1 <= num.length <= 100`
40+
*`num` only consists of digits`'0'` through`'9'`.
41+
*`num` does not contain any leading zeros.
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2801_2900.s2845_count_of_interesting_subarrays;
2+
3+
// #Medium #Array #Hash_Table #Prefix_Sum #2023_12_13_Time_27_ms_(97.76%)_Space_62.7_MB_(26.12%)
4+
5+
importjava.util.HashMap;
6+
importjava.util.List;
7+
importjava.util.Map;
8+
9+
publicclassSolution {
10+
publiclongcountInterestingSubarrays(List<Integer>nums,intmodulo,intk) {
11+
intprefixCnt =0;
12+
Map<Integer,Integer>freq =newHashMap<>();
13+
freq.put(0,1);
14+
longinterestingSubarrays =0;
15+
for (Integernum :nums) {
16+
if (num %modulo ==k) {
17+
prefixCnt++;
18+
}
19+
intexpectedPrefix = (prefixCnt -k +modulo) %modulo;
20+
interestingSubarrays +=freq.getOrDefault(expectedPrefix,0);
21+
freq.put(prefixCnt %modulo,freq.getOrDefault(prefixCnt %modulo,0) +1);
22+
}
23+
returninterestingSubarrays;
24+
}
25+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
2845\. Count of Interesting Subarrays
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums`, an integer`modulo`, and an integer`k`.
6+
7+
Your task is to find the count of subarrays that are**interesting**.
8+
9+
A**subarray**`nums[l..r]` is**interesting** if the following condition holds:
10+
11+
* Let`cnt` be the number of indices`i` in the range`[l, r]` such that`nums[i] % modulo == k`. Then,`cnt % modulo == k`.
12+
13+
Return_an integer denoting the count of interesting subarrays._
14+
15+
**Note:** A subarray is_a contiguous non-empty sequence of elements within an array_.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[3,2,4], modulo = 2, k = 1
20+
21+
**Output:** 3
22+
23+
**Explanation:** In this example the interesting subarrays are: The subarray nums[0..0] which is[3].
24+
- There is only one index, i = 0, in the range[0, 0] that satisfies nums[i] % modulo == k.
25+
- Hence, cnt = 1 and cnt % modulo == k. The subarray nums[0..1] which is[3,2].
26+
- There is only one index, i = 0, in the range[0, 1] that satisfies nums[i] % modulo == k.
27+
- Hence, cnt = 1 and cnt % modulo == k. The subarray nums[0..2] which is[3,2,4].
28+
- There is only one index, i = 0, in the range[0, 2] that satisfies nums[i] % modulo == k.
29+
- Hence, cnt = 1 and cnt % modulo == k.
30+
31+
It can be shown that there are no other interesting subarrays. So, the answer is 3.
32+
33+
**Example 2:**
34+
35+
**Input:** nums =[3,1,9,6], modulo = 3, k = 0
36+
37+
**Output:** 2
38+
39+
**Explanation:** In this example the interesting subarrays are: The subarray nums[0..3] which is[3,1,9,6].
40+
- There are three indices, i = 0, 2, 3, in the range[0, 3] that satisfy nums[i] % modulo == k.
41+
- Hence, cnt = 3 and cnt % modulo == k. The subarray nums[1..1] which is[1].
42+
- There is no index, i, in the range[1, 1] that satisfies nums[i] % modulo == k.
43+
- Hence, cnt = 0 and cnt % modulo == k.
44+
45+
It can be shown that there are no other interesting subarrays. So, the answer is 2.
46+
47+
**Constraints:**
48+
49+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
50+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
51+
* <code>1 <= modulo <= 10<sup>9</sup></code>
52+
*`0 <= k < modulo`
Lines changed: 152 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,152 @@
1+
packageg2801_2900.s2846_minimum_edge_weight_equilibrium_queries_in_a_tree;
2+
3+
// #Hard #Array #Tree #Graph #Strongly_Connected_Component
4+
// #2023_12_13_Time_74_ms_(66.04%)_Space_57_MB_(50.94%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.List;
9+
10+
@SuppressWarnings("java:S107")
11+
publicclassSolution {
12+
privatestaticclassNode {
13+
intv;
14+
intw;
15+
16+
Node(intv,intw) {
17+
this.v =v;
18+
this.w =w;
19+
}
20+
}
21+
22+
publicint[]minOperationsQueries(intn,int[][]edges,int[][]queries) {
23+
List<List<Node>>graph =createGraph(edges,n);
24+
intqueryCount =queries.length;
25+
int[]res =newint[queryCount];
26+
int[]parent =newint[n];
27+
int[]level =newint[n];
28+
int[][]weightFreq =newint[n][27];
29+
int[]freq =newint[27];
30+
intheight = (int) (Math.log(n) /Math.log(2)) +1;
31+
int[][]up =newint[n][height];
32+
for (int[]arr :up) {
33+
Arrays.fill(arr, -1);
34+
}
35+
dfs(graph,0,0, -1,parent,level,weightFreq,freq);
36+
for (inti =0;i <n;i++) {
37+
up[i][0] =parent[i];
38+
}
39+
for (inti =1;i <height;i++) {
40+
for (intj =0;j <n;j++) {
41+
if (up[j][i -1] == -1) {
42+
up[j][i] = -1;
43+
continue;
44+
}
45+
up[j][i] =up[up[j][i -1]][i -1];
46+
}
47+
}
48+
for (inti =0;i <queryCount;i++) {
49+
intsrc =queries[i][0];
50+
intdest =queries[i][1];
51+
intlcaNode =lca(src,dest,up,height,level);
52+
res[i] =processResult(weightFreq[src],weightFreq[dest],weightFreq[lcaNode]);
53+
}
54+
returnres;
55+
}
56+
57+
privateintlca(intsrc,intdest,int[][]up,intheight,int[]level) {
58+
intcurr1 =src;
59+
intcurr2 =dest;
60+
intminlevel;
61+
if (level[curr1] >level[curr2]) {
62+
minlevel =level[curr2];
63+
curr1 =getKthAncestor(curr1,level[curr1] -level[curr2],up,height);
64+
}elseif (level[curr1] <=level[curr2]) {
65+
minlevel =level[curr1];
66+
curr2 =getKthAncestor(curr2,level[curr2] -level[curr1],up,height);
67+
}else {
68+
minlevel =level[curr1];
69+
}
70+
if (curr1 ==curr2) {
71+
returncurr1;
72+
}
73+
intl =0;
74+
inth =level[curr2];
75+
while (l <=h) {
76+
intmid =l + (h -l) /2;
77+
intp1 =getKthAncestor(curr1,minlevel -mid,up,height);
78+
intp2 =getKthAncestor(curr2,minlevel -mid,up,height);
79+
if (p1 ==p2) {
80+
l =mid +1;
81+
}else {
82+
h =mid -1;
83+
}
84+
}
85+
returngetKthAncestor(curr1,minlevel -l +1,up,height);
86+
}
87+
88+
privateintgetKthAncestor(intnode,intk,int[][]up,intheight) {
89+
intcurr =node;
90+
for (inti =0;i <height &&k >>i !=0;i++) {
91+
if (((1 <<i) &k) !=0) {
92+
if (curr == -1) {
93+
return -1;
94+
}
95+
curr =up[curr][i];
96+
}
97+
}
98+
returncurr;
99+
}
100+
101+
privateintprocessResult(int[]freqSrc,int[]freqDest,int[]freqLCA) {
102+
int[]freqPath =newint[27];
103+
for (inti =1;i <27;i++) {
104+
freqPath[i] =freqSrc[i] +freqDest[i] -2 *freqLCA[i];
105+
}
106+
intmax =0;
107+
intpathlen =0;
108+
for (inti =1;i <27;i++) {
109+
max =Math.max(max,freqPath[i]);
110+
pathlen +=freqPath[i];
111+
}
112+
returnpathlen -max;
113+
}
114+
115+
privatevoiddfs(
116+
List<List<Node>>graph,
117+
intsrc,
118+
intcurrlevel,
119+
intp,
120+
int[]parent,
121+
int[]level,
122+
int[][]weightFreq,
123+
int[]freq) {
124+
parent[src] =p;
125+
level[src] =currlevel;
126+
System.arraycopy(freq,0,weightFreq[src],0,freq.length);
127+
for (Nodenode :graph.get(src)) {
128+
intv =node.v;
129+
intw =node.w;
130+
if (v !=p) {
131+
freq[w]++;
132+
dfs(graph,v,currlevel +1,src,parent,level,weightFreq,freq);
133+
freq[w]--;
134+
}
135+
}
136+
}
137+
138+
privateList<List<Node>>createGraph(int[][]edges,intn) {
139+
List<List<Node>>graph =newArrayList<>();
140+
for (inti =0;i <n;i++) {
141+
graph.add(newArrayList<>());
142+
}
143+
for (int[]edge :edges) {
144+
intu =edge[0];
145+
intv =edge[1];
146+
intw =edge[2];
147+
graph.get(u).add(newNode(v,w));
148+
graph.get(v).add(newNode(u,w));
149+
}
150+
returngraph;
151+
}
152+
}

0 commit comments

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