客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand. Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed. Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output -1. Examples: Note:
回忆一下祖玛游戏。现在桌上有一串球，颜色有红色(R)，黄色(Y)，蓝色(B)，绿色(G)，还有白色(W)。 现在你手里也有几个球。 每一次，你可以从手里的球选一个，然后把这个球插入到一串球中的某个位置上（包括最左端，最右端）。接着，如果有出现三个或者三个以上颜色相同的球相连的话，就把它们移除掉。重复这一步骤直到桌上所有的球都被移除。 找到插入并可以移除掉桌上所有球所需的最少的球数。如果不能移除桌上所有的球，输出 -1 。 示例: 输入: "WRRBBW", "RB" 输出: -1 解释: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW （翻译者标注：手上球已经用完，桌上还剩两个球无法消除，返回-1） 输入: "WWRRBBWW", "WRBRW" 输出: 2 解释: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty 输入:"G", "GGGGG" 输出: 2 解释: G -> G[G] -> GG[G] -> empty 输入: "RBYYBBRRB", "YRBGB" 输出: 3 解释: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty 标注:
1004 ms
Memory Usage: 4 MB
1 class Solution { 2 func findMinStep(_ board: String, _ hand: String) -> Int { 3 var res:Int = Int.max 4 var s:Set<Character> = Set<Character>() 5 for i in 0..<hand.count 6 { 7 if s.contains(hand[i]) {continue} 8 s.insert(hand[i]) 9 for j in 0..<board.count 10 { 11 if board[j] != hand[i] {continue} 12 var newBoard = board 13 var newHand = hand 14 let index1 = newBoard.index(newBoard.startIndex, offsetBy: j) 15 newBoard.insert(hand[i],at:index1) 16 newBoard = removeConsecutive(newBoard) 17 if newBoard.count == 0 {return 1} 18 let index2 = newHand.index(newHand.startIndex, offsetBy: i) 19 newHand.remove(at:index2) 20 var cnt:Int = findMinStep(newBoard, newHand) 21 if cnt != -1 22 { 23 res = min(res, cnt + 1) 24 } 25 } 26 } 27 return res == Int.max ? -1 : res 28 } 29 30 func removeConsecutive(_ board:String) -> String 31 { 32 var j:Int = 0 33 for i in 0...board.count 34 { 35 if i < board.count && board[i] == board[j] {continue} 36 if i - j >= 3 {return removeConsecutive(board.subString(0, j) + board.subString(i))} 37 else{j = i} 38 } 39 return board 40 } 41 } 42 43 extension String { 44 //subscript函数可以检索数组中的值 45 //直接按照索引方式截取指定索引的字符 46 subscript (_ i: Int) -> Character { 47 //读取字符 48 get {return self[index(startIndex, offsetBy: i)]} 49 } 50 51 // 截取字符串：指定索引和字符数 52 // - begin: 开始截取处索引 53 // - count: 截取的字符数量 54 func subString(_ begin:Int,_ count:Int) -> String { 55 let start = self.index(self.startIndex, offsetBy: max(0, begin)) 56 let end = self.index(self.startIndex, offsetBy: min(self.count, begin + count)) 57 return String(self[start..<end]) 58 } 59 60 // 截取字符串：从index到结束处 61 // - Parameter index: 开始索引 62 // - Returns: 子字符串 63 func subString(_ index: Int) -> String { 64 let theIndex = self.index(self.endIndex, offsetBy: index - self.count) 65 return String(self[theIndex..<endIndex]) 66 } 67 }
|
请发表评论