funcfindTheCity(_ n: Int, _ edges: [[Int]], _ distanceThreshold: Int) -> Int { var dis = [[Int]](repeating: [Int](repeating: Int.max>>2, count: n+1), count: n+1) for e in edges { dis[e[0]][e[1]] = e[2] dis[e[1]][e[0]] = e[2] } for i in0..<n { dis[i][i] = 0 } for k in0..<n { for i in0..<n { for j in0..<n { dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]) } } } var mv = n+1 var ans = -1
for i instride(from: n-1, to: -1, by: -1) { var ct = 0 for j in0..<n where dis[i][j] <= distanceThreshold { ct += 1 } if ct < mv { mv = ct ans = i } } return ans }
5322. 工作计划的最低难度
你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。
你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。
给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。
funcminDifficulty(_ jobDifficulty: [Int], _ d: Int) -> Int { let n = jobDifficulty.count if d > n { return -1 } // dp[i][j] = min diff for doing first i jobs in j days? letINF = 1000_000_009 var dp = [[Int]](repeating: [Int](repeating: INF, count: d+1), count: n+1) for i in0..<n { var diff = jobDifficulty[i] for j instride(from: i, to: -1, by: -1) { diff = max(diff, jobDifficulty[j]) if j == 0 { dp[i][1] = diff } else { for k in2..<d+1 { dp[i][k] = min(dp[i][k], diff+dp[j-1][k-1]) } } } } return dp[n - 1][d] }
funcminTaps(_ n: Int, _ ranges: [Int]) -> Int { letINF = 1000_000_009 var pairs = [(Int, Int)]() for i in ranges.indices { pairs.append((max(0, i-ranges[i]), min(n, i+ranges[i]))) } pairs = pairs.sorted { $0.1 < $1.1 } var dp = [Int](repeating: INF, count: n+1) var best = INF for i instride(from: n, to: -1, by: -1) { if pairs[i].1 >= n { dp[i] = 1 } for j in i+1..<n+1 { if pairs[i].1 >= pairs[j].0 { dp[i] = min(dp[i], dp[j]+1) } } if pairs[i].0 <= 0 { best = min(best, dp[i]) } } return best == INF ? -1 : best }
funcminimumDistance(_ word: String) -> Int { let chars = Array(word) let table = Array("abcdefghijklmnopqrstuvwxyz".uppercased()) var charDic = [Character: Int]() for i in table.indices { charDic[table[i]] = i }
var dp = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 0, count: 301), count: 27), count: 27) funccost(_ from: Int, _ to: Int) -> Int { if from == 26 { return0 } returnabs(from/6 - to/6) + abs(from%6 - to%6) }
funcdistance(_ pos: Int, _left: Int, _right: Int) -> Int { if pos >= word.count { return0 } if dp[left][right][pos] == 0 { let to = charDic[chars[pos]]! dp[left][right][pos] = min(cost(left, to) + distance(pos + 1, to, right), cost(right, to) + distance(pos + 1, left, to)) } return dp[left][right][pos]
funcwatchedVideosByFriends(_ watchedVideos: [[String]], _ friends: [[Int]], _ id: Int, _ level: Int) -> [String] { var seen = Set<Int>([id]) var queue = [(id, 0)] var dstFriends = Set<Int>() while !queue.isEmpty { let (node, d) = queue.removeFirst() if d > level { break } if d == level {dstFriends.insert(node) } for nei in friends[node] where !seen.contains(nei) { seen.insert(nei) queue.append((nei, d+1)) } }
var dic = [String: Int]() for node in dstFriends { for video in watchedVideos[node] { dic[video, default: 0] += 1 } } let videos = Array(dic.keys) return videos.sorted { if dic[$0]! == dic[$1]! { return $0 < $1 } return dic[$0]! < dic[$1]! } }
