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

Commit83c6fa9

Browse files
authored
Added tasks 3527-3534
1 parentb436f7c commit83c6fa9

File tree

24 files changed

+1152
-0
lines changed

24 files changed

+1152
-0
lines changed
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
packageg3501_3600.s3527_find_the_most_common_response;
2+
3+
// #Medium #Array #String #Hash_Table #Counting
4+
// #2025_04_28_Time_94_ms_(100.00%)_Space_211.70_MB_(22.07%)
5+
6+
importjava.util.HashMap;
7+
importjava.util.List;
8+
importjava.util.Map;
9+
10+
publicclassSolution {
11+
privatebooleancompareStrings(Stringstr1,Stringstr2) {
12+
intn =str1.length();
13+
intm =str2.length();
14+
inti =0;
15+
intj =0;
16+
while (i <n &&j <m) {
17+
if (str1.charAt(i) <str2.charAt(j)) {
18+
returntrue;
19+
}elseif (str1.charAt(i) >str2.charAt(j)) {
20+
returnfalse;
21+
}
22+
i++;
23+
j++;
24+
}
25+
returnn <m;
26+
}
27+
28+
publicStringfindCommonResponse(List<List<String>>responses) {
29+
intn =responses.size();
30+
Map<String,int[]>mp =newHashMap<>();
31+
Stringans =responses.get(0).get(0);
32+
intmaxFreq =0;
33+
for (introw =0;row <n;row++) {
34+
intm =responses.get(row).size();
35+
for (intcol =0;col <m;col++) {
36+
Stringresp =responses.get(row).get(col);
37+
int[]arr =mp.getOrDefault(resp,newint[] {0, -1});
38+
if (arr[1] !=row) {
39+
arr[0]++;
40+
arr[1] =row;
41+
mp.put(resp,arr);
42+
}
43+
if (arr[0] >maxFreq
44+
|| !ans.equals(resp) &&arr[0] ==maxFreq &&compareStrings(resp,ans)) {
45+
ans =resp;
46+
maxFreq =arr[0];
47+
}
48+
}
49+
}
50+
returnans;
51+
}
52+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
3527\. Find the Most Common Response
2+
3+
Medium
4+
5+
You are given a 2D string array`responses` where each`responses[i]` is an array of strings representing survey responses from the <code>i<sup>th</sup></code> day.
6+
7+
Return the**most common** response across all days after removing**duplicate** responses within each`responses[i]`. If there is a tie, return the_lexicographically smallest_ response.
8+
9+
**Example 1:**
10+
11+
**Input:** responses =[["good","ok","good","ok"],["ok","bad","good","ok","ok"],["good"],["bad"]]
12+
13+
**Output:** "good"
14+
15+
**Explanation:**
16+
17+
* After removing duplicates within each list,`responses = [["good", "ok"], ["ok", "bad", "good"], ["good"], ["bad"]]`.
18+
*`"good"` appears 3 times,`"ok"` appears 2 times, and`"bad"` appears 2 times.
19+
* Return`"good"` because it has the highest frequency.
20+
21+
**Example 2:**
22+
23+
**Input:** responses =[["good","ok","good"],["ok","bad"],["bad","notsure"],["great","good"]]
24+
25+
**Output:** "bad"
26+
27+
**Explanation:**
28+
29+
* After removing duplicates within each list we have`responses = [["good", "ok"], ["ok", "bad"], ["bad", "notsure"], ["great", "good"]]`.
30+
*`"bad"`,`"good"`, and`"ok"` each occur 2 times.
31+
* The output is`"bad"` because it is the lexicographically smallest amongst the words with the highest frequency.
32+
33+
**Constraints:**
34+
35+
*`1 <= responses.length <= 1000`
36+
*`1 <= responses[i].length <= 1000`
37+
*`1 <= responses[i][j].length <= 10`
38+
*`responses[i][j]` consists of only lowercase English letters
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
packageg3501_3600.s3528_unit_conversion_i;
2+
3+
// #Medium #Depth_First_Search #Breadth_First_Search #Graph
4+
// #2025_04_28_Time_3_ms_(99.90%)_Space_127.84_MB_(26.65%)
5+
6+
publicclassSolution {
7+
publicint[]baseUnitConversions(int[][]conversions) {
8+
int[]arr =newint[conversions.length +1];
9+
arr[0] =1;
10+
for (int[]conversion :conversions) {
11+
longval = ((long)arr[conversion[0]] *conversion[2]) %1000000007;
12+
arr[conversion[1]] = (int)val;
13+
}
14+
returnarr;
15+
}
16+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
3528\. Unit Conversion I
2+
3+
Medium
4+
5+
There are`n` types of units indexed from`0` to`n - 1`. You are given a 2D integer array`conversions` of length`n - 1`, where <code>conversions[i] =[sourceUnit<sub>i</sub>, targetUnit<sub>i</sub>, conversionFactor<sub>i</sub>]</code>. This indicates that a single unit of type <code>sourceUnit<sub>i</sub></code> is equivalent to <code>conversionFactor<sub>i</sub></code> units of type <code>targetUnit<sub>i</sub></code>.
6+
7+
Return an array`baseUnitConversion` of length`n`, where`baseUnitConversion[i]` is the number of units of type`i` equivalent to a single unit of type 0. Since the answer may be large, return each`baseUnitConversion[i]`**modulo** <code>10<sup>9</sup> + 7</code>.
8+
9+
**Example 1:**
10+
11+
**Input:** conversions =[[0,1,2],[1,2,3]]
12+
13+
**Output:**[1,2,6]
14+
15+
**Explanation:**
16+
17+
* Convert a single unit of type 0 into 2 units of type 1 using`conversions[0]`.
18+
* Convert a single unit of type 0 into 6 units of type 2 using`conversions[0]`, then`conversions[1]`.
19+
20+
![](https://assets.leetcode.com/uploads/2025/03/12/example1.png)
21+
22+
**Example 2:**
23+
24+
**Input:** conversions =[[0,1,2],[0,2,3],[1,3,4],[1,4,5],[2,5,2],[4,6,3],[5,7,4]]
25+
26+
**Output:**[1,2,3,8,10,6,30,24]
27+
28+
**Explanation:**
29+
30+
* Convert a single unit of type 0 into 2 units of type 1 using`conversions[0]`.
31+
* Convert a single unit of type 0 into 3 units of type 2 using`conversions[1]`.
32+
* Convert a single unit of type 0 into 8 units of type 3 using`conversions[0]`, then`conversions[2]`.
33+
* Convert a single unit of type 0 into 10 units of type 4 using`conversions[0]`, then`conversions[3]`.
34+
* Convert a single unit of type 0 into 6 units of type 5 using`conversions[1]`, then`conversions[4]`.
35+
* Convert a single unit of type 0 into 30 units of type 6 using`conversions[0]`,`conversions[3]`, then`conversions[5]`.
36+
* Convert a single unit of type 0 into 24 units of type 7 using`conversions[1]`,`conversions[4]`, then`conversions[6]`.
37+
38+
**Constraints:**
39+
40+
* <code>2 <= n <= 10<sup>5</sup></code>
41+
*`conversions.length == n - 1`
42+
* <code>0 <= sourceUnit<sub>i</sub>, targetUnit<sub>i</sub> < n</code>
43+
* <code>1 <= conversionFactor<sub>i</sub> <= 10<sup>9</sup></code>
44+
* It is guaranteed that unit 0 can be converted into any other unit through a**unique** combination of conversions without using any conversions in the opposite direction.
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
packageg3501_3600.s3529_count_cells_in_overlapping_horizontal_and_vertical_substrings;
2+
3+
// #Medium #Array #String #Matrix #Hash_Function #String_Matching #Rolling_Hash
4+
// #2025_04_28_Time_33_ms_(100.00%)_Space_62.71_MB_(100.00%)
5+
6+
publicclassSolution {
7+
publicintcountCells(char[][]grid,Stringpattern) {
8+
intk =pattern.length();
9+
int[]lps =makeLps(pattern);
10+
intm =grid.length;
11+
intn =grid[0].length;
12+
int[][]horiPats =newint[m][n];
13+
int[][]vertPats =newint[m][n];
14+
inti =0;
15+
intj =0;
16+
while (i <m *n) {
17+
if (grid[i /n][i %n] ==pattern.charAt(j)) {
18+
i++;
19+
if (++j ==k) {
20+
intd =i -j;
21+
horiPats[d /n][d %n]++;
22+
if (i <m *n) {
23+
horiPats[i /n][i %n]--;
24+
}
25+
j =lps[j -1];
26+
}
27+
}elseif (j !=0) {
28+
j =lps[j -1];
29+
}else {
30+
i++;
31+
}
32+
}
33+
i =0;
34+
j =0;
35+
// now do vert pattern, use i = 0 to m*n -1 but instead index as grid[i % m][i/m]
36+
while (i <m *n) {
37+
if (grid[i %m][i /m] ==pattern.charAt(j)) {
38+
i++;
39+
if (++j ==k) {
40+
intd =i -j;
41+
vertPats[d %m][d /m]++;
42+
if (i <m *n) {
43+
vertPats[i %m][i /m]--;
44+
}
45+
j =lps[j -1];
46+
}
47+
}elseif (j !=0) {
48+
j =lps[j -1];
49+
}else {
50+
i++;
51+
}
52+
}
53+
for (i =1;i <m *n;i++) {
54+
vertPats[i %m][i /m] +=vertPats[(i -1) %m][(i -1) /m];
55+
horiPats[i /n][i %n] +=horiPats[(i -1) /n][(i -1) %n];
56+
}
57+
intres =0;
58+
for (i =0;i <m;i++) {
59+
for (j =0;j <n;j++) {
60+
if (horiPats[i][j] >0 &&vertPats[i][j] >0) {
61+
res++;
62+
}
63+
}
64+
}
65+
returnres;
66+
}
67+
68+
privateint[]makeLps(Stringpattern) {
69+
intn =pattern.length();
70+
int[]lps =newint[n];
71+
intlen =0;
72+
inti =1;
73+
lps[0] =0;
74+
while (i <n) {
75+
if (pattern.charAt(i) ==pattern.charAt(len)) {
76+
lps[i++] = ++len;
77+
}elseif (len !=0) {
78+
len =lps[len -1];
79+
}else {
80+
lps[i++] =0;
81+
}
82+
}
83+
returnlps;
84+
}
85+
}
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
3529\. Count Cells in Overlapping Horizontal and Vertical Substrings
2+
3+
Medium
4+
5+
You are given an`m x n` matrix`grid` consisting of characters and a string`pattern`.
6+
7+
A**horizontal substring** is a contiguous sequence of characters read from left to right. If the end of a row is reached before the substring is complete, it wraps to the first column of the next row and continues as needed. You do**not** wrap from the bottom row back to the top.
8+
9+
A**vertical substring** is a contiguous sequence of characters read from top to bottom. If the bottom of a column is reached before the substring is complete, it wraps to the first row of the next column and continues as needed. You do**not** wrap from the last column back to the first.
10+
11+
Count the number of cells in the matrix that satisfy the following condition:
12+
13+
* The cell must be part of**at least** one horizontal substring and**at least** one vertical substring, where**both** substrings are equal to the given`pattern`.
14+
15+
Return the count of these cells.
16+
17+
**Example 1:**
18+
19+
![](https://assets.leetcode.com/uploads/2025/03/03/gridtwosubstringsdrawio.png)
20+
21+
**Input:** grid =[["a","a","c","c"],["b","b","b","c"],["a","a","b","a"],["c","a","a","c"],["a","a","c","c"]], pattern = "abaca"
22+
23+
**Output:** 1
24+
25+
**Explanation:**
26+
27+
The pattern`"abaca"` appears once as a horizontal substring (colored blue) and once as a vertical substring (colored red), intersecting at one cell (colored purple).
28+
29+
**Example 2:**
30+
31+
![](https://assets.leetcode.com/uploads/2025/03/03/gridexample2fixeddrawio.png)
32+
33+
**Input:** grid =[["c","a","a","a"],["a","a","b","a"],["b","b","a","a"],["a","a","b","a"]], pattern = "aba"
34+
35+
**Output:** 4
36+
37+
**Explanation:**
38+
39+
The cells colored above are all part of at least one horizontal and one vertical substring matching the pattern`"aba"`.
40+
41+
**Example 3:**
42+
43+
**Input:** grid =[["a"]], pattern = "a"
44+
45+
**Output:** 1
46+
47+
**Constraints:**
48+
49+
*`m == grid.length`
50+
*`n == grid[i].length`
51+
*`1 <= m, n <= 1000`
52+
* <code>1 <= m * n <= 10<sup>5</sup></code>
53+
*`1 <= pattern.length <= m * n`
54+
*`grid` and`pattern` consist of only lowercase English letters.
Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
packageg3501_3600.s3530_maximum_profit_from_valid_topological_order_in_dag;
2+
3+
// #Hard #Array #Dynamic_Programming #Bit_Manipulation #Graph #Bitmask #Topological_Sort
4+
// #2025_04_28_Time_1927_ms_(100.00%)_Space_66.86_MB_(100.00%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.List;
9+
10+
publicclassSolution {
11+
privateinthelper(
12+
intmask,
13+
intpos,
14+
int[]inDegree,
15+
List<List<Integer>>adj,
16+
int[]score,
17+
int[]dp,
18+
intn) {
19+
if (mask == (1 <<n) -1) {
20+
return0;
21+
}
22+
if (dp[mask] != -1) {
23+
returndp[mask];
24+
}
25+
intres =0;
26+
for (inti =0;i <n;i++) {
27+
if ((mask & (1 <<i)) ==0 &&inDegree[i] ==0) {
28+
for (intng :adj.get(i)) {
29+
inDegree[ng]--;
30+
}
31+
intval =
32+
pos *score[i]
33+
+helper(mask | (1 <<i),pos +1,inDegree,adj,score,dp,n);
34+
res =Math.max(res,val);
35+
for (intng :adj.get(i)) {
36+
inDegree[ng]++;
37+
}
38+
}
39+
}
40+
dp[mask] =res;
41+
returnres;
42+
}
43+
44+
publicintmaxProfit(intn,int[][]edges,int[]score) {
45+
List<List<Integer>>adj =newArrayList<>();
46+
for (inti =0;i <n;i++) {
47+
adj.add(newArrayList<>());
48+
}
49+
int[]inDegree =newint[n];
50+
for (int[]e :edges) {
51+
adj.get(e[0]).add(e[1]);
52+
inDegree[e[1]]++;
53+
}
54+
int[]dp =newint[1 <<n];
55+
Arrays.fill(dp, -1);
56+
returnhelper(0,1,inDegree,adj,score,dp,n);
57+
}
58+
}

0 commit comments

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