Commit3af42c9

committed

palindrome

1 parent0038568 commit3af42c9Copy full SHA for 3af42c9

File tree

+106

-6

lines changed

+106

-6

lines changed

Lines changed: 46 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,46 @@`
	`1`	`+packageAlgorithms.algorithm.dp;`
	`2`	`+`
	`3`	`+publicclassLongestPalindrome {`
	`4`	`+publicstaticvoidmain(String[]args) {`
	`5`	`+Strings ="cadfasdfsadfabaabaed";`
	`6`	`+System.out.println(longestPalindrome(s));`
	`7`	`+ }`
	`8`	`+`
	`9`	`+// Solution 1: Brute Force`
	`10`	`+publicstaticStringlongestPalindrome(Strings) {`
	`11`	`+if (s ==null) {`
	`12`	`+returnnull;`
	`13`	`+ }`
	`14`	`+`
	`15`	`+intlen =s.length();`
	`16`	`+`
	`17`	`+intmax =0;`
	`18`	`+intbegin =0;`
	`19`	`+intend =0;`
	`20`	`+for (inti =0;i <len;i++) {`
	`21`	`+for (intj =i;j <len;j++) {`
	`22`	`+if (dfs(s,i,j)) {`
	`23`	`+if (j -i +1 >max) {`
	`24`	`+max =j -i +1;`
	`25`	`+begin =i;`
	`26`	`+end =j;`
	`27`	`+ }`
	`28`	`+ }`
	`29`	`+ }`
	`30`	`+ }`
	`31`	`+`
	`32`	`+returns.substring(begin,end +1);`
	`33`	`+ }`
	`34`	`+`
	`35`	`+publicstaticbooleandfs(Strings,inti,intj) {`
	`36`	`+if (i >=j) {`
	`37`	`+returntrue;`
	`38`	`+ }`
	`39`	`+`
	`40`	`+if (s.charAt(i) ==s.charAt(j)) {`
	`41`	`+returndfs(s,i +1,j -1);`
	`42`	`+ }`
	`43`	`+`
	`44`	`+returnfalse;`
	`45`	`+ }`
	`46`	`+}`

Lines changed: 46 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,46 @@`
	`1`	`+packageAlgorithms.algorithm.dp;`
	`2`	`+`
	`3`	`+publicclassLongestPalindrome_dp1 {`
	`4`	`+publicstaticvoidmain(String[]args) {`
	`5`	`+Strings ="cabaabad";`
	`6`	`+System.out.println(longestPalindrome(s));`
	`7`	`+ }`
	`8`	`+`
	`9`	`+// Solution 1:`
	`10`	`+publicstaticStringlongestPalindrome(Strings) {`
	`11`	`+if (s ==null) {`
	`12`	`+returnnull;`
	`13`	`+ }`
	`14`	`+`
	`15`	`+intlen =s.length();`
	`16`	`+`
	`17`	`+// Record i-j is a palindrome.`
	`18`	`+boolean[][]D =newboolean[len][len];`
	`19`	`+`
	`20`	`+intmax =0;`
	`21`	`+intretB =0;`
	`22`	`+intretE =0;`
	`23`	`+// 这样写的目的是，从前往后扫描时，被记录的DP值可以被复用`
	`24`	`+// 因为D[i][j] 要用到i + 1, j - 1，所以每一次计算j时，把j对应的i全部计算完，这样`
	`25`	`+// 下一次计算i,j的时候，可以有i+1, j-1可以用。`
	`26`	`+for (intj =0;j <len;j++) {`
	`27`	`+for (inti =0;i <=j;i++) {`
	`28`	`+if (s.charAt(i) ==s.charAt(j)`
	`29`	`+ && (j -i <=2 \|\|D[i +1][j -1])`
	`30`	`+ ) {`
	`31`	`+D[i][j] =true;`
	`32`	`+`
	`33`	`+if (j -i +1 >max) {`
	`34`	`+retB =i;`
	`35`	`+retE =j;`
	`36`	`+max =j -i +1;`
	`37`	`+ }`
	`38`	`+ }else {`
	`39`	`+D[i][j] =false;`
	`40`	`+ }`
	`41`	`+ }`
	`42`	`+ }`
	`43`	`+`
	`44`	`+returns.substring(retB,retE +1);`
	`45`	`+ }`
	`46`	`+}`

Lines changed: 14 additions & 6 deletions

Original file line number	Diff line number	Diff line change
`@@ -6,14 +6,14 @@`
`6`	`6`	`* 给定一个未排序的数组，请给出波浪状排序：`
`7`	`7`	`* Example:`
`8`	`8`	`* input: 1 2 5 4 3 9`
`9`		`- * output: 1 4 32 5 9`
	`9`	`+ * output: 1 4 35 2 9`
`10`	`10`	`*`
`11`	`11`	`* input: 1 2 2 5 3 9`
`12`	`12`	`* output: 1 5 2 3 2 9`
`13`	`13`	`* */`
`14`	`14`	`publicclassWaveSort {`
`15`	`15`	`publicstaticvoidmain(String[]str) {`
`16`		`-int[]in = {1,2,5,4,3,9,12};`
	`16`	`+int[]in = {1,2,5,4,3,9,9,9,12};`
`17`	`17`
`18`	`18`	`for (inti:in) {`
`19`	`19`	`System.out.print(i +" ");`
`@@ -40,12 +40,20 @@ public static void waveSort(int[] in) {`
`40`	`40`
`41`	`41`	`Arrays.sort(in);`
`42`	`42`
	`43`	`+for (inti:in) {`
	`44`	`+System.out.print(i +" ");`
	`45`	`+ }`
	`46`	`+System.out.println();`
	`47`	`+`
`43`	`48`	`for (inti =0;i <len;i++) {`
`44`	`49`	`if (i %2 ==0) {`
`45`		`-if (i +1 <len) {`
`46`		`-inttmp =in[i];`
`47`		`-in[i] =in[i +1];`
`48`		`-in[i +1] =tmp;`
	`50`	`+for (intj =i +1;j <len;j++) {`
	`51`	`+if (in[j] !=in[i]) {`
	`52`	`+inttmp =in[i];`
	`53`	`+in[i] =in[j];`
	`54`	`+in[j] =tmp;`
	`55`	`+break;`
	`56`	`+ }`
`49`	`57`	`}`
`50`	`58`	`}`
`51`	`59`	`}`

Comments

(0)