算法成长之路leetcode5-6

算法成长之路leetcode5-6

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example

1
2
3
4
5
6
7
8
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: "cbbd"
Output: "bb"

JAVA题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package algorithm;

public class Leetcode5 {
public static void main(String[] args) {
System.out.println(longestPalindrome("abbaabb"));
}

/**
* 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
*
* 示例 1:
*
* 输入: "babad"
* 输出: "bab"
* 注意: "aba" 也是一个有效答案。
* 示例 2:
*
* 输入: "cbbd"
* 输出: "bb"
*
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/longest-palindromic-substring
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/

/**
* 终于看懂了这个中心向两边扩张算法是什么意思了。
* 先来解释一下为什么中心是2n-1而不是n 比如有字符串abcba,这时回文子串是abcda,
* 中心是c;又有字符串adccda,这时回文子串是adccda,中心是cc。 由此可见中心点既有可能是一个字符,
* 也有可能是两个字符,当中心为一个字符的时候有n个中心,
* 当中心为两个字符的时候有n-1个中心,所以一共有2n-1个中心。
* 然后for循环开始从左到右遍历,为什么会有两次expandAroundCenter,一次是i和i本身,一次是i和i+1,
* 这就是上面说到的一个中心与两个中心。 而后会去判断这两种情况下谁的回文子串最长,并标记出这个子串在原字符串中的定位,即start和end。
*
* @param s
* @return
*/
public static String longestPalindrome(String s) {

if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
// 一个数向两边扩张
int len1 = expandAroundCenter(s, i, i);
// 两个数向两边扩张
int len2 = expandAroundCenter(s, i, i + 1);
// 取最长的回文
int len = Math.max(len1, len2);
// 判读此时长度和原来的最长度
if (len > end - start) {
// 求最长回文开始位置
start = i - (len - 1) / 2;
// 求最长回文结束位置
end = i + len / 2;
}
}
// 截取最长回文
return s.substring(start, end + 1);
}

/**
* 向两边向两边扩张求长度
*
* @param s
* @param left
* @param right
* @return
*/
private static int expandAroundCenter(String s, int left, int right) {
// 定位中心位置
int L = left, R = right;
// 判读中间位置是否相等,以及两边扩张是否相等
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
// 向左扩张一位
L--;
// 向右扩张一位
R++;
}
// 回文的长度 如 aba 时,当 b = 1时,一个中心点进来,L = 1,R = 1,此时满足循环,L=0,R=2,此时也满足
// 循环,L = -1,R=3,此时循环结束,长度为3 = 3 -(-1) -1
return R - L - 1;
}
}

6. ZigZag Conversion

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)

P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P I N
A L S I G
Y A H R
P I

JAVA题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package algorithm;

import java.util.ArrayList;
import java.util.List;

public class Leetcode6 {
/**
* 将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。
* <p>
* 比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下:
* <p>
* L C I R
* E T O E S I I G
* E D H N
* 之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"。
* <p>
* 请你实现这个将字符串进行指定行数变换的函数:
* <p>
* string convert(string s, int numRows);
* 示例 1:
* <p>
* 输入: s = "LEETCODEISHIRING", numRows = 3
* 输出: "LCIRETOESIIGEDHN"
* 示例 2:
* <p>
* 输入: s = "LEETCODEISHIRING", numRows = 4
* 输出: "LDREOEIIECIHNTSG"
* 解释:
* <p>
* L D R
* E O E I I
* E C I H N
* T S G
* <p>
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/zigzag-conversion
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public String convert(String s, int numRows) {

if (numRows == 1) return s;

List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++)
// 确定有多少行,每一行放一个待填充的字符串
rows.add(new StringBuilder());
// 当前行
int curRow = 0;
// 上移或下移 false上移
boolean goingDown = false;

for (char c : s.toCharArray()) {
// 挨着放字符到对应的行
rows.get(curRow).append(c);
// 判断是否下移,当第一行和最后一行的时候转向
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
// 下移行数+1,上移行数-1
curRow += goingDown ? 1 : -1;
}
// 存最终结果
StringBuilder ret = new StringBuilder();
// 遍历每行,进行连接
for (StringBuilder row : rows) ret.append(row);
return ret.toString();
}

public static void main(String[] args) {
Leetcode6 l = new Leetcode6();
System.out.println(l.convert("weweqw", 3));
}
}
作者

byte4sec

发布于

2019-12-05

更新于

2020-12-31

许可协议

评论