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

Commitdfad59e

Browse files
authored
Added tasks 2565-2569
1 parentccd3bc4 commitdfad59e

File tree

15 files changed

+477
-0
lines changed

15 files changed

+477
-0
lines changed
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
packageg2501_2600.s2565_subsequence_with_the_minimum_score;
2+
3+
// #Hard #String #Binary_Search #Two_Pointers #2023_08_21_Time_7_ms_(92.54%)_Space_44.4_MB_(44.78%)
4+
5+
publicclassSolution {
6+
publicintminimumScore(Strings,Stringt) {
7+
intm =s.length();
8+
intn =t.length();
9+
int[]left =newint[m];
10+
intj =0;
11+
for (inti =0;i <m;i++) {
12+
if (j <n &&s.charAt(i) ==t.charAt(j)) {
13+
++j;
14+
}
15+
left[i] =j;
16+
}
17+
int[]right =newint[m];
18+
j =n -1;
19+
for (inti =m -1;i >=0;i--) {
20+
if (j >=0 &&s.charAt(i) ==t.charAt(j)) {
21+
--j;
22+
}
23+
right[i] =j;
24+
}
25+
intmin =Math.min(n -left[m -1],right[0] +1);
26+
for (inti =0;i +1 <m;i++) {
27+
min =Math.min(min,Math.max(0,right[i +1] -left[i] +1));
28+
}
29+
returnmin;
30+
}
31+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
2565\. Subsequence With the Minimum Score
2+
3+
Hard
4+
5+
You are given two strings`s` and`t`.
6+
7+
You are allowed to remove any number of characters from the string`t`.
8+
9+
The score of the string is`0` if no characters are removed from the string`t`, otherwise:
10+
11+
* Let`left` be the minimum index among all removed characters.
12+
* Let`right` be the maximum index among all removed characters.
13+
14+
Then the score of the string is`right - left + 1`.
15+
16+
Return_the minimum possible score to make_`t`_a subsequence of_`s`_._
17+
18+
A**subsequence** of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e.,`"ace"` is a subsequence of <code>"<ins>a</ins>b<ins>c</ins>d<ins>e</ins>"</code> while`"aec"` is not).
19+
20+
**Example 1:**
21+
22+
**Input:** s = "abacaba", t = "bzaa"
23+
24+
**Output:** 1
25+
26+
**Explanation:** In this example, we remove the character "z" at index 1 (0-indexed). The string t becomes "baa" which is a subsequence of the string "abacaba" and the score is 1 - 1 + 1 = 1. It can be proven that 1 is the minimum score that we can achieve.
27+
28+
**Example 2:**
29+
30+
**Input:** s = "cde", t = "xyz"
31+
32+
**Output:** 3
33+
34+
**Explanation:** In this example, we remove characters "x", "y" and "z" at indices 0, 1, and 2 (0-indexed). The string t becomes "" which is a subsequence of the string "cde" and the score is 2 - 0 + 1 = 3. It can be proven that 3 is the minimum score that we can achieve.
35+
36+
**Constraints:**
37+
38+
* <code>1 <= s.length, t.length <= 10<sup>5</sup></code>
39+
*`s` and`t` consist of only lowercase English letters.
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg2501_2600.s2566_maximum_difference_by_remapping_a_digit;
2+
3+
// #Easy #Math #Greedy #2023_08_21_Time_1_ms_(98.06%)_Space_39.2_MB_(82.52%)
4+
5+
publicclassSolution {
6+
publicintminMaxDifference(intnum) {
7+
inti;
8+
charc ='x';
9+
Strings =String.valueOf(num);
10+
for (i =0;i <s.length();i++) {
11+
if (s.charAt(i) !='9') {
12+
c =s.charAt(i);
13+
break;
14+
}
15+
}
16+
charx =s.charAt(0);
17+
s =s.replace(c,'9');
18+
Strings1 =String.valueOf(num);
19+
s1 =s1.replace(x,'0');
20+
intn1 =Integer.parseInt(s);
21+
intn2 =Integer.parseInt(s1);
22+
returnn1 -n2;
23+
}
24+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
2566\. Maximum Difference by Remapping a Digit
2+
3+
Easy
4+
5+
You are given an integer`num`. You know that Danny Mittal will sneakily**remap** one of the`10` possible digits (`0` to`9`) to another digit.
6+
7+
Return_the difference between the maximum and minimum__ values Danny can make by remapping**exactly****one** digit__in_`num`.
8+
9+
**Notes:**
10+
11+
* When Danny remaps a digit d1 to another digit d2, Danny replaces all occurrences of`d1` in`num` with`d2`.
12+
* Danny can remap a digit to itself, in which case`num` does not change.
13+
* Danny can remap different digits for obtaining minimum and maximum values respectively.
14+
* The resulting number after remapping can contain leading zeroes.
15+
* We mentioned "Danny Mittal" to congratulate him on being in the top 10 in Weekly Contest 326.
16+
17+
**Example 1:**
18+
19+
**Input:** num = 11891
20+
21+
**Output:** 99009
22+
23+
**Explanation:**
24+
25+
To achieve the maximum value, Danny can remap the digit 1 to the digit 9 to yield 99899.
26+
27+
To achieve the minimum value, Danny can remap the digit 1 to the digit 0, yielding 890. The difference between these two numbers is 99009.
28+
29+
**Example 2:**
30+
31+
**Input:** num = 90
32+
33+
**Output:** 99
34+
35+
**Explanation:**
36+
37+
The maximum value that can be returned by the function is 99 (if 0 is replaced by 9) and the minimum value that can be returned by the function is 0 (if 9 is replaced by 0).
38+
39+
Thus, we return 99.
40+
41+
**Constraints:**
42+
43+
* <code>1 <= num <= 10<sup>8</sup></code>
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
packageg2501_2600.s2567_minimum_score_by_changing_two_elements;
2+
3+
// #Medium #Array #Sorting #Greedy #2023_08_21_Time_15_ms_(98.21%)_Space_55.1_MB_(23.21%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicintminimizeSum(int[]nums) {
9+
Arrays.sort(nums);
10+
intn =nums.length -1;
11+
intd1 = (nums[n] -nums[2]);
12+
intd2 = (nums[n -2] -nums[0]);
13+
intd3 = (nums[n -1] -nums[1]);
14+
returnMath.min(d1,Math.min(d2,d3));
15+
}
16+
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
2567\. Minimum Score by Changing Two Elements
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums`.
6+
7+
* The**low** score of`nums` is the minimum value of`|nums[i] - nums[j]|` over all`0 <= i < j < nums.length`.
8+
* The**high** score of`nums` is the maximum value of`|nums[i] - nums[j]|` over all`0 <= i < j < nums.length`.
9+
* The**score** of`nums` is the sum of the**high** and**low** scores of nums.
10+
11+
To minimize the score of`nums`, we can change the value of**at most two** elements of`nums`.
12+
13+
Return_the**minimum** possible**score** after changing the value of**at most two** elements o_f`nums`.
14+
15+
Note that`|x|` denotes the absolute value of`x`.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[1,4,3]
20+
21+
**Output:** 0
22+
23+
**Explanation:** Change value of nums[1] and nums[2] to 1 so that nums becomes[1,1,1]. Now, the value of`|nums[i] - nums[j]|` is always equal to 0, so we return 0 + 0 = 0.
24+
25+
**Example 2:**
26+
27+
**Input:** nums =[1,4,7,8,5]
28+
29+
**Output:** 3
30+
31+
**Explanation:** Change nums[0] and nums[1] to be 6. Now nums becomes[6,6,7,8,5].
32+
33+
Our low score is achieved when i = 0 and j = 1, in which case |`nums[i] - nums[j]`| = |6 - 6| = 0.
34+
35+
Our high score is achieved when i = 3 and j = 4, in which case |`nums[i] - nums[j]`| = |8 - 5| = 3.
36+
37+
The sum of our high and low score is 3, which we can prove to be minimal.
38+
39+
**Constraints:**
40+
41+
* <code>3 <= nums.length <= 10<sup>5</sup></code>
42+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2501_2600.s2568_minimum_impossible_or;
2+
3+
// #Medium #Array #Bit_Manipulation #Brainteaser
4+
// #2023_08_21_Time_14_ms_(81.48%)_Space_62.4_MB_(6.17%)
5+
6+
importjava.util.HashSet;
7+
importjava.util.Set;
8+
9+
publicclassSolution {
10+
publicintminImpossibleOR(int[]nums) {
11+
Set<Integer>set =newHashSet<>();
12+
for (intn :nums) {
13+
if (n ==1 || (n &1) ==0) {
14+
set.add(n);
15+
}
16+
}
17+
intpowerOfTwo =1;
18+
while (true) {
19+
if (!set.contains(powerOfTwo)) {
20+
returnpowerOfTwo;
21+
}
22+
powerOfTwo *=2;
23+
}
24+
}
25+
}
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
2568\. Minimum Impossible OR
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums`.
6+
7+
We say that an integer x is**expressible** from`nums` if there exist some integers <code>0 <= index<sub>1</sub> < index<sub>2</sub> < ... < index<sub>k</sub> < nums.length</code> for which <code>nums[index<sub>1</sub>] | nums[index<sub>2</sub>] | ... | nums[index<sub>k</sub>] = x</code>. In other words, an integer is expressible if it can be written as the bitwise OR of some subsequence of`nums`.
8+
9+
Return_the minimum**positive non-zero integer** that is not__expressible from_`nums`.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[2,1]
14+
15+
**Output:** 4
16+
17+
**Explanation:** 1 and 2 are already present in the array. We know that 3 is expressible, since nums[0] | nums[1] = 2 | 1 = 3. Since 4 is not expressible, we return 4.
18+
19+
**Example 2:**
20+
21+
**Input:** nums =[5,3,2]
22+
23+
**Output:** 1
24+
25+
**Explanation:** We can show that 1 is the smallest number that is not expressible.
26+
27+
**Constraints:**
28+
29+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
30+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
packageg2501_2600.s2569_handling_sum_queries_after_update;
2+
3+
// #Hard #Array #Segment_Tree #2023_08_21_Time_27_ms_(94.87%)_Space_84.1_MB_(43.59%)
4+
5+
importjava.util.Deque;
6+
importjava.util.LinkedList;
7+
8+
publicclassSolution {
9+
publiclong[]handleQuery(int[]nums1,int[]nums2,int[][]queries) {
10+
Deque<Long>dq =newLinkedList<>();
11+
longsum =0;
12+
for (inti :nums2) {
13+
sum +=i;
14+
}
15+
Segmentroot =build(nums1,0,nums1.length -1);
16+
for (int[]q :queries) {
17+
if (1 ==q[0]) {
18+
root.flip(q[1],q[2]);
19+
}elseif (2 ==q[0]) {
20+
sum +=root.sum *q[1];
21+
}else {
22+
dq.add(sum);
23+
}
24+
}
25+
intn =dq.size();
26+
inti =0;
27+
long[]res =newlong[n];
28+
while (!dq.isEmpty()) {
29+
res[i++] =dq.poll();
30+
}
31+
returnres;
32+
}
33+
34+
privatestaticclassSegment {
35+
longsum;
36+
intf;
37+
intlo;
38+
inthi;
39+
Segmentleft;
40+
Segmentright;
41+
42+
publicSegment(intl,intr) {
43+
lo =l;
44+
hi =r;
45+
}
46+
47+
publicvoidflip(intl,intr) {
48+
if (hi <l ||r <lo) {
49+
return;
50+
}
51+
if (l <=lo &&hi <=r) {
52+
f ^=1;
53+
sum =hi -lo +1 -sum;
54+
return;
55+
}
56+
if (1 ==f) {
57+
left.flip(lo,hi);
58+
right.flip(lo,hi);
59+
f ^=1;
60+
}
61+
left.flip(l,r);
62+
right.flip(l,r);
63+
sum =left.sum +right.sum;
64+
}
65+
}
66+
67+
privateSegmentbuild(int[]nums,intl,intr) {
68+
if (l ==r) {
69+
Segmentnode =newSegment(l,r);
70+
node.sum =nums[l];
71+
returnnode;
72+
}
73+
intmid =l + ((r -l) >>1);
74+
Segmentleft =build(nums,l,mid);
75+
Segmentright =build(nums,mid +1,r);
76+
Segmentroot =newSegment(l,r);
77+
root.left =left;
78+
root.right =right;
79+
root.sum =left.sum +right.sum;
80+
returnroot;
81+
}
82+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2569\. Handling Sum Queries After Update
2+
3+
Hard
4+
5+
You are given two**0-indexed** arrays`nums1` and`nums2` and a 2D array`queries` of queries. There are three types of queries:
6+
7+
1. For a query of type 1,`queries[i] = [1, l, r]`. Flip the values from`0` to`1` and from`1` to`0` in`nums1` from index`l` to index`r`. Both`l` and`r` are**0-indexed**.
8+
2. For a query of type 2,`queries[i] = [2, p, 0]`. For every index`0 <= i < n`, set`nums2[i] = nums2[i] + nums1[i] * p`.
9+
3. For a query of type 3,`queries[i] = [3, 0, 0]`. Find the sum of the elements in`nums2`.
10+
11+
Return_an array containing all the answers to the third type queries._
12+
13+
**Example 1:**
14+
15+
**Input:** nums1 =[1,0,1], nums2 =[0,0,0], queries =[[1,1,1],[2,1,0],[3,0,0]]
16+
17+
**Output:**[3]
18+
19+
**Explanation:** After the first query nums1 becomes[1,1,1]. After the second query, nums2 becomes[1,1,1], so the answer to the third query is 3. Thus,[3] is returned.
20+
21+
**Example 2:**
22+
23+
**Input:** nums1 =[1], nums2 =[5], queries =[[2,0,0],[3,0,0]]
24+
25+
**Output:**[5]
26+
27+
**Explanation:** After the first query, nums2 remains[5], so the answer to the second query is 5. Thus,[5] is returned.
28+
29+
**Constraints:**
30+
31+
* <code>1 <= nums1.length,nums2.length <= 10<sup>5</sup></code>
32+
*`nums1.length = nums2.length`
33+
* <code>1 <= queries.length <= 10<sup>5</sup></code>
34+
*`queries[i].length = 3`
35+
*`0 <= l <= r <= nums1.length - 1`
36+
* <code>0 <= p <= 10<sup>6</sup></code>
37+
*`0 <= nums1[i] <= 1`
38+
* <code>0 <= nums2[i] <= 10<sup>9</sup></code>

0 commit comments

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