本系列通過Java和Kotlin這兩種語言來解決力扣上面的算法題夺克，由于本人算法菜鳥一枚弟晚，可能部分題目并不是最優(yōu)題解忘衍，希望能和各位大神共同討論~
項(xiàng)目的GitHub：Algorithm
盛最多水的容器（Container With Most Water）
難度：中等
代碼
Java
/**
* Created by TanJiaJun on 2021/6/20.
* 11. 盛最多水的容器（Container With Most Water）
* 難度：簡單
*
* @see <a >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));
}
/**
* 雙指針
* 時(shí)間復(fù)雜度：O(N)逾苫，其中N是數(shù)組heights的大小
* 空間復(fù)雜度：O(1)
*
* @param heights 高度數(shù)組
* @return 最大容量
*/
private static int maxArea(int[] heights) {
// 將左指針放置在數(shù)組的第一個(gè)元素
int left = 0;
// 將右指針放置在數(shù)組的最后一個(gè)元素
int right = heights.length - 1;
int result = 0;
// 循環(huán)遍歷直至左右指針到達(dá)同一個(gè)位置
while (left != right) {
// 寬度的值可以通過右指針的索引減去左指針的索引得到
int width = right - left;
// 根據(jù)題義可知，要想得到最大的盛水面積枚钓，高度就需要取左指針和右指針?biāo)谠氐淖钚≈? int height = Math.min(heights[left], heights[right]);
// 取最大的面積
result = Math.max(result, width * height);
if (heights[left] < heights[right]) {
// 如果左指針對(duì)應(yīng)的元素小于右指針對(duì)應(yīng)的元素铅搓，就將左指針向右移動(dòng)一格
left++;
} else {
// 如果左指針對(duì)應(yīng)的元素大于右指針對(duì)應(yīng)的元素，就將右指針向左移動(dòng)一格
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 >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))
}
/**
* 雙指針
* 時(shí)間復(fù)雜度：O(N)搀捷，其中N是數(shù)組heights的大小
* 空間復(fù)雜度：O(1)
*
* @param heights 高度數(shù)組
* @return 最大容量
*/
private fun maxArea(heights: IntArray): Int {
// 將左指針放置在數(shù)組的第一個(gè)元素
var left = 0
// 將右指針放置在數(shù)組的最后一個(gè)元素
var right = heights.size - 1
var result = 0
// 循環(huán)遍歷直至左右指針到達(dá)同一個(gè)位置
while (left != right) {
// 寬度的值可以通過右指針的索引減去左指針的索引得到
val width = right - left
// 根據(jù)題義可知星掰，要想得到最大的盛水面積，高度就需要取左指針和右指針?biāo)谠氐淖钚≈? val height = min(heights[left], heights[right])
// 取最大的面積
result = max(result, width * height)
if (heights[left] < heights[right]) {
// 如果左指針對(duì)應(yīng)的元素小于右指針對(duì)應(yīng)的元素嫩舟，就將左指針向右移動(dòng)一格
left++
} else {
// 如果左指針對(duì)應(yīng)的元素大于右指針對(duì)應(yīng)的元素蹋偏，就將右指針向左移動(dòng)一格
right--
}
}
return result
}
}
時(shí)間復(fù)雜度：O(N)，其中N是數(shù)組heights的大小至壤。
空間復(fù)雜度：O(1)威始。
題解
我們可以使用雙指針解決這道算法題，將左指針放置在數(shù)組的第一個(gè)元素像街，將右指針放置在數(shù)組的最后一個(gè)元素黎棠，寬度的值可以通過右指針的索引減去左指針的索引得到，根據(jù)題義可知镰绎，要想得到最大的盛水面積脓斩，那么高度取決于最小的值，所以我們可以取左指針和右指針所在元素的最小值畴栖，要注意的是随静，如果左指針對(duì)應(yīng)的元素小于右指針對(duì)應(yīng)的元素，我們可以將左指針向右移動(dòng)一格吗讶，否則將右指針向左移動(dòng)一格燎猛，直到左指針和右指針到達(dá)同一個(gè)位置。
整數(shù)轉(zhuǎn)羅馬數(shù)字（Integer to Roman）
難度：中等
代碼
Java
/**
* Created by TanJiaJun on 2021/6/27.
* 12. 整數(shù)轉(zhuǎn)羅馬數(shù)字（Integer to Roman）
* 難度：中等
*
* @see <a >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));
}
/**
* 貪心算法
* 時(shí)間復(fù)雜度：O(N)照皆，其中N是數(shù)組num的位數(shù)
* 空間復(fù)雜度：O(1)
*
* @param num 要轉(zhuǎn)成羅馬數(shù)字的整數(shù)
* @return 羅馬數(shù)字
*/
private static String intToRoman(int num) {
// 枚舉羅馬數(shù)字七種字符
String[] strs = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
// 枚舉羅馬數(shù)字七種字符對(duì)應(yīng)的整數(shù)
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]) {
// 如果該數(shù)值大于枚舉的羅馬數(shù)字對(duì)應(yīng)的整數(shù)重绷，就用這個(gè)數(shù)值減去該整數(shù)，并且賦值給num
num -= ints[index];
// 將該羅馬數(shù)字記錄下來
stringBuilder.append(strs[index]);
} else {
// 如果該數(shù)值小于枚舉的羅馬數(shù)字對(duì)應(yīng)的整數(shù)膜毁，就索引往右邊移動(dòng)一格
index++;
}
}
return stringBuilder.toString();
}
}
Kotlin
/**
* Created by TanJiaJun on 2021/7/21.
* 12. 整數(shù)轉(zhuǎn)羅馬數(shù)字（Integer to Roman）
* 難度：中等
*
* @see <a >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))
}
/**
* 貪心算法
* 時(shí)間復(fù)雜度：O(N)昭卓，其中N是數(shù)組num的位數(shù)
* 空間復(fù)雜度：O(1)
*
* @param num 要轉(zhuǎn)成羅馬數(shù)字的整數(shù)
* @return 羅馬數(shù)字
*/
private fun intToRoman(num: Int): String =
StringBuilder()
.apply {
var number = num
// 枚舉羅馬數(shù)字七種字符
val strs = arrayOf("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")
// 枚舉羅馬數(shù)字七種字符對(duì)應(yīng)的整數(shù)
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]) {
// 如果該數(shù)值大于枚舉的羅馬數(shù)字對(duì)應(yīng)的整數(shù)，就用這個(gè)數(shù)值減去該整數(shù)瘟滨，并且賦值給num
number -= ints[index]
// 將該羅馬數(shù)字記錄下來
append(strs[index])
} else {
// 如果該數(shù)值小于枚舉的羅馬數(shù)字對(duì)應(yīng)的整數(shù)候醒，就索引往右邊移動(dòng)一格
index++
}
}
}
.toString()
}
時(shí)間復(fù)雜度：O(N)，其中N是數(shù)組num的位數(shù)杂瘸。
空間復(fù)雜度：O(1)倒淫。
題解
根據(jù)題義可知，我們每次比較都優(yōu)先使用最大的數(shù)胧沫，所以該題可以使用貪心算法來解決昌简。
貪心算法又稱為貪婪算法，它是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或者最優(yōu)的選擇绒怨，從而導(dǎo)致結(jié)果是最好或者最優(yōu)的算法纯赎，在現(xiàn)實(shí)生活中找零錢的時(shí)候，我們會(huì)優(yōu)先使用最大面值的紙幣或者硬幣來找零錢南蹂，這樣就可以使對(duì)方拿到的紙幣或者硬幣數(shù)量最少犬金，其實(shí)這就是一種貪心算法的體現(xiàn)。
回到題目六剥，我們可以使用兩個(gè)數(shù)組分別記錄羅馬數(shù)字的七種字符和它們對(duì)應(yīng)的整數(shù)晚顷，要注意的是，為了方便我們遍歷疗疟，這兩個(gè)數(shù)組中的元素要按照數(shù)值的大小從大到小存放该默，在遍歷的時(shí)候，如果遇到大于羅馬數(shù)字字符數(shù)組的元素策彤，就用變量number減去該羅馬數(shù)字字符對(duì)應(yīng)的整數(shù)栓袖，并且將該羅馬數(shù)字記錄下來，否則就增加索引值店诗，繼續(xù)遍歷后面的羅馬數(shù)組裹刮。
羅馬數(shù)字轉(zhuǎn)整數(shù)（Roman to Integer）
難度：簡單
代碼
Java
/**
* Created by TanJiaJun on 2021/7/19.
* 13. 羅馬數(shù)字轉(zhuǎn)整數(shù)（Roman to Integer）
* 難度：簡單
*
* @see <a >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));
}
/**
* 時(shí)間復(fù)雜度：O(N)，其中N是字符串s的長度
* 空間復(fù)雜度：O(1)
*
* @param s 羅馬數(shù)字
* @return 整數(shù)
*/
private static int romanToInt(String s) {
// 得到第一個(gè)羅馬數(shù)字
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));
// 用這個(gè)數(shù)字的前一個(gè)數(shù)字與其比較
if (preNum < num) {
// 根據(jù)題義可知庞瘸，如果這個(gè)數(shù)字大于前一個(gè)數(shù)字捧弃，就做減法運(yùn)算，減去前一個(gè)數(shù)字
result -= preNum;
} else {
// 根據(jù)題義可知擦囊，如果這個(gè)數(shù)字小于前一個(gè)數(shù)字违霞，就做加法運(yùn)算，加上前一個(gè)數(shù)字
result += preNum;
}
// 記錄前一個(gè)數(shù)字
preNum = num;
}
// 相加得出最后的結(jié)果
result += preNum;
return result;
}
/**
* 通過羅馬數(shù)字字符得到對(duì)應(yīng)的整數(shù)
*
* @param roman 羅馬數(shù)字字符
* @return 整數(shù)
*/
private static int getInteger(char roman) {
// 枚舉羅馬數(shù)字七種字符和對(duì)應(yīng)的整數(shù)
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. 羅馬數(shù)字轉(zhuǎn)整數(shù)（Roman to Integer）
* 難度：簡單
*
* @see <a >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))
}
/**
* 時(shí)間復(fù)雜度：O(N)瞬场，其中N是字符串s的長度
* 空間復(fù)雜度：O(1)
*
* @param s 羅馬數(shù)字
* @return 整數(shù)
*/
private fun romanToInt(s: String): Int {
// 得到第一個(gè)羅馬數(shù)字
var preNum = getInteger(s[0])
var result = 0
var i = 1
val length = s.length
while (i < length) {
val num = getInteger(s[i])
// 用這個(gè)數(shù)字的前一個(gè)數(shù)字與其比較
if (preNum < num) {
// 根據(jù)題義可知葛家，如果這個(gè)數(shù)字大于前一個(gè)數(shù)字，就做減法運(yùn)算泌类，減去前一個(gè)數(shù)字
result -= preNum
} else {
// 根據(jù)題義可知癞谒，如果這個(gè)數(shù)字小于前一個(gè)數(shù)字，就做加法運(yùn)算刃榨，加上前一個(gè)數(shù)字
result += preNum
}
// 記錄前一個(gè)數(shù)字
preNum = num
i++
}
// 相加得出最后的結(jié)果
result += preNum
return result
}
/**
* 通過羅馬數(shù)字字符得到對(duì)應(yīng)的整數(shù)
*
* @param roman 羅馬數(shù)字字符
* @return 整數(shù)
*/
private fun getInteger(roman: Char): Int =
// 枚舉羅馬數(shù)字七種字符和對(duì)應(yīng)的整數(shù)
when (roman) {
'I' -> 1
'V' -> 5
'X' -> 10
'L' -> 50
'C' -> 100
'D' -> 500
'M' -> 1000
else -> 0
}
}
時(shí)間復(fù)雜度：O(N)弹砚，其中N是字符串s的長度。
空間復(fù)雜度：O(1)枢希。
題解
根據(jù)題義可知桌吃，如果羅馬數(shù)字一個(gè)小的值放在一個(gè)大的值的左邊，就是做減法運(yùn)算苞轿，例如：IV等于5-1茅诱，結(jié)果是4逗物，否則就做加法運(yùn)算，例如：VI等于5+1瑟俭，結(jié)果是6翎卓，要注意的是，我們每做一次遍歷的時(shí)候摆寄，都要記錄下前一個(gè)數(shù)字失暴，方便我們做比較，其他邏輯的話微饥，代碼也寫了不少注釋逗扒，這里就不再贅述了。
我的GitHub：TanJiaJunBeyond
Android通用框架：Android通用框架
我的掘金：譚嘉俊
我的簡書：譚嘉俊
我的CSDN：譚嘉俊
