Skip to content

Commit 4f39980

Browse files
ThanhNITThanhNIT
authored
Added tasks 1739, 1742, 1743, 1744, 1745.
1 parent 607889c commit 4f39980

File tree

15 files changed

+521
-0
lines changed

15 files changed

+521
-0
lines changed

‎src/main/java/g1701_1800/s1739_building_boxes/Solution.java

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package g1701_1800.s1739_building_boxes;
2+
3+
// #Hard #Math #Greedy #Binary_Search #2022_04_29_Time_1_ms_(84.38%)_Space_39.2_MB_(84.38%)
4+
5+
public class Solution {
6+
static final double ONE_THIRD = 1.0d / 3.0d;
7+
8+
public int minimumBoxes(int n) {
9+
int k = findLargestTetrahedralNotGreaterThan(n);
10+
int used = tetrahedral(k);
11+
int floor = triangular(k);
12+
int unused = (n - used);
13+
if (unused == 0) {
14+
return floor;
15+
}
16+
int r = findSmallestTriangularNotLessThan(unused);
17+
return (floor + r);
18+
}
19+
20+
private int findLargestTetrahedralNotGreaterThan(int te) {
21+
int a = (int) Math.ceil(Math.pow(product(6, te), ONE_THIRD));
22+
while (tetrahedral(a) > te) {
23+
a--;
24+
}
25+
return a;
26+
}
27+
28+
private int findSmallestTriangularNotLessThan(int t) {
29+
int a = -1 + (int) Math.floor(Math.sqrt(product(t, 2)));
30+
while (triangular(a) < t) {
31+
a++;
32+
}
33+
return a;
34+
}
35+
36+
private int tetrahedral(int a) {
37+
return (int) ratio(product(a, a + 1, a + 2), 6);
38+
}
39+
40+
private int triangular(int a) {
41+
return (int) ratio(product(a, a + 1), 2);
42+
}
43+
44+
private long product(long... vals) {
45+
long product = 1L;
46+
for (long val : vals) {
47+
product *= val;
48+
}
49+
return product;
50+
}
51+
52+
private long ratio(long a, long b) {
53+
return (a / b);
54+
}
55+
}

‎src/main/java/g1701_1800/s1739_building_boxes/readme.md

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
1739\. Building Boxes
2+
3+
Hard
4+
5+
You have a cubic storeroom where the width, length, and height of the room are all equal to `n` units. You are asked to place `n` boxes in this room where each box is a cube of unit side length. There are however some rules to placing the boxes:
6+
7+
* You can place the boxes anywhere on the floor.
8+
* If box `x` is placed on top of the box `y`, then each side of the four vertical sides of the box `y` **must** either be adjacent to another box or to a wall.
9+
10+
Given an integer `n`, return _the **minimum** possible number of boxes touching the floor._
11+
12+
**Example 1:**
13+
14+
![](https://assets.leetcode.com/uploads/2021/01/04/3-boxes.png)
15+
16+
**Input:** n = 3
17+
18+
**Output:** 3
19+
20+
**Explanation:** The figure above is for the placement of the three boxes. These boxes are placed in the corner of the room, where the corner is on the left side.
21+
22+
**Example 2:**
23+
24+
![](https://assets.leetcode.com/uploads/2021/01/04/4-boxes.png)
25+
26+
**Input:** n = 4
27+
28+
**Output:** 3
29+
30+
**Explanation:** The figure above is for the placement of the four boxes. These boxes are placed in the corner of the room, where the corner is on the left side.
31+
32+
**Example 3:**
33+
34+
![](https://assets.leetcode.com/uploads/2021/01/04/10-boxes.png)
35+
36+
**Input:** n = 10
37+
38+
**Output:** 6
39+
40+
**Explanation:** The figure above is for the placement of the ten boxes. These boxes are placed in the corner of the room, where the corner is on the back side.
41+
42+
**Constraints:**
43+
44+
* <code>1 <= n <= 10<sup>9</sup></code>

‎src/main/java/g1701_1800/s1742_maximum_number_of_balls_in_a_box/Solution.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package g1701_1800.s1742_maximum_number_of_balls_in_a_box;
2+
3+
// #Easy #Hash_Table #Math #Counting #2022_04_29_Time_7_ms_(98.87%)_Space_38.9_MB_(97.97%)
4+
5+
public class Solution {
6+
public int countBalls(int lowLimit, int highLimit) {
7+
int maxValue = 0;
8+
int[] countArray = new int[46];
9+
int currentSum = getDigitSum(lowLimit);
10+
countArray[currentSum]++;
11+
maxValue = 1;
12+
for (int i = lowLimit + 1; i <= highLimit; i++) {
13+
if (i % 10 == 0) {
14+
currentSum = getDigitSum(i);
15+
} else {
16+
currentSum++;
17+
}
18+
countArray[currentSum]++;
19+
if (countArray[currentSum] > maxValue) {
20+
maxValue = countArray[currentSum];
21+
}
22+
}
23+
return maxValue;
24+
}
25+
26+
private int getDigitSum(int num) {
27+
int currentSum = 0;
28+
while (num > 0) {
29+
currentSum += num % 10;
30+
num = num / 10;
31+
}
32+
return currentSum;
33+
}
34+
}

‎src/main/java/g1701_1800/s1742_maximum_number_of_balls_in_a_box/readme.md

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
1742\. Maximum Number of Balls in a Box
2+
3+
Easy
4+
5+
You are working in a ball factory where you have `n` balls numbered from `lowLimit` up to `highLimit` **inclusive** (i.e., `n == highLimit - lowLimit + 1`), and an infinite number of boxes numbered from `1` to `infinity`.
6+
7+
Your job at this factory is to put each ball in the box with a number equal to the sum of digits of the ball's number. For example, the ball number `321` will be put in the box number `3 + 2 + 1 = 6` and the ball number `10` will be put in the box number `1 + 0 = 1`.
8+
9+
Given two integers `lowLimit` and `highLimit`, return _the number of balls in the box with the most balls._
10+
11+
**Example 1:**
12+
13+
**Input:** lowLimit = 1, highLimit = 10
14+
15+
**Output:** 2
16+
17+
**Explanation:**
18+
19+
Box Number: 1 2 3 4 5 6 7 8 9 10 11 ...
20+
21+
Ball Count: 2 1 1 1 1 1 1 1 1 0 0 ...
22+
23+
Box 1 has the most number of balls with 2 balls.
24+
25+
**Example 2:**
26+
27+
**Input:** lowLimit = 5, highLimit = 15
28+
29+
**Output:** 2
30+
31+
**Explanation:**
32+
33+
Box Number: 1 2 3 4 5 6 7 8 9 10 11 ...
34+
35+
Ball Count: 1 1 1 1 2 2 1 1 1 0 0 ...
36+
37+
Boxes 5 and 6 have the most number of balls with 2 balls in each.
38+
39+
**Example 3:**
40+
41+
**Input:** lowLimit = 19, highLimit = 28
42+
43+
**Output:** 2
44+
45+
**Explanation:**
46+
47+
Box Number: 1 2 3 4 5 6 7 8 9 10 11 12 ...
48+
49+
Ball Count: 0 1 1 1 1 1 1 1 1 2 0 0 ...
50+
51+
Box 10 has the most number of balls with 2 balls.
52+
53+
**Constraints:**
54+
55+
* <code>1 <= lowLimit <= highLimit <= 10<sup>5</sup></code>

‎src/main/java/g1701_1800/s1743_restore_the_array_from_adjacent_pairs/Solution.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package g1701_1800.s1743_restore_the_array_from_adjacent_pairs;
2+
3+
// #Medium #Array #Hash_Table #2022_04_29_Time_95_ms_(99.08%)_Space_101.6_MB_(84.84%)
4+
5+
import java.util.ArrayList;
6+
import java.util.HashMap;
7+
import java.util.List;
8+
import java.util.Map;
9+
10+
public class Solution {
11+
public int[] restoreArray(int[][] adjacentPairs) {
12+
if (adjacentPairs == null || adjacentPairs.length == 0) {
13+
return new int[0];
14+
}
15+
if (adjacentPairs.length == 1) {
16+
return adjacentPairs[0];
17+
}
18+
19+
Map<Integer, List<Integer>> graph = new HashMap<>();
20+
21+
for (int[] pair : adjacentPairs) {
22+
graph.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]);
23+
graph.computeIfAbsent(pair[1], k -> new ArrayList<>()).add(pair[0]);
24+
}
25+
26+
int[] res = new int[graph.size()];
27+
28+
for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
29+
if (entry.getValue().size() == 1) {
30+
res[0] = entry.getKey();
31+
break;
32+
}
33+
}
34+
35+
res[1] = graph.get(res[0]).get(0);
36+
for (int i = 2; i < res.length; i++) {
37+
for (int cur : graph.get(res[i - 1])) {
38+
if (cur != res[i - 2]) {
39+
res[i] = cur;
40+
break;
41+
}
42+
}
43+
}
44+
45+
return res;
46+
}
47+
}

‎src/main/java/g1701_1800/s1743_restore_the_array_from_adjacent_pairs/readme.md

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
1743\. Restore the Array From Adjacent Pairs
2+
3+
Medium
4+
5+
There is an integer array `nums` that consists of `n` **unique** elements, but you have forgotten it. However, you do remember every pair of adjacent elements in `nums`.
6+
7+
You are given a 2D integer array `adjacentPairs` of size `n - 1` where each <code>adjacentPairs[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> indicates that the elements <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> are adjacent in `nums`.
8+
9+
It is guaranteed that every adjacent pair of elements `nums[i]` and `nums[i+1]` will exist in `adjacentPairs`, either as `[nums[i], nums[i+1]]` or `[nums[i+1], nums[i]]`. The pairs can appear **in any order**.
10+
11+
Return _the original array_ `nums`_. If there are multiple solutions, return **any of them**_.
12+
13+
**Example 1:**
14+
15+
**Input:** adjacentPairs = [[2,1],[3,4],[3,2]]
16+
17+
**Output:** [1,2,3,4]
18+
19+
**Explanation:** This array has all its adjacent pairs in adjacentPairs. Notice that adjacentPairs[i] may not be in left-to-right order.
20+
21+
**Example 2:**
22+
23+
**Input:** adjacentPairs = [[4,-2],[1,4],[-3,1]]
24+
25+
**Output:** [-2,4,1,-3]
26+
27+
**Explanation:** There can be negative numbers. Another solution is [-3,1,4,-2], which would also be accepted.
28+
29+
**Example 3:**
30+
31+
**Input:** adjacentPairs = [[100000,-100000]]
32+
33+
**Output:** [100000,-100000]
34+
35+
**Constraints:**
36+
37+
* `nums.length == n`
38+
* `adjacentPairs.length == n - 1`
39+
* `adjacentPairs[i].length == 2`
40+
* <code>2 <= n <= 10<sup>5</sup></code>
41+
* <code>-10<sup>5</sup> <= nums[i], u<sub>i</sub>, v<sub>i</sub> <= 10<sup>5</sup></code>
42+
* There exists some `nums` that has `adjacentPairs` as its pairs.

‎src/main/java/g1701_1800/s1744_can_you_eat_your_favorite_candy_on_your_favorite_day/Solution.java

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package g1701_1800.s1744_can_you_eat_your_favorite_candy_on_your_favorite_day;
2+
3+
// #Medium #Array #Prefix_Sum #2022_04_29_Time_5_ms_(100.00%)_Space_91.1_MB_(76.00%)
4+
5+
public class Solution {
6+
public boolean[] canEat(int[] candiesCount, int[][] queries) {
7+
boolean[] result = new boolean[queries.length];
8+
long[] candiesComm = new long[candiesCount.length + 1];
9+
for (int i = 1; i <= candiesCount.length; i++) {
10+
candiesComm[i] = candiesComm[i - 1] + candiesCount[i - 1];
11+
}
12+
for (int i = 0; i < queries.length; i++) {
13+
int type = queries[i][0];
14+
long day = queries[i][1];
15+
long cap = queries[i][2];
16+
result[i] = ((day + 1) * cap > candiesComm[type]) && day < candiesComm[type + 1];
17+
}
18+
19+
return result;
20+
}
21+
}

‎src/main/java/g1701_1800/s1744_can_you_eat_your_favorite_candy_on_your_favorite_day/readme.md

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
1744\. Can You Eat Your Favorite Candy on Your Favorite Day?
2+
3+
Medium
4+
5+
You are given a **(0-indexed)** array of positive integers `candiesCount` where `candiesCount[i]` represents the number of candies of the <code>i<sup>th</sup></code> type you have. You are also given a 2D array `queries` where <code>queries[i] = [favoriteType<sub>i</sub>, favoriteDay<sub>i</sub>, dailyCap<sub>i</sub>]</code>.
6+
7+
You play a game with the following rules:
8+
9+
* You start eating candies on day `**0**`.
10+
* You **cannot** eat **any** candy of type `i` unless you have eaten **all** candies of type `i - 1`.
11+
* You must eat **at least** **one** candy per day until you have eaten all the candies.
12+
13+
Construct a boolean array `answer` such that `answer.length == queries.length` and `answer[i]` is `true` if you can eat a candy of type <code>favoriteType<sub>i</sub></code> on day <code>favoriteDay<sub>i</sub></code> without eating **more than** <code>dailyCap<sub>i</sub></code> candies on **any** day, and `false` otherwise. Note that you can eat different types of candy on the same day, provided that you follow rule 2.
14+
15+
Return _the constructed array_ `answer`.
16+
17+
**Example 1:**
18+
19+
**Input:** candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
20+
21+
**Output:** [true,false,true]
22+
23+
**Explanation:**
24+
25+
1- If you eat 2 candies (type 0) on day 0 and 2 candies (type 0) on day 1, you will eat a candy of type 0 on day 2.
26+
27+
2- You can eat at most 4 candies each day.
28+
29+
If you eat 4 candies every day, you will eat 4 candies (type 0) on day 0 and 4 candies (type 0 and type 1) on day 1.
30+
31+
On day 2, you can only eat 4 candies (type 1 and type 2), so you cannot eat a candy of type 4 on day 2.
32+
33+
3- If you eat 1 candy each day, you will eat a candy of type 2 on day 13.
34+
35+
**Example 2:**
36+
37+
**Input:** candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
38+
39+
**Output:** [false,true,true,false,false]
40+
41+
**Constraints:**
42+
43+
* <code>1 <= candiesCount.length <= 10<sup>5</sup></code>
44+
* <code>1 <= candiesCount[i] <= 10<sup>5</sup></code>
45+
* <code>1 <= queries.length <= 10<sup>5</sup></code>
46+
* `queries[i].length == 3`
47+
* <code>0 <= favoriteType<sub>i</sub> < candiesCount.length</code>
48+
* <code>0 <= favoriteDay<sub>i</sub> <= 10<sup>9</sup></code>
49+
* <code>1 <= dailyCap<sub>i</sub> <= 10<sup>9</sup></code>

‎src/main/java/g1701_1800/s1745_palindrome_partitioning_iv/Solution.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package g1701_1800.s1745_palindrome_partitioning_iv;
2+
3+
// #Hard #String #Dynamic_Programming #2022_04_29_Time_10_ms_(100.00%)_Space_44_MB_(95.27%)
4+
5+
public class Solution {
6+
public boolean checkPartitioning(String s) {
7+
final int len = s.length();
8+
char[] ch = s.toCharArray();
9+
int[] dp = new int[len + 1];
10+
dp[0] = 0x01;
11+
for (int i = 0; i < len; i++) {
12+
for (int l : new int[] {i - 1, i}) {
13+
int r = i;
14+
while (l >= 0 && r < len && ch[l] == ch[r]) {
15+
dp[r + 1] |= dp[l] << 1;
16+
l--;
17+
r++;
18+
}
19+
}
20+
}
21+
return (dp[len] & 0x08) == 0x08;
22+
}
23+
}

0 commit comments

Comments
 (0)