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

Commit1181401

Browse files
authored
Added tasks 3270-3277
1 parent4e24b82 commit1181401

File tree

25 files changed

+900
-16
lines changed

25 files changed

+900
-16
lines changed
Lines changed: 20 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,32 @@
11
packageg1601_1700.s1616_split_two_strings_to_make_palindrome;
22

3-
// #Medium #String #Greedy #Two_Pointers #2022_04_13_Time_4_ms_(89.77%)_Space_43.3_MB_(85.58%)
3+
// #Medium #String #Greedy #Two_Pointers #2024_09_04_Time_2_ms_(100.00%)_Space_45.1_MB_(97.99%)
44

55
@SuppressWarnings("java:S2234")
66
publicclassSolution {
77
publicbooleancheckPalindromeFormation(Stringa,Stringb) {
8-
returncheck(a,b) ||check(b,a);
9-
}
10-
11-
privatebooleancheck(Stringa,Stringb) {
12-
inti =0;
13-
intj =b.length() -1;
14-
while (j >i &&a.charAt(i) ==b.charAt(j)) {
15-
++i;
16-
--j;
8+
intn =a.length();
9+
ints =0;
10+
inte =n -1;
11+
if (isPalindrome(a,b,s,e,true)) {
12+
returntrue;
13+
}else {
14+
returnisPalindrome(b,a,s,e,true);
1715
}
18-
returnisPalindrome(a,i,j) ||isPalindrome(b,i,j);
1916
}
2017

21-
privatebooleanisPalindrome(Strings,inti,intj) {
22-
while (j >i &&s.charAt(i) ==s.charAt(j)) {
23-
++i;
24-
--j;
18+
privatebooleanisPalindrome(Stringa,Stringb,ints,inte,booleancheck) {
19+
if (s ==e) {
20+
returntrue;
21+
}
22+
while (s <e) {
23+
if (a.charAt(s) !=b.charAt(e)) {
24+
returncheck
25+
&& (isPalindrome(a,a,s,e,false) ||isPalindrome(b,b,s,e,false));
26+
}
27+
s++;
28+
e--;
2529
}
26-
returni >=j;
30+
returntrue;
2731
}
2832
}
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg3201_3300.s3270_find_the_key_of_the_numbers;
2+
3+
// #Easy #Math #2024_09_02_Time_0_ms_(100.00%)_Space_40.5_MB_(100.00%)
4+
5+
publicclassSolution {
6+
publicintgenerateKey(intnum1,intnum2,intnum3) {
7+
ints1 =
8+
Math.min(((num1 /1000) %10),Math.min(((num2 /1000) %10), ((num3 /1000) %10)))
9+
*1000;
10+
ints2 =
11+
Math.min(((num1 /100) %10),Math.min(((num2 /100) %10), ((num3 /100) %10)))
12+
*100;
13+
ints3 =
14+
Math.min(((num1 /10) %10),Math.min(((num2 /10) %10), ((num3 /10) %10))) *10;
15+
ints4 =Math.min((num1 %10),Math.min((num2 %10), (num3 %10)));
16+
returns1 +s2 +s3 +s4;
17+
}
18+
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
3270\. Find the Key of the Numbers
2+
3+
Easy
4+
5+
You are given three**positive** integers`num1`,`num2`, and`num3`.
6+
7+
The`key` of`num1`,`num2`, and`num3` is defined as a four-digit number such that:
8+
9+
* Initially, if any number has**less than** four digits, it is padded with**leading zeros**.
10+
* The <code>i<sup>th</sup></code> digit (`1 <= i <= 4`) of the`key` is generated by taking the**smallest** digit among the <code>i<sup>th</sup></code> digits of`num1`,`num2`, and`num3`.
11+
12+
Return the`key` of the three numbers**without** leading zeros (_if any_).
13+
14+
**Example 1:**
15+
16+
**Input:** num1 = 1, num2 = 10, num3 = 1000
17+
18+
**Output:** 0
19+
20+
**Explanation:**
21+
22+
On padding,`num1` becomes`"0001"`,`num2` becomes`"0010"`, and`num3` remains`"1000"`.
23+
24+
* The <code>1<sup>st</sup></code> digit of the`key` is`min(0, 0, 1)`.
25+
* The <code>2<sup>nd</sup></code> digit of the`key` is`min(0, 0, 0)`.
26+
* The <code>3<sup>rd</sup></code> digit of the`key` is`min(0, 1, 0)`.
27+
* The <code>4<sup>th</sup></code> digit of the`key` is`min(1, 0, 0)`.
28+
29+
Hence, the`key` is`"0000"`, i.e. 0.
30+
31+
**Example 2:**
32+
33+
**Input:** num1 = 987, num2 = 879, num3 = 798
34+
35+
**Output:** 777
36+
37+
**Example 3:**
38+
39+
**Input:** num1 = 1, num2 = 2, num3 = 3
40+
41+
**Output:** 1
42+
43+
**Constraints:**
44+
45+
*`1 <= num1, num2, num3 <= 9999`
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg3201_3300.s3271_hash_divided_string;
2+
3+
// #Medium #String #Simulation #2024_09_02_Time_2_ms_(100.00%)_Space_44.7_MB_(100.00%)
4+
5+
publicclassSolution {
6+
publicStringstringHash(Strings,intk) {
7+
varresult =newStringBuilder();
8+
inti =0;
9+
intsum =0;
10+
while (i <s.length()) {
11+
sum +=s.charAt(i) -'a';
12+
if ((i +1) %k ==0) {
13+
result.append((char) ('a' +sum %26));
14+
sum =0;
15+
}
16+
i++;
17+
}
18+
returnresult.toString();
19+
}
20+
}
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
3271\. Hash Divided String
2+
3+
Medium
4+
5+
You are given a string`s` of length`n` and an integer`k`, where`n` is a**multiple** of`k`. Your task is to hash the string`s` into a new string called`result`, which has a length of`n / k`.
6+
7+
First, divide`s` into`n / k`**substrings**, each with a length of`k`. Then, initialize`result` as an**empty** string.
8+
9+
For each**substring** in order from the beginning:
10+
11+
* The**hash value** of a character is the index of that character in the**English alphabet** (e.g.,`'a' → 0`,`'b' → 1`, ...,`'z' → 25`).
12+
* Calculate the_sum_ of all the**hash values** of the characters in the substring.
13+
* Find the remainder of this sum when divided by 26, which is called`hashedChar`.
14+
* Identify the character in the English lowercase alphabet that corresponds to`hashedChar`.
15+
* Append that character to the end of`result`.
16+
17+
Return`result`.
18+
19+
**Example 1:**
20+
21+
**Input:** s = "abcd", k = 2
22+
23+
**Output:** "bf"
24+
25+
**Explanation:**
26+
27+
First substring:`"ab"`,`0 + 1 = 1`,`1 % 26 = 1`,`result[0] = 'b'`.
28+
29+
Second substring:`"cd"`,`2 + 3 = 5`,`5 % 26 = 5`,`result[1] = 'f'`.
30+
31+
**Example 2:**
32+
33+
**Input:** s = "mxz", k = 3
34+
35+
**Output:** "i"
36+
37+
**Explanation:**
38+
39+
The only substring:`"mxz"`,`12 + 23 + 25 = 60`,`60 % 26 = 8`,`result[0] = 'i'`.
40+
41+
**Constraints:**
42+
43+
*`1 <= k <= 100`
44+
*`k <= s.length <= 1000`
45+
*`s.length` is divisible by`k`.
46+
*`s` consists only of lowercase English letters.
Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
packageg3201_3300.s3272_find_the_count_of_good_integers;
2+
3+
// #Hard #Hash_Table #Math #Enumeration #Combinatorics
4+
// #2024_09_02_Time_167_ms_(100.00%)_Space_54.5_MB_(100.00%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.HashMap;
9+
importjava.util.HashSet;
10+
importjava.util.List;
11+
importjava.util.Map;
12+
importjava.util.Set;
13+
14+
publicclassSolution {
15+
privatefinalList<String>palindromes =newArrayList<>();
16+
17+
privatelongfactorial(intn) {
18+
longres =1;
19+
for (inti =2;i <=n;i++) {
20+
res *=i;
21+
}
22+
returnres;
23+
}
24+
25+
privateMap<Character,Integer>countDigits(Strings) {
26+
Map<Character,Integer>freq =newHashMap<>();
27+
for (charc :s.toCharArray()) {
28+
freq.put(c,freq.getOrDefault(c,0) +1);
29+
}
30+
returnfreq;
31+
}
32+
33+
privatelongcalculatePermutations(Map<Character,Integer>freq,intlength) {
34+
longtotalPermutations =factorial(length);
35+
for (intcount :freq.values()) {
36+
totalPermutations /=factorial(count);
37+
}
38+
returntotalPermutations;
39+
}
40+
41+
privatelongcalculateValidPermutations(Strings) {
42+
Map<Character,Integer>freq =countDigits(s);
43+
intn =s.length();
44+
longtotalPermutations =calculatePermutations(freq,n);
45+
if (freq.getOrDefault('0',0) >0) {
46+
freq.put('0',freq.get('0') -1);
47+
longinvalidPermutations =calculatePermutations(freq,n -1);
48+
totalPermutations -=invalidPermutations;
49+
}
50+
returntotalPermutations;
51+
}
52+
53+
privatevoidgeneratePalindromes(
54+
intf,intr,intk,intlb,intsum,StringBuilderans,int[]rem) {
55+
if (f >r) {
56+
if (sum ==0) {
57+
palindromes.add(ans.toString());
58+
}
59+
return;
60+
}
61+
for (inti =lb;i <=9;i++) {
62+
ans.setCharAt(f, (char) ('0' +i));
63+
ans.setCharAt(r, (char) ('0' +i));
64+
intchk =sum;
65+
chk = (chk +rem[f] *i) %k;
66+
if (f !=r) {
67+
chk = (chk +rem[r] *i) %k;
68+
}
69+
generatePalindromes(f +1,r -1,k,0,chk,ans,rem);
70+
}
71+
}
72+
73+
privateList<String>allKPalindromes(intn,intk) {
74+
StringBuilderans =newStringBuilder(n);
75+
ans.append("0".repeat(Math.max(0,n)));
76+
int[]rem =newint[n];
77+
rem[0] =1;
78+
for (inti =1;i <n;i++) {
79+
rem[i] = (rem[i -1] *10) %k;
80+
}
81+
palindromes.clear();
82+
generatePalindromes(0,n -1,k,1,0,ans,rem);
83+
returnpalindromes;
84+
}
85+
86+
publiclongcountGoodIntegers(intn,intk) {
87+
List<String>ans =allKPalindromes(n,k);
88+
Set<String>st =newHashSet<>();
89+
for (Stringstr :ans) {
90+
char[]arr =str.toCharArray();
91+
Arrays.sort(arr);
92+
st.add(newString(arr));
93+
}
94+
List<String>v =newArrayList<>(st);
95+
longchk =0;
96+
for (Stringstr :v) {
97+
longcc =calculateValidPermutations(str);
98+
chk +=cc;
99+
}
100+
returnchk;
101+
}
102+
}
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
3272\. Find the Count of Good Integers
2+
3+
Hard
4+
5+
You are given two**positive** integers`n` and`k`.
6+
7+
An integer`x` is called**k-palindromic** if:
8+
9+
*`x` is a palindrome.
10+
*`x` is divisible by`k`.
11+
12+
An integer is called**good** if its digits can be_rearranged_ to form a**k-palindromic** integer. For example, for`k = 2`, 2020 can be rearranged to form the_k-palindromic_ integer 2002, whereas 1010 cannot be rearranged to form a_k-palindromic_ integer.
13+
14+
Return the count of**good** integers containing`n` digits.
15+
16+
**Note** that_any_ integer must**not** have leading zeros,**neither** before**nor** after rearrangement. For example, 1010_cannot_ be rearranged to form 101.
17+
18+
**Example 1:**
19+
20+
**Input:** n = 3, k = 5
21+
22+
**Output:** 27
23+
24+
**Explanation:**
25+
26+
_Some_ of the good integers are:
27+
28+
* 551 because it can be rearranged to form 515.
29+
* 525 because it is already k-palindromic.
30+
31+
**Example 2:**
32+
33+
**Input:** n = 1, k = 4
34+
35+
**Output:** 2
36+
37+
**Explanation:**
38+
39+
The two good integers are 4 and 8.
40+
41+
**Example 3:**
42+
43+
**Input:** n = 5, k = 6
44+
45+
**Output:** 2468
46+
47+
**Constraints:**
48+
49+
*`1 <= n <= 10`
50+
*`1 <= k <= 9`
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
packageg3201_3300.s3273_minimum_amount_of_damage_dealt_to_bob;
2+
3+
// #Hard #Array #Sorting #Greedy #2024_09_04_Time_76_ms_(100.00%)_Space_59.5_MB_(61.02%)
4+
5+
importjava.util.Arrays;
6+
7+
@SuppressWarnings("java:S1210")
8+
publicclassSolution {
9+
publiclongminDamage(intpw,int[]damage,int[]health) {
10+
longres =0;
11+
longsum =0;
12+
for (inte :damage) {
13+
sum +=e;
14+
}
15+
Pair[]pairs =newPair[damage.length];
16+
for (inte =0;e <damage.length;e++) {
17+
pairs[e] =newPair(damage[e], (health[e] +pw -1) /pw);
18+
}
19+
Arrays.sort(pairs);
20+
for (Pairpr :pairs) {
21+
res +=pr.val *sum;
22+
sum -=pr.key;
23+
}
24+
returnres;
25+
}
26+
27+
staticclassPairimplementsComparable<Pair> {
28+
intkey;
29+
intval;
30+
31+
Pair(intkey,intval) {
32+
this.key =key;
33+
this.val =val;
34+
}
35+
36+
@Override
37+
publicintcompareTo(Pairp) {
38+
returnval *p.key -key *p.val;
39+
}
40+
}
41+
}

0 commit comments

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