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

Commitb2986d0

Browse files
authored
Added tasks 2484, 2485, 2486, 2487, 2488
1 parent5708432 commitb2986d0

File tree

16 files changed

+471
-0
lines changed

16 files changed

+471
-0
lines changed

‎README.md‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1848,6 +1848,11 @@ implementation 'com.github.javadev:leetcode-in-java:1.17'
18481848

18491849
| # | Title | Difficulty | Tag | Time, ms | Time, %
18501850
|------|----------------|-------------|-------------|----------|---------
1851+
| 2488 |[Count Subarrays With Median K](src/main/java/g2401_2500/s2488_count_subarrays_with_median_k/Solution.java)| Hard | Array, Hash_Table, Prefix_Sum | 24 | 72.25
1852+
| 2487 |[Remove Nodes From Linked List](src/main/java/g2401_2500/s2487_remove_nodes_from_linked_list/Solution.java)| Medium | Stack, Linked_List, Monotonic_Stack, Recursion | 5 | 99.79
1853+
| 2486 |[Append Characters to String to Make Subsequence](src/main/java/g2401_2500/s2486_append_characters_to_string_to_make_subsequence/Solution.java)| Medium | String, Greedy, Two_Pointers | 2 | 99.89
1854+
| 2485 |[Find the Pivot Integer](src/main/java/g2401_2500/s2485_find_the_pivot_integer/Solution.java)| Easy | Math, Prefix_Sum | 1 | 95.67
1855+
| 2484 |[Count Palindromic Subsequences](src/main/java/g2401_2500/s2484_count_palindromic_subsequences/Solution.java)| Hard | String, Dynamic_Programming | 93 | 76.16
18511856
| 2483 |[Minimum Penalty for a Shop](src/main/java/g2401_2500/s2483_minimum_penalty_for_a_shop/Solution.java)| Medium | String, Prefix_Sum | 17 | 69.62
18521857
| 2482 |[Difference Between Ones and Zeros in Row and Column](src/main/java/g2401_2500/s2482_difference_between_ones_and_zeros_in_row_and_column/Solution.java)| Medium | Array, Matrix, Simulation | 9 | 94.05
18531858
| 2481 |[Minimum Cuts to Divide a Circle](src/main/java/g2401_2500/s2481_minimum_cuts_to_divide_a_circle/Solution.java)| Easy | Math, Geometry | 0 | 100.00
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg2401_2500.s2484_count_palindromic_subsequences;
2+
3+
// #Hard #String #Dynamic_Programming #2023_01_26_Time_93_ms_(76.16%)_Space_40.2_MB_(99.74%)
4+
5+
publicclassSolution {
6+
publicintcountPalindromes(Strings) {
7+
intn =s.length();
8+
longans =0;
9+
intmod = (int)1e9 +7;
10+
int[]count =newint[10];
11+
for (inti =0;i <n;i++) {
12+
longm =0;
13+
for (intj =n -1;j >i;j--) {
14+
if (s.charAt(i) ==s.charAt(j)) {
15+
ans += (m * (j -i -1));
16+
ans =ans %mod;
17+
}
18+
m +=count[s.charAt(j) -'0'];
19+
}
20+
count[s.charAt(i) -'0']++;
21+
}
22+
return (int)ans;
23+
}
24+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
2484\. Count Palindromic Subsequences
2+
3+
Hard
4+
5+
Given a string of digits`s`, return_the number of**palindromic subsequences** of_`s`_having length_`5`. Since the answer may be very large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
6+
7+
**Note:**
8+
9+
* A string is**palindromic** if it reads the same forward and backward.
10+
* A**subsequence** is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
11+
12+
**Example 1:**
13+
14+
**Input:** s = "103301"
15+
16+
**Output:** 2
17+
18+
**Explanation:** There are 6 possible subsequences of length 5: "10330","10331","10301","10301","13301","03301". Two of them (both equal to "10301") are palindromic.
19+
20+
**Example 2:**
21+
22+
**Input:** s = "0000000"
23+
24+
**Output:** 21
25+
26+
**Explanation:** All 21 subsequences are "00000", which is palindromic.
27+
28+
**Example 3:**
29+
30+
**Input:** s = "9999900000"
31+
32+
**Output:** 2
33+
34+
**Explanation:** The only two palindromic subsequences are "99999" and "00000".
35+
36+
**Constraints:**
37+
38+
* <code>1 <= s.length <= 10<sup>4</sup></code>
39+
*`s` consists of digits.
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg2401_2500.s2485_find_the_pivot_integer;
2+
3+
// #Easy #Math #Prefix_Sum #2023_01_26_Time_1_ms_(95.67%)_Space_39.2_MB_(91.00%)
4+
5+
publicclassSolution {
6+
publicintpivotInteger(intn) {
7+
if (n ==0 ||n ==1) {
8+
returnn;
9+
}
10+
intsum =0;
11+
for (inti =1;i <=n;i++) {
12+
sum +=i;
13+
}
14+
intad =0;
15+
for (inti =1;i <=n;i++) {
16+
ad +=i -1;
17+
sum -=i;
18+
if (sum ==ad) {
19+
returni;
20+
}
21+
}
22+
return -1;
23+
}
24+
}
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
2485\. Find the Pivot Integer
2+
3+
Easy
4+
5+
Given a positive integer`n`, find the**pivot integer**`x` such that:
6+
7+
* The sum of all elements between`1` and`x` inclusively equals the sum of all elements between`x` and`n` inclusively.
8+
9+
Return_the pivot integer_`x`. If no such integer exists, return`-1`. It is guaranteed that there will be at most one pivot index for the given input.
10+
11+
**Example 1:**
12+
13+
**Input:** n = 8
14+
15+
**Output:** 6
16+
17+
**Explanation:** 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.
18+
19+
**Example 2:**
20+
21+
**Input:** n = 1
22+
23+
**Output:** 1
24+
25+
**Explanation:** 1 is the pivot integer since: 1 = 1.
26+
27+
**Example 3:**
28+
29+
**Input:** n = 4
30+
31+
**Output:** -1
32+
33+
**Explanation:** It can be proved that no such integer exist.
34+
35+
**Constraints:**
36+
37+
*`1 <= n <= 1000`
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2401_2500.s2486_append_characters_to_string_to_make_subsequence;
2+
3+
// #Medium #String #Greedy #Two_Pointers #2023_01_26_Time_2_ms_(99.89%)_Space_49.5_MB_(39.30%)
4+
5+
publicclassSolution {
6+
publicintappendCharacters(Strings,Stringt) {
7+
intlengthOfT =t.length();
8+
intindexOfT =0;
9+
intindexOfS =0;
10+
intposition;
11+
if (s.contains(t)) {
12+
return0;
13+
}
14+
while (indexOfT <lengthOfT) {
15+
position =s.indexOf(t.charAt(indexOfT),indexOfS);
16+
if (position <0) {
17+
returnlengthOfT -indexOfT;
18+
}
19+
indexOfS =position;
20+
indexOfT++;
21+
indexOfS++;
22+
}
23+
returnlengthOfT - (indexOfT);
24+
}
25+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2486\. Append Characters to String to Make Subsequence
2+
3+
Medium
4+
5+
You are given two strings`s` and`t` consisting of only lowercase English letters.
6+
7+
Return_the minimum number of characters that need to be appended to the end of_`s`_so that_`t`_becomes a**subsequence** of_`s`.
8+
9+
A**subsequence** is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
10+
11+
**Example 1:**
12+
13+
**Input:** s = "coaching", t = "coding"
14+
15+
**Output:** 4
16+
17+
**Explanation:** Append the characters "ding" to the end of s so that s = "coachingding". Now, t is a subsequence of s ("<ins>**co**</ins>aching<ins>**ding**</ins>"). It can be shown that appending any 3 characters to the end of s will never make t a subsequence.
18+
19+
**Example 2:**
20+
21+
**Input:** s = "abcde", t = "a"
22+
23+
**Output:** 0
24+
25+
**Explanation:** t is already a subsequence of s ("<ins>**a**</ins>bcde").
26+
27+
**Example 3:**
28+
29+
**Input:** s = "z", t = "abcde"
30+
31+
**Output:** 5
32+
33+
**Explanation:** Append the characters "abcde" to the end of s so that s = "zabcde". Now, t is a subsequence of s ("z<ins>**abcde**</ins>"). It can be shown that appending any 4 characters to the end of s will never make t a subsequence.
34+
35+
**Constraints:**
36+
37+
* <code>1 <= s.length, t.length <= 10<sup>5</sup></code>
38+
*`s` and`t` consist only of lowercase English letters.
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
packageg2401_2500.s2487_remove_nodes_from_linked_list;
2+
3+
// #Medium #Stack #Linked_List #Monotonic_Stack #Recursion
4+
// #2023_01_26_Time_5_ms_(99.79%)_Space_67_MB_(74.44%)
5+
6+
importcom_github_leetcode.ListNode;
7+
8+
publicclassSolution {
9+
publicListNoderemoveNodes(ListNodehead) {
10+
head =reverse(head);
11+
if (head ==null) {
12+
returnnull;
13+
}
14+
intmax =head.val;
15+
ListNodetemp =head;
16+
ListNodetemp1 =head.next;
17+
while (temp1 !=null) {
18+
if (temp1.val >=max) {
19+
max =temp1.val;
20+
temp.next =temp1;
21+
temp =temp.next;
22+
}
23+
temp1 =temp1.next;
24+
}
25+
temp.next =null;
26+
returnreverse(head);
27+
}
28+
29+
privateListNodereverse(ListNodehead) {
30+
if (head ==null ||head.next ==null) {
31+
returnhead;
32+
}
33+
ListNodeprev =null;
34+
ListNodecurr =head;
35+
ListNodenext;
36+
while (curr !=null) {
37+
next =curr.next;
38+
curr.next =prev;
39+
prev =curr;
40+
curr =next;
41+
}
42+
returnprev;
43+
}
44+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2487\. Remove Nodes From Linked List
2+
3+
Medium
4+
5+
You are given the`head` of a linked list.
6+
7+
Remove every node which has a node with a**strictly greater** value anywhere to the right side of it.
8+
9+
Return_the_`head`_of the modified linked list._
10+
11+
**Example 1:**
12+
13+
![](https://assets.leetcode.com/uploads/2022/10/02/drawio.png)
14+
15+
**Input:** head =[5,2,13,3,8]
16+
17+
**Output:**[13,8]
18+
19+
**Explanation:** The nodes that should be removed are 5, 2 and 3.
20+
21+
- Node 13 is to the right of node 5.
22+
- Node 13 is to the right of node 2.
23+
- Node 8 is to the right of node 3.
24+
25+
**Example 2:**
26+
27+
**Input:** head =[1,1,1,1]
28+
29+
**Output:**[1,1,1,1]
30+
31+
**Explanation:** Every node has value 1, so no nodes are removed.
32+
33+
**Constraints:**
34+
35+
* The number of the nodes in the given list is in the range <code>[1, 10<sup>5</sup>]</code>.
36+
* <code>1 <= Node.val <= 10<sup>5</sup></code>
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
packageg2401_2500.s2488_count_subarrays_with_median_k;
2+
3+
// #Hard #Array #Hash_Table #Prefix_Sum #2023_01_26_Time_24_ms_(72.25%)_Space_51_MB_(99.24%)
4+
5+
importjava.util.HashMap;
6+
importjava.util.Map;
7+
8+
publicclassSolution {
9+
publicintcountSubarrays(int[]nums,intk) {
10+
intidx;
11+
intn =nums.length;
12+
intans =0;
13+
for (idx =0;idx <n;idx++) {
14+
if (nums[idx] ==k) {
15+
break;
16+
}
17+
}
18+
int[][]arr =newint[n -idx][2];
19+
intj =1;
20+
for (inti =idx +1;i <n;i++) {
21+
if (nums[i] <k) {
22+
arr[j][0] =arr[j -1][0] +1;
23+
arr[j][1] =arr[j -1][1];
24+
}else {
25+
arr[j][1] =arr[j -1][1] +1;
26+
arr[j][0] =arr[j -1][0];
27+
}
28+
j++;
29+
}
30+
Map<Integer,Integer>map =newHashMap<>();
31+
for (int[]ints :arr) {
32+
intd2 =ints[1] -ints[0];
33+
map.put(d2,map.getOrDefault(d2,0) +1);
34+
}
35+
ints1 =0;
36+
intg1 =0;
37+
for (inti =idx;i >=0;i--) {
38+
if (nums[i] <k) {
39+
s1++;
40+
}elseif (nums[i] >k) {
41+
g1++;
42+
}
43+
intd1 =g1 -s1;
44+
intcur =map.getOrDefault(-d1,0) +map.getOrDefault(1 -d1,0);
45+
ans +=cur;
46+
}
47+
returnans;
48+
}
49+
}

0 commit comments

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