本系列通过Java和Kotlin这两种语言来解决力扣上面的算法题,由于本人算法菜鸟一枚,可能部分题目并不是最优题解,希望能和各位大神共同讨论~
阿俊带你用Kotlin刷算法(一)
阿俊带你用Kotlin刷算法(二)
阿俊带你用Kotlin刷算法(三)
阿俊带你用Kotlin刷算法(四)
项目的GitHub:Algorithm
最长公共前缀(Longest Common Prefix)
难度:简单
链接:Longest Common Prefix
代码
Java
/**
* Created by TanJiaJun on 2021/7/5.
* 14. 最长公共前缀(Longest Common Prefix)
* 难度:简单
*
* @see <a href="https://leetcode-cn.com/problems/longest-common-prefix/">Longest Common Prefix</a>
*/
class LongestCommonPrefix {
public static void main(String[] args) {
// 示例一
System.out.print("示例一:");
String[] firstStrs = {"flower", "flow", "flight"};
System.out.println(longestCommonPrefix(firstStrs));
System.out.print("\n");
// 示例二
System.out.print("示例二:");
String[] secondStrs = {"dog", "racecar", "car"};
System.out.println(longestCommonPrefix(secondStrs));
}
/**
* 横向扫描
* <p>
* 时间复杂度:O(mn),其中m是字符串数组strs中的字符串平均长度,n是字符串数组strs的长度。
* 空间复杂度:O(1),使用的空间复杂度为常数。
*
* @param strs 字符串数组
* @return 最长公共前缀字符串
*/
private static String longestCommonPrefix(String[] strs) {
if (strs == null) {
// 如果是空的字符串数组,就不运行下面的逻辑了,直接返回空字符串
return "";
}
String result = strs[0];
for (int i = 1, length = strs.length; i < length; i++) {
// 得到当前两个字符串的公共前缀
result = getLongestCommonPrefix(result, strs[i]);
if (result.isEmpty()) {
// 如果result是空字符串,说明当前两个字符串不存在公共前缀,证明该字符串数组中所有字符串之间不存在公共前缀,
// 所以跳出循环,不再遍历剩下的字符串,返回空字符串
break;
}
}
return result;
}
/**
* 得到两个字符串的公共前缀
*
* @param firstStr 第一个字符串
* @param secondStr 第二个字符串
* @return 两个字符串的最长公共前缀字符串,要注意的是,如果没有的话,就返回空字符串
*/
private static String getLongestCommonPrefix(String firstStr, String secondStr) {
// 得到两个字符串的最小长度
int minLen = Math.min(firstStr.length(), secondStr.length());
int index = 0;
// 遍历两个字符串的字符
while (index < minLen && firstStr.charAt(index) == secondStr.charAt(index)) {
// 如果索引小于最短长度,并且当前两个字符串的字符相同,就增加索引值
index++;
}
// 截取两个字符串的公共前缀,要注意的是,如果找不到公共前缀会返回空字符串
return firstStr.substring(0, index);
}
}
Kotlin
import kotlin.math.min
/**
* Created by TanJiaJun on 2021/7/24.
* 14. 最长公共前缀(Longest Common Prefix)
* 难度:简单
*
* @see <a href="https://leetcode-cn.com/problems/longest-common-prefix/">Longest Common Prefix</a>
*/
object LongestCommonPrefixKotlin {
@JvmStatic
fun main(args: Array<String>) {
// 示例一
print("示例一:")
val firstStrs = arrayOf("flower", "flow", "flight")
println(longestCommonPrefix(firstStrs))
print("\n")
// 示例二
print("示例二:")
val secondStrs = arrayOf("dog", "racecar", "car")
println(longestCommonPrefix(secondStrs))
}
/**
* 横向扫描
*
* 时间复杂度:O(mn),其中m是字符串数组strs中的字符串平均长度,n是字符串数组strs的长度。
* 空间复杂度:O(1),使用的空间复杂度为常数。
*
* @param strs 字符串数组
* @return 最长公共前缀字符串
*/
private fun longestCommonPrefix(strs: Array<String>): String {
var result: String = strs[0]
for (i in 1 until strs.size) {
// 得到当前两个字符串的公共前缀
result = getLongestCommonPrefix(result, strs[i])
if (result.isEmpty()) {
// 如果result是空字符串,说明当前两个字符串不存在公共前缀,证明该字符串数组中所有字符串之间不存在公共前缀,
// 所以跳出循环,不再遍历剩下的字符串,返回空字符串
break
}
}
return result
}
/**
* 得到两个字符串的公共前缀
*
* @param firstStr 第一个字符串
* @param secondStr 第二个字符串
* @return 两个字符串的最长公共前缀字符串,要注意的是,如果没有的话,就返回空字符串
*/
private fun getLongestCommonPrefix(firstStr: String, secondStr: String): String {
// 得到两个字符串的最小长度
val minLen = min(firstStr.length, secondStr.length)
var index = 0
// 遍历两个字符串的字符
while (index < minLen && firstStr[index] == secondStr[index]) {
// 如果索引小于最短长度,并且当前两个字符串的字符相同,就增加索引值
index++
}
// 截取两个字符串的公共前缀,要注意的是,如果找不到公共前缀会返回空字符串
return firstStr.substring(0, index)
}
}
时间复杂度
O(mn),其中m是字符串数组strs中的字符串平均长度,n是字符串数组strs的长度。
空间复杂度
O(1),使用的空间复杂度为常数。
题解
我们可以通过横向扫描来解决这道算法题。大概流程为依次遍历字符串数组中的每一个字符串,得到两个字符串的公共前缀,当遍历完所有字符串后,就能得到该字符串数组中的最长公共前缀。要注意的是,如果在尚未遍历完字符串数组的情况下,公共前缀返回为空字符串,说明当前两个字符串不存在公共前缀,证明该字符串数组中所有字符串之间不存在公共前缀,所以就不需要继续遍历剩下的字符串,返回空字符串作为结果。
三数之和(3Sum)
难度:中等
链接:3Sum
代码
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Created by TanJiaJun on 2021/7/25.
* 15. 三数之和(3Sum)
* 难度:中等
*
* @see <a href="https://leetcode-cn.com/problems/3sum/">3Sum</a>
*/
class ThreeSum {
public static void main(String[] args) {
// 示例一
System.out.print("示例一:");
int[] firstNums = {-1, 0, 1, 2, -1, -4};
System.out.println(threeSum(firstNums));
System.out.print("\n");
// 示例二
System.out.print("示例二:");
int[] secondNums = {};
System.out.println(threeSum(secondNums));
System.out.print("\n");
// 示例三
System.out.print("示例三:");
int[] thirdNums = {0};
System.out.println(threeSum(thirdNums));
}
/**
* 双指针
* <p>
* 时间复杂度:O(n^2),数组遍历为O(n),双指针遍历为O(n),总体为O(n)*O(n)=O(n^2)
* 空间复杂度:O(1),使用的空间复杂度为常数。
*
* @param nums 整型数组
* @return 结果集合
*/
private static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length < 3) {
// 如果数组为空或者其长度小于3,就返回空集合
return result;
}
// 将数组进行排序
Arrays.sort(nums);
for (int i = 0, length = nums.length; i < length - 2; i++) {
if (nums[i] > 0) {
// 如果当前起始元素大于0,由于数组已经进行排序,所以最小的元素都大于0,
// 证明三数之和肯定大于0,跳出循环,返回空集合
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
// 去除重复结果:从第二个元素开始,如果当前元素和上一个元素相等,那么会得到相同的结果,跳出当前循环
continue;
}
// 左指针:初始左指针为当前索引的下一个元素
int left = i + 1;
// 右指针:初始右指针为数组的最后一个元素
int right = length - 1;
// 遍历,使左右指针靠近
while (left < right) {
// 将当前元素、左指针对应的元素和右指针对应的元素相加
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
// 如果结果小于0,证明需要更大的元素,左指针往右移动一个元素
left++;
} else if (sum > 0) {
// 如果结果大于0,证明需要更小的元素,右指针往左移动一个元素
right--;
} else {
// 如果等于0,就把结果放进集合
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
// 去除重复结果:如果当前左指针对应的元素和下一个(右边)元素相等,就把左指针往右边移动多一个元素
left++;
}
// 左指针往右边移动一个元素
left++;
while (left < right && nums[right] == nums[right - 1]) {
// 去除重复结果:如果当前右指针对应的元素和下一个(左边)元素相等,就把右指针往左边移动多一个元素
right--;
}
// 右指针往左边移动一个元素
right--;
}
}
}
return result;
}
}
Kotlin
import java.util.*
/**
* Created by TanJiaJun on 2021/7/25.
* 15. 三数之和(3Sum)
* 难度:中等
*
* @see <a href="https://leetcode-cn.com/problems/3sum/">3Sum</a>
*/
object ThreeSumKotlin {
@JvmStatic
fun main(args: Array<String>) {
// 示例一
print("示例一:")
val firstNums = intArrayOf(-1, 0, 1, 2, -1, -4)
println(threeSum(firstNums))
print("\n")
// 示例二
print("示例二:")
val secondNums = intArrayOf()
println(threeSum(secondNums))
print("\n")
// 示例三
print("示例三:")
val thirdNums = intArrayOf(0)
println(threeSum(thirdNums))
}
/**
* 双指针
* <p>
* 时间复杂度:O(n^2),数组遍历为O(n),双指针遍历为O(n),总体为O(n)*O(n)=O(n^2)
* 空间复杂度:O(1),使用的空间复杂度为常数。
*
* @param nums 整型数组
* @return 结果集合
*/
private fun threeSum(nums: IntArray): List<List<Int>> =
mutableListOf<List<Int>>().apply {
if (nums.size < 3) {
// 如果数组为空或者其长度小于3,就返回空集合
return@apply
}
// 将数组进行排序
Arrays.sort(nums)
for (i in 0 until nums.size - 2) {
if (nums[i] > 0) {
// 如果当前起始元素大于0,由于数组已经进行排序,所以最小的元素都大于0,
// 证明三数之和肯定大于0,跳出循环,返回空集合
break
}
if (i > 0 && nums[i] == nums[i - 1]) {
// 去除重复结果:从第二个元素开始,如果当前元素和上一个元素相等,那么会得到相同的结果,跳出当前循环
continue
}
// 左指针:初始左指针为当前索引的下一个元素
var left = i + 1
// 右指针:初始右指针为数组的最后一个元素
var right = nums.size - 1
// 遍历,使左右指针靠近
while (left < right) {
// 将当前元素、左指针对应的元素和右指针对应的元素相加
val sum = nums[i] + nums[left] + nums[right]
when {
// 如果结果小于0,证明需要更大的元素,左指针往右移动一个元素
sum < 0 -> left++
// 如果结果大于0,证明需要更小的元素,右指针往左移动一个元素
sum > 0 -> right--
else -> {
// 如果等于0,就把结果放进集合
add(listOf(nums[i], nums[left], nums[right]))
while (left < right && nums[left] == nums[left + 1]) {
// 去除重复结果:如果当前左指针对应的元素和下一个(右边)元素相等,就把左指针往右边移动多一个元素
left++
}
// 左指针往右边移动一个元素
left++
while (left < right && nums[right] == nums[right - 1]) {
// 去除重复结果:如果当前右指针对应的元素和下一个(左边)元素相等,就把右指针往左边移动多一个元素
right--
}
// 右指针往左边移动一个元素
right--
}
}
}
}
}
}
时间复杂度
O(n^2),数组遍历为O(n),双指针遍历为O(n),总体为O(n)O(n)=O(n^2)*。
空间复杂度
O(1),使用的空间复杂度为常数。
题解
我们可以通过双指针来解决这道算法题。大概流程为遍历该数组,初始左指针设置为当前元素的下一个(右边)元素,初始右指针设置为数组的最后一个元素。通过遍历,使左右指针靠近,如果结果小于0,证明需要更大的元素,左指针往右移动一个元素;如果结果大于0,证明需要更小的元素,右指针往左移动一个元素;如果等于0,就把结果放进集合。要注意的是,有三个地方需要去除重复结果,如下所示:
从第二个元素开始,如果当前元素和上一个元素相等,那么会得到相同的结果,跳出当前循环。
如果当前左指针对应的元素和下一个(右边)元素相等,就把左指针往右边移动多一个元素。
如果当前右指针对应的元素和下一个(左边)元素相等,就把右指针往左边移动多一个元素。
我的GitHub:TanJiaJunBeyond
Android通用框架:Android通用框架
我的掘金:谭嘉俊
我的简书:谭嘉俊
我的CSDN:谭嘉俊