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

Commit0f854a6

Browse files
author
Botao Xiao
committed
[Function add]: 1. Add leetcode solutions.
1 parent83feef3 commit0f854a6

3 files changed

+212
-0
lines changed
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+
classSolution {
55+
privateint max=0;
56+
privateint sum;
57+
publicintdepthSumInverse(List<NestedInteger>nestedList) {
58+
if(nestedList==null|| nestedList.size()==0)return0;
59+
maxDepth(nestedList,1);
60+
dfs(nestedList,1);
61+
return sum;
62+
}
63+
privatevoiddfs(List<NestedInteger>nestedList,intdepth){
64+
int cur=0;
65+
List<NestedInteger> next=newArrayList<>();
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+
privatevoidmaxDepth(List<NestedInteger>nestedList,intdepth){
77+
List<NestedInteger> next=newArrayList<>();
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+
```
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+
classSolution {
30+
privatechar[] arr;
31+
publicintcountSubstrings(Strings) {
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+
privateintexpand(inti,intj){
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+
classSolution {
53+
publicintcountSubstrings(Strings) {
54+
int len= s.length();
55+
boolean[][] dp=newboolean[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)
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+
classSolution {
30+
publicint[][]intervalIntersection(int[][]A,int[][]B) {
31+
int len=A.length+B.length;
32+
int[] starts=newint[len];
33+
int[] ends=newint[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=newArrayList<>();
45+
for(int i=1; i< starts.length; i++){
46+
if(starts[i]<= ends[i-1]){
47+
res.add(newint[]{starts[i], ends[i-1]});
48+
}
49+
}
50+
int size= res.size();
51+
int[][] result=newint[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)
[8]ページ先頭
©2009-2025 Movatter.jp