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

Commitc06840b

Browse files
authored
Added tasks 2699-2706
1 parentcaba152 commitc06840b

File tree

15 files changed

+456
-0
lines changed

15 files changed

+456
-0
lines changed
Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
packageg2601_2700.s2699_modify_graph_edge_weights;
2+
3+
// #Hard #Heap_Priority_Queue #Graph #Shortest_Path
4+
// #2023_09_14_Time_88_ms_(85.25%)_Space_49.9_MB_(85.25%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Comparator;
8+
importjava.util.List;
9+
importjava.util.PriorityQueue;
10+
11+
@SuppressWarnings("java:S135")
12+
publicclassSolution {
13+
publicint[][]modifiedGraphEdges(
14+
intn,int[][]edges,intsource,intdestination,inttarget) {
15+
List<int[]>[]graph =newArrayList[n];
16+
for (inti =0;i <n;i++) {
17+
graph[i] =newArrayList<>();
18+
}
19+
for (inti =0;i <edges.length;i++) {
20+
int[]e =edges[i];
21+
graph[e[0]].add(newint[] {e[1],i});
22+
graph[e[1]].add(newint[] {e[0],i});
23+
}
24+
PriorityQueue<int[]>pq =newPriorityQueue<>(Comparator.comparingInt(v ->v[1]));
25+
pq.add(newint[] {destination,0});
26+
Integer[]distances =newInteger[n];
27+
processQueue(edges,source,pq,distances,graph);
28+
if (distances[source] >target) {
29+
returnnewint[][] {};
30+
}
31+
pq =newPriorityQueue<>(Comparator.comparingInt(v ->v[1]));
32+
if (distances[source] !=target) {
33+
pq.add(newint[] {source,0});
34+
}
35+
boolean[]visited =newboolean[n];
36+
while (!pq.isEmpty()) {
37+
int[]c =pq.poll();
38+
if (visited[c[0]]) {
39+
continue;
40+
}
41+
visited[c[0]] =true;
42+
if (c[0] ==destination) {
43+
returnnewint[][] {};
44+
}
45+
for (int[]e :graph[c[0]]) {
46+
if (visited[e[0]] ||distances[e[0]] ==null) {
47+
continue;
48+
}
49+
intdif =target -c[1] -distances[e[0]];
50+
if (Math.abs(edges[e[1]][2]) >=dif) {
51+
continue;
52+
}
53+
if (edges[e[1]][2] == -1) {
54+
edges[e[1]][2] =dif;
55+
continue;
56+
}
57+
pq.add(newint[] {e[0],c[1] +edges[e[1]][2]});
58+
}
59+
}
60+
for (int[]e :edges) {
61+
if (e[2] == -1) {
62+
e[2] =1;
63+
}
64+
}
65+
returnedges;
66+
}
67+
68+
privatevoidprocessQueue(
69+
int[][]edges,
70+
intsource,
71+
PriorityQueue<int[]>pq,
72+
Integer[]distances,
73+
List<int[]>[]graph) {
74+
while (!pq.isEmpty()) {
75+
int[]c =pq.poll();
76+
if (distances[c[0]] !=null) {
77+
continue;
78+
}
79+
distances[c[0]] =c[1];
80+
if (c[0] ==source) {
81+
continue;
82+
}
83+
for (int[]e :graph[c[0]]) {
84+
if (distances[e[0]] !=null) {
85+
continue;
86+
}
87+
pq.add(newint[] {e[0],c[1] +Math.abs(edges[e[1]][2])});
88+
}
89+
}
90+
}
91+
}
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
2699\. Modify Graph Edge Weights
2+
3+
Hard
4+
5+
You are given an**undirected weighted****connected** graph containing`n` nodes labeled from`0` to`n - 1`, and an integer array`edges` where <code>edges[i] =[a<sub>i</sub>, b<sub>i</sub>, w<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> with weight <code>w<sub>i</sub></code>.
6+
7+
Some edges have a weight of`-1` (<code>w<sub>i</sub> = -1</code>), while others have a**positive** weight (<code>w<sub>i</sub> > 0</code>).
8+
9+
Your task is to modify**all edges** with a weight of`-1` by assigning them**positive integer values** in the range <code>[1, 2 * 10<sup>9</sup>]</code> so that the**shortest distance** between the nodes`source` and`destination` becomes equal to an integer`target`. If there are**multiple****modifications** that make the shortest distance between`source` and`destination` equal to`target`, any of them will be considered correct.
10+
11+
Return_an array containing all edges (even unmodified ones) in any order if it is possible to make the shortest distance from_`source`_to_`destination`_equal to_`target`_, or an**empty array** if it's impossible._
12+
13+
**Note:** You are not allowed to modify the weights of edges with initial positive weights.
14+
15+
**Example 1:**
16+
17+
**![](https://assets.leetcode.com/uploads/2023/04/18/graph.png)**
18+
19+
**Input:** n = 5, edges =[[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5
20+
21+
**Output:**[[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
22+
23+
**Explanation:** The graph above shows a possible modification to the edges, making the distance from 0 to 1 equal to 5.
24+
25+
**Example 2:**
26+
27+
**![](https://assets.leetcode.com/uploads/2023/04/18/graph-2.png)**
28+
29+
**Input:** n = 3, edges =[[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6
30+
31+
**Output:**[]
32+
33+
**Explanation:** The graph above contains the initial edges. It is not possible to make the distance from 0 to 2 equal to 6 by modifying the edge with weight -1. So, an empty array is returned.
34+
35+
**Example 3:**
36+
37+
**![](https://assets.leetcode.com/uploads/2023/04/19/graph-3.png)**
38+
39+
**Input:** n = 4, edges =[[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6
40+
41+
**Output:**[[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
42+
43+
**Explanation:** The graph above shows a modified graph having the shortest distance from 0 to 2 as 6.
44+
45+
**Constraints:**
46+
47+
*`1 <= n <= 100`
48+
*`1 <= edges.length <= n * (n - 1) / 2`
49+
*`edges[i].length == 3`
50+
* <code>0 <= a<sub>i</sub>, b<sub>i </sub>< n</code>
51+
* <code>w<sub>i</sub> = -1 </code>or <code>1 <= w<sub>i </sub><= 10<sup>7</sup></code>
52+
* <code>a<sub>i </sub>!= b<sub>i</sub></code>
53+
*`0 <= source, destination < n`
54+
*`source != destination`
55+
* <code>1 <= target <= 10<sup>9</sup></code>
56+
* The graph is connected, and there are no self-loops or repeated edges
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
2703\. Return Length of Arguments Passed
2+
3+
Easy
4+
5+
Write a function`argumentsLength` that returns the count of arguments passed to it.
6+
7+
**Example 1:**
8+
9+
**Input:** argsArr =[5]
10+
11+
**Output:** 1
12+
13+
**Explanation:** argumentsLength(5); // 1 One value was passed to the function so it should return 1.
14+
15+
**Example 2:**
16+
17+
**Input:** argsArr =[{}, null, "3"]
18+
19+
**Output:** 3
20+
21+
**Explanation:** argumentsLength({}, null, "3"); // 3 Three values were passed to the function so it should return 3.
22+
23+
**Constraints:**
24+
25+
*`argsArr is a valid JSON array`
26+
*`0 <= argsArr.length <= 100`
Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
// #Easy #2023_09_14_Time_49_ms_(86.01%)_Space_42.9_MB_(39.39%)
2+
3+
functionargumentsLength(...args:any[]):number{
4+
returnargs.length
5+
}
6+
7+
export{argumentsLength}
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
2704\. To Be Or Not To Be
2+
3+
Easy
4+
5+
Write a function`expect` that helps developers test their code. It should take in any value`val` and return an object with the following two functions.
6+
7+
*`toBe(val)` accepts another value and returns`true` if the two values`===` each other. If they are not equal, it should throw an error`"Not Equal"`.
8+
*`notToBe(val)` accepts another value and returns`true` if the two values`!==` each other. If they are equal, it should throw an error`"Equal"`.
9+
10+
**Example 1:**
11+
12+
**Input:** func = () => expect(5).toBe(5)
13+
14+
**Output:** {"value": true}
15+
16+
**Explanation:** 5 === 5 so this expression returns true.
17+
18+
**Example 2:**
19+
20+
**Input:** func = () => expect(5).toBe(null)
21+
22+
**Output:** {"error": "Not Equal"}
23+
24+
**Explanation:** 5 !== null so this expression throw the error "Not Equal".
25+
26+
**Example 3:**
27+
28+
**Input:** func = () => expect(5).notToBe(null)
29+
30+
**Output:** {"value": true}
31+
32+
**Explanation:** 5 !== null so this expression returns true.
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
// #Easy #2023_09_14_Time_45_ms_(96.05%)_Space_42.5_MB_(76.36%)
2+
3+
typeToBeOrNotToBe={
4+
toBe:(val:any)=>boolean
5+
notToBe:(val:any)=>boolean
6+
}
7+
8+
constexpect=(val:any):ToBeOrNotToBe=>({
9+
toBe:(equality:any)=>{
10+
if(val!==equality){
11+
thrownewError('Not Equal')
12+
}
13+
returntrue
14+
},
15+
notToBe:(equality:any)=>{
16+
if(val===equality){
17+
thrownewError('Equal')
18+
}
19+
returntrue
20+
},
21+
})
22+
23+
/*
24+
* expect(5).toBe(5); // true
25+
* expect(5).notToBe(5); // throws "Equal"
26+
*/
27+
28+
export{expect}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2705\. Compact Object
2+
3+
Medium
4+
5+
Given an object or array`obj`, return a**compact object**. A**compact object** is the same as the original object, except with keys containing**falsy** values removed. This operation applies to the object and any nested objects. Arrays are considered objects where the indices are keys. A value is considered**falsy** when`Boolean(value)` returns`false`.
6+
7+
You may assume the`obj` is the output of`JSON.parse`. In other words, it is valid JSON.
8+
9+
**Example 1:**
10+
11+
**Input:** obj =[null, 0, false, 1]
12+
13+
**Output:**[1]
14+
15+
**Explanation:** All falsy values have been removed from the array.
16+
17+
**Example 2:**
18+
19+
**Input:** obj = {"a": null, "b":[false, 1]}
20+
21+
**Output:** {"b":[1]}
22+
23+
**Explanation:** obj["a"] and obj["b"][0] had falsy values and were removed.
24+
25+
**Example 3:**
26+
27+
**Input:** obj =[null, 0, 5,[0],[false, 16]]
28+
29+
**Output:**[5,[],[16]]
30+
31+
**Explanation:** obj[0], obj[1], obj[3][0], and obj[4][0] were falsy and removed.
32+
33+
**Constraints:**
34+
35+
*`obj is a valid JSON object`
36+
* <code>2 <= JSON.stringify(obj).length <= 10<sup>6</sup></code>
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
// #Medium #2023_09_14_Time_80_ms_(88.30%)_Space_53.2_MB_(70.41%)
2+
3+
typeObj=Record<any,any>
4+
5+
functioncompactObject(obj:Obj):Obj{
6+
if(Array.isArray(obj)){
7+
letretArr=[]
8+
obj.forEach((e,idx)=>{
9+
if(e){
10+
retArr.push(compactObject(e))
11+
}
12+
})
13+
returnretArr
14+
}elseif(obj!==null&&typeofobj==='object'){
15+
letretObj={}
16+
for(constkeyofObject.keys(obj)){
17+
if(obj[key]){
18+
retObj[key]=compactObject(obj[key])
19+
}
20+
}
21+
returnretObj
22+
}
23+
returnobj
24+
}
25+
26+
export{compactObject}
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packageg2701_2800.s2706_buy_two_chocolates;
2+
3+
// #Easy #Array #Sorting #2023_09_14_Time_1_ms_(100.00%)_Space_43_MB_(74.68%)
4+
5+
publicclassSolution {
6+
publicintbuyChoco(int[]prices,intmoney) {
7+
intminPrice1 =Integer.MAX_VALUE;
8+
intminPrice2 =Integer.MAX_VALUE;
9+
10+
for (intprice :prices) {
11+
if (price <minPrice1) {
12+
minPrice2 =minPrice1;
13+
minPrice1 =price;
14+
}elseif (price <minPrice2) {
15+
minPrice2 =price;
16+
}
17+
}
18+
19+
inttotalPrice =minPrice1 +minPrice2;
20+
21+
if (totalPrice >money) {
22+
returnmoney;
23+
}else {
24+
returnmoney -totalPrice;
25+
}
26+
}
27+
}
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
2706\. Buy Two Chocolates
2+
3+
Easy
4+
5+
You are given an integer array`prices` representing the prices of various chocolates in a store. You are also given a single integer`money`, which represents your initial amount of money.
6+
7+
You must buy**exactly** two chocolates in such a way that you still have some**non-negative** leftover money. You would like to minimize the sum of the prices of the two chocolates you buy.
8+
9+
Return_the amount of money you will have leftover after buying the two chocolates_. If there is no way for you to buy two chocolates without ending up in debt, return`money`. Note that the leftover must be non-negative.
10+
11+
**Example 1:**
12+
13+
**Input:** prices =[1,2,2], money = 3
14+
15+
**Output:** 0
16+
17+
**Explanation:** Purchase the chocolates priced at 1 and 2 units respectively. You will have 3 - 3 = 0 units of money afterwards. Thus, we return 0.
18+
19+
**Example 2:**
20+
21+
**Input:** prices =[3,2,3], money = 3
22+
23+
**Output:** 3
24+
25+
**Explanation:** You cannot buy 2 chocolates without going in debt, so we return 3.
26+
27+
**Constraints:**
28+
29+
*`2 <= prices.length <= 50`
30+
*`1 <= prices[i] <= 100`
31+
*`1 <= money <= 100`

0 commit comments

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