力扣题库：《腾讯精选练习 50 题》 Swift 版
🏓🏸🏒⚽️🏀🥎🏄♀️🏄🏄♂️
每道题目都经过亲自编写和测试，尽量保证执行效率双百 + 极简 + swifty，如有不足请各位道友多加指正
给定两个非空链表表示两个非负整数，其中，它们各自按照逆序方式存储，并且每个节点只能存储一位数字。将两个数相加，并使用链表返回它们的和（同样逆序）
差点看成了两数之和😅，本题难度为中等，没有啥捷径，借助哑节点进行遍历即可，注意进位的处理。
let dummy = ListNode(-1)
var cur: ListNode? = dummy
var node1 = l1
var node2 = l2
var carry = false // 记录是否有进位
while node1 != nil || node2 != nil || carry { // 这里使用三个条件，将代码简化到一个循环中
var sum = 0
if let n1 = node1 {
sum += n1.val
}
if let n2 = node2 {
sum += n2.val
}
sum += carry ? 1 : 0
carry = sum / 10 > 0
let newNode = ListNode(sum % 10)
cur?.next = newNode
cur = cur?.next
node1 = node1?.next
node2 = node2?.next
}
return dummy.next给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。
虽然有两个解法，但解法二为 hard 型题解，所以面试时尽量保一争二
class Solution {
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
var nums1 = nums1
func helper() {
// 合并两个有序数组
var l1 = nums1.count - 1
var l2 = nums2.count - 1
var l = nums1.count + nums2.count - 1
nums1.append(contentsOf: [Int](repeating: 0, count: nums2.count))
while l1 >= 0 && l2 >= 0 {
if nums1[l1] > nums2[l2] {
nums1[l] = nums1[l1]
l1 -= 1
} else {
nums1[l] = nums2[l2]
l2 -= 1
}
l -= 1
}
if l2 >= 0 {
while l2 >= 0 {
nums1[l2] = nums2[l2]
l2 -= 1
}
}
}
helper()
if nums1.isEmpty {
return -1
}
if nums1.count % 2 == 1 {
return Double(nums1[nums1.count / 2])
} else {
return Double(nums1[nums1.count / 2 - 1] + nums1[nums1.count / 2]) / 2
}
}
}class Solution {
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
let count1 = nums1.count, count2 = nums2.count
let totalCount = count1 + count2
if totalCount % 2 == 1 {
let mid = totalCount / 2
return Double(getKthElement(nums1, nums2, mid + 1))
} else {
let mid1 = totalCount / 2 - 1, mid2 = totalCount / 2
return Double(getKthElement(nums1, nums2, mid1 + 1) + getKthElement(nums1, nums2, mid2 + 1)) / 2
}
}
// 获取两个数组中第 K 小的数
func getKthElement(_ nums1: [Int], _ nums2: [Int],_ k: Int) -> Int {
var k = k
let count1 = nums1.count, count2 = nums2.count
var index1 = 0, index2 = 0
while true {
if index1 == count1 {
return nums2[index2 + k - 1]
}
if index2 == count2 {
return nums1[index1 + k - 1]
}
if k == 1 {
return min(nums1[index1], nums2[index2])
}
let half = k / 2
let newIndex1 = min(index1 + half, count1) - 1
let newIndex2 = min(index2 + half, count2) - 1
let pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2]
if pivot1 <= pivot2 {
k -= newIndex1 - index1 + 1
index1 = newIndex1 + 1
} else {
k -= newIndex2 - index2 + 1
index2 = newIndex2 + 1
}
}
}
}给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
Time:O(n^3) Space: O(1)
func longestPalindrome(_ s: String) -> String {
// 暴力算法
let n = s.count
guard n >= 2 else { return s }
var maxLength = 1
var begin = 0
let chars = Array(s)
// 枚举所有长度严格大于 1 的子串 chars[i..j]
for i in 0..<n - 1 {
for j in i + 1..<n {
if j - i + 1 > maxLength && validHelper(chars, i, j) {
maxLength = j - i + 1
begin = i
}
}
}
return String(chars[begin..<(begin + maxLength)])
}
func validHelper(_ arr: [Character], _ i: Int, _ j: Int) -> Bool {
var i = i
var j = j
while i < j {
if arr[i] != arr[j] {
return false
}
i += 1
j -= 1
}
return true
}Time: O(n^2) space: O(n^2)
func longestPalindrome(_ s: String) -> String {
// 动态规划
// dp(i, j) = s[i] == s[j] && dp(i + 1, j - 1)
let n = s.count
guard n >= 2 else {
return s
}
var maxLength = 1
var begin = 0
var dp = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n)
// 对角线都为 true（因为单个字符必定为回文序列）
for i in 0..<n {
dp[i][i] = true
}
let chars = Array(s)
for j in 1..<n { // 对角线已经处理，所以列从 1 开始
for i in 0..<j { // 对角线以下不用管，所以只到 j 就结束了
if chars[i] != chars[j] {
dp[i][j] = false
} else {
dp[i][j] = j - i < 3 || dp[i + 1][j - 1] // 简化为 1 行，等同于下面 5 行
// if j - 1 - (i + 1) + 1 < 2 { // 表示 j - 1 到 i + 1 之间没有字符或只有一个字符，则肯定是回文串
// dp[i][j] = true
// } else {
// dp[i][j] = dp[i + 1][j - 1] // 状态转移，更里面的子串会优先计算出回文性质
// }
}
if dp[i][j] && j - i + 1 > maxLength { // 如果状态正确且长度大于原先的最大长度，则对 begin 和 maxLength 进行更新
maxLength = j - i + 1
begin = i
}
}
}
return String(chars[begin..<(begin+maxLength)])
}给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转
func reverse(_ x: Int) -> Int {
var x = x
var res = 0
while x != 0 {
let mod = x % 10
x /= 10
res = res * 10 + mod
}
return res < Int32.min || res > Int32.max ? 0 : res
}请你来实现一个 atoi 函数，使其能将字符串转换成整数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。在任何情况下，若函数不能进行有效的转换时，请返回 0 。
func myAtoi(_ str: String) -> Int {
let chars = Array(str)
let n = chars.count
var idx = 0
while idx < n && chars[idx] == " " {
idx += 1 // 去空格
}
if idx == n {
return 0
}
// 处理符号
var sign = 1
if chars[idx] == "-" {
sign = -1
idx += 1
} else if chars[idx] == "+" {
idx += 1
} else if !(chars[idx].isASCII && chars[idx].isWholeNumber) {
return 0
}
var ans = 0
while idx < n {
if !(chars[idx].isASCII && chars[idx].isWholeNumber) {
break
}
let digit = chars[idx].wholeNumberValue!
if ans > (Int(Int32.max) - digit) / 10 {
return Int(sign > 0 ? Int32.max : Int32.min)
}
ans = ans * 10 + digit
idx += 1
}
return ans * sign
}判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
func isPalindrome(_ x: Int) -> Bool {
if x < 0 || (x % 10 == 0 && x != 0) {
return false
}
var reverseNumber = 0
var x = x
while reverseNumber < x {
reverseNumber = reverseNumber * 10 + x % 10
x /= 10
}
return reverseNumber == x || x == reverseNumber / 10
}给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
双指针搞起
func maxArea(_ height: [Int]) -> Int {
var result = 0, leftBar = 0, rightBar = height.count - 1
while leftBar < rightBar {
let area = (rightBar - leftBar) * min(height[leftBar], height[rightBar])
result = max(result, area)
if height[leftBar] < height[rightBar] {
leftBar += 1
} else {
rightBar -= 1
}
}
return result
}编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
func longestCommonPrefix(_ strs: [String]) -> String {
guard strs.count > 0 else { return "" }
var ans = Array(strs[0])
for i in 1..<strs.count {
let chars = Array(strs[i])
var count = 0
for j in 0..<min(chars.count, ans.count) {
if ans[j] != chars[j] {
break
}
count += 1
}
ans = Array(ans[0..<count])
if ans.isEmpty {
return ""
}
}
return String(ans)
}给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
先对数组排序，方便使用双指针进行夹逼求值，然后左右边界不停调平
func threeSum(_ nums: [Int]) -> [[Int]] {
var ans = [[Int]]()
let n = nums.count
guard n >= 3 else { return ans }
var a = nums
a.sort() // 一定记住要排序
for i in 0..<n {
guard a[i] <= 0 else { break } // 1. 第一个数一定小于等于0
if i > 0 && a[i] == a[i - 1] { continue } // 2. 去重
var lb = i + 1
var rb = n - 1
while lb < rb {
let sum = a[i] + a[lb] + a[rb]
if sum == 0 {
ans.append([a[i], a[lb], a[rb]])
while lb < rb && a[lb] == a[lb + 1] { lb += 1 } // 左边界去重
while lb < rb && a[rb] == a[rb - 1] { rb -= 1 } // 右边界去重
lb += 1
rb -= 1
} else if sum < 0 {
lb += 1 // 左边界调平
} else {
rb -= 1 // 右边界调平
}
}
}
return ans
}给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
同15题，使用双指针向中间夹逼得出
func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
let n = nums.count
guard n >= 3 else { return 0 }
var a = nums
a.sort()
var res = a[0] + a[1] + a[2]
for i in 0..<n {
var l = i + 1
var r = n - 1
while l < r {
let sum = a[i] + a[l] + a[r]
if abs(sum - target) < abs(res - target) {
res = sum
}
if sum > target {
r -= 1
} else if sum < target {
l += 1
} else {
return sum
}
}
}
return res
}给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
func isValid(_ s: String) -> Bool {
let map: [Character: Character] = ["{": "}", "[": "]", "(": ")"]
var stack = [Character]()
for char in s {
if map[char] != nil {
stack.append(char)
} else {
guard let top = stack.popLast(), map[top] == char else {
return false
}
}
}
return stack.isEmpty
}将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var l1 = l1, l2 = l2
let dummy = ListNode(-1)
var pre: ListNode? = dummy
while l1 != nil && l2 != nil {
if l1!.val < l2!.val {
pre?.next = l1
l1 = l1?.next
} else {
pre?.next = l2
l2 = l2?.next
}
pre = pre?.next
}
pre?.next = l1 != nil ? l1 : l2
return dummy.next
} func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
guard let l1 = l1 else { return l2 }
guard let l2 = l2 else { return l1 }
if l1.val < l2.val {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
}给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
思路：同合并两个有序链表
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
var lists = lists
let dummy = ListNode(-1)
var cur: ListNode? = dummy
while true {
var minNode: ListNode?
var minPoint = -1
for i in 0..<lists.count {
if lists[i] == nil {
continue
}
if minNode == nil || lists[i]!.val < minNode!.val {
minNode = lists[i]
minPoint = i
}
}
if minPoint == -1 {
break
}
cur?.next = minNode
cur = cur?.next
lists[minPoint] = lists[minPoint]?.next
}
return dummy.next
}使用分治法求解
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
func merge2List(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
guard let l1 = l1 else { return l2 }
guard let l2 = l2 else { return l1 }
if l1.val < l2.val {
l1.next = merge2List(l1.next, l2)
return l1
} else {
l2.next = merge2List(l1, l2.next)
return l2
}
}
func mergeHelper(_ lists: [ListNode?], _ l: Int, _ r: Int) -> ListNode? {
if l == r {
return lists[l]
}
if l > r {
return nil
}
let mid = (l + r) >> 1
let l1 = mergeHelper(lists, l, mid)
let l2 = mergeHelper(lists, mid + 1, r)
return merge2List(l1, l2)
}
return mergeHelper(lists, 0, lists.count - 1)
}给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
使用慢指针进行比较和赋值
func removeDuplicates(_ nums: inout [Int]) -> Int {
guard nums.count > 1 else { return nums.count }
var slow = 0
for i in 0..<nums.count {
if nums[i] != nums[slow] {
slow += 1
nums[slow] = nums[i]
}
}
return slow + 1
}假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
func search(_ nums: [Int], _ target: Int) -> Int {
guard nums.count > 0 else { return -1 }
var lb = 0, rb = nums.count - 1
while lb <= rb {
let mid = lb + (rb - lb) >> 1
if nums[mid] == target {
return mid
}
if nums[mid] >= nums[lb] {
// mid 在左边
if target >= nums[lb] && target < nums[mid] { // 在有序区间
rb = mid - 1
} else {
lb = mid + 1
}
} else {
// mid 在右边
if target > nums[mid] && target <= nums[rb] { // 在有序区间
lb = mid + 1
} else {
rb = mid - 1
}
}
}
return -1
}Easy
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
原地反转
func reverseWords(_ s: String) -> String {
var chars = [Character](s)
var i = 0
while i < chars.count {
let start = i
while i < chars.count && chars[i] != " " {
i += 1
}
var left = start, right = i - 1
while left < right {
chars.swapAt(left, right)
left += 1
right -= 1
}
while i < chars.count && chars[i] == " " {
i += 1
}
}
return String(chars)
}编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
func reverseString(_ s: inout [Character]) {
guard s.count > 1 else { return }
var left = 0, right = s.count - 1
while left < right {
s.swapAt(left, right)
left += 1
right -= 1
}
}给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
- 动态规划.
计算前面的和与当前的位置的和，如果前面的和大于0则相加，否则，直接覆盖，并一边计算最大结果
func maxSubArray(_ nums: [Int]) -> Int {
guard nums.count > 0 else { return 0 }
var sum = 0, maxAns = nums[0]
for n in nums {
if sum > 0 {
sum += n
} else {
sum = n
}
maxAns = max(maxAns, sum)
}
return maxAns
}假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
**注意：**给定 n 是一个正整数。
func climbStairs(_ n: Int) -> Int {
guard n > 2 else { return n }
var first = 1
var second = 2
for _ in 3...n {
(first, second) = (second, first + second)
}
return second
}给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
// 双指针
var l1 = m - 1
var l2 = n - 1
var l = m + n - 1
while l1 >= 0 && l2 >= 0 {
if nums1[l1] > nums2[l2] {
nums1[l] = nums1[l1]
l1 -= 1
} else {
nums1[l] = nums2[l2]
l2 -= 1
}
l -= 1
}
if l2 >= 0 {
nums1.replaceSubrange(0..<l2 + 1, with: nums2[0..<l2 + 1]) // 这里可以替换为 while 循环
/*
while l2 >= 0 {
nums1[l2] = nums2[l2]
l2 -= 1
}
*/
}
}求二叉树的最大深度，也就是根节点到叶子节点的最远路径的节点数。
推荐使用深度优先，递归即可快速解题，并且复杂度和广度优先相同
class Solution {
func maxDepth(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }
return max(maxDepth(root.left), maxDepth(root.right)) + 1
}
} func maxDepth(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }
var queue = [TreeNode]()
queue.append(root)
var depth = 0
while !queue.isEmpty {
depth += 1
let width = queue.count
for i in 0..<width {
let node = queue.removeFirst()
if let leftNode = node.left {
queue.append(leftNode)
}
if let rightNode = node.right {
queue.append(rightNode)
}
}
}
return depth
}给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
低点买入，高点抛出，通俗易懂
func maxProfit(_ prices: [Int]) -> Int {
var minProfit = Int.max
var maxProfit = 0
for p in prices {
if p < minProfit {
minProfit = p
} else {
maxProfit = max(maxProfit, p - minProfit)
}
}
return maxProfit
}给定一个 node 节点，将其在链表中删除。（比较 tricky，直接换 val 可还行？）
class Solution {
func deleteNode(_ node: ListNode?) {
guard let next = node?.next else { return }
node?.val = next.val
node?.next = next.next
}
}