Skip to content

Commit 0f854a6

Browse files
author
Botao Xiao
committed
[Function add]: 1. Add leetcode solutions.
1 parent 83feef3 commit 0f854a6

3 files changed

+212
-0
lines changed

‎leetcode/364. Nested List Weight Sum II.md

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
## 364. Nested List Weight Sum II
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+
Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.
9+
10+
```
11+
Example 1:
12+
13+
Input: [[1,1],2,[1,1]]
14+
Output: 8
15+
Explanation: Four 1's at depth 1, one 2 at depth 2.
16+
Example 2:
17+
18+
Input: [1,[4,[6]]]
19+
Output: 17
20+
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17.
21+
```
22+
23+
### Solution
24+
* Method 1: Recursion. O(nlgn)
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+
class Solution {
55+
private int max = 0;
56+
private int sum;
57+
public int depthSumInverse(List<NestedInteger> nestedList) {
58+
if(nestedList == null || nestedList.size() == 0) return 0;
59+
maxDepth(nestedList, 1);
60+
dfs(nestedList, 1);
61+
return sum;
62+
}
63+
private void dfs(List<NestedInteger> nestedList, int depth){
64+
int cur = 0;
65+
List<NestedInteger> next = new ArrayList<>();
66+
for(NestedInteger num : nestedList){
67+
if(num.isInteger()){
68+
cur += num.getInteger();
69+
}else{
70+
next.addAll(num.getList());
71+
}
72+
}
73+
if(!next.isEmpty()) dfs(next, depth + 1);
74+
sum += cur * (max - depth + 1);
75+
}
76+
private void maxDepth(List<NestedInteger> nestedList, int depth){
77+
List<NestedInteger> next = new ArrayList<>();
78+
max = Math.max(max, depth);
79+
for(NestedInteger num : nestedList){
80+
if(!num.isInteger()) next.addAll(num.getList());
81+
}
82+
if(!next.isEmpty()) maxDepth(next, depth + 1);
83+
}
84+
}
85+
```

‎leetcode/647. Palindromic Substrings.md

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
## 647. Palindromic Substrings
2+
3+
### Question
4+
Given a string, your task is to count how many palindromic substrings in this string.
5+
6+
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
7+
8+
```
9+
Example 1:
10+
11+
Input: "abc"
12+
Output: 3
13+
Explanation: Three palindromic strings: "a", "b", "c".
14+
15+
16+
Example 2:
17+
18+
Input: "aaa"
19+
Output: 6
20+
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
21+
```
22+
23+
Note:
24+
* The input string length won't exceed 1000.
25+
26+
### Solutions
27+
* Method 1: O(n^2) => two sides insert values
28+
```Java
29+
class Solution {
30+
private char[] arr;
31+
public int countSubstrings(String s) {
32+
arr = s.toCharArray();
33+
int sum = 0;
34+
for(int i = 0; i < arr.length; i++){
35+
sum += expand(i, i);
36+
sum += expand(i, i + 1);
37+
}
38+
return sum;
39+
}
40+
private int expand(int i, int j){
41+
int res = 0;
42+
while(i >= 0 && j < arr.length && arr[i--] == arr[j++]){
43+
res++;
44+
}
45+
return res;
46+
}
47+
}
48+
```
49+
50+
* Method 2: dp
51+
```Java
52+
class Solution {
53+
public int countSubstrings(String s) {
54+
int len = s.length();
55+
boolean[][] dp = new boolean[len][len];
56+
int res = 0;
57+
for(int i = len - 1; i >= 0; i--){
58+
for(int j = i; j < len; j++){
59+
dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i < 3 || dp[i + 1][j - 1]);
60+
if(dp[i][j]) res++;
61+
}
62+
}
63+
return res;
64+
}
65+
}
66+
```
67+
68+
### Reference
69+
1. [Java DP solution based on longest palindromic substring](https://leetcode.com/problems/palindromic-substrings/discuss/105707/Java-DP-solution-based-on-longest-palindromic-substring)

‎leetcode/986. Interval List Intersections.md

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
## 986. Interval List Intersections
2+
3+
### Question
4+
Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.
5+
6+
Return the intersection of these two interval lists.
7+
8+
(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)
9+
10+
11+
```
12+
Example 1:
13+
14+
15+
16+
Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
17+
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
18+
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.
19+
```
20+
21+
Note:
22+
1. 0 <= A.length < 1000
23+
2. 0 <= B.length < 1000
24+
3. 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9
25+
26+
### Solutions
27+
* Method 1: Sort
28+
```Java
29+
class Solution {
30+
public int[][] intervalIntersection(int[][] A, int[][] B) {
31+
int len = A.length + B.length;
32+
int[] starts = new int[len];
33+
int[] ends = new int[len];
34+
for(int i = 0; i < A.length; i++){
35+
starts[i] = A[i][0];
36+
ends[i] = A[i][1];
37+
}
38+
for(int i = A.length; i < A.length + B.length; i++){
39+
starts[i] = B[i - A.length][0];
40+
ends[i] = B[i - A.length][1];
41+
}
42+
Arrays.sort(starts);
43+
Arrays.sort(ends);
44+
List<int[]> res = new ArrayList<>();
45+
for(int i = 1; i < starts.length; i++){
46+
if(starts[i] <= ends[i - 1]){
47+
res.add(new int[]{starts[i], ends[i - 1]});
48+
}
49+
}
50+
int size = res.size();
51+
int[][] result = new int[size][2];
52+
for(int i = 0; i < size; i++){
53+
result[i] = res.get(i);
54+
}
55+
return result;
56+
}
57+
}
58+
```

0 commit comments

Comments
 (0)