本系列通过Java和Kotlin这两种语言来解决力扣上面的算法题，由于本人算法菜鸟一枚，可能部分题目并不是最优题解，希望能和各位大神共同讨论~
项目的GitHub：Algorithm
寻找两个正序数组的中位数（Median of Two Sorted Arrays）
难度：困难
链接：Median of Two Sorted Arrays
代码
Java
/**
* Created by TanJiaJun on 2021/6/9.
* 4. 寻找两个正序数组的中位数（Median of Two Sorted Arrays）
* 难度：困难
*
* @see <a href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/">Median of Two Sorted Arrays</a>
*/
class MedianOfTwoSortedArrays {
public static void main(String[] args) {
// 示例一
System.out.println("示例一：");
int[] firstNumbers = {1, 3};
int[] secondNumbers = {2};
System.out.println(findMedianSortedArrays(firstNumbers, secondNumbers));
System.out.print("\n");
// 示例二
System.out.println("示例二：");
int[] thirdNumbers = {1, 2};
int[] fourthNumbers = {3, 4};
System.out.println(findMedianSortedArrays(thirdNumbers, fourthNumbers));
System.out.print("\n");
// 示例三
System.out.println("示例三：");
int[] fifthNumbers = {0, 0};
int[] sixthNumbers = {0, 0};
System.out.println(findMedianSortedArrays(fifthNumbers, sixthNumbers));
System.out.print("\n");
// 示例四
System.out.println("示例四：");
int[] seventhNumbers = {};
int[] eightNumbers = {1};
System.out.println(findMedianSortedArrays(seventhNumbers, eightNumbers));
System.out.print("\n");
// 示例五
System.out.println("示例五：");
int[] ninthNumbers = {2};
int[] tenthNumbers = {};
System.out.println(findMedianSortedArrays(ninthNumbers, tenthNumbers));
}
/**
* 双指针
* 时间复杂度：O(m+n)，其中m是数组num1的长度，n是数组num2的长度
* 空间复杂度：O(m+n)，其中m是数组num1的长度，n是数组num2的长度
*
* @param firstNumbers 第一个数组
* @param secondNumbers 第二个数组
* @return 结果
*/
public static double findMedianSortedArrays(int[] firstNumbers, int[] secondNumbers) {
int len1 = firstNumbers.length;
int len2 = secondNumbers.length;
// 合并后的数组的索引
int index = 0;
// 第一个数组的指针，下面用i指针描述
int i = 0;
// 第二个数组的指针，下面用j指针描述
int j = 0;
// 合并两个数组
// 创建一个大小是两个数组长度之和的数组
int[] arrays = new int[len1 + len2];
while (i < len1 || j < len2) {
if (i == len1) {
// 如果第一个数组遍历完毕后，就继续遍历第二个数组
arrays[index++] = secondNumbers[j++];
} else if (j == len2) {
// 如果第二个数组遍历完毕后，就继续遍历第一个数组
arrays[index++] = firstNumbers[i++];
} else if (firstNumbers[i] < secondNumbers[j]) {
// 如果第一个数组的元素小于第二个数组的元素，就将第一个数组中的该元素添加到合并后的新数组，同时将i指针向右移动一格
arrays[index++] = firstNumbers[i++];
} else {
// 如果第一个数组的元素大于第二个数组的元素，就将第二个数组中的该元素添加到合并后的新数组，同时将j指针向右移动一格
arrays[index++] = secondNumbers[j++];
}
}
// 找出数组的中位数
double median;
int length = arrays.length;
if (length % 2 == 0) {
// 如果数组长度是偶数，就找出这条中线旁边的两个元素，然后相加之后除以2得到结果
median = (arrays[length / 2] + arrays[length / 2 - 1]) / 2.0D;
} else {
// 如果数组长度是奇数，就找出这条中线对应的元素，该元素就是结果
median = arrays[length / 2];
}
return median;
}
}
Kotlin
/**
* Created by TanJiaJun on 2021/6/13.
* 4. 寻找两个正序数组的中位数（Median of Two Sorted Arrays）
* 难度：困难
*
* @see <a href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/">Median of Two Sorted Arrays</a>
*/
object MedianOfTwoSortedArraysKotlin {
@JvmStatic
fun main(args: Array<String>) {
// 示例一
println("示例一：")
val firstNumbers = intArrayOf(1, 3)
val secondNumbers = intArrayOf(2)
println(findMedianSortedArrays(firstNumbers, secondNumbers))
print("\n")
// 示例二
println("示例二：")
val thirdNumbers = intArrayOf(1, 2)
val fourthNumbers = intArrayOf(3, 4)
println(findMedianSortedArrays(thirdNumbers, fourthNumbers))
print("\n")
// 示例三
println("示例三：")
val fifthNumbers = intArrayOf(0, 0)
val sixthNumbers = intArrayOf(0, 0)
println(findMedianSortedArrays(fifthNumbers, sixthNumbers))
print("\n")
// 示例四
println("示例四：")
val seventhNumbers = intArrayOf()
val eightNumbers = intArrayOf(1)
println(findMedianSortedArrays(seventhNumbers, eightNumbers))
print("\n")
// 示例五
println("示例五：")
val ninthNumbers = intArrayOf(2)
val tenthNumbers = intArrayOf()
println(findMedianSortedArrays(ninthNumbers, tenthNumbers))
}
/**
* 双指针
* 时间复杂度：O(m+n)，其中m是数组num1的长度，n是数组num2的长度
* 空间复杂度：O(m+n)，其中m是数组num1的长度，n是数组num2的长度
*
* @param nums1 第一个数组
* @param nums2 第二个数组
* @return 结果
*/
private fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
val size1 = nums1.size
val size2 = nums2.size
// 合并后的数组的索引
var index = 0
// 第一个数组的指针，下面用i指针描述
var i = 0
// 第二个数组的指针，下面用j指针描述
var j = 0
// 合并两个数组
// 创建一个大小是两个数组长度之和的数组
val arrays = IntArray(size1 + size2)
while (i < size1 || j < size2) {
when {
// 如果第一个数组遍历完毕后，就继续遍历第二个数组
i == size1 -> arrays[index++] = nums2[j++]
// 如果第二个数组遍历完毕后，就继续遍历第一个数组
j == size2 -> arrays[index++] = nums1[i++]
// 如果第一个数组的元素小于第二个数组的元素，就将第一个数组中的该元素添加到合并后的新数组，同时将i指针向右移动一格
nums1[i] < nums2[j] -> arrays[index++] = nums1[i++]
// 如果第一个数组的元素大于第二个数组的元素，就将第二个数组中的该元素添加到合并后的新数组，同时将j指针向右移动一格
else -> arrays[index++] = nums2[j++]
}
}
// 找出数组的中位数
val size = arrays.size
return if (size % 2.0 == 0.0) {
// 如果数组长度是偶数，就找出这条中线旁边的两个元素，然后相加之后除以2得到结果
(arrays[size / 2] + arrays[size / 2 - 1]) / 2.0
} else {
// 如果数组长度是奇数，就找出这条中线对应的元素，该元素就是结果
arrays[size / 2].toDouble()
}
}
}
时间复杂度：O(m+n)，其中m是数组num1的长度，n是数组num2的长度。
空间复杂度：O(m+n)，其中m是数组num1的长度，n是数组num2的长度。
题解
根据题目可知，这两个数组都是正序（从小到大）的，所以我们可以先使用双指针将这两个数组合并成一个数组，注释写得挺详细了，这里就不在赘述了，合并后得到一个大小是两个数组长度之和的新数组，然后我们从这个数组找出中位数，有两种情况：
- 如果数组长度是偶数，就找出这条中线旁边的两个元素，然后相加之后除以2得到结果。
- 如果数组长度是奇数，就找出这条中线对应的元素，该元素就是结果。
最长回文子串（Longest Palindromic Substring）
难度：中等
链接：Longest Palindromic Substring
代码
Java
/**
* Created by TanJiaJun on 2021/6/10.
* 5. 最长回文子串（Longest Palindromic Substring）
* 难度：中等
*
* @see <a href="https://leetcode-cn.com/problems/longest-palindromic-substring/">Longest Palindromic Substring</a>
*/
class LongestPalindromicSubstring {
public static void main(String[] args) {
// 示例一
System.out.print("示例一：");
String firstStr = "babad";
System.out.println(expandAroundCenterLongestPalindrome(firstStr));
System.out.print("\n");
// 示例二
System.out.print("示例二：");
String secondStr = "cbbd";
System.out.println(expandAroundCenterLongestPalindrome(secondStr));
System.out.print("\n");
// 示例三
System.out.print("示例三：");
String thirdStr = "a";
System.out.println(expandAroundCenterLongestPalindrome(thirdStr));
System.out.print("\n");
// 示例四
System.out.print("示例四：");
String fourthStr = "ac";
System.out.println(expandAroundCenterLongestPalindrome(fourthStr));
}
/**
* 方法一：枚举算法
* 时间复杂度：O(N^3)，其中N是字符串的长度
* 空间复杂度：O(1)
*
* @param str 字符串
* @return 结果
*/
private static String longestPalindrome(String str) {
int maxLength = 0;
String result = "";
// 枚举所有的元素
for (int i = 0, iLen = str.length(); i < iLen; i++) {
for (int j = i + 1, jLen = str.length(); j <= jLen; j++) {
String substring = str.substring(i, j);
if (isPalindromeSubstring(substring) && substring.length() > maxLength) {
maxLength = substring.length();
result = substring;
}
}
}
return result;
}
/**
* 判断字符串是否为回文串
*
* @param str 字符串
* @return 结果
*/
private static boolean isPalindromeSubstring(String str) {
int length = str.length();
for (int i = 0; i < length / 2; i++) {
// 找出该元素作为回文子串的起始位置还有结束位置
if (str.charAt(i) != str.charAt(length - i - 1)) {
// 如果其中一个不相同，证明该字符串不是回文串
return false;
}
}
// 如果字符都相同，证明该字符串是回文串
return true;
}
/**
* 方法二：中心扩展法（双指针）
* 时间复杂度：O(N^2)，其中N是字符串的长度
* 空间复杂度：O(1)
*
* @param str 字符串
* @return 结果
*/
private static String expandAroundCenterLongestPalindrome(String str) {
int start = 0;
int end = 0;
for (int i = 0, length = str.length(); i < length; i++) {
// 长度是奇数
int oddLength = getExpandAroundCenterLength(str, i, i);
// 长度是偶数
int evenLength = getExpandAroundCenterLength(str, i, i + 1);
// 得到最大长度
int maxLength = Math.max(oddLength, evenLength);
if (maxLength > end - start) {
// 得到起始位置
start = i - (maxLength - 1) / 2;
// 得到结束位置
end = i + maxLength / 2;
}
}
// 截取对应的字符
return str.substring(start, end + 1);
}
/**
* 得到中心往两边扩展的长度
*
* @param str 字符串
* @param left 左指针
* @param right 右指针
* @return 长度
*/
private static int getExpandAroundCenterLength(String str, int left, int right) {
// 找出该元素作为回文子串的起始位置还有结束位置
while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
// 如果符合条件，左指针向左移动一格，右指针向右移动一格
left--;
right++;
}
// 得到长度
return right - left - 1;
}
}
Kotlin
import kotlin.math.max
/**
* Created by TanJiaJun on 2021/6/14.
* 5. 最长回文子串（Longest Palindromic Substring）
* 难度：中等
*
* @see <a href="https://leetcode-cn.com/problems/longest-palindromic-substring/">Longest Palindromic Substring</a>
*/
object LongestPalindromicSubstringKotlin {
@JvmStatic
fun main(args: Array<String>) {
// 示例一
print("示例一：")
val firstStr = "babad"
println(expandAroundCenterLongestPalindrome(firstStr))
print("\n")
// 示例二
print("示例二：")
val secondStr = "cbbd"
println(expandAroundCenterLongestPalindrome(secondStr))
print("\n")
// 示例三
print("示例三：")
val thirdStr = "a"
println(expandAroundCenterLongestPalindrome(thirdStr))
print("\n")
// 示例四
print("示例四：")
val fourthStr = "ac"
println(expandAroundCenterLongestPalindrome(fourthStr))
}
/**
* 方法一：枚举算法
* 时间复杂度：O(N^3)，其中N是字符串的长度
* 空间复杂度：O(1)
*
* @param str 字符串
* @return 结果
*/
private fun longestPalindrome(str: String): String {
var maxLength = 0
var result = ""
// 枚举所有的元素
str.forEachIndexed { index, _ ->
for (i in index + 1..str.length) {
val substring = str.substring(index, i)
if (isPalindromicSubstring(substring) && substring.length > maxLength) {
maxLength = substring.length
result = substring
}
}
}
return result
}
/**
* 判断字符串是否为回文串
*
* @param str 字符串
* @return 结果
*/
private fun isPalindromicSubstring(str: String): Boolean {
val length = str.length
for (i in 0 until length / 2) {
// 找出该元素作为回文子串的起始位置还有结束位置
if (str[i] != str[length - i - 1]) {
// 如果其中一个不相同，证明该字符串不是回文串
return false
}
}
// 如果字符都相同，证明该字符串是回文串
return true
}
/**
* 方法二：中心扩展法（双指针）
* 时间复杂度：O(N^2)，其中N是字符串的长度
* 空间复杂度：O(1)
*
* @param str 字符串
* @return 结果
*/
private fun expandAroundCenterLongestPalindrome(str: String): String {
var start = 0
var end = 0
str.forEachIndexed { index, _ ->
// 长度是奇数
val oddLength = getExpandAroundCenterLength(str = str, left = index, right = index)
// 长度是偶数
val evenLength = getExpandAroundCenterLength(str = str, left = index, right = index + 1)
// 得到最大长度
val maxLength = max(oddLength, evenLength)
if (maxLength > end - start) {
// 得到起始位置
start = index - (maxLength - 1) / 2
// 得到结束位置
end = index + maxLength / 2
}
}
return str.substring(start, end + 1)
}
/**
* 得到中心往两边扩展的长度
*
* @param str 字符串
* @param left 左指针
* @param right 右指针
* @return 长度
*/
private fun getExpandAroundCenterLength(str: String, left: Int, right: Int): Int {
var l = left
var r = right
// 找出该元素作为回文子串的起始位置还有结束位置
while ((l >= 0 && r < str.length && str[l] == str[r])) {
// 如果符合条件，左指针向左移动一格，右指针向右移动一格
l--
r++
}
// 得到长度
return r - l - 1
}
}
题解
枚举
// LongestPalindromicSubstringKotlin.kt
/**
* 方法一：枚举
* 时间复杂度：O(N^3)，其中N是字符串的长度
* 空间复杂度：O(1)
*
* @param str 字符串
* @return 结果
*/
private fun longestPalindrome(str: String): String {
var maxLength = 0
var result = ""
// 枚举所有的元素
str.forEachIndexed { index, _ ->
for (i in index + 1..str.length) {
val substring = str.substring(index, i)
if (isPalindromicSubstring(substring) && substring.length > maxLength) {
maxLength = substring.length
result = substring
}
}
}
return result
}
/**
* 判断字符串是否为回文串
*
* @param str 字符串
* @return 结果
*/
private fun isPalindromicSubstring(str: String): Boolean {
val length = str.length
for (i in 0 until length / 2) {
// 找出该元素作为回文子串的起始位置还有结束位置
if (str[i] != str[length - i - 1]) {
// 如果其中一个不相同，证明该字符串不是回文串
return false
}
}
// 如果字符都相同，证明该字符串是回文串
return true
}
时间复杂度：O(N^3)，其中N是字符串的长度。
空间复杂度：O(1)。
暴力解法，枚举所有元素，要注意的是，由于回文串的特征是正读和反读都一样，例如：abba就是回文串，abda就不是回文串了，所以我们只要找到某个字符，并且找到该字符对应索引的字符，只需要遍历该数组长度一半就可以判断该字符串是否为回文串，注释写得挺详细了，这里就不再赘述了。
中心扩展法（双指针）
// LongestPalindromicSubstringKotlin.kt
/**
* 方法二：中心扩展法（双指针）
* 时间复杂度：O(N^2)，其中N是字符串的长度
* 空间复杂度：O(1)
*
* @param str 字符串
* @return 结果
*/
private fun expandAroundCenterLongestPalindrome(str: String): String {
var start = 0
var end = 0
str.forEachIndexed { index, _ ->
// 长度是奇数
val oddLength = getExpandAroundCenterLength(str = str, left = index, right = index)
// 长度是偶数
val evenLength = getExpandAroundCenterLength(str = str, left = index, right = index + 1)
// 得到最大长度
val maxLength = max(oddLength, evenLength)
if (maxLength > end - start) {
// 得到起始位置
start = index - (maxLength - 1) / 2
// 得到结束位置
end = index + maxLength / 2
}
}
return str.substring(start, end + 1)
}
/**
* 得到中心往两边扩展的长度
*
* @param str 字符串
* @param left 左指针
* @param right 右指针
* @return 长度
*/
private fun getExpandAroundCenterLength(str: String, left: Int, right: Int): Int {
var l = left
var r = right
// 找出该元素作为回文子串的起始位置还有结束位置
while ((l >= 0 && r < str.length && str[l] == str[r])) {
// 如果符合条件，左指针向左移动一格，右指针向右移动一格
l--
r++
}
// 得到长度
return r - l - 1
}
时间复杂度：O(N^2)，其中N是字符串的长度。
空间复杂度：O(1)。
由于回文串的特征是正读和反读都一样，例如：abba就是回文串，abda就不是回文串了，所以我们可以从该字符串的中间向两边扩展地遍历，这样就能快速地得到最长的回文子串，要注意的是，因为数组的长度可能是奇数，也可能是偶数，如果是奇数的话，中心点就只有一个；如果是偶数的话，中心点就有两个。
Z字形变换（ZigZag Conversion）
难度：中等
代码
Java
/**
* Created by TanJiaJun on 2021/6/12.
* 6. Z字形变换（ZigZag Conversion）
* 难度：中等
*
* @see <a href="https://leetcode-cn.com/problems/zigzag-conversion/">ZigZag Conversion</a>
*/
class ZigZagConversion {
public static void main(String[] args) {
// 示例一
System.out.print("示例一：");
String firstStr = "PAYPALISHIRING";
int firstNumRows = 3;
System.out.println(convert(firstStr, firstNumRows));
System.out.print("\n");
// 示例二
System.out.print("示例二：");
String secondStr = "PAYPALISHIRING";
int secondNumRows = 4;
System.out.println(convert(secondStr, secondNumRows));
System.out.print("\n");
// 示例三
System.out.print("示例三：");
String thirdStr = "A";
int thirdNumRows = 1;
System.out.println(convert(thirdStr, thirdNumRows));
}
/**
* 时间复杂度：O(N)，其中N是字符串的长度
* 空间复杂度：O(N)
*
* @param str 字符串
* @param numRows 行数
* @return 结果
*/
private static String convert(String str, int numRows) {
if (numRows == 1) {
// 如果只是一行的话，就直接返回该字符串
return str;
}
// 创建长度是行数的StringBuilder数组，并且每个元素都创建StringBuilder对象
StringBuilder[] stringBuilders = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) {
stringBuilders[i] = new StringBuilder();
}
// 索引
int index = 0;
// 行数
int row = 0;
int length = str.length();
while (index < length) {
// 从第一行开始，按照行数添加到对应的数组，并且追加字符，然后一直遍历到最后一行对应的数组
while (index < length && row < numRows) {
char ch = str.charAt(index++);
stringBuilders[row++].append(ch);
}
// 此时row是最后一行，所以我们需要回到倒数第二行，执行以下逻辑
row = numRows - 2;
// 从倒数第二行开始，按照行数添加到对应的数组，并且追加字符，然后一直遍历到第一行的对应的数组
while (index < length && row >= 0) {
char ch = str.charAt(index++);
stringBuilders[row--].append(ch);
}
// 此时row是-1，所以我们需要回到第二行，执行以下逻辑
row += 2;
}
// 创建一个新的StringBuilder，将每一行对应的StringBuilder数组对应的StringBuilder追加到这个对象
StringBuilder resultSB = new StringBuilder();
for (StringBuilder stringBuilder : stringBuilders) {
resultSB.append(stringBuilder);
}
// 将这个StringBuilder转成字符串
return resultSB.toString();
}
}
Kotlin
/**
* Created by TanJiaJun on 2021/6/14.
* 6. Z字形变换（ZigZag Conversion）
* 难度：中等
*
* @see <a href="https://leetcode-cn.com/problems/zigzag-conversion/">ZigZag Conversion</a>
*/
object ZigZagConversionKotlin {
@JvmStatic
fun main(args: Array<String>) {
// 示例一
print("示例一：")
val firstStr = "PAYPALISHIRING"
val firstNumRows = 3
println(convert(firstStr, firstNumRows))
print("\n")
// 示例二
print("示例二：")
val secondStr = "PAYPALISHIRING"
val secondNumRows = 4
println(convert(secondStr, secondNumRows))
print("\n")
// 示例三
print("示例三：")
val thirdStr = "A"
val thirdNumRows = 1
println(convert(thirdStr, thirdNumRows))
}
/**
* 时间复杂度：O(N)，其中N是字符串的长度
* 空间复杂度：O(N)
*
* @param str 字符串
* @param numRows 行数
* @return 结果
*/
private fun convert(str: String, numRows: Int): String {
if (numRows == 1) {
// 如果只是一行的话，就直接返回该字符串
return str
}
// 创建长度是行数的StringBuilder数组，并且每个元素都创建StringBuilder对象
val stringBuilders = Array(numRows, init = { StringBuilder() })
// 索引
var index = 0
// 行数
var row = 0
val length = str.length
while (index < length) {
// 从第一行开始，按照行数添加到对应的数组，并且追加字符，然后一直遍历到最后一行对应的数组
while (index < length && row < numRows) {
stringBuilders[row++].append(str[index++])
}
// 此时row是最后一行，所以我们需要回到倒数第二行，执行以下逻辑
row = numRows - 2
// 从倒数第二行开始，按照行数添加到对应的数组，并且追加字符，然后一直遍历到第一行的对应的数组
while (index < length && row >= 0) {
stringBuilders[row--].append(str[index++])
}
// 此时row是-1，所以我们需要回到第二行，执行以下逻辑
row += 2
}
// 创建一个新的StringBuilder，将每一行对应的StringBuilder数组对应的StringBuilder追加到这个对象
val resultSB = StringBuilder()
stringBuilders.forEach { resultSB.append(it) }
// 将这个StringBuilder转成字符串
return resultSB.toString()
}
}
时间复杂度：O(N)，其中N是字符串的长度。
空间复杂度：O(N)。
题解
根据题目我们可以知道，字符串是按着反向N字形排列的，我们可以先创建一个长度是行数的StringBuilder数组，然后定义一个row这样的指针来确定行数，为了方便理解，我举个例子，假设字符串是PAYPALISHIRING，行数是3，我们从第一行开始，按照行数将字符添加到对应的数组，并且追加字符，然后一直遍历到最后一行对应的数组，此时这三个数组的情况如下所示：
- 第一个数组：P
- 第二个数组：A
- 第三个数组：Y
此时的row的值是4，然后这个时候根据题目要求，我们的指针要回到倒数第二行，所以我们就要将row的值调整为行数减去2，也就是3-2等于1，然后开始继续遍历，此时这三个数组的情况如下所示：
- 第一个数组：P
- 第二个数组：A、P
- 第三个数组：Y
然后我们的指针要从倒数第二行开始，按照行数添加到对应的数组，并且追加字符，然后一直遍历到第一行的对应的数组，此时这三个数组的情况如下所示：
- 第一个数组：P、A
- 第二个数组：A、P、L
- 第三个数组：Y、I
此时row的值是-1，最后根据题目要求，我们的指针row要回到第二行，所以我们就要将row的值调整为自增2，也就是-1+2等于1，然后开始继续遍历，此时这三个数组的情况如下所示：
- 第一个数组：P、A
- 第二个数组：A、P、L、S
- 第三个数组：Y、I
以此类推遍历下去，后面的逻辑就跟前面的逻辑一样了，这里就不再赘述了。
最后将这个StringBuilder数组遍历后追加到一个新的StringBuilder对象，然后转成字符串就可以得到最后的结果了。
我的GitHub：TanJiaJunBeyond
Android通用框架：Android通用框架
我的掘金：谭嘉俊
我的简书：谭嘉俊
我的CSDN：谭嘉俊
网友评论