This series of Java and Kotlin these two languages to solve the force buckle above the algorithm, because I algorithm rookie one, may be part of the problem is not the best solution, I hope to discuss with you together ~
With Kotlin brush algorithm (1)
With Kotlin brush algorithm (2)
A Jun takes you to brush with Kotlin algorithm (3)
A Jun with you using Kotlin brush algorithm (4)
Project GitHub: Algorithm
Container With Most Water
Difficulty: Medium
Link: Container With Most Water
code
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) {
/ / sample
System.out.print(Example 1:);
int[] firstHeights = {1.8.6.2.5.4.8.3.7};
System.out.println(maxArea(firstHeights));
System.out.print("\n");
/ / sample 2
System.out.print("Example 2:");
int[] secondHeights = {1.1};
System.out.println(maxArea(secondHeights));
System.out.print("\n");
/ / sample 3
System.out.print("Example 3:");
int[] thirdHeights = {4.3.2.1.4};
System.out.println(maxArea(thirdHeights));
System.out.print("\n");
/ / sample 4
System.out.print("Example 4:");
int[] fourthHeights = {1.2.1};
System.out.println(maxArea(fourthHeights));
}
/** * Double pointer * time complexity: O(N), where N is the size of array heights * Space complexity: O(1) **@paramHeights Array of heights *@returnMaximum capacity */
private static int maxArea(int[] heights) {
// Place the left pointer on the first element of the array
int left = 0;
// Place the right pointer on the last element of the array
int right = heights.length - 1;
int result = 0;
// Loop until the left and right Pointers reach the same position
while(left ! = right) {// The width value can be obtained by subtracting the index of the left pointer from the index of the right pointer
int width = right - left;
// In order to obtain the maximum water area, the height should be the minimum value of the elements where the left and right Pointers are located
int height = Math.min(heights[left], heights[right]);
// Take the largest area
result = Math.max(result, width * height);
if (heights[left] < heights[right]) {
// If the element corresponding to the left pointer is less than the element corresponding to the right pointer, move the left pointer one space to the right
left++;
} else {
// If the element corresponding to the left pointer is larger than the element corresponding to the right pointer, move the right pointer one space to the leftright--; }}returnresult; }}Copy the codeKotlin
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>) {
/ / sample
print(Example 1:)
val firstHeights = intArrayOf(1.8.6.2.5.4.8.3.7)
println(maxArea(firstHeights))
print("\n")
/ / sample 2
print("Example 2:")
val secondHeights = intArrayOf(1.1)
println(maxArea(secondHeights))
print("\n")
/ / sample 3
print("Example 3:")
val thirdHeights = intArrayOf(4.3.2.1.4)
println(maxArea(thirdHeights))
print("\n")
/ / sample 4
print("Example 4:")
val fourthHeights = intArrayOf(1.2.1)
println(maxArea(fourthHeights))
}
/** * Double pointer * time complexity: O(N), where N is the size of array heights * Space complexity: O(1) **@paramHeights Array of heights *@returnMaximum capacity */
private fun maxArea(heights: IntArray): Int {
// Place the left pointer on the first element of the array
var left = 0
// Place the right pointer on the last element of the array
var right = heights.size - 1
var result = 0
// Loop until the left and right Pointers reach the same position
while(left ! = right) {// The width value can be obtained by subtracting the index of the left pointer from the index of the right pointer
val width = right - left
// In order to obtain the maximum water area, the height should be the minimum value of the elements where the left and right Pointers are located
val height = min(heights[left], heights[right])
// Take the largest area
result = max(result, width * height)
if (heights[left] < heights[right]) {
// If the element corresponding to the left pointer is less than the element corresponding to the right pointer, move the left pointer one space to the right
left++
} else {
// If the element corresponding to the left pointer is larger than the element corresponding to the right pointer, move the right pointer one space to the left
right--
}
}
return result
}
}
Copy the codeTime complexity: O(N), where N is the size of array heights.
Space complexity: O(1).
Answer key
We can use double pointer address this algorithm problem, placed in the left pointer to the first element of the array, place the pointer right the last element in the array, the value of width can through right pointer index minus the left pointer index, according to the topic righteousness, to get the largest water area, so highly depends on the value of the minimum So we can take the minimum value of the element in which the left pointer and the right pointer are located. Notice that if the left pointer is smaller than the right pointer, we can move the left pointer to the right one space. Otherwise, we can move the right pointer to the left one space until the left and right Pointers reach the same position.
Integer to Roman
Difficulty: Medium
Link: Integer to Roman
code
Java
/** * Created by TanJiaJun on 2021/6/27. * 12. Integer to Roman * Difficulty: medium * *@see <a href="https://leetcode-cn.com/problems/integer-to-roman/">Integer to Roman</a>
*/
class IntegerToRoman {
public static void main(String[] args) {
/ / sample
System.out.print(Example 1:);
int firstNumber = 3;
System.out.println(intToRoman(firstNumber));
System.out.print("\n");
/ / sample 2
System.out.print("Example 2:");
int secondNumber = 4;
System.out.println(intToRoman(secondNumber));
System.out.print("\n");
/ / sample 3
System.out.print("Example 3:");
int thirdNumber = 58;
System.out.println(intToRoman(thirdNumber));
System.out.print("\n");
/ / sample 4
System.out.print("Example 4:");
int fourthNumber = 1994;
System.out.println(intToRoman(fourthNumber));
}
/** * Greedy algorithm * time complexity: O(N), where N is the number of digits in the array num * space complexity: O(1) **@paramNum to be converted to the Roman numeral integer *@returnRoman numeral */
private static String intToRoman(int num) {
Enumerates the seven characters of Roman numerals
String[] strs = {"M"."CM"."D"."CD"."C"."XC"."L"."XL"."X"."IX"."V"."IV"."I"};
Enumerates the seven characters of the Roman numeral
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]) {
// If this value is greater than the integer corresponding to the enumerated Roman numeral, subtract the integer from this value and assign the value to num
num -= ints[index];
// Write down the Roman numeral
stringBuilder.append(strs[index]);
} else {
// If the value is less than the integer corresponding to the enumerated Roman numeral, move the index one space to the rightindex++; }}returnstringBuilder.toString(); }}Copy the codeKotlin
/** * Created by TanJiaJun on 2021/7/21. * 12. Integer to Roman * Difficulty: medium * *@see <a href="https://leetcode-cn.com/problems/integer-to-roman/">Integer to Roman</a>
*/
object IntegerToRomanKotlin {
@JvmStatic
fun main(args: Array<String>) {
/ / sample
print(Example 1:)
val firstNumber = 3
println(intToRoman(firstNumber))
print("\n")
/ / sample 2
print("Example 2:")
val secondNumber = 4
println(intToRoman(secondNumber))
print("\n")
/ / sample 3
print("Example 3:")
val thirdNumber = 58
println(intToRoman(thirdNumber))
print("\n")
/ / sample 4
print("Example 4:")
val fourthNumber = 1994
println(intToRoman(fourthNumber))
}
/** * Greedy algorithm * time complexity: O(N), where N is the number of digits in the array num * space complexity: O(1) **@paramNum to be converted to the Roman numeral integer *@returnRoman numeral */
private fun intToRoman(num: Int): String =
StringBuilder()
.apply {
var number = num
Enumerates the seven characters of Roman numerals
val strs = arrayOf("M"."CM"."D"."CD"."C"."XC"."L"."XL"."X"."IX"."V"."IV"."I")
Enumerates the seven characters of the Roman numeral
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]) {
// If this value is greater than the integer corresponding to the enumerated Roman numeral, subtract the integer from this value and assign the value to num
number -= ints[index]
// Write down the Roman numeral
append(strs[index])
} else {
// If the value is less than the integer corresponding to the enumerated Roman numeral, move the index one space to the right
index++
}
}
}
.toString()
}
Copy the codeTime complexity: O(N), where N is the number of bits in array NUM.
Space complexity: O(1).
Answer key
We use the largest number first for each comparison, so we can use the greedy algorithm to solve this problem.
Greedy algorithm is also known as the greedy algorithm, which is a were taken in every step to choose the best or optimal choice under the current state, which leads to the result is the best or optimal algorithm, change in real life, we will give priority to use the largest denomination notes or COINS to change, so that you can make the other side to get at least the number of notes or COINS, In fact, this is a kind of greedy algorithm.
Back to the topic, we can use two arrays respectively recorded Roman numerals of the seven characters and their corresponding integer, note that in order to facilitate our traversal, these two elements in the array to deposit according to the numerical size from big to small, at the time of traversal, if encounter is greater than the Roman numeral element of an array of characters, Subtract the integer of the Roman numeral character from the variable number, and record the Roman numeral. Otherwise, increase the index value and continue to iterate through the Roman array.
Roman to Integer
Difficulty: Easy
Link: Roman to Integer
code
Java
/** * Created by TanJiaJun on 2021/7/19. * 13. Difficulty: easy * *@see <a href="https://leetcode-cn.com/problems/roman-to-integer/">Roman to Integer</a>
*/
class RomanToInteger {
public static void main(String[] args) {
/ / sample
System.out.print(Example 1:);
String firstStr = "III";
System.out.println(romanToInt(firstStr));
System.out.print("\n");
/ / sample 2
System.out.print("Example 2:");
String secondStr = "IV";
System.out.println(romanToInt(secondStr));
System.out.print("\n");
/ / sample 3
System.out.print("Example 3:");
String thirdStr = "IX";
System.out.println(romanToInt(thirdStr));
System.out.print("\n");
/ / sample 4
System.out.print("Example 4:");
String fourthStr = "LVIII";
System.out.println(romanToInt(fourthStr));
System.out.print("\n");
/ / sample 5
System.out.print("Example 5:");
String fifthStr = "MCMXCIV";
System.out.println(romanToInt(fifthStr));
}
/** * time complexity: O(N), where N is the length of string s * Space complexity: O(1) **@paramS Roman numeral *@returnInteger * /
private static int romanToInt(String s) {
// Get the first Roman numeral
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));
// Compare this number with the previous one
if (preNum < num) {
// If this number is greater than the previous one, subtract the previous one
result -= preNum;
} else {
// If this number is less than the previous one, add the previous one
result += preNum;
}
// Record the previous number
preNum = num;
}
// Add them together to get the final result
result += preNum;
return result;
}
/** * Get the corresponding integer ** from the Roman numeral character@paramRoman The Roman numeral character *@returnInteger * /
private static int getInteger(char roman) {
Enumerates the seven characters of Roman numerals and their corresponding integers
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; }; }}Copy the codeKotlin
/** * Created by TanJiaJun on 2021/7/21. * 13. Difficulty: easy * *@see <a href="https://leetcode-cn.com/problems/roman-to-integer/">Roman to Integer</a>
*/
object RomanToIntegerKotlin {
@JvmStatic
fun main(args: Array<String>) {
/ / sample
print(Example 1:)
val firstStr = "III"
println(romanToInt(firstStr))
print("\n")
/ / sample 2
print("Example 2:")
val secondStr = "IV"
println(romanToInt(secondStr))
print("\n")
/ / sample 3
print("Example 3:")
val thirdStr = "IX"
println(romanToInt(thirdStr))
print("\n")
/ / sample 4
print("Example 4:")
val fourthStr = "LVIII"
println(romanToInt(fourthStr))
print("\n")
/ / sample 5
print("Example 5:")
val fifthStr = "MCMXCIV"
println(romanToInt(fifthStr))
}
/** * time complexity: O(N), where N is the length of string s * Space complexity: O(1) **@paramS Roman numeral *@returnInteger * /
private fun romanToInt(s: String): Int {
// Get the first Roman numeral
var preNum = getInteger(s[0])
var result = 0
var i = 1
val length = s.length
while (i < length) {
val num = getInteger(s[i])
// Compare this number with the previous one
if (preNum < num) {
// If this number is greater than the previous one, subtract the previous one
result -= preNum
} else {
// If this number is less than the previous one, add the previous one
result += preNum
}
// Record the previous number
preNum = num
i++
}
// Add them together to get the final result
result += preNum
return result
}
/** * Get the corresponding integer ** from the Roman numeral character@paramRoman The Roman numeral character *@returnInteger * /
private fun getInteger(roman: Char): Int =
Enumerates the seven characters of Roman numerals and their corresponding integers
when (roman) {
'I' -> 1
'V' -> 5
'X' -> 10
'L' -> 50
'C' -> 100
'D' -> 500
'M' -> 1000
else -> 0}}Copy the codeTime complexity: O(N), where N is the length of the string s.
Space complexity: O(1).
Answer key
If a smaller value is placed to the left of a larger value, we subtract. For example, IV is equal to 5-1, and the result is 4. Otherwise, we add. VI is equal to 5 plus 1, which is 6, and notice that every time we do this, we have to write down the previous number, so we can compare it, and the other logic is also commented in the code, so I won’t go over it here.
My GitHub: TanJiaJunBeyond
Android Universal Framework: Android Universal Framework
My nugget: Tan Jiajun
My Short Book: Tan Jiajun
My CSDN: Tan Jiajun