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

Commit6e2cf14

Browse files
committed
feat: add 006
1 parent4ee26f8 commit6e2cf14

File tree

3 files changed

+177
-0
lines changed

3 files changed

+177
-0
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -70,6 +70,7 @@
7070
| 2|[Add Two Numbers][002]| Linked List, Math|
7171
| 3|[Longest Substring Without Repeating Characters][003]| Hash Table, Two Pointers, String|
7272
| 5|[Longest Palindromic Substring][005]| String|
73+
| 6|[ZigZag Conversion][006]| String|
7374
| 8|[String to Integer (atoi)][008]| Math, String|
7475
| 15|[3Sum][015]| Array, Two Pointers|
7576
| 17|[Letter Combinations of a Phone Number][017]| String, Backtracking|
@@ -138,6 +139,7 @@
138139
[002]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/002/README.md
139140
[003]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/003/README.md
140141
[005]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/005/README.md
142+
[005]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/006/README.md
141143
[008]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/008/README.md
142144
[015]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/015/README.md
143145
[017]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/017/README.md

‎note/006/README.md

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
#[Longest Palindromic Substring][title]
2+
3+
##Description
4+
5+
The string`"PAYPALISHIRING"` is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
6+
7+
```
8+
P A H N
9+
A P L S I I G
10+
Y I R
11+
```
12+
13+
And then read line by line:`"PAHNAPLSIIGYIR"`
14+
15+
Write the code that will take a string and make this conversion given a number of rows:
16+
17+
```
18+
string convert(string text, int nRows);
19+
```
20+
21+
`convert("PAYPALISHIRING", 3)` should return`"PAHNAPLSIIGYIR"`.
22+
23+
**Tags:** String
24+
25+
26+
##思路 0
27+
28+
题意是让你把字符串按波浪形排好，然后返回横向读取的字符串。
29+
30+
听不懂的话，看下图应该就明白了：
31+
32+
```
33+
34+
0 2n-2 4n-4
35+
1 2n-3 2n-1 4n-5 4n-5
36+
2 2n-4 2n 4n-6 .
37+
. . . . .
38+
. n+1 . 3n-1 .
39+
n-2 n 3n-4 3n-2 5n-6
40+
n-1 3n-3 5n-5
41+
42+
```
43+
44+
那么我们可以根据上图找规律，可以看到最波峰和波谷是单顶点的，它们周期是`2 * (n - 1)`，单独处理即可；中间的部分每个周期会出现两次，规律很好找，留给读者自己想象，不懂的可以结合以下代码。
45+
46+
```java
47+
classSolution {
48+
publicStringconvert(Strings,intnumRows) {
49+
if (numRows<=1)return s;
50+
int len= s.length();
51+
char[] chars= s.toCharArray();
52+
int cycle=2* (numRows-1);
53+
StringBuilder sb=newStringBuilder();
54+
for (int j=0; j< len; j+= cycle) {
55+
sb.append(chars[j]);
56+
}
57+
for (int i=1; i< numRows-1; i++) {
58+
int step=2* i;
59+
for (int j= i; j< len; j+= step) {
60+
sb.append(chars[j]);
61+
step= cycle- step;
62+
}
63+
}
64+
for (int j= numRows-1; j< len; j+= cycle) {
65+
sb.append(chars[j]);
66+
}
67+
return sb.toString();
68+
}
69+
}
70+
```
71+
72+
73+
##思路 1
74+
75+
另外一种思路就是开辟相应行数的`StringBuilder` 对象，然后模拟波浪生成的样子分别插入到相应的`StringBuilder` 对象，具体代码如下，比较直白简单。
76+
77+
```java
78+
classSolution {
79+
publicStringconvert(Strings,intnumRows) {
80+
if (numRows<=1)return s;
81+
int len= s.length();
82+
char[] chars= s.toCharArray();
83+
StringBuilder[] sbs=newStringBuilder[numRows];
84+
for (int i=0; i< numRows; i++) {
85+
sbs[i]=newStringBuilder();
86+
}
87+
int i=0;
88+
while (i< len) {
89+
for (int j=0; j< numRows&& i< len;++j) {
90+
sbs[j].append(chars[i++]);
91+
}
92+
for (int j= numRows-2; j>=1&& i< len;--j) {
93+
sbs[j].append(chars[i++]);
94+
}
95+
}
96+
for (i=1; i< numRows; i++) {
97+
sbs[0].append(sbs[i]);
98+
}
99+
return sbs[0].toString();
100+
}
101+
}
102+
```
103+
104+
105+
##结语
106+
107+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-java-leetcode][ajl]
108+
109+
110+
111+
[title]:https://leetcode.com/problems/longest-palindromic-substring
112+
[ajl]:https://github.com/Blankj/awesome-java-leetcode
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
packagecom.blankj.medium._006;
2+
3+
/**
4+
* <pre>
5+
* author: Blankj
6+
* blog : http://blankj.com
7+
* time : 2017/12/11
8+
* desc :
9+
* </pre>
10+
*/
11+
classSolution {
12+
13+
// public String convert(String s, int numRows) {
14+
// if (numRows <= 1) return s;
15+
// int len = s.length();
16+
// char[] chars = s.toCharArray();
17+
// int cycle = 2 * (numRows - 1);
18+
// StringBuilder sb = new StringBuilder();
19+
// for (int j = 0; j < len; j += cycle) {
20+
// sb.append(chars[j]);
21+
// }
22+
// for (int i = 1; i < numRows - 1; i++) {
23+
// int step = 2 * i;
24+
// for (int j = i; j < len; j += step) {
25+
// sb.append(chars[j]);
26+
// step = cycle - step;
27+
// }
28+
// }
29+
// for (int j = numRows - 1; j < len; j += cycle) {
30+
// sb.append(chars[j]);
31+
// }
32+
// return sb.toString();
33+
// }
34+
35+
publicStringconvert(Strings,intnumRows) {
36+
if (numRows <=1)returns;
37+
intlen =s.length();
38+
char[]chars =s.toCharArray();
39+
StringBuilder[]sbs =newStringBuilder[numRows];
40+
for (inti =0;i <numRows;i++) {
41+
sbs[i] =newStringBuilder();
42+
}
43+
inti =0;
44+
while (i <len) {
45+
for (intj =0;j <numRows &&i <len; ++j) {
46+
sbs[j].append(chars[i++]);
47+
}
48+
for (intj =numRows -2;j >=1 &&i <len; --j) {
49+
sbs[j].append(chars[i++]);
50+
}
51+
}
52+
for (i =1;i <numRows;i++) {
53+
sbs[0].append(sbs[i]);
54+
}
55+
returnsbs[0].toString();
56+
}
57+
58+
publicstaticvoidmain(String[]args) {
59+
Solutionsolution =newSolution();
60+
System.out.println(solution.convert("PAYPALISHIRING",3));// PAHNAPLSIIGYIR
61+
System.out.println(solution.convert("ABCD",4));
62+
}
63+
}

0 commit comments

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