本文主要是介绍【leetcode系列】【算法】第 185 场周赛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目一:重新格式化字符串
题目链接: https://leetcode-cn.com/problems/reformat-the-string/
解题思路:
先遍历字符串,把字母和数字分开保存在两个容器中
从数目比较多的开始交替遍历拼接字符串
如果最后少的已经用完了,多的还有剩余,则表示无法重新格式化,返回空字符串
代码实现:
class Solution:def reformat(self, s: str) -> str:rec = collections.defaultdict(list)lst1 = 'qwertyuiopasdfghjklzxcvbnm'lst2 = '1234567890'for a in s:if a in lst1:rec['a'].append(a)else:rec['b'].append(a)if len(rec['a']) < len(rec['b']):rec['a'], rec['b'] = rec['b'][:], rec['a'][:]res = ''while 0 < len(rec):if 0 == len(rec['a']):if 0 != len(rec['b']):return ''return resres += rec['a'][-1]rec['a'].pop()if 0 == len(rec['b']):if 0 != len(rec['a']):return ''return resres += rec['b'][-1]rec['b'].pop()return ''
题目二:点菜展示表
题目链接: https://leetcode-cn.com/problems/display-table-of-food-orders-in-a-restaurant/
解题思路:
先遍历订单,合并同一桌的所有菜,同时保存所有点过的菜
然后将所有点过的菜名排序,并对排序后的桌号进行遍历拼接对应菜品的个数
代码实现:
class Solution:def displayTable(self, orders: List[List[str]]) -> List[List[str]]:rec = collections.defaultdict(list)food_lst = set()for content in orders:rec[int(content[1])].append(content[2])food_lst.add(content[2])food_lst = list(food_lst)food_lst.sort()res = [['Table'] + food_lst]for table_id in sorted(rec.keys()):curr_content = [str(table_id)]for food in food_lst:curr_content.append(str(rec[table_id].count(food)))res.append(curr_content)return res
题目三:数青蛙
题目链接: https://leetcode-cn.com/problems/minimum-number-of-frogs-croaking/
解题思路:
添加一个变量保存喊完一次的青蛙个数
如果没有青蛙的声音结束,则来新的c时,新增青蛙个数
否则,更新已经喊完的青蛙个数 - 1,继续遍历
代码实现:
class Solution:def minNumberOfFrogs(self, croakOfFrogs: str) -> int:num = 0finish_num = 0last_word_tab = {'r' : 'c', 'o' : 'r', 'a' : 'o', 'k' : 'a'}res = {'c' : 0, 'r' : 0, 'o' : 0, 'a' : 0, 'k' : 0}for word in croakOfFrogs:if word == 'c':if finish_num <= 0:num += 1else:finish_num -= 1is_add_new = Trueres['c'] += 1continueelif word == 'k':if res['a'] > 0:res['a'] -= 1finish_num += 1continueelse:return -1res[last_word_tab[word]] -= 1res[word] += 1if res[last_word_tab[word]] < 0:return -1if sum(res.values()) > 0:return -1return num
题目四:
题目链接: https://leetcode-cn.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/
解题思路:
三维动态规划,没做出来,详细看大神的题解
代码实现:
class Solution:def numOfArrays(self, n: int, m: int, k: int) -> int:if k == 0:return 0dp = [[[0] * (m) for _ in range(k + 1)] for __ in range(n)]dp[0][1] = [1] * mfor i in range(1, n):for j in range(1, k + 1):for p in range(m):dp[i][j][p] = sum(dp[i - 1][j - 1][: p]) + dp[i - 1][j][p] * (p + 1)dp[i][j][p] %= 1e9+7return int(sum(dp[-1][-1])%(1e9+7))作者:coldme-2
链接:https://leetcode-cn.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/solution/jian-dan-san-wei-dong-tai-gui-hua-by-coldme-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
这篇关于【leetcode系列】【算法】第 185 场周赛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!