本系列通過(guò)Java和Kotlin這兩種語(yǔ)言來(lái)解決力扣上面的算法題撼泛，由于本人算法菜鳥(niǎo)一枚冷离，可能部分題目并不是最優(yōu)題解吵冒，希望能和各位大神共同討論~
項(xiàng)目的GitHub：Algorithm
尋找兩個(gè)正序數(shù)組的中位數(shù)（Median of Two Sorted Arrays）
難度：困難
鏈接：Median of Two Sorted Arrays
代碼
Java
/**
* Created by TanJiaJun on 2021/6/9.
* 4. 尋找兩個(gè)正序數(shù)組的中位數(shù)（Median of Two Sorted Arrays）
* 難度：困難
*
* @see <a >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));
}
/**
* 雙指針
* 時(shí)間復(fù)雜度：O(m+n)，其中m是數(shù)組num1的長(zhǎng)度西剥，n是數(shù)組num2的長(zhǎng)度
* 空間復(fù)雜度：O(m+n)痹栖，其中m是數(shù)組num1的長(zhǎng)度，n是數(shù)組num2的長(zhǎng)度
*
* @param firstNumbers 第一個(gè)數(shù)組
* @param secondNumbers 第二個(gè)數(shù)組
* @return 結(jié)果
*/
public static double findMedianSortedArrays(int[] firstNumbers, int[] secondNumbers) {
int len1 = firstNumbers.length;
int len2 = secondNumbers.length;
// 合并后的數(shù)組的索引
int index = 0;
// 第一個(gè)數(shù)組的指針瞭空，下面用i指針描述
int i = 0;
// 第二個(gè)數(shù)組的指針揪阿，下面用j指針描述
int j = 0;
// 合并兩個(gè)數(shù)組
// 創(chuàng)建一個(gè)大小是兩個(gè)數(shù)組長(zhǎng)度之和的數(shù)組
int[] arrays = new int[len1 + len2];
while (i < len1 || j < len2) {
if (i == len1) {
// 如果第一個(gè)數(shù)組遍歷完畢后，就繼續(xù)遍歷第二個(gè)數(shù)組
arrays[index++] = secondNumbers[j++];
} else if (j == len2) {
// 如果第二個(gè)數(shù)組遍歷完畢后咆畏，就繼續(xù)遍歷第一個(gè)數(shù)組
arrays[index++] = firstNumbers[i++];
} else if (firstNumbers[i] < secondNumbers[j]) {
// 如果第一個(gè)數(shù)組的元素小于第二個(gè)數(shù)組的元素南捂，就將第一個(gè)數(shù)組中的該元素添加到合并后的新數(shù)組，同時(shí)將i指針向右移動(dòng)一格
arrays[index++] = firstNumbers[i++];
} else {
// 如果第一個(gè)數(shù)組的元素大于第二個(gè)數(shù)組的元素旧找，就將第二個(gè)數(shù)組中的該元素添加到合并后的新數(shù)組溺健，同時(shí)將j指針向右移動(dòng)一格
arrays[index++] = secondNumbers[j++];
}
}
// 找出數(shù)組的中位數(shù)
double median;
int length = arrays.length;
if (length % 2 == 0) {
// 如果數(shù)組長(zhǎng)度是偶數(shù)，就找出這條中線旁邊的兩個(gè)元素钮蛛，然后相加之后除以2得到結(jié)果
median = (arrays[length / 2] + arrays[length / 2 - 1]) / 2.0D;
} else {
// 如果數(shù)組長(zhǎng)度是奇數(shù)鞭缭，就找出這條中線對(duì)應(yīng)的元素剖膳，該元素就是結(jié)果
median = arrays[length / 2];
}
return median;
}
}
Kotlin
/**
* Created by TanJiaJun on 2021/6/13.
* 4. 尋找兩個(gè)正序數(shù)組的中位數(shù)（Median of Two Sorted Arrays）
* 難度：困難
*
* @see <a >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))
}
/**
* 雙指針
* 時(shí)間復(fù)雜度：O(m+n)，其中m是數(shù)組num1的長(zhǎng)度岭辣，n是數(shù)組num2的長(zhǎng)度
* 空間復(fù)雜度：O(m+n)潮秘，其中m是數(shù)組num1的長(zhǎng)度，n是數(shù)組num2的長(zhǎng)度
*
* @param nums1 第一個(gè)數(shù)組
* @param nums2 第二個(gè)數(shù)組
* @return 結(jié)果
*/
private fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
val size1 = nums1.size
val size2 = nums2.size
// 合并后的數(shù)組的索引
var index = 0
// 第一個(gè)數(shù)組的指針易结，下面用i指針描述
var i = 0
// 第二個(gè)數(shù)組的指針枕荞，下面用j指針描述
var j = 0
// 合并兩個(gè)數(shù)組
// 創(chuàng)建一個(gè)大小是兩個(gè)數(shù)組長(zhǎng)度之和的數(shù)組
val arrays = IntArray(size1 + size2)
while (i < size1 || j < size2) {
when {
// 如果第一個(gè)數(shù)組遍歷完畢后，就繼續(xù)遍歷第二個(gè)數(shù)組
i == size1 -> arrays[index++] = nums2[j++]
// 如果第二個(gè)數(shù)組遍歷完畢后搞动，就繼續(xù)遍歷第一個(gè)數(shù)組
j == size2 -> arrays[index++] = nums1[i++]
// 如果第一個(gè)數(shù)組的元素小于第二個(gè)數(shù)組的元素躏精，就將第一個(gè)數(shù)組中的該元素添加到合并后的新數(shù)組，同時(shí)將i指針向右移動(dòng)一格
nums1[i] < nums2[j] -> arrays[index++] = nums1[i++]
// 如果第一個(gè)數(shù)組的元素大于第二個(gè)數(shù)組的元素鹦肿，就將第二個(gè)數(shù)組中的該元素添加到合并后的新數(shù)組矗烛，同時(shí)將j指針向右移動(dòng)一格
else -> arrays[index++] = nums2[j++]
}
}
// 找出數(shù)組的中位數(shù)
val size = arrays.size
return if (size % 2.0 == 0.0) {
// 如果數(shù)組長(zhǎng)度是偶數(shù)，就找出這條中線旁邊的兩個(gè)元素箩溃，然后相加之后除以2得到結(jié)果
(arrays[size / 2] + arrays[size / 2 - 1]) / 2.0
} else {
// 如果數(shù)組長(zhǎng)度是奇數(shù)瞭吃，就找出這條中線對(duì)應(yīng)的元素，該元素就是結(jié)果
arrays[size / 2].toDouble()
}
}
}
時(shí)間復(fù)雜度：O(m+n)涣旨，其中m是數(shù)組num1的長(zhǎng)度歪架，n是數(shù)組num2的長(zhǎng)度。
空間復(fù)雜度：O(m+n)霹陡，其中m是數(shù)組num1的長(zhǎng)度和蚪，n是數(shù)組num2的長(zhǎng)度。
題解
根據(jù)題目可知烹棉，這兩個(gè)數(shù)組都是正序（從小到大）的攒霹，所以我們可以先使用雙指針將這兩個(gè)數(shù)組合并成一個(gè)數(shù)組，注釋寫(xiě)得挺詳細(xì)了浆洗，這里就不在贅述了催束，合并后得到一個(gè)大小是兩個(gè)數(shù)組長(zhǎng)度之和的新數(shù)組，然后我們從這個(gè)數(shù)組找出中位數(shù)伏社，有兩種情況：
- 如果數(shù)組長(zhǎng)度是偶數(shù)抠刺，就找出這條中線旁邊的兩個(gè)元素，然后相加之后除以2得到結(jié)果洛口。
- 如果數(shù)組長(zhǎng)度是奇數(shù)矫付，就找出這條中線對(duì)應(yīng)的元素凯沪，該元素就是結(jié)果第焰。
最長(zhǎng)回文子串（Longest Palindromic Substring）
難度：中等
鏈接：Longest Palindromic Substring
代碼
Java
/**
* Created by TanJiaJun on 2021/6/10.
* 5. 最長(zhǎng)回文子串（Longest Palindromic Substring）
* 難度：中等
*
* @see <a >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));
}
/**
* 方法一：枚舉算法
* 時(shí)間復(fù)雜度：O(N^3)，其中N是字符串的長(zhǎng)度
* 空間復(fù)雜度：O(1)
*
* @param str 字符串
* @return 結(jié)果
*/
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 結(jié)果
*/
private static boolean isPalindromeSubstring(String str) {
int length = str.length();
for (int i = 0; i < length / 2; i++) {
// 找出該元素作為回文子串的起始位置還有結(jié)束位置
if (str.charAt(i) != str.charAt(length - i - 1)) {
// 如果其中一個(gè)不相同妨马，證明該字符串不是回文串
return false;
}
}
// 如果字符都相同挺举，證明該字符串是回文串
return true;
}
/**
* 方法二：中心擴(kuò)展法（雙指針）
* 時(shí)間復(fù)雜度：O(N^2)杀赢，其中N是字符串的長(zhǎng)度
* 空間復(fù)雜度：O(1)
*
* @param str 字符串
* @return 結(jié)果
*/
private static String expandAroundCenterLongestPalindrome(String str) {
int start = 0;
int end = 0;
for (int i = 0, length = str.length(); i < length; i++) {
// 長(zhǎng)度是奇數(shù)
int oddLength = getExpandAroundCenterLength(str, i, i);
// 長(zhǎng)度是偶數(shù)
int evenLength = getExpandAroundCenterLength(str, i, i + 1);
// 得到最大長(zhǎng)度
int maxLength = Math.max(oddLength, evenLength);
if (maxLength > end - start) {
// 得到起始位置
start = i - (maxLength - 1) / 2;
// 得到結(jié)束位置
end = i + maxLength / 2;
}
}
// 截取對(duì)應(yīng)的字符
return str.substring(start, end + 1);
}
/**
* 得到中心往兩邊擴(kuò)展的長(zhǎng)度
*
* @param str 字符串
* @param left 左指針
* @param right 右指針
* @return 長(zhǎng)度
*/
private static int getExpandAroundCenterLength(String str, int left, int right) {
// 找出該元素作為回文子串的起始位置還有結(jié)束位置
while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
// 如果符合條件，左指針向左移動(dòng)一格湘纵，右指針向右移動(dòng)一格
left--;
right++;
}
// 得到長(zhǎng)度
return right - left - 1;
}
}
Kotlin
import kotlin.math.max
/**
* Created by TanJiaJun on 2021/6/14.
* 5. 最長(zhǎng)回文子串（Longest Palindromic Substring）
* 難度：中等
*
* @see <a >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))
}
/**
* 方法一：枚舉算法
* 時(shí)間復(fù)雜度：O(N^3)脂崔，其中N是字符串的長(zhǎng)度
* 空間復(fù)雜度：O(1)
*
* @param str 字符串
* @return 結(jié)果
*/
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 結(jié)果
*/
private fun isPalindromicSubstring(str: String): Boolean {
val length = str.length
for (i in 0 until length / 2) {
// 找出該元素作為回文子串的起始位置還有結(jié)束位置
if (str[i] != str[length - i - 1]) {
// 如果其中一個(gè)不相同，證明該字符串不是回文串
return false
}
}
// 如果字符都相同梧喷，證明該字符串是回文串
return true
}
/**
* 方法二：中心擴(kuò)展法（雙指針）
* 時(shí)間復(fù)雜度：O(N^2)砌左，其中N是字符串的長(zhǎng)度
* 空間復(fù)雜度：O(1)
*
* @param str 字符串
* @return 結(jié)果
*/
private fun expandAroundCenterLongestPalindrome(str: String): String {
var start = 0
var end = 0
str.forEachIndexed { index, _ ->
// 長(zhǎng)度是奇數(shù)
val oddLength = getExpandAroundCenterLength(str = str, left = index, right = index)
// 長(zhǎng)度是偶數(shù)
val evenLength = getExpandAroundCenterLength(str = str, left = index, right = index + 1)
// 得到最大長(zhǎng)度
val maxLength = max(oddLength, evenLength)
if (maxLength > end - start) {
// 得到起始位置
start = index - (maxLength - 1) / 2
// 得到結(jié)束位置
end = index + maxLength / 2
}
}
return str.substring(start, end + 1)
}
/**
* 得到中心往兩邊擴(kuò)展的長(zhǎng)度
*
* @param str 字符串
* @param left 左指針
* @param right 右指針
* @return 長(zhǎng)度
*/
private fun getExpandAroundCenterLength(str: String, left: Int, right: Int): Int {
var l = left
var r = right
// 找出該元素作為回文子串的起始位置還有結(jié)束位置
while ((l >= 0 && r < str.length && str[l] == str[r])) {
// 如果符合條件，左指針向左移動(dòng)一格铺敌，右指針向右移動(dòng)一格
l--
r++
}
// 得到長(zhǎng)度
return r - l - 1
}
}
題解
枚舉
// LongestPalindromicSubstringKotlin.kt
/**
* 方法一：枚舉
* 時(shí)間復(fù)雜度：O(N^3)汇歹，其中N是字符串的長(zhǎng)度
* 空間復(fù)雜度：O(1)
*
* @param str 字符串
* @return 結(jié)果
*/
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 結(jié)果
*/
private fun isPalindromicSubstring(str: String): Boolean {
val length = str.length
for (i in 0 until length / 2) {
// 找出該元素作為回文子串的起始位置還有結(jié)束位置
if (str[i] != str[length - i - 1]) {
// 如果其中一個(gè)不相同，證明該字符串不是回文串
return false
}
}
// 如果字符都相同偿凭，證明該字符串是回文串
return true
}
時(shí)間復(fù)雜度：O(N^3)产弹，其中N是字符串的長(zhǎng)度。
空間復(fù)雜度：O(1)弯囊。
暴力解法痰哨，枚舉所有元素，要注意的是匾嘱，由于回文串的特征是正讀和反讀都一樣斤斧，例如：abba就是回文串，abda就不是回文串了霎烙，所以我們只要找到某個(gè)字符折欠，并且找到該字符對(duì)應(yīng)索引的字符，只需要遍歷該數(shù)組長(zhǎng)度一半就可以判斷該字符串是否為回文串吼过，注釋寫(xiě)得挺詳細(xì)了锐秦，這里就不再贅述了。
中心擴(kuò)展法（雙指針）
// LongestPalindromicSubstringKotlin.kt
/**
* 方法二：中心擴(kuò)展法（雙指針）
* 時(shí)間復(fù)雜度：O(N^2)盗忱，其中N是字符串的長(zhǎng)度
* 空間復(fù)雜度：O(1)
*
* @param str 字符串
* @return 結(jié)果
*/
private fun expandAroundCenterLongestPalindrome(str: String): String {
var start = 0
var end = 0
str.forEachIndexed { index, _ ->
// 長(zhǎng)度是奇數(shù)
val oddLength = getExpandAroundCenterLength(str = str, left = index, right = index)
// 長(zhǎng)度是偶數(shù)
val evenLength = getExpandAroundCenterLength(str = str, left = index, right = index + 1)
// 得到最大長(zhǎng)度
val maxLength = max(oddLength, evenLength)
if (maxLength > end - start) {
// 得到起始位置
start = index - (maxLength - 1) / 2
// 得到結(jié)束位置
end = index + maxLength / 2
}
}
return str.substring(start, end + 1)
}
/**
* 得到中心往兩邊擴(kuò)展的長(zhǎng)度
*
* @param str 字符串
* @param left 左指針
* @param right 右指針
* @return 長(zhǎng)度
*/
private fun getExpandAroundCenterLength(str: String, left: Int, right: Int): Int {
var l = left
var r = right
// 找出該元素作為回文子串的起始位置還有結(jié)束位置
while ((l >= 0 && r < str.length && str[l] == str[r])) {
// 如果符合條件酱床，左指針向左移動(dòng)一格，右指針向右移動(dòng)一格
l--
r++
}
// 得到長(zhǎng)度
return r - l - 1
}
時(shí)間復(fù)雜度：O(N^2)趟佃，其中N是字符串的長(zhǎng)度扇谣。
空間復(fù)雜度：O(1)。
由于回文串的特征是正讀和反讀都一樣闲昭，例如：abba就是回文串罐寨，abda就不是回文串了，所以我們可以從該字符串的中間向兩邊擴(kuò)展地遍歷序矩，這樣就能快速地得到最長(zhǎng)的回文子串鸯绿，要注意的是，因?yàn)閿?shù)組的長(zhǎng)度可能是奇數(shù)，也可能是偶數(shù)瓶蝴，如果是奇數(shù)的話毒返，中心點(diǎn)就只有一個(gè)；如果是偶數(shù)的話舷手，中心點(diǎn)就有兩個(gè)拧簸。
Z字形變換（ZigZag Conversion）
難度：中等
代碼
Java
/**
* Created by TanJiaJun on 2021/6/12.
* 6. Z字形變換（ZigZag Conversion）
* 難度：中等
*
* @see <a >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));
}
/**
* 時(shí)間復(fù)雜度：O(N)，其中N是字符串的長(zhǎng)度
* 空間復(fù)雜度：O(N)
*
* @param str 字符串
* @param numRows 行數(shù)
* @return 結(jié)果
*/
private static String convert(String str, int numRows) {
if (numRows == 1) {
// 如果只是一行的話男窟，就直接返回該字符串
return str;
}
// 創(chuàng)建長(zhǎng)度是行數(shù)的StringBuilder數(shù)組盆赤，并且每個(gè)元素都創(chuàng)建StringBuilder對(duì)象
StringBuilder[] stringBuilders = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) {
stringBuilders[i] = new StringBuilder();
}
// 索引
int index = 0;
// 行數(shù)
int row = 0;
int length = str.length();
while (index < length) {
// 從第一行開(kāi)始，按照行數(shù)添加到對(duì)應(yīng)的數(shù)組歉眷，并且追加字符弟劲，然后一直遍歷到最后一行對(duì)應(yīng)的數(shù)組
while (index < length && row < numRows) {
char ch = str.charAt(index++);
stringBuilders[row++].append(ch);
}
// 此時(shí)row是最后一行，所以我們需要回到倒數(shù)第二行姥芥，執(zhí)行以下邏輯
row = numRows - 2;
// 從倒數(shù)第二行開(kāi)始兔乞，按照行數(shù)添加到對(duì)應(yīng)的數(shù)組，并且追加字符凉唐，然后一直遍歷到第一行的對(duì)應(yīng)的數(shù)組
while (index < length && row >= 0) {
char ch = str.charAt(index++);
stringBuilders[row--].append(ch);
}
// 此時(shí)row是-1庸追，所以我們需要回到第二行，執(zhí)行以下邏輯
row += 2;
}
// 創(chuàng)建一個(gè)新的StringBuilder台囱，將每一行對(duì)應(yīng)的StringBuilder數(shù)組對(duì)應(yīng)的StringBuilder追加到這個(gè)對(duì)象
StringBuilder resultSB = new StringBuilder();
for (StringBuilder stringBuilder : stringBuilders) {
resultSB.append(stringBuilder);
}
// 將這個(gè)StringBuilder轉(zhuǎn)成字符串
return resultSB.toString();
}
}
Kotlin
/**
* Created by TanJiaJun on 2021/6/14.
* 6. Z字形變換（ZigZag Conversion）
* 難度：中等
*
* @see <a >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))
}
/**
* 時(shí)間復(fù)雜度：O(N)淡溯，其中N是字符串的長(zhǎng)度
* 空間復(fù)雜度：O(N)
*
* @param str 字符串
* @param numRows 行數(shù)
* @return 結(jié)果
*/
private fun convert(str: String, numRows: Int): String {
if (numRows == 1) {
// 如果只是一行的話，就直接返回該字符串
return str
}
// 創(chuàng)建長(zhǎng)度是行數(shù)的StringBuilder數(shù)組簿训，并且每個(gè)元素都創(chuàng)建StringBuilder對(duì)象
val stringBuilders = Array(numRows, init = { StringBuilder() })
// 索引
var index = 0
// 行數(shù)
var row = 0
val length = str.length
while (index < length) {
// 從第一行開(kāi)始咱娶，按照行數(shù)添加到對(duì)應(yīng)的數(shù)組，并且追加字符强品，然后一直遍歷到最后一行對(duì)應(yīng)的數(shù)組
while (index < length && row < numRows) {
stringBuilders[row++].append(str[index++])
}
// 此時(shí)row是最后一行膘侮，所以我們需要回到倒數(shù)第二行，執(zhí)行以下邏輯
row = numRows - 2
// 從倒數(shù)第二行開(kāi)始的榛，按照行數(shù)添加到對(duì)應(yīng)的數(shù)組琼了，并且追加字符，然后一直遍歷到第一行的對(duì)應(yīng)的數(shù)組
while (index < length && row >= 0) {
stringBuilders[row--].append(str[index++])
}
// 此時(shí)row是-1夫晌，所以我們需要回到第二行雕薪，執(zhí)行以下邏輯
row += 2
}
// 創(chuàng)建一個(gè)新的StringBuilder，將每一行對(duì)應(yīng)的StringBuilder數(shù)組對(duì)應(yīng)的StringBuilder追加到這個(gè)對(duì)象
val resultSB = StringBuilder()
stringBuilders.forEach { resultSB.append(it) }
// 將這個(gè)StringBuilder轉(zhuǎn)成字符串
return resultSB.toString()
}
}
時(shí)間復(fù)雜度：O(N)晓淀，其中N是字符串的長(zhǎng)度所袁。
空間復(fù)雜度：O(N)。
題解
根據(jù)題目我們可以知道凶掰，字符串是按著反向N字形排列的燥爷，我們可以先創(chuàng)建一個(gè)長(zhǎng)度是行數(shù)的StringBuilder數(shù)組蜈亩，然后定義一個(gè)row這樣的指針來(lái)確定行數(shù)，為了方便理解局劲，我舉個(gè)例子勺拣，假設(shè)字符串是PAYPALISHIRING奶赠，行數(shù)是3鱼填，我們從第一行開(kāi)始，按照行數(shù)將字符添加到對(duì)應(yīng)的數(shù)組毅戈，并且追加字符苹丸，然后一直遍歷到最后一行對(duì)應(yīng)的數(shù)組，此時(shí)這三個(gè)數(shù)組的情況如下所示：
- 第一個(gè)數(shù)組：P
- 第二個(gè)數(shù)組：A
- 第三個(gè)數(shù)組：Y
此時(shí)的row的值是4苇经，然后這個(gè)時(shí)候根據(jù)題目要求赘理，我們的指針要回到倒數(shù)第二行，所以我們就要將row的值調(diào)整為行數(shù)減去2扇单，也就是3-2等于1商模，然后開(kāi)始繼續(xù)遍歷，此時(shí)這三個(gè)數(shù)組的情況如下所示：
- 第一個(gè)數(shù)組：P
- 第二個(gè)數(shù)組：A蜘澜、P
- 第三個(gè)數(shù)組：Y
然后我們的指針要從倒數(shù)第二行開(kāi)始施流，按照行數(shù)添加到對(duì)應(yīng)的數(shù)組，并且追加字符鄙信，然后一直遍歷到第一行的對(duì)應(yīng)的數(shù)組瞪醋，此時(shí)這三個(gè)數(shù)組的情況如下所示：
- 第一個(gè)數(shù)組：P、A
- 第二個(gè)數(shù)組：A装诡、P银受、L
- 第三個(gè)數(shù)組：Y、I
此時(shí)row的值是-1鸦采，最后根據(jù)題目要求宾巍，我們的指針row要回到第二行，所以我們就要將row的值調(diào)整為自增2渔伯，也就是-1+2等于1蜀漆，然后開(kāi)始繼續(xù)遍歷，此時(shí)這三個(gè)數(shù)組的情況如下所示：
- 第一個(gè)數(shù)組：P咱旱、A
- 第二個(gè)數(shù)組：A确丢、P、L吐限、S
- 第三個(gè)數(shù)組：Y鲜侥、I
以此類(lèi)推遍歷下去，后面的邏輯就跟前面的邏輯一樣了诸典，這里就不再贅述了描函。
最后將這個(gè)StringBuilder數(shù)組遍歷后追加到一個(gè)新的StringBuilder對(duì)象，然后轉(zhuǎn)成字符串就可以得到最后的結(jié)果了。
我的GitHub：TanJiaJunBeyond
Android通用框架：Android通用框架
我的掘金：譚嘉俊
我的簡(jiǎn)書(shū)：譚嘉俊
我的CSDN：譚嘉俊
