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

Commita783111

Browse files
committed
greedy
1 parent3c7c731 commita783111

File tree

5 files changed

+35
-12
lines changed

5 files changed

+35
-12
lines changed

‎algorithm/dp/LongestPalindrome_dp1.java

Lines changed: 6 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ public static String longestPalindrome1(String s) {
1515
intlen =s.length();
1616

1717
// Record i-j is a palindrome.
18-
boolean[][]D =newint[len][len];
18+
boolean[][]D =newboolean[len][len];
1919
for (inti =0;i <len;i++) {
2020
for (intj =0;j <len;j++) {
2121
D[i][j] =false;
@@ -25,9 +25,6 @@ public static String longestPalindrome1(String s) {
2525
intmax =0;
2626
intretB =0;
2727
intretE =0;
28-
// 这样写的目的是，从前往后扫描时，被记录的DP值可以被复用
29-
// 因为D[i][j] 要用到i + 1, j - 1，所以每一次计算j时，把j对应的i全部计算完，这样
30-
// 下一次计算i,j的时候，可以有i+1, j-1可以用。
3128
for (intj =0;j <len;j++) {
3229
for (inti =0;i <=j;i++) {
3330
if (s.charAt(i) ==s.charAt(j)
@@ -48,8 +45,8 @@ public static String longestPalindrome1(String s) {
4845
returns.substring(retB,retE +1);
4946
}
5047

51-
// solution 2:中心展开法。从头扫到尾部，每一个字符以它为中心向两边扩展，找最长回文。
52-
//复杂度为N^2并且是inplace，空间复杂度O(1)
48+
// solution 2:���������������������������������������������������������������������������������������������������������
49+
//������������N^2���������inplace������������������O(1)
5350
publicstaticStringlongestPalindrome(Strings) {
5451
if (s ==null) {
5552
returnnull;
@@ -65,14 +62,14 @@ public static String longestPalindrome(String s) {
6562
Stringret ="";
6663

6764
for (inti =0;i <len;i++) {
68-
//考虑奇数字符串
65+
//���������������������
6966
Strings1 =expandAround(s,i,i);
7067
if (s1.length() >max) {
7168
ret =s1;
7269
max =s1.length();
7370
}
7471

75-
//考虑偶数长度的字符串
72+
//������������������������������
7673
Strings2 =expandAround(s,i,i);
7774
if (s2.length() >max) {
7875
ret =s2;
@@ -95,7 +92,7 @@ public static String expandAround(String s, int c1, int c2) {
9592
c2--;
9693
}
9794

98-
//注意，根据 substring的定义，c2不要减1
95+
//��������������� substring������������c2���������1
9996
returns.substring(c1 +1,c2);
10097
}
10198
}

‎greedy/Jump.java

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageAlgorithms.greedy;
2+
3+
publicclassJump {
4+
publicintjump(int[]A) {
5+
if (A ==null ||A.length ==0) {
6+
return0;
7+
}
8+
9+
intlen =A.length;
10+
11+
intsum =0;
12+
13+
intdes =len -1;
14+
while (des >0) {// destination index
15+
for (inti =0;i <des;i++) {// 不断向前移动dest
16+
if (A[i] +i >=des) {// 说明从i位置能1步到达dest的位置
17+
sum++;
18+
des =i;// 更新dest位置，下一步就是计算要几步能调到当前i的位置
19+
break;// 没必要再继续找，因为越早找到的i肯定越靠前，说明这一跳的距离越远
20+
}
21+
}
22+
}
23+
24+
returnsum;
25+
}
26+
}

‎sort/SortList.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -212,7 +212,7 @@ public static ListNode quickSort(ListNode head) {
212212
}
213213

214214
// Return the new head;
215-
publicListNodepartition(ListNodehead,intx) {
215+
publicstaticListNodepartition(ListNodehead,intx) {
216216
if (head ==null) {
217217
returnnull;
218218
}

‎string/LongestValidParentheses.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@ public static void main(String[] strs) {
77
System.out.println(longestValidParentheses("(()()())"));
88
}
99

10-
publicintlongestValidParentheses(Strings) {
10+
publicstaticintlongestValidParentheses(Strings) {
1111
if (s ==null) {
1212
return0;
1313
}

‎tree/TreeLinkNode.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,6 @@ public class TreeLinkNode {
33
intval;
44
publicTreeLinkNodeleft;
55
publicTreeLinkNoderight;
6-
TreeLinkNodenext;
6+
publicTreeLinkNodenext;
77
publicTreeLinkNode(intx) {val =x; }
88
}

0 commit comments

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