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

Commite956631

Browse files
authored
Added tasks 2761, 2801-2808
1 parent395b7d5 commite956631

File tree

15 files changed

+485
-0
lines changed

15 files changed

+485
-0
lines changed
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
packageg2701_2800.s2761_prime_pairs_with_target_sum;
2+
3+
// #Medium #Array #Math #Enumeration #Number_Theory
4+
// #2023_09_25_Time_57_ms_(99.24%)_Space_56.4_MB_(10.58%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.HashSet;
8+
importjava.util.List;
9+
10+
publicclassSolution {
11+
privatestaticfinalHashSet<Integer>PRIMES =newHashSet<>();
12+
privatestaticfinalList<Integer>LIST =newArrayList<>();
13+
14+
publicList<List<Integer>>findPrimePairs(intn) {
15+
List<List<Integer>>answer =newArrayList<>();
16+
for (inta :LIST) {
17+
intother =n -a;
18+
if (other <n /2 ||a >n /2) {
19+
break;
20+
}
21+
if (PRIMES.contains(other)) {
22+
answer.add(List.of(a,other));
23+
}
24+
}
25+
returnanswer;
26+
}
27+
28+
static {
29+
intm =1000001;
30+
boolean[]visited =newboolean[m];
31+
for (inti =2;i <m;i++) {
32+
if (!visited[i]) {
33+
PRIMES.add(i);
34+
LIST.add(i);
35+
intj =i;
36+
while (j <m) {
37+
visited[j] =true;
38+
j +=i;
39+
}
40+
}
41+
}
42+
}
43+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
2761\. Prime Pairs With Target Sum
2+
3+
Medium
4+
5+
You are given an integer`n`. We say that two integers`x` and`y` form a prime number pair if:
6+
7+
*`1 <= x <= y <= n`
8+
*`x + y == n`
9+
*`x` and`y` are prime numbers
10+
11+
Return_the 2D sorted list of prime number pairs_ <code>[x<sub>i</sub>, y<sub>i</sub>]</code>. The list should be sorted in**increasing** order of <code>x<sub>i</sub></code>. If there are no prime number pairs at all, return_an empty array_.
12+
13+
**Note:** A prime number is a natural number greater than`1` with only two factors, itself and`1`.
14+
15+
**Example 1:**
16+
17+
**Input:** n = 10
18+
19+
**Output:**[[3,7],[5,5]]
20+
21+
**Explanation:**
22+
23+
In this example, there are two prime pairs that satisfy the criteria.
24+
25+
These pairs are[3,7] and[5,5], and we return them in the sorted order as described in the problem statement.
26+
27+
**Example 2:**
28+
29+
**Input:** n = 2
30+
31+
**Output:**[]
32+
33+
**Explanation:**
34+
35+
We can show that there is no prime number pair that gives a sum of 2, so we return an empty array.
36+
37+
**Constraints:**
38+
39+
* <code>1 <= n <= 10<sup>6</sup></code>
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
packageg2801_2900.s2801_count_stepping_numbers_in_range;
2+
3+
// #Hard #String #Dynamic_Programming #2023_09_25_Time_22_ms_(74.37%)_Space_44.5_MB_(24.69%)
4+
5+
publicclassSolution {
6+
privatestaticfinalintMOD = (int) (1e9 +7);
7+
privateInteger[][][][]dp;
8+
9+
publicintcountSteppingNumbers(Stringlow,Stringhigh) {
10+
dp =newInteger[low.length() +1][10][2][2];
11+
intcount1 =solve(low,0,0,1,1);
12+
dp =newInteger[high.length() +1][10][2][2];
13+
intcount2 =solve(high,0,0,1,1);
14+
return (count2 -count1 +isStep(low) +MOD) %MOD;
15+
}
16+
17+
privateintsolve(Strings,inti,intprevDigit,inthasBound,intcurIsZero) {
18+
if (i >=s.length()) {
19+
if (curIsZero ==1) {
20+
return0;
21+
}
22+
return1;
23+
}
24+
if (dp[i][prevDigit][hasBound][curIsZero] !=null) {
25+
returndp[i][prevDigit][hasBound][curIsZero];
26+
}
27+
intcount =0;
28+
intlimit =9;
29+
if (hasBound ==1) {
30+
limit =s.charAt(i) -'0';
31+
}
32+
for (intdigit =0;digit <=limit;digit++) {
33+
intnextIsZero = (curIsZero ==1 &&digit ==0) ?1 :0;
34+
intnextHasBound = (hasBound ==1 &&digit ==limit) ?1 :0;
35+
if (curIsZero ==1 ||Math.abs(digit -prevDigit) ==1) {
36+
count = (count +solve(s,i +1,digit,nextHasBound,nextIsZero)) %MOD;
37+
}
38+
}
39+
40+
dp[i][prevDigit][hasBound][curIsZero] =count;
41+
returndp[i][prevDigit][hasBound][curIsZero];
42+
}
43+
44+
privateintisStep(Strings) {
45+
booleanisValid =true;
46+
for (inti =0;i <s.length() -1;i++) {
47+
if (Math.abs(s.charAt(i +1) -s.charAt(i)) !=1) {
48+
isValid =false;
49+
break;
50+
}
51+
}
52+
if (isValid) {
53+
return1;
54+
}
55+
return0;
56+
}
57+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2801\. Count Stepping Numbers in Range
2+
3+
Hard
4+
5+
Given two positive integers`low` and`high` represented as strings, find the count of**stepping numbers** in the inclusive range`[low, high]`.
6+
7+
A**stepping number** is an integer such that all of its adjacent digits have an absolute difference of**exactly**`1`.
8+
9+
Return_an integer denoting the count of stepping numbers in the inclusive range_`[low, high]`_._
10+
11+
Since the answer may be very large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
12+
13+
**Note:** A stepping number should not have a leading zero.
14+
15+
**Example 1:**
16+
17+
**Input:** low = "1", high = "11"
18+
19+
**Output:** 10
20+
21+
**Explanation:** The stepping numbers in the range[1,11] are 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10. There are a total of 10 stepping numbers in the range. Hence, the output is 10.
22+
23+
**Example 2:**
24+
25+
**Input:** low = "90", high = "101"
26+
27+
**Output:** 2
28+
29+
**Explanation:** The stepping numbers in the range[90,101] are 98 and 101. There are a total of 2 stepping numbers in the range. Hence, the output is 2.
30+
31+
**Constraints:**
32+
33+
* <code>1 <= int(low) <= int(high) < 10<sup>100</sup></code>
34+
*`1 <= low.length, high.length <= 100`
35+
*`low` and`high` consist of only digits.
36+
*`low` and`high` don't have any leading zeros.
Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
packageg2801_2900.s2806_account_balance_after_rounded_purchase;
2+
3+
// #Easy #Math #2023_09_25_Time_0_ms_(100.00%)_Space_39.2_MB_(64.97%)
4+
5+
publicclassSolution {
6+
publicintaccountBalanceAfterPurchase(intpurchaseAmount) {
7+
intx = (int) ((purchaseAmount +5) / (double)10) *10;
8+
return100 -x;
9+
}
10+
}
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
2806\. Account Balance After Rounded Purchase
2+
3+
Easy
4+
5+
Initially, you have a bank account balance of`100` dollars.
6+
7+
You are given an integer`purchaseAmount` representing the amount you will spend on a purchase in dollars.
8+
9+
At the store where you will make the purchase, the purchase amount is rounded to the**nearest multiple** of`10`. In other words, you pay a**non-negative** amount,`roundedAmount`, such that`roundedAmount` is a multiple of`10` and`abs(roundedAmount - purchaseAmount)` is**minimized**.
10+
11+
If there is more than one nearest multiple of`10`, the**largest multiple** is chosen.
12+
13+
Return_an integer denoting your account balance after making a purchase worth_`purchaseAmount`_dollars from the store._
14+
15+
**Note:**`0` is considered to be a multiple of`10` in this problem.
16+
17+
**Example 1:**
18+
19+
**Input:** purchaseAmount = 9
20+
21+
**Output:** 90
22+
23+
**Explanation:** In this example, the nearest multiple of 10 to 9 is 10. Hence, your account balance becomes 100 - 10 = 90.
24+
25+
**Example 2:**
26+
27+
**Input:** purchaseAmount = 15
28+
29+
**Output:** 80
30+
31+
**Explanation:** In this example, there are two nearest multiples of 10 to 15: 10 and 20. So, the larger multiple, 20, is chosen. Hence, your account balance becomes 100 - 20 = 80.
32+
33+
**Constraints:**
34+
35+
*`0 <= purchaseAmount <= 100`
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
packageg2801_2900.s2807_insert_greatest_common_divisors_in_linked_list;
2+
3+
// #Medium #Array #Math #Linked_List #2023_09_25_Time_1_ms_(100.00%)_Space_43.4_MB_(93.05%)
4+
5+
importcom_github_leetcode.ListNode;
6+
7+
/*
8+
* Definition for singly-linked list.
9+
* public class ListNode {
10+
* int val;
11+
* ListNode next;
12+
* ListNode() {}
13+
* ListNode(int val) { this.val = val; }
14+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
15+
* }
16+
*/
17+
publicclassSolution {
18+
publicListNodeinsertGreatestCommonDivisors(ListNodehead) {
19+
ListNodeprevNode =null;
20+
ListNodecurrNode =head;
21+
while (currNode !=null) {
22+
if (prevNode !=null) {
23+
intgcd =greatestCommonDivisor(prevNode.val,currNode.val);
24+
prevNode.next =newListNode(gcd,currNode);
25+
}
26+
prevNode =currNode;
27+
currNode =currNode.next;
28+
}
29+
returnhead;
30+
}
31+
32+
privateintgreatestCommonDivisor(intval1,intval2) {
33+
if (val2 ==0) {
34+
returnval1;
35+
}
36+
returngreatestCommonDivisor(val2,val1 %val2);
37+
}
38+
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
2807\. Insert Greatest Common Divisors in Linked List
2+
3+
Medium
4+
5+
Given the head of a linked list`head`, in which each node contains an integer value.
6+
7+
Between every pair of adjacent nodes, insert a new node with a value equal to the**greatest common divisor** of them.
8+
9+
Return_the linked list after insertion_.
10+
11+
The**greatest common divisor** of two numbers is the largest positive integer that evenly divides both numbers.
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2023/07/18/ex1_copy.png)
16+
17+
**Input:** head =[18,6,10,3]
18+
19+
**Output:**[18,6,6,2,10,1,3]
20+
21+
**Explanation:** The 1<sup>st</sup> diagram denotes the initial linked list and the 2<sup>nd</sup> diagram denotes the linked list after inserting the new nodes (nodes in blue are the inserted nodes).
22+
23+
- We insert the greatest common divisor of 18 and 6 = 6 between the 1<sup>st</sup> and the 2<sup>nd</sup> nodes.
24+
- We insert the greatest common divisor of 6 and 10 = 2 between the 2<sup>nd</sup> and the 3<sup>rd</sup> nodes.
25+
- We insert the greatest common divisor of 10 and 3 = 1 between the 3<sup>rd</sup> and the 4<sup>th</sup> nodes.
26+
27+
There are no more adjacent nodes, so we return the linked list.
28+
29+
**Example 2:**
30+
31+
![](https://assets.leetcode.com/uploads/2023/07/18/ex2_copy1.png)
32+
33+
**Input:** head =[7]
34+
35+
**Output:**[7]
36+
37+
**Explanation:** The 1<sup>st</sup> diagram denotes the initial linked list and the 2<sup>nd</sup> diagram denotes the linked list after inserting the new nodes. There are no pairs of adjacent nodes, so we return the initial linked list.
38+
39+
**Constraints:**
40+
41+
* The number of nodes in the list is in the range`[1, 5000]`.
42+
*`1 <= Node.val <= 1000`
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
packageg2801_2900.s2808_minimum_seconds_to_equalize_a_circular_array;
2+
3+
// #Medium #Array #Hash_Table #Greedy #2023_09_25_Time_59_ms_(88.86%)_Space_82.4_MB_(29.30%)
4+
5+
importjava.util.ArrayList;
6+
importjava.util.HashMap;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
publicintminimumSeconds(List<Integer>nums) {
11+
intn =nums.size();
12+
intmin =n /2;
13+
HashMap<Integer,List<Integer>>hm =newHashMap<>();
14+
for (inti =0;i <n;i++) {
15+
intv =nums.get(i);
16+
hm.computeIfAbsent(v,k ->newArrayList<>()).add(i);
17+
}
18+
19+
for (List<Integer>list :hm.values()) {
20+
if (list.size() >1) {
21+
intcurr = (list.get(0) +n -list.get(list.size() -1)) /2;
22+
for (inti =1;i <list.size();i++) {
23+
curr =Math.max(curr, (list.get(i) -list.get(i -1)) /2);
24+
}
25+
min =Math.min(min,curr);
26+
}
27+
}
28+
returnmin;
29+
}
30+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
2808\. Minimum Seconds to Equalize a Circular Array
2+
3+
Medium
4+
5+
You are given a**0-indexed** array`nums` containing`n` integers.
6+
7+
At each second, you perform the following operation on the array:
8+
9+
* For every index`i` in the range`[0, n - 1]`, replace`nums[i]` with either`nums[i]`,`nums[(i - 1 + n) % n]`, or`nums[(i + 1) % n]`.
10+
11+
**Note** that all the elements get replaced simultaneously.
12+
13+
Return_the**minimum** number of seconds needed to make all elements in the array_`nums`_equal_.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[1,2,1,2]
18+
19+
**Output:** 1
20+
21+
**Explanation:** We can equalize the array in 1 second in the following way:
22+
- At 1<sup>st</sup> second, replace values at each index with[nums[3],nums[1],nums[3],nums[3]]. After replacement, nums =[2,2,2,2]. It can be proven that 1 second is the minimum amount of seconds needed for equalizing the array.
23+
24+
**Example 2:**
25+
26+
**Input:** nums =[2,1,3,3,2]
27+
28+
**Output:** 2
29+
30+
**Explanation:** We can equalize the array in 2 seconds in the following way:
31+
- At 1<sup>st</sup> second, replace values at each index with[nums[0],nums[2],nums[2],nums[2],nums[3]]. After replacement, nums =[2,3,3,3,3].
32+
- At 2<sup>nd</sup> second, replace values at each index with[nums[1],nums[1],nums[2],nums[3],nums[4]]. After replacement, nums =[3,3,3,3,3].
33+
34+
It can be proven that 2 seconds is the minimum amount of seconds needed for equalizing the array.
35+
36+
**Example 3:**
37+
38+
**Input:** nums =[5,5,5,5]
39+
40+
**Output:** 0
41+
42+
**Explanation:** We don't need to perform any operations as all elements in the initial array are the same.
43+
44+
**Constraints:**
45+
46+
* <code>1 <= n == nums.length <= 10<sup>5</sup></code>
47+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>

0 commit comments

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