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

Commit410335f

Browse files
committed
[Function add]
1. Add leetcode solutions.
1 parent0f854a6 commit410335f

4 files changed

+251
-1
lines changed
Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
##339. Nested List Weight Sum
2+
3+
###Question
4+
Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
5+
6+
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
7+
8+
```
9+
Example 1:
10+
11+
Input: [[1,1],2,[1,1]]
12+
Output: 10
13+
Explanation: Four 1's at depth 2, one 2 at depth 1.
14+
15+
Example 2:
16+
17+
Input: [1,[4,[6]]]
18+
Output: 27
19+
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27.
20+
```
21+
22+
23+
###Solutions:
24+
* Method 1: Recursion
25+
```Java
26+
/**
27+
* // This is the interface that allows for creating nested lists.
28+
* // You should not implement it, or speculate about its implementation
29+
* public interface NestedInteger {
30+
* // Constructor initializes an empty nested list.
31+
* public NestedInteger();
32+
*
33+
* // Constructor initializes a single integer.
34+
* public NestedInteger(int value);
35+
*
36+
* //@return true if this NestedInteger holds a single integer, rather than a nested list.
37+
* public boolean isInteger();
38+
*
39+
* // @return the single integer that this NestedInteger holds, if it holds a single integer
40+
* // Return null if this NestedInteger holds a nested list
41+
* public Integer getInteger();
42+
*
43+
* // Set this NestedInteger to hold a single integer.
44+
* public void setInteger(int value);
45+
*
46+
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
47+
* public void add(NestedInteger ni);
48+
*
49+
* // @return the nested list that this NestedInteger holds, if it holds a nested list
50+
* // Return null if this NestedInteger holds a single integer
51+
* public List<NestedInteger> getList();
52+
* }
53+
*/
54+
classSolution {
55+
privateint sum=0;
56+
publicintdepthSum(List<NestedInteger>nestedList) {
57+
if(nestedList==null|| nestedList.size()==0)return0;
58+
depthSum(nestedList,1);
59+
returnthis.sum;
60+
}
61+
privatevoiddepthSum(List<NestedInteger>nestedList,intdepth){
62+
List<NestedInteger> next=newArrayList<>();
63+
int sum=0;
64+
for(NestedInteger num: nestedList){
65+
if(num.isInteger()) sum+= num.getInteger();
66+
else next.addAll(num.getList());
67+
}
68+
this.sum+= depth* sum;
69+
if(next.size()!=0) depthSum(next, depth+1);
70+
}
71+
}
72+
```

‎leetcode/759. Employee Free Time.md

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
##759. Employee Free Time
2+
3+
###Question
4+
We are given a list schedule of employees, which represents the working time for each employee.
5+
6+
Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.
7+
8+
Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.
9+
10+
```
11+
Example 1:
12+
13+
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
14+
Output: [[3,4]]
15+
Explanation:
16+
There are a total of three employees, and all common
17+
free time intervals would be [-inf, 1], [3, 4], [10, inf].
18+
We discard any intervals that contain inf as they aren't finite.
19+
20+
Example 2:
21+
22+
Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
23+
Output: [[5,6],[7,9]]
24+
```
25+
26+
(Even though we are representing Intervals in the form[x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)
27+
28+
Also, we wouldn't include intervals like[5, 5] in our answer, as they have zero length.
29+
30+
Note:
31+
1. schedule and schedule[i] are lists with lengths in range[1, 50].
32+
2. 0 <= schedule[i].start < schedule[i].end <= 10^8.
33+
34+
35+
###Solution
36+
* Method 1: Sort
37+
```Java
38+
classSolution {
39+
privatestaticfinalComparator<int[]> cmp=newComparator<int[]>(){
40+
@Override
41+
publicintcompare(int[]a,int[]b){
42+
return a[0]== b[0]? (a[1]- b[1]): (a[0]- b[0]);
43+
}
44+
};
45+
publicint[][]employeeFreeTime(int[][][]schedule) {
46+
List<int[]> list=newArrayList<>();
47+
for(int[][] person: schedule){// O(N), N is the total number of intervals
48+
for(int[] interval: person)
49+
list.add(interval);
50+
}
51+
if(list.size()==0)returnnewint[0][2];
52+
Collections.sort(list, cmp);//O(NlgN)
53+
List<int[]> res=newArrayList<>();
54+
int end= list.get(0)[1];
55+
for(int i=1; i< list.size(); i++){// O(N)
56+
int[] cur= list.get(i);
57+
if(cur[0]> end){
58+
res.add(newint[]{end, cur[0]});
59+
}
60+
end=Math.max(end, cur[1]);
61+
}
62+
return res.toArray(newint[0][2]);
63+
}
64+
}
65+
```
Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
##939. Minimum Area Rectangle
2+
3+
###Question
4+
Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.
5+
6+
If there isn't any rectangle, return 0.
7+
8+
```
9+
Example 1:
10+
11+
Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
12+
Output: 4
13+
14+
Example 2:
15+
16+
Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
17+
Output: 2
18+
```
19+
20+
Note:
21+
1. 1 <= points.length <= 500
22+
2. 0 <= points[i][0] <= 40000
23+
3. 0 <= points[i][1] <= 40000
24+
4. All points are distinct.
25+
26+
27+
28+
###Solutions
29+
* Method 1: HashSet O(n^2)
30+
```Java
31+
classSolution {
32+
publicintminAreaRect(int[][]points) {
33+
Set<Integer> set=newHashSet<>();
34+
int len= points.length;
35+
int res=Integer.MAX_VALUE;
36+
for(int i=0; i< len; i++){
37+
int[] first= points[i];
38+
set.add(first[0]*40001+ first[1]);
39+
for(int j= i+1; j< len; j++){
40+
int[] second= points[j];
41+
set.add(second[0]*40001+ second[1]);
42+
if(first[0]== second[0]|| first[1]== second[1])continue;
43+
int find1= second[0]*40001+ first[1], find2= first[0]*40001+ second[1];
44+
if(set.contains(find1)&& set.contains(find2))
45+
res=Math.min(res,Math.abs(first[0]- second[0])*Math.abs(first[1]- second[1]));
46+
}
47+
}
48+
return res==Integer.MAX_VALUE?0: res;
49+
}
50+
}
51+
```
52+
53+
* Method 2: TreeMap + HashMap
54+
```Java
55+
class Solution {
56+
public int minAreaRect(int[][] points) {
57+
Map<Integer, List<Integer>> map = new TreeMap<>();
58+
for(int[] point: points){ //O(nlgn)
59+
int x = point[0], y = point[1];
60+
List<Integer> ys = map.getOrDefault(x, new ArrayList<>());
61+
ys.add(y);
62+
map.put(x, ys);
63+
}
64+
Map<Integer, Integer> last = new HashMap<>(); // key is y diff and x is row number
65+
int res = Integer.MAX_VALUE;
66+
for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()){ //O(n)
67+
List<Integer> list = entry.getValue();
68+
Collections.sort(list); // O(lineNum lg lineNum)
69+
for(int i = 0; i < list.size(); i++){
70+
int first = list.get(i);
71+
for(int j = i + 1; j < list.size(); j++){
72+
int second = list.get(j);
73+
int key = first * 40001 + second;
74+
if(last.containsKey(key)){
75+
res = Math.min(res, Math.abs(first - second) * Math.abs(entry.getKey() - last.get(key)));
76+
}
77+
last.put(key, entry.getKey());
78+
}
79+
}
80+
}
81+
return res == Integer.MAX_VALUE ? 0: res;
82+
}
83+
}
84+
```

‎leetcode/986. Interval List Intersections.md

Lines changed: 30 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ Note:
2424
3. 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9
2525

2626
###Solutions
27-
* Method 1: Sort
27+
* Method 1: Sort head and tail sparately
2828
```Java
2929
classSolution {
3030
publicint[][]intervalIntersection(int[][]A,int[][]B) {
@@ -56,3 +56,32 @@ Note:
5656
}
5757
}
5858
```
59+
60+
* Method 2: Sort with head and tail together.
61+
```Java
62+
class Solution {
63+
public int[][] intervalIntersection(int[][] A, int[][] B) {
64+
int len = A.length + B.length;
65+
if(len == 0) return new int[0][2];
66+
int[][] arr = new int[len][2];
67+
for(int i = 0; i < A.length; i++) arr[i] = A[i];
68+
for(int i = A.length; i < len; i++) arr[i] = B[i - A.length];
69+
Arrays.sort(arr, (a, b)->{
70+
return a[0] == b[0] ? a[1] - b[1]: a[0] - b[0];
71+
});
72+
int end = arr[0][1];
73+
List<int[]> res = new ArrayList<>();
74+
for(int i = 1; i < len; i++){
75+
if(arr[i][0] <= end){
76+
res.add(new int[]{arr[i][0], Math.min(arr[i][1], end)});
77+
}
78+
if(end < arr[i][1])
79+
end = arr[i][1];
80+
}
81+
int size = res.size();
82+
int[][] result = new int[size][2];
83+
for(int i = 0; i < size; i++) result[i] = res.get(i);
84+
return result;
85+
}
86+
}
87+
```

0 commit comments

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