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

Commit08d4dc5

Browse files
committed
Modified 3 solutions
1 parent897a32d commit08d4dc5

File tree

3 files changed

+55
-79
lines changed

3 files changed

+55
-79
lines changed
Lines changed: 13 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,42 +1,36 @@
11
classSolution {
2-
int[][]dp;
2+
int[][]dirs = {{1,0}, {0,1}, {-1,0}, {0, -1}};
33
publicintlongestIncreasingPath(int[][]matrix) {
44
if (matrix.length ==0 ||matrix[0].length ==0) {
55
return0;
66
}
77

8+
int[][]dp =newint[matrix.length][matrix[0].length];
89
intmax =0;
9-
dp =newint[matrix.length][matrix[0].length];
10-
1110
for (inti =0;i <matrix.length;i++) {
1211
for (intj =0;j <matrix[0].length;j++) {
13-
max =Math.max(max,getIncreasingPathLength(matrix,i,j,Integer.MIN_VALUE));
12+
max =Math.max(max,dfs(matrix,i,j,dp,Integer.MIN_VALUE));
1413
}
1514
}
1615

1716
returnmax;
1817
}
1918

20-
privateintgetIncreasingPathLength(int[][]matrix,introw,intcol,intprev) {
21-
if (row <0 ||
22-
col <0 ||
23-
row >=matrix.length ||
24-
col >=matrix[0].length ||
25-
matrix[row][col] <=prev) {
19+
privateintdfs(int[][]matrix,intx,inty,int[][]dp,intprevVal) {
20+
if (x <0 ||x >=matrix.length ||y <0 ||y >=matrix[0].length ||matrix[x][y] <=prevVal) {
2621
return0;
2722
}
2823

29-
if (dp[row][col] !=0) {
30-
returndp[row][col];
24+
if (dp[x][y] !=0) {
25+
returndp[x][y];
3126
}
3227

33-
intup =getIncreasingPathLength(matrix,row -1,col,matrix[row][col]);
34-
intdown =getIncreasingPathLength(matrix,row +1,col,matrix[row][col]);
35-
intright =getIncreasingPathLength(matrix,row,col +1,matrix[row][col]);
36-
intleft =getIncreasingPathLength(matrix,row,col -1,matrix[row][col]);
37-
38-
dp[row][col] =1 +Math.max(Math.max(up,down),Math.max(right,left));
28+
inttemp =0;
29+
for (int[]dir :dirs) {
30+
temp =Math.max(temp,dfs(matrix,x +dir[0],y +dir[1],dp,matrix[x][y]));
31+
}
3932

40-
returndp[row][col];
33+
dp[x][y] =temp +1;
34+
returndp[x][y];
4135
}
4236
}

‎Medium/Flatten Nested List Iterator.java

Lines changed: 19 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -16,41 +16,35 @@
1616
* }
1717
*/
1818
publicclassNestedIteratorimplementsIterator<Integer> {
19-
List<Integer>list;
20-
intindex;
21-
intsize;
22-
publicNestedIterator(List<NestedInteger>nestedList) {
23-
list =newArrayList<>();
24-
index =0;
25-
for (NestedIntegern :nestedList) {
26-
dfsHelper(n);
27-
}
28-
29-
size =list.size();
30-
}
3119

32-
privatevoiddfsHelper(NestedIntegern) {
33-
if (n.isInteger()) {
34-
list.add(n.getInteger());
35-
}
36-
else {
37-
for (NestedIntegerni :n.getList()) {
38-
dfsHelper(ni);
39-
}
20+
Stack<NestedInteger>stack;
21+
publicNestedIterator(List<NestedInteger>nestedList) {
22+
stack =newStack<>();
23+
for (inti =nestedList.size() -1;i >=0;i--) {
24+
stack.push(nestedList.get(i));
4025
}
4126
}
4227

4328
@Override
4429
publicIntegernext() {
45-
if (index <size) {
46-
returnlist.get(index++);
47-
}
48-
return -1;
30+
returnstack.pop().getInteger();
4931
}
5032

5133
@Override
5234
publicbooleanhasNext() {
53-
return !(index ==size);
35+
while (!stack.isEmpty()) {
36+
NestedIntegercurr =stack.peek();
37+
if (curr.isInteger()) {
38+
returntrue;
39+
}
40+
41+
NestedIntegertemp =stack.pop();
42+
for (inti =temp.getList().size() -1;i >=0;i--) {
43+
stack.push(temp.getList().get(i));
44+
}
45+
}
46+
47+
returnfalse;
5448
}
5549
}
5650

Lines changed: 23 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -1,47 +1,35 @@
11
classSolution {
2-
32
publicStringfrequencySort(Strings) {
4-
Map<Character,Integer>map =newHashMap<>();
5-
6-
for (inti=0;i<s.length();i++) {
7-
if (map.containsKey(s.charAt(i))) {
8-
map.put(s.charAt(i),map.get(s.charAt(i))+1);
9-
}
10-
else {
11-
map.put(s.charAt(i),1);
12-
}
3+
List<Character>chars =newArrayList<>();
4+
for (charc :s.toCharArray()) {
5+
chars.add(c);
136
}
147

15-
Map<Character,Integer>sortedMap =sortByValue(map);
16-
17-
18-
StringBuildersb =newStringBuilder("");
19-
20-
for (Map.Entry<Character,Integer>entry :sortedMap.entrySet()) {
21-
Stringt =String.join("",Collections.nCopies(entry.getValue(),String.valueOf(entry.getKey())));
22-
sb.append(t);
8+
Map<Character,Integer>map =newHashMap<>();
9+
intval =0;
10+
for (charc :chars) {
11+
map.put(c,map.getOrDefault(c,0) +1);
12+
val =Math.max(val,map.get(c));
2313
}
2414

25-
returnsb.toString();
26-
}
27-
28-
privateMap<Character,Integer>sortByValue(Map<Character,Integer>unsortMap) {
29-
30-
List<Map.Entry<Character,Integer>>list =
31-
newLinkedList<Map.Entry<Character,Integer>>(unsortMap.entrySet());
15+
Map<Integer,List<Character>>revMap =newHashMap<>();
16+
for (Characterkey :map.keySet()) {
17+
revMap.computeIfAbsent(map.get(key),k ->newArrayList<>()).add(key);
18+
}
3219

33-
Collections.sort(list,newComparator<Map.Entry<Character,Integer>>() {
34-
publicintcompare(Map.Entry<Character,Integer>o1,
35-
Map.Entry<Character,Integer>o2) {
36-
return (o2.getValue()).compareTo(o1.getValue());
20+
StringBuildersb =newStringBuilder();
21+
for (inti =val;i >=0;i--) {
22+
if (revMap.containsKey(i)) {
23+
List<Character>characters =revMap.get(i);
24+
for (Charactercharacter :characters) {
25+
intcount =i;
26+
while (count-- >0) {
27+
sb.append(character);
28+
}
29+
}
3730
}
38-
});
39-
40-
Map<Character,Integer>sortedMap =newLinkedHashMap<Character,Integer>();
41-
for (Map.Entry<Character,Integer>entry :list) {
42-
sortedMap.put(entry.getKey(),entry.getValue());
4331
}
4432

45-
returnsortedMap;
33+
returnsb.toString();
4634
}
4735
}

0 commit comments

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