每日LeetCode力扣（41~45） _Leetcode

【每日LeetCode力扣（41~45）】人生必须的知识就是引人向光明方面的明灯。这篇文章主要讲述每日LeetCode力扣（41~45）相关的知识，希望能为你提供帮助。
41. 缺失的第一个正数

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

解题

fun _0041_firstMissingPositive()
println("--------_0041_firstMissingPositive-------")
println(firstMissingPositive(intArrayOf(1, 2, 0)))
println(firstMissingPositive(intArrayOf(3, 4, -1, 1)))
println(firstMissingPositive(intArrayOf(7, 8, 9, 11, 12)))

/**
需要把 nums[i] 放在 nums[nums[i] - 1]上，遍历整个数组，如果 nums[i] != i + 1, 而 nums[i] 为整数且不大于n，
另外 nums[i] 不等于 nums[nums[i] - 1] 的话，将两者位置调换，如果不满足上述条件直接跳过，
最后再遍历一遍数组，如果对应位置上的数不正确则返回正确的数
*/
fun firstMissingPositive(nums: IntArray): Int
val n = nums.size
for (i in nums.indices)
while (nums[i] in 1..n & & nums[nums[i] - 1] != nums[i])
swap(i, nums[i] - 1, nums)

for (i in nums.indices)
if (nums[i] != i + 1)
return i + 1

return n + 1

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1:
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length
0 < = n < = 3 * 104
0 < = height[i] < = 105

解题

fun _0042_trap()
println("--------_0042_trap-------")
println(trap(intArrayOf(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)))
println(trap(intArrayOf(4, 2, 0, 3, 2, 5)))

/**
* 只需要遍历一次, 需要 left 和 right 两个指针分别指向数组的首尾位置，从两边向中间扫描，
* 在当前两指针确定的范围内，先比较两头找出较小值，如果较小值是 left 指向的值，则从左向右扫描，
* 如果较小值是 right 指向的值，则从右向左扫描，若遇到的值比当较小值小，则将差值存入结果，
* 如遇到的值大，则重新确定新的窗口范围，以此类推直至 left 和 right 指针重合
*/
fun trap(height: IntArray): Int
var left = 0
var right = height.size - 1
var level = 0
var res = 0
while (left < right)
val lower = height[if (height[left] < height[right]) left++ else right--]
level = Math.max(level, lower)
res += level - lower

return res

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

解题

fun _0043_multiply()
println("--------_0043_multiply-------")
println(multiply("2", "3"))
println(multiply("8", "22"))
println(multiply("123", "456"))

/**
由于要从个位上开始相乘，所以从 num1 和 num2 字符串的尾部开始往前遍历，分别提取出对应位置上的字符，将其转为整型后相乘。
然后确定相乘后的两位数所在的位置 p1 和 p2，由于 p2 相较于 p1 是低位，所以将得到的两位数 mul 先加到 p2 位置上去，
这样可能会导致 p2 位上的数字大于9，所以将十位上的数字要加到高位 p1 上去，只将余数留在 p2 位置，这样每个位上的数字都变成一位。
然后要做的是从高位开始，将数字存入结果 res 中，记住 leading zeros 要跳过，
最后处理下 corner case，即若结果 res 为空，则返回 "0"，否则返回结果 res
*/
fun multiply(num1: String, num2: String): String
var res = StringBuffer()
val m = num1.length
val n = num2.length
val vals = IntArray(m + n)
for (i in m - 1 downTo 0)
for (j in n - 1 downTo 0)
val mul = (num1[i] - 0) * (num2[j] - 0)
val p1 = i + j
val p2 = i + j + 1
val sum = mul + vals[p2]
vals[p1] += sum / 10
vals[p2] = sum % 10

for (v in vals)
if (res.isNotEmpty() || v != 0)
res.append((v))

return if (res.isEmpty()) "0" else res.toString()

44. 通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ? 和 * 的通配符匹配。
? 可以匹配任何单个字符。
* 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "*"
输出: true
解释: * 可以匹配任意字符串。
示例 3:
输入:
s = "cb"
p = "?a"
输出: false
解释: ? 可以匹配 c, 但第二个 a 无法匹配 b。
示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 * 可以匹配空字符串, 第二个 * 可以匹配字符串 "dce".
示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输出: false

解题

fun _0044_isMatch()
println("--------_0044_isMatch-------")
println(isMatch1("aa", "a"))
println(isMatch1("aa", "*"))
println(isMatch1("cb", "?a"))
println(isMatch1("adceb", "*a*b"))
println(isMatch1("acdcb", "a*c?b"))

fun isMatch1(s: String, p: String): Boolean
var i = 0
var j = 0
var iStar = -1
var jStar = -1
val m = s.length
val n = p.length
while (i < m)
if (j < n & & (s[i] == p[j] || p[j] == ?))
++i
++j
else if (j < n & & p[j] == *)
iStar = i
jStar = j++
else if (iStar > = 0)
i = ++iStar
j = jStar + 1
else return false

while (j < n & & p[j] == *)
++j
return j == n

45. 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。

解题

fun _0045_jump()
println("--------_0045_jump-------")
println(jump(intArrayOf(2, 3, 1, 1, 4)))

/**
cur 是当前能到达的最远位置，last 是上一步能到达的最远位置，遍历数组，首先用 i + nums[i] 更新 cur，
然后判断如果当前位置到达了 last，即上一步能到达的最远位置，说明需要再跳一次了，将 last 赋值为 cur，
并且步数 res 自增1，这里小优化一下，判断如果 cur 到达末尾了，直接 break 掉即可
*/
fun jump(nums: IntArray): Int
var res = 0
val n = nums.size
var last = 0
var cur = 0
for (i in nums.indices)
cur = Math.max(cur, i + nums[i])
if (i == last)
last = cur
++res
if (cur > = n - 1) break

return res