肇鑫的技术博客

业精于勤,荒于嬉

207. 课程表

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: 2, [[1,0]]
Output: true
Explanation: 
There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: 
There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

错误的解答

因为是n个课程,全部都要完成。因此课程的数量是无关的。需要考虑的是前置的限制之间是否冲突。前置的限制冲突,指的有向图的路径形成了环。

  1. 获得所有前置条件的序号
  2. 如果前置不为空
  3. 选取第一个条件
  4. 将第一个条件加入路径
  5. 在序号中删除该序号
  6. 不断地查找路径的前置顶点,如果该顶点以存在于路径,则为环,返回假
    1. 否则将该点插入到路径的头
    2. 继续查找前置顶点,直到没有前置顶点
  7. 不断地查找路径的后置顶点,如果该顶点以存在于路径,则为环,返回假
    1. 否则将该顶点添加到路径的尾
    2. 继续查找后置顶点,直到没有后置顶点
class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var availableIndexes = (0..<prerequisites.count).map {$0}
        while !availableIndexes.isEmpty {
            var path = [Int]()
            let pre = prerequisites[availableIndexes[0]]
            path.append(contentsOf: pre.reversed())
            availableIndexes.removeFirst()
            
            while let from = prePre(path, prerequisites: prerequisites, from: &availableIndexes) {
                guard !path.contains(from) else {
                    // 如果前置条件成环,则整条路径不可用,因为缺乏前置条件
                    return false
                }
                
                path.insert(from, at: 0)
            }
            
            while let to = postPre(path, prerequisites: prerequisites, from: &availableIndexes) {
                guard !path.contains(to) else {
                    // 如果后续为环,则之前的to对应值的顶点到路径末尾的内容不可用
                    return false
                }
                path.append(to)
            }
        }
        
        return true
    }
    
    func prePre(_ path:[Int], prerequisites: [[Int]], from availableIndexes:inout [Int]) -> Int? {
        let from = path[0]
        for i in 0..<availableIndexes.count {
            let a = availableIndexes[i]
            let p = prerequisites[a]
            if p[0] == from {
                availableIndexes.remove(at: i)
                return p[1]
            }
        }
        
        return nil
    }
    
    func postPre(_ path:[Int], prerequisites: [[Int]], from availableIndexes:inout [Int]) -> Int? {
        let to = path.last!
        for i in 0..<availableIndexes.count {
            let a = availableIndexes[i]
            let p = prerequisites[a]
            if to == p[1] {
                availableIndexes.remove(at: i)
                return p[0]
            }
        }
        
        return nil
    }
}

let s = Solution()
print(s.canFinish(3, [[1,0],[2,0],[0,2]]))

上面的代码虽然通过了提交,但是算法其实存在问题。

bad_solution

示例:5, [[1,0],[2,1],[3,2],[1,4],[4,2]]。图见上图,存在一个环。但是由于选取时,选择不是全部的向上顶点或向下顶点,而只是第一组,造成了环并没有被解析到的现象。算法会先获得路径[0,1,2,3],然后获得[1,4,2]。完美避开了环[1,2,4,1]。

要想解决这个问题,就不能只取一条一个向上顶点或向下顶点,而应该全部获取。

正确的解答

正确的解答使用的邻近链表的方法。(^表示无后继)

顶点Vertex 入度InDegree 出度链表OutDegree LinkedList
0 0 -> 1^
1 2 -> 2 -> 4^
2 1 -> 3 -> 4^
3 1 ^
4 1 -> 1^
  1. numCourses生成最初的邻近链表。初始化顶点数为0。
  2. 根据限制条件prerequisites设定邻近链表的属性
  3. 寻找临近链表的最初顶点,最初顶点即不依赖任何其它顶点的点。也就是入度为0的顶点。
    1. 找到之后。顶点数增加1。移除该顶点。以及该顶点与其它顶点的连线。
    2. 回到3
  4. 查看顶点数是否与numCourses相当,如果不等,就是遇到了环,无法完成课表。
class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var vertexNumber = 0
        var vertices:Array<Vertex> = (0..<numCourses).map {
            Vertex(value: $0, inDegree: 0, link: nil)
        }
        prerequisites.forEach { pre in
            let to = pre[0]
            let from = pre[1]
            
            vertices[to].inDegree += 1
            
            if let link = vertices[from].link {
                link.append(LinkList(value: to))
            } else {
                vertices[from].link = LinkList(value: to)
            }
        }
        
        while let vertex = getZeroInDegreeVertex(vertices) {
            //            print(vertex.value)
            vertexNumber += 1
            vertex.inDegree = -1
            var link = vertex.link
            while link != nil  {
                vertices[link!.value].inDegree -= 1
                link = link?.next
            }
        }
        
        return vertexNumber == numCourses
    }
    
    func getZeroInDegreeVertex(_ vertices:[Vertex]) -> Vertex? {
        for v in vertices {
            if v.inDegree == 0 {
                return v
            }
        }
        
        return nil
    }
}

class Vertex {
    let value:Int
    var inDegree:Int
    var link:LinkList<Int>? = nil
    
    init(value:Int, inDegree:Int, link:LinkList<Int>?) {
        self.value = value
        self.inDegree = inDegree
        self.link = link
    }
}

class LinkList<T> {
    let value:T
    var next:LinkList<T>? = nil
    
    init(value:T) {
        self.value = value
    }
    
    func append(_ link:LinkList<T>) {
        if self.next == nil {
            self.next = link
        } else {
            var l = self.next
            while l?.next != nil {
                l = l?.next
            }
            l?.next = link
        }
    }
}

let s = Solution()
//print(s.canFinish(5, [[1,0],[2,1],[3,2],[1,4],[4,2]])) // false
print(s.canFinish(5, [[1,0],[2,1],[3,2],[4,1],[2,4]])) // true
//print(s.canFinish(2, [[1,0]])) // true
//print(s.canFinish(2, [[1,0],[0,1]])) // false

相关

210. 课程表 II

asdfa

“309. 最佳买卖股票时机含冷冻期”的解题思路

309. 最佳买卖股票时机含冷冻期

原题

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解题思路1

尝试走出所有路径。利用递归和缓存结果的方式进行优化,并设置结束条件进行约束。可惜,不能通过所有测试,提示超时。

class Solution {
    var cachedResults = [[Int]:Int]()
    
    func maxProfit(_ prices: [Int]) -> Int {
        var dealProfit = 0
        var firstDealEndAt:Int? = nil
        
         // 买,卖,冻;买,卖,冻
        for buyIndex in 0..<prices.count {
            let sellIndexStartAt = buyIndex + 1
            guard sellIndexStartAt < prices.count else {
                return dealProfit
            }
            
            let buyPrice = prices[buyIndex]
            for sellIndex in sellIndexStartAt..<prices.count {
                if let dealEndAt = firstDealEndAt {
                    guard buyIndex < dealEndAt else {
                        break
                    }
                }
                
                let sellPrice = prices[sellIndex]
                if buyPrice < sellPrice {
                    if let endDealAt = firstDealEndAt {
                        if endDealAt > sellIndex {
                            firstDealEndAt = sellIndex
                        }
                    } else {
                        firstDealEndAt = sellIndex
                    }
                    
                    var profit = sellPrice - buyPrice
                    
                    let nextIndex = sellIndex + 2
                    
                    if nextIndex < prices.count {
                        let remainPrices = Array(prices[nextIndex...])
                        let remainProfit:Int = {
                            if let profit = cachedResults[remainPrices] {
                                return profit
                            }
                            
                            let profit = maxProfit(remainPrices)
                            cachedResults.updateValue(profit, forKey: remainPrices)
                            
                            return profit
                        }()
                        
                        profit += remainProfit
                    }
                    
                    dealProfit = max(dealProfit, profit)
                }
            }
        }

        return dealProfit
    }
}

解题思路2

思路2是同时计算每一步的状态。我们知道,针对每一个数据,它可能的状态有3个,即买、卖、等待。如图:

wvR4TN8.png-1

s0[i] = max(s0[i - 1], s2[i - 1]); // 冷却可能是原地等待,也可能是卖完之后强制冷却
s1[i] = max(s1[i - 1], s0[i - 1] - prices[i]); // Stay at s1, or buy from s0 原地等待,或者购买,如果购买,则肯定是从s0状态过来的。
s2[i] = s1[i - 1] + prices[i]; // 卖出获利

最终代码:

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        guard !prices.isEmpty else {
            return 0
        }
        
        var s0 = Array<Int>(repeating: 0, count: prices.count)
        var s1 = Array<Int>(repeating: 0, count: prices.count)
        var s2 = Array<Int>(repeating: 0, count: prices.count)
        
        s0[0] = 0
        s1[0] = -prices[0]
        s2[0] = Int.min
        
        for index in 1..<prices.count {
            s0[index] = max(s0[index - 1], s2[index - 1])
            s1[index] = max(s1[index - 1], s0[index - 1] - prices[index])
            s2[index] = s1[index - 1] + prices[index]
        }

        return max(s0.last!, s2.last!) // 最后一步,要么是冷却状态,要么是卖出状态。不可能是买入状态
    }
}

参考资料:

"916. 单词子集"的解题思路

916. 单词子集

原题

我们给出两个单词数组 A 和 B。每个单词都是一串小写字母。

现在,如果 b 中的每个字母都出现在 a 中,包括重复出现的字母,那么称单词 b 是单词 a 的子集。 例如,“wrr” 是 “warrior” 的子集,但不是 “world” 的子集。

如果对 B 中的每一个单词 bb 都是 a 的子集,那么我们称 A 中的单词 a通用的

你可以按任意顺序以列表形式返回 A 中所有的通用单词。

示例 1:

输入:A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
输出:["facebook","google","leetcode"]

示例 2:

输入:A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
输出:["apple","google","leetcode"]

示例 3:

输入:A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
输出:["facebook","google"]

示例 4:

输入:A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
输出:["google","leetcode"]

示例 5:

输入:A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
输出:["facebook","leetcode"]

提示:

  1. 1 <= A.length, B.length <= 10000
  2. 1 <= A[i].length, B[i].length <= 10
  3. A[i] 和 B[i] 只由小写字母组成。
  4. A[i] 中所有的单词都是独一无二的,也就是说不存在 i != j 使得 A[i] == A[j]

解题思路1

这道题的一般思路很简单。循环A,然后循环B,B中的字符串中的字符如果在A的字符串中存在,则移除掉该字符,然后循环下一个字符。代码如下:

class Solution {
    func wordSubsets(_ A: [String], _ B: [String]) -> [String] {
        let array = A.filter { (s) -> Bool in
            for b in B {
                var s = s
                
                for bCharacter in b {
                    if let index = s.firstIndex(of: bCharacter) {
                        s.remove(at: index)
                    } else {
                        return false
                    }
                }
            }
            
            return true
        }
        
        return array
    }
}

这个思路验证时,提示会超时。也就是性能不达标。

解题思路2

我们注意到示例3中,存在两个相同的字母”oo“。

示例 3:

输入:A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
输出:["facebook","google"]

我的优化思路是,把不重复的字符单独优化,重复的仍然按照“思路1”的方式进行处理。代码如下:

class Solution {
    func wordSubsets(_ A: [String], _ B: [String]) -> [String] {
        var bSet = Set<Character>()
        var bArray = [String]()
        
        B.forEach {
            let set:Set<Character> = Set($0)
            if set.count == $0.count {  // no duplicated
                bSet = bSet.union(set)
            } else {
                bArray.append($0)
            }
        }
        
        let array = A.filter { (s) -> Bool in
            // bSet filter
            let aSet:Set<Character> = Set(s)
            guard aSet.isSuperset(of: bSet) else {
                return false
            }
            
            
            for b in bArray {
                var s = s
                
                for bCharacter in b {
                    if let index = s.firstIndex(of: bCharacter) {
                        s.remove(at: index)
                    } else {
                        return false
                    }
                }
            }
            
            return true
        }
        
        return array
    }
}

进行验证。还是性能不达标。

最终的解题思路

没办法,只好去翻评论。结果有人说,必须全部优化重复的字母,不然就一定会超时。所谓全部优化,就是把B中所有重复的字母计算出来。

原题的B等价于所有的字母都存在,且出现的次数大于等于B中的字符串中出现的那个字符的最多次数。

单独计算B的字母频率。

func characterFrequencies(in array:[String]) -> Dictionary<Character,Int> {
    var dictionary = Dictionary<Character,Int>()
    
    for s in array {
        var sDic = [Character:Int]()
        
        for c in s {
            if let f = sDic[c] {
                sDic[c] = f + 1
            } else {
                sDic[c] = 1
            }
        }
        
        sDic.forEach { (c, f) in
            if let frequency = dictionary[c] {
                dictionary[c] = max(frequency, f)
            } else {
                dictionary[c] = f
            }
        }
    }
    
    return dictionary
}

完整代码:

class Solution {
    func wordSubsets(_ A: [String], _ B: [String]) -> [String] {
        let dictionary = characterFrequencies(in: B)
        
        let array = A.filter { (s) -> Bool in
            for (c,f) in dictionary {
                var index = s.startIndex
                
                for _ in 1...f {
                    if index < s.endIndex, let firstIndex = s[index...].firstIndex(of: c) {
                        let nextIndex = s.index(after: firstIndex)
                        index = nextIndex
                    } else {
                        return false
                    }
                }
            }
            
            return true
        }
        
        
        return array
    }
    
    func characterFrequencies(in array:[String]) -> Dictionary<Character,Int> {
        var dictionary = Dictionary<Character,Int>()
        
        for s in array {
            var sDic = [Character:Int]()
            
            for c in s {
                if let f = sDic[c] {
                    sDic[c] = f + 1
                } else {
                    sDic[c] = 1
                }
            }
            
            sDic.forEach { (c, f) in
                if let frequency = dictionary[c] {
                    dictionary[c] = max(frequency, f)
                } else {
                    dictionary[c] = f
                }
            }
        }
        
        return dictionary
    }
}

小结

我们经常需要用到字典结构来挺高应用的性能。