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

Commitfd08e46

Browse files
committed
🎨 Format files (🛠️ from Github Actions)
1 parent5c2b18e commitfd08e46

File tree

142 files changed

+2163
-1991
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

142 files changed

+2163
-1991
lines changed
Lines changed: 20 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1,31 +1,30 @@
11
classSolution {
22

33
publicbooleanisMatch(Strings,Stringp) {
4+
boolean[][]cache =newboolean[s.length() +1][p.length() +1];
45

5-
boolean[][]cache =newboolean[s.length() +1][p.length() +1];
6-
7-
returndfs(cache ,s,p,0 ,0);
8-
}
6+
returndfs(cache,s,p,0,0);
7+
}
98

10-
privatebooleandfs(boolean[][]cache,Strings,Stringp ,inti,intj) {
11-
12-
if(cache[i][j] !=false)
13-
returncache[i][j];
9+
privatebooleandfs(boolean[][]cache,Strings,Stringp,inti,intj) {
10+
if (cache[i][j] !=false)returncache[i][j];
1411

15-
if(i >=s.length() &&j>=p.length())
16-
returntrue;
12+
if (i >=s.length() &&j >=p.length())returntrue;
1713

18-
if(j >=p.length())
19-
returnfalse;
14+
if (j >=p.length())returnfalse;
2015

21-
booleanmatch =i <s.length() && (s.charAt(i) ==p.charAt(j) ||p.charAt(j) =='.');
16+
booleanmatch =
17+
i <s.length() &&
18+
(s.charAt(i) ==p.charAt(j) ||p.charAt(j) =='.');
2219

23-
if(j +1 <p.length() &&p.charAt(j+1)=='*' ) {
24-
cache[i][j] =dfs(cache,s,p,i,j+2) || (match &&dfs(cache,s,p,i+1,j));
25-
}else {
26-
cache[i][j] =match &&dfs(cache,s,p,i+1,j+1);
27-
}
20+
if (j +1 <p.length() &&p.charAt(j +1) =='*') {
21+
cache[i][j] =
22+
dfs(cache,s,p,i,j +2) ||
23+
(match &&dfs(cache,s,p,i +1,j));
24+
}else {
25+
cache[i][j] =match &&dfs(cache,s,p,i +1,j +1);
26+
}
2827

29-
returncache[i][j];
30-
}
31-
}
28+
returncache[i][j];
29+
}
30+
}

‎java/1143-Longest-Common-Subsequence.java

Lines changed: 1 addition & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -20,9 +20,9 @@ public int LCS(String s1, String s2, int i, int j, int[][] dp) {
2020
}
2121
}
2222

23-
2423
// Iterative version
2524
classSolution {
25+
2626
publicintlongestCommonSubsequence(Stringtext1,Stringtext2) {
2727
//O(n*m)/O(n*m) time/memory
2828
if (text1.isEmpty() ||text2.isEmpty()) {
@@ -43,15 +43,12 @@ public int longestCommonSubsequence(String text1, String text2) {
4343
for (intj =1;j <=text2.length();j++) {
4444
if (text1.charAt(i -1) ==text2.charAt(j -1)) {
4545
dp[i][j] =1 +dp[i -1][j -1];
46-
4746
}else {
4847
dp[i][j] =Math.max(dp[i][j -1],dp[i -1][j]);
4948
}
50-
5149
}
5250
}
5351

5452
returndp[text1.length()][text2.length()];
5553
}
5654
}
57-

‎java/115-Distinct-Subsequences.java

Lines changed: 20 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1,43 +1,40 @@
11
// Dynammic Programming - Memoization
22
// Time Complexity O(s * t) | Space Complexity O(s * t)
33
classSolution {
4+
45
publicintnumDistinct(Strings,Stringt) {
5-
66
intn =s.length() +1;
77
intm =t.length() +1;
88
int[][]memo =newint[n][m];
9-
10-
for (int[]row :memo){
11-
Arrays.fill(row, -1);
9+
10+
for (int[]row :memo){
11+
Arrays.fill(row, -1);
1212
}
13-
13+
1414
returnrecursion(s,t,0,0,memo);
15-
1615
}
17-
18-
19-
publicintrecursion(Strings,Stringt,intsIdx,inttIdx,int[][]memo){
20-
21-
if (memo[sIdx][tIdx] != -1){
16+
17+
publicintrecursion(Strings,Stringt,intsIdx,inttIdx,int[][]memo) {
18+
if (memo[sIdx][tIdx] != -1) {
2219
returnmemo[sIdx][tIdx];
2320
}
24-
25-
if (tIdx >=t.length()){
21+
22+
if (tIdx >=t.length()){
2623
return1;
2724
}
28-
29-
if (sIdx >=s.length()){
25+
26+
if (sIdx >=s.length()){
3027
return0;
3128
}
32-
33-
if (t.charAt(tIdx) ==s.charAt(sIdx)){
34-
memo[sIdx][tIdx] =recursion(s,t,sIdx +1,tIdx +1,memo) +recursion(s,t,sIdx +1,tIdx,memo);
35-
returnmemo[sIdx][tIdx];
29+
30+
if (t.charAt(tIdx) ==s.charAt(sIdx)) {
31+
memo[sIdx][tIdx] =
32+
recursion(s,t,sIdx +1,tIdx +1,memo) +
33+
recursion(s,t,sIdx +1,tIdx,memo);
34+
returnmemo[sIdx][tIdx];
3635
}
37-
36+
3837
memo[sIdx][tIdx] =recursion(s,t,sIdx +1,tIdx,memo);
3938
returnmemo[sIdx][tIdx];
40-
4139
}
42-
43-
}
40+
}
Lines changed: 12 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,18 @@
11
classSolution {
22

33
publicintmaxProfit(int[]prices) {
4-
intleft =0;
5-
intright =1;
6-
intmaxProfit =0;
7-
while (right <prices.length) {
8-
if (prices[left] <prices[right]) {
9-
maxProfit =Math.max(maxProfit,prices[right] -prices[left]);
10-
right++;
11-
}else {
12-
left =right;
13-
right++;
4+
intleft =0;
5+
intright =1;
6+
intmaxProfit =0;
7+
while (right <prices.length) {
8+
if (prices[left] <prices[right]) {
9+
maxProfit =Math.max(maxProfit,prices[right] -prices[left]);
10+
right++;
11+
}else {
12+
left =right;
13+
right++;
14+
}
1415
}
15-
}
16-
returnmaxProfit;
16+
returnmaxProfit;
1717
}
1818
}

‎java/124-Binary-Tree-Maximum-Path-Sum.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -14,20 +14,20 @@
1414
* }
1515
*/
1616
classSolution {
17+
1718
publicintmaxPathSum(TreeNoderoot) {
1819
int[]res = {Integer.MIN_VALUE };
1920
maxPathSum(root,res);
2021
returnres[0];
2122
}
2223

2324
publicintmaxPathSum(TreeNoderoot,int[]res) {
24-
if (root ==null)
25-
return0;
25+
if (root ==null)return0;
2626

2727
intleft =Math.max(0,maxPathSum(root.left,res));
2828
intright =Math.max(0,maxPathSum(root.right,res));
2929
res[0] =Math.max(res[0],root.val +left +right);
3030

3131
returnroot.val +Math.max(left,right);
3232
}
33-
}
33+
}

‎java/127-Word-Ladder.java

Lines changed: 29 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,48 +1,57 @@
11
packagejava;
2+
23
classSolution {
3-
publicintladderLength(StringbeginWord,StringendWord,List<String>wordList) {
4+
5+
publicintladderLength(
6+
StringbeginWord,
7+
StringendWord,
8+
List<String>wordList
9+
) {
410
Map<String,List<String>>adjlist =newHashMap<>();
511
wordList.add(beginWord);
6-
for(Stringword:wordList){
7-
StringBuilderstring=null;
8-
for(inti=0;i<word.length();i++){
9-
string =newStringBuilder(word);
10-
string.setCharAt(i,'*');
11-
List<String>wordlist =adjlist.getOrDefault(string.toString(),newArrayList<String>());
12-
wordlist.add(word);
13-
adjlist.put(string.toString(),wordlist);
12+
for (Stringword :wordList) {
13+
StringBuilderstring =null;
14+
for (inti =0;i <word.length();i++) {
15+
string =newStringBuilder(word);
16+
string.setCharAt(i,'*');
17+
List<String>wordlist =adjlist.getOrDefault(
18+
string.toString(),
19+
newArrayList<String>()
20+
);
21+
wordlist.add(word);
22+
adjlist.put(string.toString(),wordlist);
1423
}
1524
}
16-
25+
1726
Queue<String>queue =newLinkedList<>();
1827
queue.offer(beginWord);
1928
Set<String>visited =newHashSet<>();
2029
visited.add(beginWord);
2130
intstep =1;
22-
StringBuilderstring=null;
23-
while(!queue.isEmpty()){
24-
step++;
31+
StringBuilderstring =null;
32+
while(!queue.isEmpty()){
33+
step++;
2534
intsize =queue.size();
26-
for(intj=0;j<size;j++){
35+
for(intj =0;j <size;j++){
2736
Stringstr =queue.poll();
2837

29-
for(inti=0;i<str.length();i++){
38+
for(inti =0;i <str.length();i++){
3039
string =newStringBuilder(str);
3140
string.setCharAt(i,'*');
32-
for(Stringpat:adjlist.get(string.toString())){
33-
if(pat.equals(endWord)){
41+
for(Stringpat :adjlist.get(string.toString())){
42+
if(pat.equals(endWord)){
3443
returnstep;
3544
}
36-
if(visited.contains(pat)){
45+
if(visited.contains(pat)){
3746
continue;
3847
}
3948
queue.offer(pat);
4049
visited.add(pat);
4150
}
42-
}
51+
}
4352
}
4453
// step++;
4554
}
4655
return0;
4756
}
48-
}
57+
}
Lines changed: 18 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1,35 +1,36 @@
11
classSolution {
2+
23
// Time Complexity: O(N^2 log(N)) where N is the length of points. N^2 comes from the fact we need to find the distance between a currNode and every other node to pick the shortest distance. log(N) comes from Priority Queue
34
// Space Complexity: O(N^2)
45
publicintminCostConnectPoints(int[][]points) {
5-
PriorityQueue<int[]>pq =newPriorityQueue<>((a,b) ->a[0] -b[0]);// edge weight, the index of next node
6-
pq.offer(newint[]{0,0});
6+
PriorityQueue<int[]>pq =newPriorityQueue<>((a,b) ->a[0] -b[0]);// edge weight, the index of next node
7+
pq.offer(newint[] {0,0});
78
intlen =points.length;
89
Set<Integer>visited =newHashSet<>();
910
intcost =0;
10-
11-
// When visited.size() == points.len meaning that all the nodes has been connected.
12-
while(visited.size() <len){
11+
12+
// When visited.size() == points.len meaning that all the nodes has been connected.
13+
while(visited.size() <len){
1314
int[]arr =pq.poll();
14-
15+
1516
intweight =arr[0];
1617
intcurrNode =arr[1];
17-
18-
if(visited.contains(currNode))
19-
continue;
20-
18+
19+
if (visited.contains(currNode))continue;
20+
2121
visited.add(currNode);
2222
cost +=weight;
23-
24-
for(intnextNode =0;nextNode <len;nextNode++){
25-
if(!visited.contains(nextNode)){
26-
intnextWeight =Math.abs(points[nextNode][0] -points[currNode][0]) +Math.abs(points[nextNode][1] -points[currNode][1]);
27-
pq.offer(newint[]{nextWeight,nextNode});
23+
24+
for (intnextNode =0;nextNode <len;nextNode++) {
25+
if (!visited.contains(nextNode)) {
26+
intnextWeight =
27+
Math.abs(points[nextNode][0] -points[currNode][0]) +
28+
Math.abs(points[nextNode][1] -points[currNode][1]);
29+
pq.offer(newint[] {nextWeight,nextNode });
2830
}
2931
}
3032
}
31-
32-
33+
3334
returncost;
3435
}
3536
}

0 commit comments

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