LeetCode 顺序随练 | 1 - 10

原题链接: https://leetcode.com/problemset/all

咱刚开始学 Kotlin,写得大概比较 naive。


1. Two Sum

暴力做法显然。

考虑优化,我们可以建一个HashMap,存(target - 当前值, 下标)键值对。

class Solution {
  fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = HashMap<Int, Int>()
    for (i in nums.indices) {
      val num = nums[i]
      map[num]?.let {
        return intArrayOf(i, it);
      } ?: let {
        map[target - num] = i
      }
    }
    return IntArray(2)
  }
}

2. Add Two Numbers

先建一个 dummy node,然后模拟。

class Solution {
  fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
    val dummy = ListNode(0)
    
    var i = l1
    var j = l2
    var k = dummy
    var carry = false
    
    while (i != null || j != null) {
      var tmp = 0
      i?.let {
        tmp += it.`val`
        i = it.next
      }
      j?.let {
        tmp += it.`val`
        j = it.next
      }
      if (carry) {
        ++tmp
        carry = false
      }
      if (tmp >= 10) {
        tmp -= 10
        carry = true
      }
      k.next = ListNode(tmp)
      k = k.next
    }
    if (carry) k.next = ListNode(1)
    
    return dummy.next
  }
}

3. Longest Substring Without Repeating Characters

暴力做法显然。

考虑优化,我们可以建一个HashMap,存(当前字符, 当前下标)键值对。

取了冲突字符时,若当前的区间长度小于(旧字符下标, 新字符下标]的区间长度,则无需修改,否则区间会包含曾经查出的冲突字符。

在修改前以及输出前尝试更新答案。

class Solution {
  private fun max(a: Int, b: Int) = if (a > b) a else b
  private fun min(a: Int, b: Int) = if (a < b) a else b

  fun lengthOfLongestSubstring(s: String): Int {
    var ans = 0
    val map = HashMap<Char, Int>()
    var tmp = 0
    for (i in s.indices) {
      val c = s[i]
      tmp = map[c]?.let {
        ans = max(tmp, ans)
        min(i - it, tmp + 1)
      } ?: tmp + 1
      map[c] = i
    }
    return max(tmp, ans)
  }
}

4. Median of Two Sorted Arrays

题目给了提示,O(log(m + n)),那么考虑二分。

对于大小为m + n的有序递增数组,我们考虑将其分为左右两侧。大小为偶数时,两侧大小相等,中位数即为左侧最大值与右侧最小值的平均数;大小为奇数时,不妨令左侧少一个元素,中位数即为右侧最小值。

现在,我们分别有大小为mn的两个有序递增数组nums1nums2。我们选择分别选合适数量(nums1inums2j)的元素进入左侧(左侧大小为i + j),剩下的进入右侧,使得左侧的最大值小于等于右侧的最小值,这样,我们就可以凭上一段的做法求解中位数。

二分搜索合适的i。由于左侧可能比右侧少一个元素,或两侧可能相等,我们有 k=i+j= \lfloor \frac {m+n}{2} \rfloork即为进入左侧的元素数量 ,这样,我们可以通过i求出j

若进入左侧的nums1元素的最大值大于进入右侧的nums2元素的最小值,说明i取大了;若进入左侧的nums2元素的最大值大于进入右侧的nums1元素的最小值,说明j取大了(即i取小了);若这两种情况都没出现,说明i是合适的。可证前两种情况不可能同时出现。

注意处理二分边界和数组访问边界(坑点,交了好几次 ←_← )。

class Solution {
  private fun max(a: Int, b: Int) = if (a > b) a else b
  private fun min(a: Int, b: Int) = if (a < b) a else b
  
  fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
    val m = nums1.size
    val n = nums2.size
    val k = (m + n) / 2
    
    var l = max(0, k - n)
    var r = min(m, k)
    var i: Int
    var j: Int
    
    while (true) {
      i = (l + r) / 2
      j = k - i
      if (l == r) break
      
      if (i != 0 && j != n && nums1[i - 1] > nums2[j]) r = i
      else if (j != 0 && i != m && nums2[j - 1] > nums1[i]) l = i + 1
      else break
    }
    
    val mi = if (i == m) nums2[j]
    else if (j == n) nums1[i]
    else min(nums1[i], nums2[j])
    
    if ((m + n) % 2 == 1) return mi.toDouble()
    
    val ma = if (i == 0) nums2[j - 1]
    else if (j == 0) nums1[i - 1]
    else max(nums1[i - 1], nums2[j - 1])
    
    return (mi + ma).toDouble() / 2
  }
}

5. Longest Palindromic Substring

暴力做法显然。

考虑优化,不难想出状态转移方程:dp[i][j] = dp[i - 2][j + 1] && s[j] == s[j + i - 1]dp[i][j]存储长度为i,下标从j开始的子串是否为回文串。状态转移的过程中更新答案。

然后用滚动数组优化空间,同时发现可以剪枝。

注意在开始时判空串,注意下标范围。

class Solution {
  fun longestPalindrome(s: String): String {
    val len = s.length
    if (len == 0) return ""

    val dp = Array(2) { BooleanArray(len) }
    for (j in s.indices) {
      dp[0][j] = true
      dp[1][j] = true
    }
    var sz = 1
    var id = 0

    var i = 1
    for (k in 2..len) {
      if (sz < k - 2) break
      i = if (i == 0) 1 else 0
      for (j in s.indices) {
        if (j + k > len) break
        dp[i][j] = dp[i][j + 1] && s[j] == s[j + k - 1]
        if (sz < k && dp[i][j]) {
          id = j
          sz = k
        }
      }
    }
    return s.substring(id, id + sz)
  }
}

看了下标答,此题有 O(n) 解法(Manacher’s Algorithm),到时有空学一学。

6. ZigZag Conversion

一个简单的模拟,存下每一行的字符串即可。

特判一行的情况,注意处理自增的方向。

class Solution {
  fun convert(s: String, numRows: Int): String {
    if (numRows == 1) return s
    
    val rows = Array(numRows) { StringBuilder() }
    var k = 0
    var inc = true
    for (c in s) {
      rows[k].append(c);
      when (k) {
        0 -> inc = true
        numRows - 1 -> inc = false
      }
      k += if (inc) 1 else -1
    }

    val ans = StringBuilder()
    for (row in rows) ans.append(row)
    return ans.toString()
  }
}

7. Reverse Integer

又一道模拟,开Long并判断是否 overflow。

class Solution {
  fun reverse(x: Int): Int {
    if (x == 0) return 0

    var ans: Long = 0
    var tmp: Int

    val sign: Boolean
    if (x < 0) {
      sign = true
      tmp = -x
    } else {
      sign = false
      tmp = x
    }

    do {
      ans *= 10
      ans += tmp % 10
      tmp /= 10
    } while (tmp != 0)

    if (sign) ans = -ans

    return when {
      ans < Int.MIN_VALUE -> 0
      ans > Int.MAX_VALUE -> 0
      else -> ans.toInt()
    }
  }
}

8. String to Integer (atoi)

思路与上题类似,没判'+'被坑了一次提交。。

class Solution {
  fun myAtoi(str: String): Int {
    val len = str.length
    if (len == 0) return 0

    var ans: Long = 0
    var sign = false

    var id = len
    for (i in 0 until len) {
      val c = str[i]
      if (c == ' ') continue
      else if (c == '-') sign = true
      else if (c == '+') sign = false
      else if (c in '0'..'9') ans += c - '0'
      else return 0
      id = i + 1
      break
    }

    for (i in id until len) {
      val c = str[i]
      if (c < '0' || '9' < c) break
      ans *= 10
      if (sign) {
        ans -= c - '0'
        if (ans < Int.MIN_VALUE) return Int.MIN_VALUE
      } else {
        ans += c - '0'
        if (ans > Int.MAX_VALUE) return Int.MAX_VALUE
      }
    }

    return ans.toInt()
  }
}

9. Palindrome Number

第 7 题的变体,判负数即可。

class Solution {
  private fun reverse(x: Int): Int {
    var ans = 0
    var tmp = x

    do {
      ans *= 10
      ans += tmp % 10
      tmp /= 10
    } while (tmp != 0)

    return ans
  }

  fun isPalindrome(x: Int): Boolean {
    return when {
      x < 0 -> false
      else -> x == 0 || x == reverse(x)
    }
  }
}

10. Regular Expression Matching

CSP-S2 2019 考完回来写。

点赞

Leave a Reply