Skip to content

Commit 98c2b76

Browse files
morpheus-ossmorpheus-oss
committed
Updated with more problems and experimented features
1 parent 815c637 commit 98c2b76

13 files changed

Lines changed: 574 additions & 82 deletions

File tree

‎.gitignore‎

Lines changed: 9 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,14 @@
11
.idea/codeStyles/**
22
.idea/**
33

4-
Leetcode/target/**
54

5+
.gradle/**
6+
buildSrc/.gradle/**
7+
buildSrc/build/**
8+
9+
10+
Leetcode/target/**
611
/Leetcode/target/classes/**
7-
/Leetcode/target/test-classes/**
8-
Leetcode/target/classes/dev/leetcode/ArrayProblems.class
12+
13+
/java-features/target
14+
/Leetcode/target

‎Leetcode/pom.xml‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,4 +17,84 @@
1717
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
1818
</properties>
1919

20+
21+
<build>
22+
<plugins>
23+
<plugin>
24+
<groupId>org.apache.maven.plugins</groupId>
25+
<artifactId>maven-compiler-plugin</artifactId>
26+
<version>3.10.1</version>
27+
<configuration>
28+
<source>${maven.compiler.source}</source>
29+
<target>${maven.compiler.target}</target>
30+
<encoding>${project.build.sourceEncoding}</encoding>
31+
</configuration>
32+
</plugin>
33+
34+
<plugin>
35+
<groupId>org.jacoco</groupId>
36+
<artifactId>jacoco-maven-plugin</artifactId>
37+
<version>0.8.7</version>
38+
<executions>
39+
<execution>
40+
<id>default-prepare-agent</id>
41+
<goals>
42+
<goal>prepare-agent</goal>
43+
</goals>
44+
<configuration>
45+
<destFile>${project.build.directory}/coverage-reports/jacoco.exec</destFile>
46+
<propertyName>surefireArgLine</propertyName>
47+
</configuration>
48+
</execution>
49+
<execution>
50+
<id>default-report</id>
51+
<phase>test</phase>
52+
<goals>
53+
<goal>report</goal>
54+
</goals>
55+
<configuration>
56+
<dataFile>${project.build.directory}/coverage-reports/jacoco.exec</dataFile>
57+
<outputDirectory>${project.reporting.outputDirectory}/jacoco</outputDirectory>
58+
</configuration>
59+
</execution>
60+
<execution>
61+
<id>default-check</id>
62+
<goals>
63+
<goal>check</goal>
64+
</goals>
65+
<configuration>
66+
<rules>
67+
<rule>
68+
<element>BUNDLE</element>
69+
<limits>
70+
<limit>
71+
<counter>COMPLEXITY</counter>
72+
<value>COVEREDRATIO</value>
73+
<minimum>0.70</minimum>
74+
</limit>
75+
</limits>
76+
</rule>
77+
</rules>
78+
</configuration>
79+
</execution>
80+
</executions>
81+
</plugin>
82+
83+
<plugin>
84+
<groupId>org.apache.maven.plugins</groupId>
85+
<artifactId>maven-surefire-plugin</artifactId>
86+
<version>2.22.2</version>
87+
<configuration>
88+
<testFailureIgnore>true</testFailureIgnore>
89+
<forkCount>2</forkCount>
90+
<reuseForks>true</reuseForks>
91+
<!--suppress UnresolvedMavenProperty -->
92+
<argLine>${surefireArgLine}</argLine>
93+
</configuration>
94+
</plugin>
95+
96+
</plugins>
97+
</build>
98+
99+
20100
</project>

‎Leetcode/src/main/java/dev/leetcode/DailyChallenge.java‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package dev.leetcode;
2+
3+
import java.util.Arrays;
4+
import java.util.Collections;
5+
import java.util.Comparator;
6+
import java.util.PriorityQueue;
7+
8+
public class DailyChallenge {
9+
/**
10+
* 3075. Maximize Happiness of Selected Children
11+
* <pre>
12+
* You are given an array happiness of length n, and a positive integer k.
13+
*
14+
* There are n children standing in a queue, where the ith child has happiness value
15+
* happiness[i]. You want to select k children from these n children in k turns.
16+
*
17+
* In each turn, when you select a child, the happiness value of all the children that have
18+
* not been selected till now decreases by 1. Note that the happiness value cannot become
19+
* negative and gets decremented only if it is positive.
20+
*
21+
* Return the maximum sum of the happiness values of the selected children you can achieve
22+
* by selecting k children.
23+
*
24+
* Example 1:
25+
* Input: happiness = [1,2,3], k = 2
26+
* Output: 4
27+
* Explanation: We can pick 2 children in the following way:
28+
* - Pick the child with the happiness value == 3. The happiness value of the remaining
29+
* children becomes [0,1].
30+
* - Pick the child with the happiness value == 1. The happiness value of the remaining
31+
* child becomes [0]. Note that the happiness value cannot become less than 0.
32+
* The sum of the happiness values of the selected children is 3 + 1 = 4.
33+
*
34+
* Example 2:
35+
* Input: happiness = [1,1,1,1], k = 2
36+
* Output: 1
37+
* Explanation: We can pick 2 children in the following way:
38+
* - Pick any child with the happiness value == 1. The happiness value of the remaining
39+
* children becomes [0,0,0].
40+
* - Pick the child with the happiness value == 0. The happiness value of the remaining
41+
* child becomes [0,0].
42+
* The sum of the happiness values of the selected children is 1 + 0 = 1.
43+
*
44+
* Example 3:
45+
* Input: happiness = [2,3,4,5], k = 1
46+
* Output: 5
47+
* Explanation: We can pick 1 child in the following way:
48+
* - Pick the child with the happiness value == 5. The happiness value of the remaining
49+
* children becomes [1,2,3].
50+
* The sum of the happiness values of the selected children is 5.
51+
* </pre>
52+
*
53+
* Constraints:
54+
* <ul>
55+
* <li>1 <= n == happiness.length <= 2 * 105 </li>
56+
* <li>1 <= happiness[i] <= 108 </li>
57+
* <li>1 <= k <= n </li>
58+
* </ul>
59+
*
60+
* @param happiness
61+
* @param k
62+
* @return
63+
*/
64+
public long maximumHappinessSum(int[] happiness, int k) {
65+
66+
Arrays.sort(happiness);
67+
68+
int decrement = 0;
69+
int n = happiness.length;
70+
long maxHappiness=0;
71+
for(int i=n-1;i>=n-k;i--){
72+
maxHappiness += Math.max(0, happiness[i]-decrement);
73+
decrement++;
74+
}
75+
return maxHappiness;
76+
77+
}
78+
79+
}

‎Leetcode/src/main/java/dev/leetcode/StringProblems.java‎

Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1635,4 +1635,126 @@ public boolean repeatedSubstringPattern(String s) {
16351635
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
16361636
return charCountMap.values().stream().anyMatch(val -> val <= 1);
16371637
}
1638+
1639+
/**
1640+
* 5. Longest Palindromic Substring
1641+
*
1642+
* <pre>
1643+
* Given a string s, return the longest palindromic substring in s.
1644+
*
1645+
* Example 1:
1646+
* Input: s = "babad"
1647+
* Output: "bab"
1648+
* Explanation: "aba" is also a valid answer.
1649+
*
1650+
* Example 2:
1651+
* Input: s = "cbbd"
1652+
* Output: "bb"
1653+
* </pre>
1654+
*
1655+
* Constraints:
1656+
*
1657+
* <ul>
1658+
* <li>1 <= s.length <= 1000
1659+
* <li>s consist of only digits and English letters.
1660+
* </ul>
1661+
*
1662+
* <p>
1663+
* @see <a
1664+
* href="https://leetcode.com/problems/longest-palindromic-substring/
1665+
* solutions/4212564/beats-96-49-5-different-approaches-brute-force-eac-dp-ma-recursion/">
1666+
* Explained Manacher's Algorithm </a>
1667+
* @see <a href="https://www.youtube.com/watch?v=IvakBbsAhUU">Manacher's Algorithm (Video)</a>
1668+
* </p>
1669+
* @param str
1670+
* @return
1671+
*/
1672+
public String longestPalindrome(String str) {
1673+
if (str.length() <= 1) {
1674+
return str;
1675+
}
1676+
1677+
int maxLen = 1;
1678+
String maxStr = str.substring(0, 1);
1679+
str = "#" + str.replaceAll("", "#") + "#";
1680+
System.out.println("Reformed input:" + str);
1681+
int[] pal = new int[str.length()];
1682+
int center = 0;
1683+
int right = 0;
1684+
1685+
for (int i = 0; i < str.length(); i++) {
1686+
if (i < right) {
1687+
pal[i] = Math.min(right - i, pal[2 * center - i]);
1688+
}
1689+
1690+
while (i - pal[i] - 1 >= 0
1691+
&& i + pal[i] + 1 < str.length()
1692+
&& str.charAt(i - pal[i] - 1) == str.charAt(i + pal[i] + 1)) {
1693+
pal[i]++;
1694+
}
1695+
1696+
if (i + pal[i] > right) {
1697+
center = i;
1698+
right = i + pal[i];
1699+
}
1700+
1701+
if (pal[i] > maxLen) {
1702+
maxLen = pal[i];
1703+
maxStr = str.substring(i - pal[i], i + pal[i] + 1).replaceAll("#", "");
1704+
}
1705+
}
1706+
1707+
return maxStr;
1708+
}
1709+
1710+
/**
1711+
* 1668. Maximum Repeating Substring
1712+
* <pre>
1713+
* For a string sequence, a string word is k-repeating if word concatenated k times is a
1714+
* substring of sequence. The word's maximum k-repeating value is the highest value k where
1715+
* word is k-repeating in sequence. If word is not a substring of sequence, word's maximum
1716+
* k-repeating value is 0.
1717+
*
1718+
* Given strings sequence and word, return the maximum k-repeating value of word in sequence.
1719+
*
1720+
* Example 1:
1721+
* Input: sequence = "ababc", word = "ab"
1722+
* Output: 2
1723+
* Explanation: "abab" is a substring in "ababc".
1724+
*
1725+
* Example 2:
1726+
* Input: sequence = "ababc", word = "ba"
1727+
* Output: 1
1728+
* Explanation: "ba" is a substring in "ababc". "baba" is not a substring in "ababc".
1729+
*
1730+
* Example 3:
1731+
* Input: sequence = "ababc", word = "ac"
1732+
* Output: 0
1733+
* Explanation: "ac" is not a substring in "ababc".
1734+
* </pre>
1735+
*
1736+
* Constraints:
1737+
* <ul>
1738+
* <li>1 <= sequence.length <= 100 </li>
1739+
* <li>1 <= word.length <= 100 </li>
1740+
* <li>sequence and word contains only lowercase English letters. </li>
1741+
* </ul>
1742+
*
1743+
* @param sequence
1744+
* @param word
1745+
* @return
1746+
*/
1747+
public int maxRepeating(String sequence, String word) {
1748+
int count = 0;
1749+
if (!sequence.contains(word)) return count;
1750+
if (sequence.equals(word)) return ++count;
1751+
1752+
while(sequence.contains(word)) {
1753+
count++;
1754+
int idx = sequence.indexOf(word);
1755+
sequence = sequence.substring( idx + (word.length()- 1));
1756+
}
1757+
return count;
1758+
}
1759+
16381760
}

‎Leetcode/src/test/java/dev/leetcode/DailyChallengeTest.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package dev.leetcode;
2+
3+
import org.javatuples.Triplet;
4+
import org.junit.jupiter.api.DisplayName;
5+
import org.junit.jupiter.api.Test;
6+
7+
import static org.junit.jupiter.api.Assertions.*;
8+
9+
import java.util.List;
10+
11+
public class DailyChallengeTest {
12+
DailyChallenge challenge = new DailyChallenge();
13+
14+
@Test
15+
@DisplayName("3075. Maximize Happiness of Selected Children")
16+
public void testMaximumHappinessSum() {
17+
List<Triplet<Long, List<Integer>, Integer>> tests =
18+
List.of(
19+
Triplet.with(4L, List.of(1, 2, 3), 2),
20+
Triplet.with(
21+
2517853814L,
22+
List.of(
23+
2135218, 73431904, 92495076, 77528042, 82824634, 3036629, 28375907, 65220365,
24+
40948869, 58914871, 57169530, 89783499, 19582915, 19676695, 11932465, 21770144,
25+
49740276, 22303751, 80746555, 97391584, 95775653, 43396943, 47271136, 43935930,
26+
59643137, 64183008, 8892641, 39587569, 85086654, 5663585, 82925096, 24868817,
27+
95900395, 48155864, 74447380, 7618448, 63299623, 91141186, 33347112, 81951555,
28+
52867615, 92184410, 7024265, 85525916, 29846922, 59532692, 47267934, 6514603,
29+
1137830, 97807470),
30+
41),
31+
Triplet.with(1L, List.of(1, 1, 1, 1), 2),
32+
Triplet.with(5L, List.of(2, 3, 4, 5), 1));
33+
34+
tests.forEach(
35+
test ->
36+
assertEquals(
37+
test.getValue0(),
38+
challenge.maximumHappinessSum(
39+
test.getValue1().stream().mapToInt(val -> val).toArray(), test.getValue2())));
40+
}
41+
}

‎Leetcode/src/test/java/dev/leetcode/Interview150Test.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,7 @@ public void testMerge() {
2929
)
3030
);
3131

32-
tests.forEach(test -> assertEquals(
32+
tests.forEach(test -> assertArrayEquals(
3333
test.getValue0().stream()
3434
.mapToInt(val -> val)
3535
.toArray(),

‎Leetcode/src/test/java/dev/leetcode/StringProblemsTest.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -277,4 +277,22 @@ public void testTruncateSentence() {
277277
assertEquals(
278278
test.getValue0(), problems.truncateSentence(test.getValue1(), test.getValue2())));
279279
}
280+
281+
@Test
282+
@DisplayName("1668. Maximum Repeating Substring")
283+
public void testMaxRepeating() {
284+
List<Triplet<Integer, String, String>> tests = List.of(
285+
Triplet.with(2, "ababc", "ab"),
286+
Triplet.with(1, "ababc", "ba"),
287+
Triplet.with(0, "ababc", "ac"),
288+
Triplet.with(1, "a", "a"),
289+
Triplet.with(7, "aaabaaaabaaabaaaabaaaabaaaabaaaaba", "aaaba")
290+
);
291+
292+
tests.forEach(
293+
test ->
294+
assertEquals(
295+
test.getValue0(), problems.maxRepeating(test.getValue1(), test.getValue2())));
296+
}
297+
280298
}

0 commit comments

Comments
 (0)