算法基础（六）题目综合

实习准备

字数统计: 16.2k阅读时长: 71 min

 2020/08/29 

算法基础（六）题目综合

一些知识

时间复杂度

在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 n**0 大）的输入，它至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3)。

影响算法时间代价的最主要因素是问题规模。问题规模是算法求解问题输入量的的多少,是问题大小的本质表示,一般用整数n表示。
问题规模n对不同的问题含义不同。
例如,在排序运算中n为参加排序的记录数,在矩阵运算中n为矩阵的阶数,在多项式运算中n为多项式的项数,在集合运算中n为集合中元素的个数,在树的有关运算中n为树的结点个数,在图的有关运算中n为图的顶点数或边数。
显然,n越大算法的执行时间越长。

一个算法的执行时间大致上等于其所有语句执行时间的总和,而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积

语句频度

一条语句的重复执行次数称作语句频度( Frequency Count)
由于语句的执行要由源程序经编译程序翻译成目标代码,目标代码经装配再执行,因此语句执行一次实际所需的具体时间是与机器的软、硬件环境(如机器速度、编译程序质量等)密切相关的。所以,所谓的算法分析并非精确统计算法实际执行所需时间,而是针对算法中语句的执行次数做出估计,从中得到算法执行时间的信息。
设每条语句执行一次所需的时间均是单位时间,则一个算法的执行时间可用该算法中所有语句频度之和来度量。

对于稍微复杂一些的算法,则通常是比较困难的,即便能够给出,也可能是个非常复杂的函数。因此,为了客观地反映一个算法的执行时间,可以只用算法中的“基本语句”的执行次数来度量算法的工作量所谓“基本语句”指的是算法中重复执行次数和算法的执行时间成正比的语句,它对算法运行时间的贡献最大。通常,算法的执行时间是随问题规模增长而增长的,因此对算法的评价通常只需考虑其随冋题规模增长的趋势。这种情况下,我们只需要考虑当问题规模充分大时,算法中基本语句的执行次数在渐近意义下的阶。

因此，时间复杂度也是渐进时间复杂度。因此一些情况的非递归算法就会有通用的时间复杂度。

var x = 0
var s = 0

//常亮阶  O(1)
x++
s = 0

//线性阶 O(n)
for i in 1...n {
	x++
	s = 0
}

//多阶 O(n^m)  由最深层次的循环体决定阶数m（但是最深层次也应是循环n次）
for i in 1...n {
	x++
	s = 0
}
for j in 1...n {
	x++
	for m in 1...n {
		x++
		s = 0
	}
}

//对数阶示例 O(log2n)
var i = 1
while i <= n {
    print(String(format: "i=%zd", i))
    i = i * 2
}

由此看出，O(log2n)会是最好的效率。

空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

我们举例两个算法


//算法1
for i in 0...n-1 {
    t = array[i]
    array[i] = array[n-i-1]
    array[n-i-1] = t
}

//算法2
for i in 0...n-1 {
    b[i] = array[n-i-1]
}
for i in 0...n-1 {
    array[i] = b[i]
}

hash相关

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希表可以用来表示特殊数据结构，比如说字典，映射和关联数组等。这一类的结构可以通过树状图或者普通数组来表示，但是使用哈希表的话效率更高。

Swift中常见的数据结构与之相关的就是字典（Dictionary）,通过键值存储能大大提高时间效率。

所以，当遇到一些时间复杂度为n2的要求，但是空间复杂度不限的情况，可以优先考虑字典这样的数组结构。

两数之和 - 简单

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

这种情况我们会想到三种，第一种暴力法，时间复杂度n2，空间复杂度为1。第二种排序+双指针的方法，时间复杂度nlogn，空间复杂度为n。第三种就是hash法，时间复杂度为n，空间复杂度为n。

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var dic = Dictionary<Int, Int>()
    for (i,num) in nums.enumerated() {
        if dic.keys.contains(target-num) {
            return [dic[target-num]!, i]
        }
        dic[num] = i
    }
    return []
}

字符串中的第一个唯一字符 - 简单

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：
s = “leetcode”
返回 0
s = “loveleetcode”
返回 2

这里的话，想要找出不重复的字符我们首先得知道哪些重复了，像这个题目要求会更友好些只让你返回第一个不重复的。为了达到时间复杂度为n，我们可以使用hash方法来达到效果。

func firstUniqChar(_ s: String) -> Int {
    var dic = Dictionary<Character, Int>()
    for (i,value) in s.enumerated() {
        if dic.keys.contains(value) {
            dic[value] = -1
        } else {
            dic[value] = i
        }
    }
    for (i,value) in s.enumerated() {
        if dic[value] == i {
            return i
        }
    }
    return -1
}

链表操作

链表这样的数据结构再熟悉不过，核心主要是指针的概念。对于链表的题目要求，我们应该思考怎么高效找到要操作的点。

两数相加 - 中等

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

这道题看上去不难但是需要注意的是两链表的位数问题以及进位问题，特殊情况的考虑会成为这个算法的关键。用新链表存储位数和以及进位
，并且最后处理尾结点。

class Solution_1 {
     public class ListNode {
         public var val: Int
         public var next: ListNode?
         public init(_ val: Int) {
             self.val = val
             self.next = nil
         }
    }
    
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        guard l1 != nil && l2 != nil else {
            return (l1 != nil) ? l1:((l2 != nil) ? l2:nil)
        }
        var nodel = l1
        var noder = l2
        let head = ListNode.init(0)
        var dummyHead: ListNode? = ListNode.init(-1)
        dummyHead?.next = head
        while nodel != nil || noder != nil {
            let value = (nodel?.val ?? 0) + (noder?.val ?? 0) + dummyHead!.next!.val
            dummyHead!.next!.val = value%10
            dummyHead!.next!.next = ListNode.init((value < 10) ? 0:1)
            dummyHead = dummyHead?.next
            nodel = nodel?.next
            noder = noder?.next
        }
        if dummyHead!.next!.val == 0 {
            dummyHead?.next = nil
        }
        return head
    }
}

删除链表的倒数第N个节点 - 中等

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。

这道题目需要双指针来进行操作，但是我们需要怎么解决获取我们要删除的点。我们应该将两指针做n的距离，然后两指针同时向后移动直到右指针到底。
需要注意的是，链表节点的增删改一般我们都会用哑节点来屏蔽头节点另外变动的问题。特别是增删操作，我们需要指针指向目标的前一个节点，哑节点也很方便的解决了这个问题。

class Solution_2 {
    public class ListNode {
        public var val: Int
        public var next: ListNode?
        public init(_ val: Int) {
            self.val = val
            self.next = nil
        }
    }
    
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        guard head != nil && n > 0 else {
            return nil
        }
        let dummyHead = ListNode.init(-1)
        dummyHead.next = head!
        var lnode: ListNode? = dummyHead
        var rnode: ListNode?
        for _ in 1...n {
            if rnode == nil {
                rnode = dummyHead
            } else {
                rnode = rnode?.next
            }
        }
        guard rnode?.next != nil else {
            return nil
        }
        while rnode?.next?.next != nil {
            rnode = rnode?.next
            lnode = lnode?.next
        }
        lnode?.next = lnode?.next?.next
        return dummyHead.next
    }
}

K 个一组翻转链表 - 困难

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

这个算法麻烦在部分翻转，所以这道题需要考虑怎么做步骤设计才达到最好的效果。我们需要对每组翻转前后节点进行记录，后节点还需要断开以免翻转被关联，最后翻转好后接上去并继续下一组。这个算法要求空间复杂度为1，那我们最好时间复杂度控制在n（每次停留需要进行一次 O(k) 的翻转操作。）。

class Solution_3 {
    public class ListNode {
        public var val: Int
        public var next: ListNode?
        public init(_ val: Int) {
            self.val = val
            self.next = nil
        }
    }
    
    func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
        guard head != nil && k > 1 else {
            return head
        }
        let dummy:ListNode? = ListNode.init(-1)
        dummy?.next = head
        var pre = dummy
        var end = dummy
        while (end?.next != nil) {
            for _ in 0..<k {
                end = end?.next
            }
            if (end == nil) {
                break
            }
            let start = pre?.next
            let next = end?.next
            end?.next = nil
            pre?.next = reverse(start)
            start?.next = next
            pre = start
            end = pre
        }
        return dummy?.next
    }
    
    private func reverse(_ pre: ListNode?) -> ListNode? {
        var pre = pre
        var node = pre?.next
        while node != nil {
            let next = node?.next
            node?.next = pre
            pre = node
            node = next
        }
        return pre
    }
}

旋转链表 - 中等

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

从题目上看我们会误以为我们需要按照步骤那样解题，其实仔细观察是倒数k个节点成为头节点，前面部分贴到末尾，如果k大于长度则是倒数k%length个节点。那我们需要找到末尾以及目标成为头节点的节点即可。同时，算法需要时间复杂度为n，空间复杂度为1

class Solution_4 {
    public class ListNode {
        public var val: Int
        public var next: ListNode?
        public init(_ val: Int) {
            self.val = val
            self.next = nil
        }
    }
    
    func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
        guard k > 0 && head != nil else {
            return (k == 0 ? head:nil)
        }
        let dummy: ListNode? = ListNode.init(-1)
        dummy?.next = head
        var keyPre = dummy
        var end = dummy
        var i = 1
        while end?.next?.next != nil {
            end = end?.next
            i += 1
        }
        guard i != k else {
            return head
        }
        i = (k<i ? i-k:i-k%i)
        for _ in 1...i {
            keyPre = keyPre?.next
        }
        end?.next?.next = dummy?.next
        let res = keyPre?.next
        keyPre?.next = nil
        return res
    }
}

复制带随机指针的链表 - 中等

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

提示：
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

这道题要想做到深拷贝你需要额外的空间存储拷贝节点，因为随机节点他需要指向拷贝节点。这里我们使用字典（hash化）来高效存储于优化时间，key为源node，value为拷贝node，利用递归算法对next和random进行递归。时间复杂度达到了n

class Solution_5 {
    public class Node {
        public var val: Int
        public var next: Node?
        public var random: Node?
        public init(_ val: Int) {
            self.val = val
            self.next = nil
            self.random = nil
        }
    }
    
    fileprivate var dic = [UnsafeMutableRawPointer: Node]()
    
    func copyRandomList(_ head: Node?) -> Node? {
        guard let head = head else {
            return nil
        }
        let key = Unmanaged.passUnretained(head).toOpaque()
        if let item = dic[key] {
            return item
        }
        let node = Node.init(head.val)
        dic[key] = node
        node.next = copyRandomList(head.next)
        node.random = copyRandomList(head.random)
        return node
    }
}

反转链表 - 简单

反转链表的算法在K 个一组翻转链表的题目中我们有写过。主要考虑反转的操作，就是节点next指向前面一个节点。

双指针遍历/滑动窗口

无重复字符的最长子串 - 中等

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，”pwke” 是一个子序列，不是子串。

这道题或许会思考很复杂因为我们要确定重复字符的位置以及他怎么样合并才是正确的。那我们想的是利用双指针，我们右指针遍历的时候出现了重复数字，我们的左指针就前重复数字进行向后+1，然后两指针距离和前不重复字符串距离比较就行。整个过程我们对于查找重复数字可以利用字典来实现，达到了时间复杂度为n，空间复杂度为n。

func lengthOfLongestSubstring(_ s: String) -> Int {
    var left = 0
    var len = 0
    var dic = [Character: Int]()
    for (i,char) in s.enumerated() {
        let index = dic[char]
        dic[char] = i
        if index != nil && index! >= left {
            left = index! + 1
        }
        if i - left + 1 > len {
            len = i - left + 1
        }
    }
    return len
}

盛最多水的容器 - 中等

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49

就于这题我们会无法下手，那我们抽象下用图表来表示下解题实例。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
那我们想怎么获取到这个最大的面积同时是高效的寻找到。那我们会利用双指针来实现它。我们得先设置初始左右指针的位置，我们观察到x轴的长度（两端长度）是线性的，我们可以双指针左右放置使得x轴长度递减。最矮的y轴（min（left，right））是第二个乘数，相乘结果和上一个结果比较大小，通过比较left，right指针大小来移动，寻找下一个结果。
整个过程时间复杂度为n，空间复杂度为1

func maxArea(_ height: [Int]) -> Int {
    guard height.count > 1 else {
        return 0
    }
    var res = 0
    var left = 0
    var right = height.count-1
    while right > left {
        let temp = min(height[left], height[right])*(right-left)
        if temp > res {
            res = temp
        }
        if height[left] < height[right] {
            left += 1
        } else {
            right -= 1
        }
    }
    return res
}

三数之和 - 中等

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

这道题相对于两数之和一题而言会有一定差距，首先条件不一样，要求三个数加起来为0，其次不能包含重复的三元组，再者三个变量的算法时间复杂度势必会大于n，这是不可避免的。
这道题的解决思路可以使用双指针，但是我们的第三个变量需要是遍历操作，这样控制时间复杂度为n2。也就是说，两数之和为第三数的倒数。那为了得到双指针控制效果，我们将数组排序, 然后从0到nums.count - 2选取第一个元素, 然后用双指针标记后面两个元素,
l = i + 1, r = nums.count - 1. 根据三数和的大小关系移动l或者r直到l和r相遇.
需要注意的点:
* 如果第一个元素大于0, 直接跳出循环就可以了, 因为最小的值都大于0, 三个数相加不可能等于0
* 重复值的处理
* 如果 nums[i] == nums[i-1]直接continue
* 每次移动l或者r之后需要跳过下一个相同的nums[l]或者nums[r] 否则会出现重复的结果, 这里我们用repeat while.

func threeSum(_ nums: [Int]) -> [[Int]] {
    guard nums.count > 2 else {
        return []
    }
    let nums = nums.sorted()
    guard nums.first! <= 0 else {
        return []
    }
    var res = [[Int]]()
    for i in 0..<nums.count - 2 {
        if i > 0 && nums[i] == nums[i - 1] {
            continue
        }
        var left = i + 1
        var right = nums.count - 1
        while left < right {
            let temp = nums[left]+nums[right]+nums[i]
            if temp == 0 {
                res.append([nums[i], nums[left], nums[right]])
                repeat {
                    left += 1
                } while left < right && nums[left] == nums[left-1]
                repeat {
                    right -= 1
                } while left < right && nums[right] == nums[right+1]
            } else if temp < 0 {
                repeat {
                    left += 1
                } while left < right && nums[left] == nums[left-1]
            } else {
                repeat {
                    right -= 1
                } while left < right && nums[right] == nums[right+1]
            }
        }
    }
    return res
}

最接近的三数之和 - 中等

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

这道题是上一题的变换的形式，所以大致相同的算法结构我们可以直接套用，主要的是我们需要怎么判断哪个值接近目标值。最直接的是三个数之和与目标值的差的绝对值的比较，通过比较三个数之和与目标值来移动双指针。

func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
    guard nums.count > 2 else {
        return 0
    }
    let nums = nums.sorted()
    var res = nums[0]+nums[1]+nums[2]
    guard res != target else {
        return res
    }
    for i in 0..<nums.count - 2 {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        var left = i + 1
        var right = nums.count - 1
        while left < right {
            let temp = nums[left]+nums[right]+nums[i]
            guard temp != target else {
                return target
            }
            if abs(target-temp) < abs(target-res) {
                res = temp
            }
            if temp > target {
                repeat {
                    right -= 1
                } while left < right && nums[right] == nums[right+1]
            } else {
                repeat {
                    left += 1
                } while left < right && nums[left] == nums[left-1]
            }
        }
    }
    return res
}

删除排序数组中的重复项 - 简单

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

这道题，给了你些暗示性的语句，你不需要考虑数组中超出新长度后面的元素。也就是说，我的里面重复的数字被换到了后面（也就是新长度后面），那么，这题在使用双指针上的解决会方便很多，我们只需要一个指针来指向不重复子数组末尾，一个指针进行遍历，当有不重复的数字出现则进行交换。

func removeDuplicates(_ nums: inout [Int]) -> Int {
    guard nums.count > 1 else {
        return nums.count
    }
    var c = 0
    for i in 1..<nums.count {
        if nums[i] != nums[c] {
            c += 1
            nums[c] = nums[i]
        }
    }
    return c+1
}

买卖股票的最佳时机 - 简单

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

这道题看清题目后就能理解他的用意。利用一指针加一遍历的方法，我们得获得最小数，当前数与最小数的差与最大利润比较就能解决问题。

func maxProfit(_ prices: [Int]) -> Int {
    guard prices.count > 1 else {
        return 0
    }
    var money = 0
    var min = Int.max
    for i in 0..<prices.count {
        if prices[i] < min {
            min = prices[i]
        }
        if prices[i] - min > money {
            money = prices[i] - min
        }
    }
    return money
}

长度最小的子数组 - 中等

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

首先这道题只需要输出子数组长度，因此我们需要一个变量存储子数组长度用来比较。利用双指针滑动窗口来选择，当窗口内之和（我们也需要一个变量存储子数组之和）大于等于目标值，移动左指针，否则移动右指针。实现的时间复杂度为n，空间复杂度为1。

func minSubArrayLen(_ s: Int, _ nums: [Int]) -> Int {
    var res = Int.max
    var left = 0
    var sum = 0
    for (i, value) in nums.enumerated() {
        sum += value
        while sum >= s {
            res = min(res, i-left+1)
            sum -= nums[left]
            left += 1
        }
    }
    return res == Int.max ? 0:res
}

快慢指针遍历

在我的印象里，快慢指针的使用，有遇到成环检测以及快速获得中间点的方法。

环形链表 - 简单

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

这个题主要实现思想是一个指针走1步，一个指针走2步，如果成环，那势必两指针会相遇。

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

class Solution_6 {
    func hasCycle(_ head: ListNode?) -> Bool {
        var slow = head
        var fast = head
        while fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            if fast == slow {
                return true
            }
        }
        return false
    }
}

extension ListNode: Equatable {
    public static func == (lhs: ListNode, rhs: ListNode) -> Bool {
        return lhs === rhs
    }
}

快乐数 - 简单

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

这道题会出现循环的问题，那我们也可以使用快慢指针解决。也就是获得结果的一个值要执行两遍。当快慢值相同时，我们根据相同值判断是否是1就能决定是否是快乐数。

fileprivate func bitSquareSum(_ n: Int) -> Int {
    var n = n
    var sum = 0
    while n > 0 {
        let bit = n%10
        sum += bit*bit
        n = n/10
    }
    return sum
}

func isHappy(_ n: Int) -> Bool {
    var slow = n
    var fast = n
    repeat {
        slow = bitSquareSum(slow)
        fast = bitSquareSum(fast)
        fast = bitSquareSum(fast)
    } while slow != fast
    return slow == 1
}

链表的中间结点 - 简单

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

这个题利用快慢指针找到中间节点即可。

func middleNode(_ head: ListNode?) -> ListNode? {
    var slow = head
    var fast = head
    while fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
    }
    return slow
}

字符串操作

z字形转换 - 中等

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);

示例1:
输入: s = “LEETCODEISHIRING”, numRows = 3
输出: “LCIRETOESIIGEDHN”

示例2:
输入: s = “LEETCODEISHIRING”, numRows = 4
输出: “LDREOEIIECIHNTSG”
解释:
L D R
E O E I I
E C I H N
T S G

这道题需要你通过草稿画出实例，然后你会发现基本是numRows*2-2为一组按规律进行放置。这道题需要额外的空间放置结果。

func convert(_ s: String, _ numRows: Int) -> String {
    guard numRows > 1 && s.count > numRows else {
        return s
    }
    var list = [String].init(repeating: "", count: numRows)
    var c = 0
    var x = numRows*2-2
    for (i, value) in s.enumerated() {
        var r = (i-c)%(x)
        if r == x-1 {
            c += x
        }
        if r >= numRows {
            r = x-r
        }
        list[r] += String(value)
    }
    var res = ""
    for s in list {
        res += s
    }
    return res
}

最长公共前缀 - 简单

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例 1:
输入: [“flower”,”flow”,”flight”]
输出: “fl”

示例 2:
输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。

这道题先对数组排序，找到最小的字符串，对最小字符串进行遍历，遍历过程中对数组遍历，也就是每次检查同下标的值。

func longestCommonPrefix(_ strs: [String]) -> String {
    guard strs.count > 1 else {
        return strs.first ?? ""
    }
    let strs = strs.sorted()
    var index = 0
    let first = strs.first!
    for (i, value) in first.enumerated() {
        for (j, str) in strs[1..<strs.count].enumerated() {
            if value == str[String.Index.init(utf16Offset: i, in: str)] {
                if j == strs.count-2 {
                    index += 1
                }
            } else {
                return index == 0 ? "":String(first.prefix(index))
            }
        }
    }
    return String(first.prefix(index))
}

数字操作

整数反转 - 简单

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

func reverse(_ x: Int) -> Int {
    var num = x
    var res = 0
    while num != 0 {
        res = res*10 + num%10
        num = num/10
    }
    guard abs(res) <= Int32.max else {
        return 0
    }
    return res
}

字符串转换整数 (atoi) - 中等

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示：
本题中的空白字符只包括空格字符 ‘ ‘ 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: “42”
输出: 42
示例 2:

输入: “ -42”
输出: -42
解释: 第一个非空白字符为 ‘-‘, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:

输入: “4193 with words”
输出: 4193
解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。
示例 4:

输入: “words and 987”
输出: 0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:

输入: “-91283472332”
输出: -2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。

这道题实则对每个字符进行判断，然后进行强制转换。

func myAtoi(_ str: String) -> Int {
    let str = str.trimmingCharacters(in: .whitespaces)
    guard str.count > 0 else {
        return 0
    }
    var res = ""
    for value in str {
        if value.isNumber {
            res += String(value)
        } else if value == "-" || value == "+" {
            guard res == "" else {
                break
            }
            res += String(value)
        } else {
            break
        }
    }
    guard res != "" && res != "-" && res != "+" else {
        return 0
    }
    let ans = Int32(res)
    guard let x = ans else {
        if res.first!.isNumber {
            return Int(Int32.max)
        } else {
            return res.first! == "+" ? Int(Int32.max):Int(Int32.min)
        }
    }
    return Int(x)
}

回文数 - 简单

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true
示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

这道题利用转换成string类型然后双指针遍历。

func isPalindrome(_ x: Int) -> Bool {
    guard x >= 0 else {
        return false
    }
    let str = "\(x)"
    var start = 0
    var end = str.count-1
    while start < end {
        guard str[str.index(str.startIndex, offsetBy: start)] == str[str.index(str.startIndex, offsetBy: end)] else {
            return false
        }
        start += 1
        end -= 1
    }
    return true
}

阶乘后的零 - 简单

给定一个整数 n，返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

这道题要求这样的时间复杂度，说明我们不能用常规遍历相乘的方法，需要找到其中的规律。首先我们知道产生0必须是5的倍数。按照这样的思维，我们找到了这样的公式。

这样，我们可以根据公式写出答案，在此，我们进行优化下，公式可以变化成：

func trailingZeroes(_ n: Int) -> Int {
    var n = n
    var count = 0
    while n != 0 {
        count += n/5
        n = n/5
    }
    return count
}

各位相加 - 简单

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

示例:

输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。由于2 是一位数，所以返回 2。

这道题利用循环和递归，是可以解决，但是我们也可以达成时间复杂度为1的算法。分析这个题，我们只需要个位数，那么我们对于原数进行余9就能获得结果。

func addDigits(_ num: Int) -> Int {
        if (num < 10) {
            return num;
        }
        let result = num % 9;
        if (result == 0) {
            return 9;
        }
        return result;
}

数组操作

螺旋矩阵 - 中等

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

这道题我们可以想成每次操作消除顶部和右边，然后消除底部（倒序）和左边（倒序），这样当元素没有了，操作也就完成了。这里需要一个mn的额外空间，但是时间上是优秀的。如果额外空间上达到1，可以用指针控制矩阵长宽来实现。

func spiralOrder(_ matrix: [[Int]]) -> [Int] {
    var matrix = matrix
    var isReversed = false
    var res = [Int]()
    while !matrix.isEmpty {
        if !isReversed {
            res += matrix.removeFirst()
            if (matrix.first == nil) {
                break
            }
            for i in 0..<matrix.count {
                res.append(matrix[i].removeLast())
            }
            if matrix.first!.isEmpty {
                break
            }
            isReversed = true
        } else {
            res += matrix.removeLast().reversed()
            if (matrix.first == nil) {
                break
            }
            for i in (0..<matrix.count).reversed() {
                res.append(matrix[i].removeFirst())
            }
            if matrix.first!.isEmpty {
                break
            }
            isReversed = false
        }
    }
    return res
}

矩阵置零 - 中等

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:

输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

这道题我们想着怎么找到0的行列，然后置0。这里我们想要实现空间复杂度为1的情况，我们得另起方法来获取行列。我们不难发现，我们对于0点的位置，可以对于他的行首和列首进行置0，因此我们需要遍历一遍矩阵，这样行首和列首就得到了需要置零的行列。但是，注意一点行首和列首本身有0的情况，我们可以用两个布尔值记录就行了。时间复杂度为mn。

func setZeroes(_ matrix: inout [[Int]]) {
    var zeroRow = false
    var zeroColumn = false
    for y in 0 ..< matrix.count {
        for x in 0 ..< matrix[y].count {
            if matrix[y][x] == 0  {
                if y == 0  {
                    zeroRow = true
                }
                if x == 0 {
                    zeroColumn = true
                }
                matrix[0][x] = 0
                matrix[y][0] = 0
            }
        }
    }
    for x in 0 ..< matrix[0].count {
        if matrix[0][x] == 0 && x != 0  {
            for y in 0 ..< matrix.count {
                matrix[y][x] = 0
            }
        }
    }
    for y in 0 ..< matrix.count {
        if matrix[y][0] == 0 && y != 0  {
            for x in 0 ..< matrix[y].count {
                matrix[y][x] = 0
            }
        }
    }
    if zeroRow {
        for x in 0 ..< matrix[0].count {
            matrix[0][x] = 0
        }
    }
    if zeroColumn {
        for y in 0 ..< matrix.count {
            matrix[y][0] = 0
        }
    }
}

子集 - 中等

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

这道题为了输出子集，势必时间复杂度为n2^n，空间复杂度为n2^n。主要我们要想怎么得到子集并且不能重复。这里我们使用二进制来解决问题。听起来两者表面没什么关系，但是子集的个数是2^n。对应了n位的二进制数。将每个子集映射到长度为 n 的位掩码中，其中第 i 位掩码 nums[i] 为 1，表示第 i 个元素在子集中；如果第 i 位掩码 nums[i] 为 0，表示第 i 个元素不在子集中。按照这样的思想我们就能很轻松的求出子集。

最短无序连续子数组 - 简单

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

这道题会让你看着迷糊并且不知道分析方向，其实这道题隐约着还是用双指针比较好，因为有涉及到比较的问题。我们要得到升序数组，我们得知道他的上界和下界，因此我们需要消耗两次遍历找到上界和下界，根据上界和下界的位置利用双指针进行遍历。最后通过指针位置得到数组。

func findUnsortedSubarray(_ nums: [Int]) -> Int {
    var minValue = Int.max
    var maxValue = Int.min
    for i in 1..<nums.count {
        if nums[i] < nums[i-1] {
            minValue = min(minValue,nums[i])
        }
    }
    for i in (0..<nums.count-1).reversed() {
        if nums[i] > nums[i+1] {
            maxValue = max(maxValue, nums[i])
        }
    }
    var left = 0
    var right = nums.count-1
    while left < nums.count {
        if minValue < nums[left] {
            break
        }
        left += 1
    }
    while right >= 0 {
        if maxValue > nums[right] {
            break
        }
        right -= 1
    }
    return right < left ? 0:right-left+1
}

判断是否形成等差数列 - 简单

给你一个数字数组 arr 。

如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为等差数列。

如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。

示例 1：

输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
示例 2：

输入：arr = [1,2,4]
输出：false
解释：无法通过重新排序得到等差数列。

这道题我们的反应是想用等差数列的性质来进行判断，但是给出的数组并不是有序的，所以直接使用是不行的。因此，我们需要排除一些情况以及变换角度。首先我们需要排除存在相等的（count>2），我们可以利用字典来实现一次遍历（时间复杂度为n），在遍历同时我们获取最大值和最小值。通过字典的过滤，我们得到数组内元素完全不相等的情况。我们核心还是依靠等差数列性质，那么在有最大值和最小值情况下，我们可以得到等差值d，要满足是等差数列，相邻两值差值一定是d，在无序情况下，当前值与最小值的差值是等差值d的倍数。
因此这个算法能达到时间复杂度为n

func canMakeArithmeticProgression(_ arr: [Int]) -> Bool {
    guard arr.count > 2 else {
        return true
    }
    var minValue = Int.max
    var maxValue = Int.min
    var dic = Dictionary<Int,Int>()
    for num in arr {
        dic[num] = (dic[num] != nil) ? dic[num]!+1:1
        if minValue > num {
            minValue = num
        }
        if maxValue < num {
            maxValue = num
        }
    }
    guard dic.keys.count == arr.count else {
        return dic.keys.count == 1 ? true:false
    }
    guard (maxValue-minValue)%(arr.count-1) == 0 else {
        return false
    }
    let d = (maxValue-minValue)/(arr.count-1)
    for num in arr {
        if (num-minValue)%d != 0 {
            return false
        }
    }
    return true
}

栈操作

有效括号 - 简单

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：
* 左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true
示例 2:

输入: “()[]{}”
输出: true
示例 3:

输入: “(]”
输出: false
示例 4:

输入: “([)]”
输出: false
示例 5:

输入: “{[]}”
输出: true

这道题要求判断括号是否闭合，我们可以使用栈思想来实现这个功能，左括号进行入栈，右括号进行出栈对比操作。

func isValid(_ s: String) -> Bool {
    guard s.count%2 == 0 else {
        return s.isEmpty ? true:false
    }
    var arr = [String.Element]()
    for e in s {
        switch e {
        case "{","(","[":
            arr.append(e)
        case "}":
            if arr.popLast() != "{" {
                return false
            }
        case ")":
            if arr.popLast() != "(" {
                return false
            }
        case "]":
            if arr.popLast() != "[" {
                return false
            }
        default:
            break
        }
    }
    return arr.isEmpty ? true:false
}

最长有效括号 - 困难

给定一个只包含 ‘(‘和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”
示例 2:

输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”

这道题是上一题的升级题，同时难度也增加因为需要你判断有效括号的最大长度。我们仍旧可以使用栈操作，只不过这次我们不能够使用元素来存储了，因为是连续的，我们想到了下标的存储。
具体做法是我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：
* 对于遇到的每个 \text{‘(’}‘(’ ，我们将它的下标放入栈中
* 对于遇到的每个 \text{‘)’}‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：
* 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
* 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
我们从前往后遍历字符串并更新答案即可。

func longestValidParentheses(_ s: String) -> Int {
    var maxans = 0
    var stack = [Int]()
    stack.append(-1)
    for (i, value) in s.enumerated() {
        if value == "(" {
            stack.append(i)
        } else {
            stack.popLast()
            if stack.isEmpty {
                stack.append(i)
            } else {
                maxans = max(maxans, i-stack.last!)
            }
        }
    }
    return maxans
}

最小栈 - 简单

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

pop、top 和 getMin 操作总是在 非空栈 上调用。

示例:

输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.

这道题是设计题，自由度高但是也需要考虑合理性与最优化。难点在于常数时间复杂度输出栈中最小值，那么我们可以使用额外的空间来满足时间。那么判断最小值应该在入栈期间进行判断。我们可以通过辅助栈来存储每个元素插入后当前的栈的最小值，这样出栈时辅助栈也出栈。
这里，可能还有进阶要求不能用额外空间，这种情况，我们利用差值来存储最小值变化。

class MinStack {
    
    private var stack = [Int]()
    private var minStack = [Int]()

    init() {
        minStack.append(Int.max)
    }
    
    func push(_ x: Int) {
        stack.append(x)
        minStack.append(minStack.last! < x ? minStack.last!:x)
    }
    
    func pop() {
        if !stack.isEmpty {
            _ = stack.popLast()
            _ = minStack.popLast()
        }
    }
    
    func top() -> Int {
        return stack.last!
    }
    
    func getMin() -> Int {
        return minStack.last!
    }
}

用栈实现队列 - 简单

使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

这道题需要一个辅助栈来存储倒序栈，对倒序栈进行出栈实现队列功能。

class MyQueue {
    
    private class Stack {
        private var elements = [Int]()
        
        /** Push element x to the back of queue. */
        func push(_ x: Int) {
            elements.append(x)
        }
        
        /** Removes the element from in front of queue and returns that element. */
        func pop() -> Int {
            return elements.popLast()!
        }
        
        /** Get the front element. */
        func peek() -> Int {
            return elements.last!
        }
        
        /** Returns whether the queue is empty. */
        func empty() -> Bool {
            return elements.isEmpty
        }
    }
    
    private var stack1 = Stack()
    private var stack2 = Stack()
    
    /** Initialize your data structure here. */
    init() {

    }
    
    /** Push element x to the back of queue. */
    func push(_ x: Int) {
        stack1.push(x)
    }
    
    /** Removes the element from in front of queue and returns that element. */
    func pop() -> Int {
        if stack2.empty() {
            while !stack1.empty() {
                stack2.push(stack1.pop())
            }
        }
        return stack2.pop()
    }
    
    /** Get the front element. */
    func peek() -> Int {
        if stack2.empty() {
            while !stack1.empty() {
                stack2.push(stack1.pop())
            }
        }
        return stack2.peek()
    }
    
    /** Returns whether the queue is empty. */
    func empty() -> Bool {
        return stack1.empty() && stack2.empty()
    }
}

用队列实现栈 - 简单

使用队列实现栈的下列操作：

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空

注意:
你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

这道题与上一题相反要求，我们仍可以用两个队列来实现栈。但是我们这次辅助队列是用来暂存除最后一个元素的队列，出栈结束后要恢复到源队列中。

class MyStack {
    
    private class Queue {
        
        private var elements = [Int]()
        
        /** Push element x onto stack. */
        func enqueue(_ x: Int) {
            elements.append(x)
        }
        
        /** Removes the element on top of the stack and returns that element. */
        func dequeue() -> Int {
            return elements.removeFirst()
        }
        
        /** Get the top element. */
        func top() -> Int {
            return elements.first!
        }
        
        /** Returns whether the stack is empty. */
        func empty() -> Bool {
            return elements.isEmpty
        }
        
        func size() -> Int {
            return elements.count
        }
    }
    
    private var queue1 = Queue()
    private var queue2 = Queue()
    private var topValue = 0

    /** Initialize your data structure here. */
    init() {

    }
    
    /** Push element x onto stack. */
    func push(_ x: Int) {
        queue1.enqueue(x)
        topValue = x
    }
    
    /** Removes the element on top of the stack and returns that element. */
    func pop() -> Int {
        while queue1.size() > 1 {
            topValue = queue1.dequeue()
            queue2.enqueue(topValue)
        }
        let res = queue1.dequeue()
        queue1 = queue2
        queue2 = Queue()
        return res
    }
    
    /** Get the top element. */
    func top() -> Int {
        return topValue
    }
    
    /** Returns whether the stack is empty. */
    func empty() -> Bool {
        return queue1.empty() && queue2.empty()
    }
}

去除重复字母 - 困难

给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1:
输入: “bcabc”
输出: “abc”
示例 2:
输入: “cbacdcbc”
输出: “acdb”

这道题看上去用字典解决就可以直接得到答案，但是这里有保证字典序最小的要求，情况就要复杂得多。
首先要知道什么叫 “字典序”。字符串之间比较跟数字之间比较是不太一样的。字符串比较是从头往后一个字符一个字符比较的。哪个字符串大取决于两个字符串中第一个对应不相等的字符。根据这个规则，任意一个以 a 开头的字符串都大于任意一个以 b 开头的字符串。
按照这个要求，我们可以想到用栈来实现这样的过程。对字符串进行遍历，并选择入栈还是出栈
* 如果栈里已经存在，则忽略（只存在一个元素）
* 如果比栈顶元素字典序小，且栈顶元素在后面还会出现，则出栈
* 否则，入栈

func removeDuplicateLetters(_ s: String) -> String {
    var stack = [Character]()
    var lastAppearIndexDic = [Character:Int]()
    var set = [Character:Bool]()
    // 为了减低时间复杂度，提前求出元素出现的最后一个位置
    for (i, c) in s.enumerated() {
        lastAppearIndexDic[c] = i
    }
    for (i, c) in s.enumerated() {
        guard !(set[c] ?? false) else { continue } // 栈里已经有直接跳过
        while let top = stack.last, top > c, lastAppearIndexDic[top]! >= i {
            let poped = stack.popLast()!
            set[poped] = false
        }
        stack.append(c)
        set[c] = true
    }
    return String(stack)
}

堆相关

数组中的第K个最大元素 - 中等

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

这道题是排序题，这里我们不用库函数，而是堆排序来实现。利用大小堆上，这里封装了一个堆的类，通过这个类实现堆排序。
具体查看网站Swift实现优先队列PriorityQueue - 山青咏芝 - 博客园

class Solution_findKthTarget {
    
    public struct Heap {
        var elements: [Int] = []
        let sort: (Int, Int) -> Bool
        var isEmpty: Bool {
            return self.elements.isEmpty
        }

        var count: Int {
            return self.elements.count
        }

        func peek() -> Int? {
            return elements.first
        }

        init(sort: @escaping (Int, Int) -> Bool, elements: [Int] = []) {
            self.sort = sort
            self.elements = elements

            if !elements.isEmpty {
                for i in stride(from: elements.count/2 - 1, through: 0, by: -1) {
                    siftDown(from: i)
                }
            }
        }

        mutating func siftDown(from index: Int) {
            var parent = index
            while true {
                let left = leftIndex(of: parent)
                let right = rightIndex(of: parent)
                var candidate = parent
                if left < count && sort(elements[left], elements[candidate]) {
                    candidate = left
                }
                if right < count && sort(elements[right], elements[candidate]) {
                    candidate = right
                }
                if candidate == parent {
                    return
                }
                elements.swapAt(parent, candidate)
                parent = candidate
            }
        }

        mutating func siftUp(from index: Int) {
            var child = index
            var parent = parentIndex(of: child)
            while child > 0 && sort(elements[child], elements[parent]) {
                elements.swapAt(child, parent)
                child = parent
                parent = parentIndex(of: child)
            }
        }

        mutating func push(_ element: Int) {
            elements.append(element)
            siftUp(from: count-1)
        }

        mutating func pop() -> Int? {
            guard !isEmpty else { return nil }
            elements.swapAt(0, count-1)
            defer {
                siftDown(from: 0)
            }
            return elements.popLast()
        }

        func leftIndex(of index: Int) -> Int {
            return (2 * index) + 1
        }

        func rightIndex(of index: Int) -> Int {
            return (2 * index) + 2
        }

        func parentIndex(of index: Int) -> Int {
            return (index - 1) / 2
        }
    }
    
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        var heap = Heap.init(sort: >)
        for num in nums {
            heap.push(num)
            if heap.count > k {
                heap.pop()
            }
        }
        return heap.pop()!
    }
}

前k个高频元素 - 中等

给定一个非空的整数数组，返回其中出现频率前 k高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

这道题与上一题类似，只不过排序对象为频率，同时返回元素。那我们可以使用键值对象来导入到堆类中。

class Solution_topKFrequent {
    
    private struct Heap {
        var elements: [Dictionary<Int,Int>.Element] = []
        let sort: (Int, Int) -> Bool
        var isEmpty: Bool {
            return self.elements.isEmpty
        }

        var count: Int {
            return self.elements.count
        }

        func peek() -> Dictionary<Int,Int>.Element? {
            return elements.first
        }

        init(sort: @escaping (Int, Int) -> Bool, elements: [Dictionary<Int,Int>.Element] = []) {
            self.sort = sort
            self.elements = elements

            if !elements.isEmpty {
                for i in stride(from: elements.count/2 - 1, through: 0, by: -1) {
                    siftDown(from: i)
                }
            }
        }

        mutating func siftDown(from index: Int) {
            var parent = index
            while true {
                let left = leftIndex(of: parent)
                let right = rightIndex(of: parent)
                var candidate = parent
                if left < count && sort(elements[left].value, elements[candidate].value) {
                    candidate = left
                }
                if right < count && sort(elements[right].value, elements[candidate].value) {
                    candidate = right
                }
                if candidate == parent {
                    return
                }
                elements.swapAt(parent, candidate)
                parent = candidate
            }
        }

        mutating func siftUp(from index: Int) {
            var child = index
            var parent = parentIndex(of: child)
            while child > 0 && sort(elements[child].value, elements[parent].value) {
                elements.swapAt(child, parent)
                child = parent
                parent = parentIndex(of: child)
            }
        }

        mutating func push(_ element: Dictionary<Int,Int>.Element) {
            elements.append(element)
            siftUp(from: count-1)
        }

        mutating func pop() -> Dictionary<Int,Int>.Element? {
            guard !isEmpty else { return nil }
            elements.swapAt(0, count-1)
            defer {
                siftDown(from: 0)
            }
            return elements.popLast()
        }

        func leftIndex(of index: Int) -> Int {
            return (2 * index) + 1
        }

        func rightIndex(of index: Int) -> Int {
            return (2 * index) + 2
        }

        func parentIndex(of index: Int) -> Int {
            return (index - 1) / 2
        }
    }
    
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        var countDic = [Int:Int]()
        for n in nums {
            countDic[n] = (countDic[n] ?? 0) + 1
        }
        var heap = Heap.init(sort: <)
        for n in countDic {
            heap.push(n)
            if heap.count > k {
                heap.pop()
            }
        }
        return heap.elements.reversed().map { (v) -> Int in
            return v.key
        }
    }
}

递归相关

什么是递归呢？函数在运行时调用自己，这个函数就叫递归函数，调用的过程叫做递归。
比如定义函数
f(x)=x+f(x-1)
f(x)=x+f(x−1)：
代码为

1 2	def f(x): return x + f(x-1)

如果代入 f(2)：

返回 2+f(1)；
调用 f(1)；
返回 1+f(0)；
调用 f(0)；
返回 0+f(-1)
……
这时程序会无休止地运行下去，直到崩溃。
如果我们加一个判断语句 x > 0：

def f(x):
    if x > 0:
        return x + f(x-1)
    else:  # f(0) = 0
        return 0

这次计算 f(2)=2+f(1)=2+1+f(0)=2+1+0=3f(2)=2+f(1)=2+1+f(0)=2+1+0=3。

我们从中总结两个规律：
* 递归函数必须要有终止条件，否则会出错；
* 递归函数先不断调用自身，直到遇到终止条件后进行回溯，最终返回答案。

合并两个有序链表 - 简单

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

这道题使用递归方法简洁。

终止条件：当两个链表都为空时，表示我们对链表已合并完成。
如何递归：我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）
时间复杂度为m+n

class Solution_mergeTwoLists {
    public class ListNode {
        public var val: Int
        public var next: ListNode?
        public init() { self.val = 0; self.next = nil; }
        public init(_ val: Int) { self.val = val; self.next = nil; }
        public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = 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
        }
    }

反转字符串 - 简单

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：[“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：

输入：[“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]

这道题我们也可以使用双指针，但是这里准备用递归实现双指针的思想。但是空间复杂度会产生n因为用了系统栈。

func reverseString(_ s: inout [Character]) {
    helper_reverseString(&s, 0, s.count-1)
}

fileprivate func helper_reverseString(_ s: inout [Character],_ left: Int, _ right: Int) {
    guard left < right else {
        return
    }
    s.swapAt(left, right)
    helper_reverseString(&s, left+1, right-1)
}

两两交换链表中的节点 - 中等

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

从链表的头节点 head 开始递归。
每次递归都负责交换一对节点。由 firstNode 和 secondNode 表示要交换的两个节点。
下一次递归则是传递的是下一对需要交换的节点。若链表中还有节点，则继续递归。
交换了两个节点以后，返回 secondNode，因为它是交换后的新头。
在所有节点交换完成以后，我们返回交换后的头，实际上是原始链表的第二个节点。
时间复杂度为n，空间复杂度为n。

func swapPairs(_ head: ListNode?) -> ListNode? {
    guard let next = head?.next else {
        return head
    }
    head?.next = swapPairs(next.next)
    next.next = head
    return next
}

二叉树的最大深度 - 简单

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

class Solution_maxDepth {
    public class TreeNode {
        public var val: Int
        public var left: TreeNode?
        public var right: TreeNode?
        public init(_ val: Int) {
            self.val = val
            self.left = nil
            self.right = nil
        }
    }
    
    func maxDepth(_ root: TreeNode?) -> Int {
        guard root != nil else {
            return 0
        }
        return max(maxDepth(root?.left),maxDepth(root?.right)) + 1
    }
}

回溯法

也被称为深度优先遍历

括号生成 - 中等

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的括号组合。

一般回溯的问题有三种：

Find a path to success 有没有解
Find all paths to success 求所有解
求所有解的个数
求所有解的具体信息
Find the best path to success 求最优解
回溯法是一个剪枝了的二叉树。我们要得到的结果是可以 good leaf，如果不满足 good leaf 就继续向下搜索，搜索的时候需要满足一定的条件。

这道题的解题流程就是这样：

func generateParenthesis(_ n: Int) -> [String] {
    var arr = [String]()
    backtrack(&arr, "", 0, 0, n)
    return arr
}

fileprivate func backtrack(_ arr: inout [String], _ cur: String, _ left: Int, _ right: Int, _ max: Int) {
    if cur.count == max*2 {
        arr.append(cur)
        return
    }
    if left < max {
        backtrack(&arr, cur+"(", left+1, right, max)
    }
    if right < left {
        backtrack(&arr, cur+")", left, right+1, max)
    }
}

组合总和2 - 中等

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

参考力扣最佳解答。

func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
    var res = [[Int]]()
    if candidates.isEmpty {
        return res
    }
    let arr = candidates.sorted()
    var path = [Int]()
    helper_combinationSum2(arr, target, 0, &path, &res)
    return res
}

fileprivate func helper_combinationSum2(_ candidates: [Int], _ target: Int, _ begin: Int, _ path: inout [Int], _ res: inout [[Int]]) {
    if target == 0 {
        res.append(path)
        return
    }
    for i in begin..<candidates.count {
        if target-candidates[i] < 0 {
            break
        }
        if i > begin && candidates[i] == candidates[i-1] {
            continue
        }
        path.append(candidates[i])
        helper_combinationSum2(candidates, target-candidates[i], i+1, &path, &res)
        path.removeLast()
    }
}

原文作者：Jonathan Lu

原文链接：https://jonathanlu98.github.io/2020/08/29/%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%EF%BC%88%E5%85%AD%EF%BC%89%20%E9%A2%98%E7%9B%AE%E7%BB%BC%E5%90%88/

发表日期：August 29th 2020, 9:54:01 pm

更新日期：October 5th 2021, 11:34:35 pm

Next Post

算法基础（三）排序和搜索
Previous Post

实习面试整理

CATALOG

1. 算法基础（六）题目综合

算法基础（六） 题目综合

算法基础（六） 题目综合

一些知识

时间复杂度

语句频度

空间复杂度

hash相关

两数之和 - 简单

字符串中的第一个唯一字符 - 简单

链表操作

两数相加 - 中等

删除链表的倒数第N个节点 - 中等

K 个一组翻转链表 - 困难

旋转链表 - 中等

复制带随机指针的链表 - 中等

反转链表 - 简单

双指针遍历/滑动窗口

无重复字符的最长子串 - 中等

盛最多水的容器 - 中等

三数之和 - 中等

最接近的三数之和 - 中等

删除排序数组中的重复项 - 简单

买卖股票的最佳时机 - 简单

长度最小的子数组 - 中等

快慢指针遍历

环形链表 - 简单

快乐数 - 简单

链表的中间结点 - 简单

字符串操作

z字形转换 - 中等

最长公共前缀 - 简单

数字操作

整数反转 - 简单

字符串转换整数 (atoi) - 中等

回文数 - 简单

阶乘后的零 - 简单

各位相加 - 简单

数组操作

螺旋矩阵 - 中等

矩阵置零 - 中等

子集 - 中等

最短无序连续子数组 - 简单

判断是否形成等差数列 - 简单

栈操作

有效括号 - 简单

最长有效括号 - 困难

最小栈 - 简单

用栈实现队列 - 简单

用队列实现栈 - 简单

去除重复字母 - 困难

堆相关

数组中的第K个最大元素 - 中等

前k个高频元素 - 中等

递归相关

合并两个有序链表 - 简单

反转字符串 - 简单

两两交换链表中的节点 - 中等

二叉树的最大深度 - 简单

回溯法

括号生成 - 中等

组合总和2 - 中等

算法基础（六）题目综合

算法基础（六）题目综合