本系列通过Java和Kotlin这两种语言来解决力扣上面的算法题，由于本人算法菜鸟一枚，可能部分题目并不是最优题解，希望能和各位大神共同讨论~
项目的GitHub：Algorithm
盛最多水的容器（Container With Most Water）
难度：中等
代码
Java
/**
* Created by TanJiaJun on 2021/6/20.
* 11. 盛最多水的容器（Container With Most Water）
* 难度：简单
*
* @see <a href="https://leetcode-cn.com/problems/container-with-most-water/">Container With Most Water</a>
*/
class ContainerWithMostWater {
public static void main(String[] args) {
// 示例一
System.out.print("示例一：");
int[] firstHeights = {1, 8, 6, 2, 5, 4, 8, 3, 7};
System.out.println(maxArea(firstHeights));
System.out.print("\n");
// 示例二
System.out.print("示例二：");
int[] secondHeights = {1, 1};
System.out.println(maxArea(secondHeights));
System.out.print("\n");
// 示例三
System.out.print("示例三：");
int[] thirdHeights = {4, 3, 2, 1, 4};
System.out.println(maxArea(thirdHeights));
System.out.print("\n");
// 示例四
System.out.print("示例四：");
int[] fourthHeights = {1, 2, 1};
System.out.println(maxArea(fourthHeights));
}
/**
* 双指针
* 时间复杂度：O(N)，其中N是数组heights的大小
* 空间复杂度：O(1)
*
* @param heights 高度数组
* @return 最大容量
*/
private static int maxArea(int[] heights) {
// 将左指针放置在数组的第一个元素
int left = 0;
// 将右指针放置在数组的最后一个元素
int right = heights.length - 1;
int result = 0;
// 循环遍历直至左右指针到达同一个位置
while (left != right) {
// 宽度的值可以通过右指针的索引减去左指针的索引得到
int width = right - left;
// 根据题义可知，要想得到最大的盛水面积，高度就需要取左指针和右指针所在元素的最小值
int height = Math.min(heights[left], heights[right]);
// 取最大的面积
result = Math.max(result, width * height);
if (heights[left] < heights[right]) {
// 如果左指针对应的元素小于右指针对应的元素，就将左指针向右移动一格
left++;
} else {
// 如果左指针对应的元素大于右指针对应的元素，就将右指针向左移动一格
right--;
}
}
return result;
}
}
Kotlin
import kotlin.math.max
import kotlin.math.min
/**
* Created by TanJiaJun on 2021/7/20.
* 11. 盛最多水的容器（Container With Most Water）
* 难度：简单
*
* @see <a href="https://leetcode-cn.com/problems/container-with-most-water/">Container With Most Water</a>
*/
object ContainerWithMostWaterKotlin {
@JvmStatic
fun main(args: Array<String>) {
// 示例一
print("示例一：")
val firstHeights = intArrayOf(1, 8, 6, 2, 5, 4, 8, 3, 7)
println(maxArea(firstHeights))
print("\n")
// 示例二
print("示例二：")
val secondHeights = intArrayOf(1, 1)
println(maxArea(secondHeights))
print("\n")
// 示例三
print("示例三：")
val thirdHeights = intArrayOf(4, 3, 2, 1, 4)
println(maxArea(thirdHeights))
print("\n")
// 示例四
print("示例四：")
val fourthHeights = intArrayOf(1, 2, 1)
println(maxArea(fourthHeights))
}
/**
* 双指针
* 时间复杂度：O(N)，其中N是数组heights的大小
* 空间复杂度：O(1)
*
* @param heights 高度数组
* @return 最大容量
*/
private fun maxArea(heights: IntArray): Int {
// 将左指针放置在数组的第一个元素
var left = 0
// 将右指针放置在数组的最后一个元素
var right = heights.size - 1
var result = 0
// 循环遍历直至左右指针到达同一个位置
while (left != right) {
// 宽度的值可以通过右指针的索引减去左指针的索引得到
val width = right - left
// 根据题义可知，要想得到最大的盛水面积，高度就需要取左指针和右指针所在元素的最小值
val height = min(heights[left], heights[right])
// 取最大的面积
result = max(result, width * height)
if (heights[left] < heights[right]) {
// 如果左指针对应的元素小于右指针对应的元素，就将左指针向右移动一格
left++
} else {
// 如果左指针对应的元素大于右指针对应的元素，就将右指针向左移动一格
right--
}
}
return result
}
}
时间复杂度：O(N)，其中N是数组heights的大小。
空间复杂度：O(1)。
题解
我们可以使用双指针解决这道算法题，将左指针放置在数组的第一个元素，将右指针放置在数组的最后一个元素，宽度的值可以通过右指针的索引减去左指针的索引得到，根据题义可知，要想得到最大的盛水面积，那么高度取决于最小的值，所以我们可以取左指针和右指针所在元素的最小值，要注意的是，如果左指针对应的元素小于右指针对应的元素，我们可以将左指针向右移动一格，否则将右指针向左移动一格，直到左指针和右指针到达同一个位置。
整数转罗马数字（Integer to Roman）
难度：中等
代码
Java
/**
* Created by TanJiaJun on 2021/6/27.
* 12. 整数转罗马数字（Integer to Roman）
* 难度：中等
*
* @see <a href="https://leetcode-cn.com/problems/integer-to-roman/">Integer to Roman</a>
*/
class IntegerToRoman {
public static void main(String[] args) {
// 示例一
System.out.print("示例一：");
int firstNumber = 3;
System.out.println(intToRoman(firstNumber));
System.out.print("\n");
// 示例二
System.out.print("示例二：");
int secondNumber = 4;
System.out.println(intToRoman(secondNumber));
System.out.print("\n");
// 示例三
System.out.print("示例三：");
int thirdNumber = 58;
System.out.println(intToRoman(thirdNumber));
System.out.print("\n");
// 示例四
System.out.print("示例四：");
int fourthNumber = 1994;
System.out.println(intToRoman(fourthNumber));
}
/**
* 贪心算法
* 时间复杂度：O(N)，其中N是数组num的位数
* 空间复杂度：O(1)
*
* @param num 要转成罗马数字的整数
* @return 罗马数字
*/
private static String intToRoman(int num) {
// 枚举罗马数字七种字符
String[] strs = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
// 枚举罗马数字七种字符对应的整数
int[] ints = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
StringBuilder stringBuilder = new StringBuilder();
int index = 0;
while (index < 13) {
if (num >= ints[index]) {
// 如果该数值大于枚举的罗马数字对应的整数，就用这个数值减去该整数，并且赋值给num
num -= ints[index];
// 将该罗马数字记录下来
stringBuilder.append(strs[index]);
} else {
// 如果该数值小于枚举的罗马数字对应的整数，就索引往右边移动一格
index++;
}
}
return stringBuilder.toString();
}
}
Kotlin
/**
* Created by TanJiaJun on 2021/7/21.
* 12. 整数转罗马数字（Integer to Roman）
* 难度：中等
*
* @see <a href="https://leetcode-cn.com/problems/integer-to-roman/">Integer to Roman</a>
*/
object IntegerToRomanKotlin {
@JvmStatic
fun main(args: Array<String>) {
// 示例一
print("示例一：")
val firstNumber = 3
println(intToRoman(firstNumber))
print("\n")
// 示例二
print("示例二：")
val secondNumber = 4
println(intToRoman(secondNumber))
print("\n")
// 示例三
print("示例三：")
val thirdNumber = 58
println(intToRoman(thirdNumber))
print("\n")
// 示例四
print("示例四：")
val fourthNumber = 1994
println(intToRoman(fourthNumber))
}
/**
* 贪心算法
* 时间复杂度：O(N)，其中N是数组num的位数
* 空间复杂度：O(1)
*
* @param num 要转成罗马数字的整数
* @return 罗马数字
*/
private fun intToRoman(num: Int): String =
StringBuilder()
.apply {
var number = num
// 枚举罗马数字七种字符
val strs = arrayOf("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")
// 枚举罗马数字七种字符对应的整数
val ints = intArrayOf(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
var index = 0
while (index < 13) {
if (number >= ints[index]) {
// 如果该数值大于枚举的罗马数字对应的整数，就用这个数值减去该整数，并且赋值给num
number -= ints[index]
// 将该罗马数字记录下来
append(strs[index])
} else {
// 如果该数值小于枚举的罗马数字对应的整数，就索引往右边移动一格
index++
}
}
}
.toString()
}
时间复杂度：O(N)，其中N是数组num的位数。
空间复杂度：O(1)。
题解
根据题义可知，我们每次比较都优先使用最大的数，所以该题可以使用贪心算法来解决。
贪心算法又称为贪婪算法，它是一种在每一步选择中都采取在当前状态下最好或者最优的选择，从而导致结果是最好或者最优的算法，在现实生活中找零钱的时候，我们会优先使用最大面值的纸币或者硬币来找零钱，这样就可以使对方拿到的纸币或者硬币数量最少，其实这就是一种贪心算法的体现。
回到题目，我们可以使用两个数组分别记录罗马数字的七种字符和它们对应的整数，要注意的是，为了方便我们遍历，这两个数组中的元素要按照数值的大小从大到小存放，在遍历的时候，如果遇到大于罗马数字字符数组的元素，就用变量number减去该罗马数字字符对应的整数，并且将该罗马数字记录下来，否则就增加索引值，继续遍历后面的罗马数组。
罗马数字转整数（Roman to Integer）
难度：简单
代码
Java
/**
* Created by TanJiaJun on 2021/7/19.
* 13. 罗马数字转整数（Roman to Integer）
* 难度：简单
*
* @see <a href="https://leetcode-cn.com/problems/roman-to-integer/">Roman to Integer</a>
*/
class RomanToInteger {
public static void main(String[] args) {
// 示例一
System.out.print("示例一：");
String firstStr = "III";
System.out.println(romanToInt(firstStr));
System.out.print("\n");
// 示例二
System.out.print("示例二：");
String secondStr = "IV";
System.out.println(romanToInt(secondStr));
System.out.print("\n");
// 示例三
System.out.print("示例三：");
String thirdStr = "IX";
System.out.println(romanToInt(thirdStr));
System.out.print("\n");
// 示例四
System.out.print("示例四：");
String fourthStr = "LVIII";
System.out.println(romanToInt(fourthStr));
System.out.print("\n");
// 示例五
System.out.print("示例五：");
String fifthStr = "MCMXCIV";
System.out.println(romanToInt(fifthStr));
}
/**
* 时间复杂度：O(N)，其中N是字符串s的长度
* 空间复杂度：O(1)
*
* @param s 罗马数字
* @return 整数
*/
private static int romanToInt(String s) {
// 得到第一个罗马数字
int preNum = getInteger(s.charAt(0));
int result = 0;
for (int i = 1, length = s.length(); i < length; i++) {
int num = getInteger(s.charAt(i));
// 用这个数字的前一个数字与其比较
if (preNum < num) {
// 根据题义可知，如果这个数字大于前一个数字，就做减法运算，减去前一个数字
result -= preNum;
} else {
// 根据题义可知，如果这个数字小于前一个数字，就做加法运算，加上前一个数字
result += preNum;
}
// 记录前一个数字
preNum = num;
}
// 相加得出最后的结果
result += preNum;
return result;
}
/**
* 通过罗马数字字符得到对应的整数
*
* @param roman 罗马数字字符
* @return 整数
*/
private static int getInteger(char roman) {
// 枚举罗马数字七种字符和对应的整数
return switch (roman) {
case 'I' -> 1;
case 'V' -> 5;
case 'X' -> 10;
case 'L' -> 50;
case 'C' -> 100;
case 'D' -> 500;
case 'M' -> 1000;
default -> 0;
};
}
}
Kotlin
/**
* Created by TanJiaJun on 2021/7/21.
* 13. 罗马数字转整数（Roman to Integer）
* 难度：简单
*
* @see <a href="https://leetcode-cn.com/problems/roman-to-integer/">Roman to Integer</a>
*/
object RomanToIntegerKotlin {
@JvmStatic
fun main(args: Array<String>) {
// 示例一
print("示例一：")
val firstStr = "III"
println(romanToInt(firstStr))
print("\n")
// 示例二
print("示例二：")
val secondStr = "IV"
println(romanToInt(secondStr))
print("\n")
// 示例三
print("示例三：")
val thirdStr = "IX"
println(romanToInt(thirdStr))
print("\n")
// 示例四
print("示例四：")
val fourthStr = "LVIII"
println(romanToInt(fourthStr))
print("\n")
// 示例五
print("示例五：")
val fifthStr = "MCMXCIV"
println(romanToInt(fifthStr))
}
/**
* 时间复杂度：O(N)，其中N是字符串s的长度
* 空间复杂度：O(1)
*
* @param s 罗马数字
* @return 整数
*/
private fun romanToInt(s: String): Int {
// 得到第一个罗马数字
var preNum = getInteger(s[0])
var result = 0
var i = 1
val length = s.length
while (i < length) {
val num = getInteger(s[i])
// 用这个数字的前一个数字与其比较
if (preNum < num) {
// 根据题义可知，如果这个数字大于前一个数字，就做减法运算，减去前一个数字
result -= preNum
} else {
// 根据题义可知，如果这个数字小于前一个数字，就做加法运算，加上前一个数字
result += preNum
}
// 记录前一个数字
preNum = num
i++
}
// 相加得出最后的结果
result += preNum
return result
}
/**
* 通过罗马数字字符得到对应的整数
*
* @param roman 罗马数字字符
* @return 整数
*/
private fun getInteger(roman: Char): Int =
// 枚举罗马数字七种字符和对应的整数
when (roman) {
'I' -> 1
'V' -> 5
'X' -> 10
'L' -> 50
'C' -> 100
'D' -> 500
'M' -> 1000
else -> 0
}
}
时间复杂度：O(N)，其中N是字符串s的长度。
空间复杂度：O(1)。
题解
根据题义可知，如果罗马数字一个小的值放在一个大的值的左边，就是做减法运算，例如：IV等于5-1，结果是4，否则就做加法运算，例如：VI等于5+1，结果是6，要注意的是，我们每做一次遍历的时候，都要记录下前一个数字，方便我们做比较，其他逻辑的话，代码也写了不少注释，这里就不再赘述了。
我的GitHub：TanJiaJunBeyond
Android通用框架：Android通用框架
我的掘金：谭嘉俊
我的简书：谭嘉俊
我的CSDN：谭嘉俊
网友评论