- The algorithm is weak. Let’s brush 5 leetcode a day and use Kotlin
1. Sum of two numbers
- Given an array of integers nums and a target value target, find the two integers in the array and the target values and return their array subscripts. You can assume that there is only one answer for each type of input. However, the same element in an array cannot be used twice.
Example: Given nums = [2, 7, 11, 15], target = 9Copy the code- Problem solving:
The title of “TwoSum”, as the opening topic of LeetCode, is a classic among the classics. As the saying goes, “I have never known TwoSum, but it is in vain to brush all the LeetCode
fun _0001_twoSum() { println("--------_001_twoSum-------") val nums = intArrayOf(1, 2, 11, 7, 15) println("_001_AddTwoNumber-->") for (i in twoSum(nums, 9)!!) { println(i) } } fun twoSum(nums: IntArray, target: Int): IntArray? { val map = HashMap<Int, Int>() for (i in nums.indices) { if (map.containsKey(target - nums[i])) { return intArrayOf(map[target - nums[i]]!! , i) } map[nums[i]] = i } return null }Copy the code2. Add two numbers
- Give two non-empty linked lists to represent two non-negative integers. Their respective bits are stored in reverse order, and each node can store only one digit. If we add these two numbers together, a new linked list is returned to represent their sum. You can assume that neither of these numbers will start with 0, except for the number 0.
Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Cause: 342 + 465 = 807Copy the code- The problem solving
Create a new list, and then roll the two input lists back from the beginning, adding each of the two to add a new node to the new list. To avoid both input linked lists being empty at the same time, we create a dummy node and add the new nodes to the dummy node in sequence. Since the dummy node cannot be changed, we use a cur to point to the last node of the new linked list.
fun _0002_addTwoNumbers() { println("--------_002_addTwoNumbers-------") addTwoNumbers( ListNode(2, ListNode(4, ListNode(3, ListNode(1)))), ListNode(5, ListNode(6, ListNode(4, ListNode(5)))) )? .print() println() } fun addTwoNumbers(l1: ListNode? , l2: ListNode?) : ListNode? { var l1 = l1 var l2 = l2 val dummy = ListNode(-1) var cur: ListNode? = dummy var carry = 0 while (l1 ! = null || l2 ! = null) { val d1 = l1? .data ? : 0 val d2 = l2? .data ? : 0 val sum = d1 + d2 + carry carry = if (sum >= 10) 1 else 0 cur? .next = ListNode(sum % 10) cur = cur? .next if (l1 ! = null) { l1 = l1.next } if (l2 ! = null) { l2 = l2.next } } if (carry == 1) cur? .next = ListNode(1) return dummy.next } class ListNode { var data = 0 var next: ListNode? = null internal constructor(data: Int) { this.data = data } internal constructor(data: Int, next: ListNode?) { this.data = data this.next = next } fun print() { print("-->$data") if (next ! = null) { next? .print() } else { println() } } }Copy the code3. The oldest string without repeating characters
- Given a string, find the length of the smallest string that does not contain repeating characters.
Example 1: Input: "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3. Example 2: Input: "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1. Example 3: Input: "pwwkew" Output: 3 Explanation: Since the oldest string without repeating characters is "wke", its length is 3. Note that your answer must be the length of the substring, "pwke" is a subsequence, not a substring.Copy the code- The problem solving
Select * from HashSet; select * from HashSet; select * from HashSet; select * from HashSet; select * from HashSet;
fun _0003_lengthOfLongestSubstring() {
println("--------_003_lengthOfLongestSubstring-------")
lengthOfLongestSubstring("abcabcbb")
lengthOfLongestSubstring("bbbbb")
lengthOfLongestSubstring("pwwkew")
lengthOfLongestSubstring("pwwkewabcdefghijkabcabc")
}
fun lengthOfLongestSubstring(s: String) {
var maxLen = 0
var left = 0
var right = 0
val temp = HashSet<Char>()
while (right < s.length) {
if (!temp.contains(s[right])) {
temp.add(s[right++])
maxLen = Math.max(maxLen, temp.size)
} else {
temp.remove(s[left++])
}
}
println("len：$maxLen")
}
Copy the code4. Find the median of two positive ordinal groups
- Given two positively ordered (from small to large) arrays of size m and n, nums1 and nums2. Please find and return the median of the two positive ordinal groups.
- Advanced: Can you design a time complexity O(log (m+n)) algorithm to solve this problem?
Example 1: input: nums1 = [1,3], nums2 = [2] output: 2.00000 description: merge array = [1,2,3], median 2 example 2: input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 description: merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5 example 3: input: nums1 = [0,0], nums2 = [0,0] output: 0.00000 example 4: input: Nums1 = [], nums2 = [1] Output: 1.00000 Example 5: Input: nums1 = [2], nums2 = [] Output: 2.00000 Hint: nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106Copy the code- The problem solving
To solve it by binary search method in iterative form, is the so-called median. Another way to look at it is to divide an ordered array into two segments of equal length. The median is the average of the maximum value of the first half and the minimum value of the second half, that is, the average of the two adjacent digits from the split point. For example, for an even number of arrays [1, 3, 5, 7], the split is [1, 3/5, 7], where ‘/’ represents the split point, and the median is the average of 3 and 5. For an odd number of arrays [1, 3, 4, 5, 7], which can be divided into [1, 3, 4/4, 5, 7], you can find a 4 on both sides, so the median is the average of two fours, or 4.
fun _0004_findMedianSortedArrays() { println("--------_004_findMedianSortedArrays-------") println(findMedianSortedArrays(intArrayOf(1, 3), intArrayOf(2))) println(findMedianSortedArrays(intArrayOf(1, 2), intArrayOf(3, 4))) println(findMedianSortedArrays(intArrayOf(0, 0), intArrayOf(0, 0))) println(findMedianSortedArrays(intArrayOf(), intArrayOf(1))) println(findMedianSortedArrays(intArrayOf(2), intArrayOf())) println(findMedianSortedArrays(intArrayOf(1, 2, 3, 4, 5), intArrayOf(3, 4, 5, 6))) } fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double { var m = nums1.size var n = nums2.size if (m < n) return findMedianSortedArrays(nums2, Nums1) if (n == 0) {return (nums1[(m-1) / 2] + nums1[m / 2]) / 2.0} var left = 0 var right = 2 * n while (left <= 0) right) { var mid2 = (left + right) / 2 var mid1 = m + n - mid2 var l1: Double = if (mid1 == 0) Double.MIN_VALUE else nums1[(mid1 - 1) / 2].toDouble() var l2: Double = if (mid2 == 0) Double.MIN_VALUE else nums2[(mid2 - 1) / 2].toDouble() var r1: Double = if (mid1 == m * 2) Double.MAX_VALUE else nums1[mid1 / 2].toDouble() var r2: Double = if (mid2 == n * 2) Double.MAX_VALUE else nums2[mid2 / 2].toDouble() if (l1 > r2) left = mid2 + 1 else if (l2 > R1) right = mid2-1 else return (math.max (l1, l2) + math.min (R1, r2)) / 2} return -1.0}Copy the code5. The longest subroutine string
- Given a string s, find the longest subroutine in s. You can assume that the maximum length of s is 1000.
Example 1: Input: "babad" Output: "bab" Note: "ABA" is also a valid answer. Example 2: Input: "CBBD" Output: "bb"Copy the code- The problem solving
Manacher’s Algorithm is a linear method for finding the longest substring of a string. It was invented by a man named Manacher in 1975. The greatest contribution of this method is to improve the time complexity to linearity.
fun _0005_longestPalindrome() { println("--------_005_longestPalindrome-------") println(longestPalindrome("babad")) println(longestPalindrome("cbbd")) println(longestPalindrome("aaaadcbabcdfabcccccc")) } fun longestPalindrome(s: String): String? { if (s.length < 2) { return s } var temp = "$" for (element in s) { temp += "#$element" } temp += "#@" val n = temp.length val p = IntArray(n) var id = 0 var mx = 0 var index = 0 var maxLen = -1 for (i in 1 until n - 1) { p[i] = if (mx > i) Math.min(p[2 * id - i], mx - i) else 1 while (temp[i + p[i]] == temp[i - p[i]]) { p[i]++ } if (mx < i + p[i]) { mx = i + p[i] id = i } if (maxLen < p[i] - 1) { maxLen = p[i] - 1 index = i } } val start = (index - maxLen) / 2 return s.substring(start, start + maxLen) }Copy the code