【LeetCode】设计食物评分系统 Java 题解
题目描述
设计一个支持下述操作的食物评分系统:
修改 系统中列出的某种食物的评分。返回系统中某一类烹饪方式下评分最高的食物。实现 FoodRatings 类:
FoodRatings(String[] foods, String[] cuisines, int[] ratings) 初始化系统。食物由 foods、cuisines 和 ratings 描述,长度均为 n 。foods[i] 是第 i 种食物的名字。cuisines[i] 是第 i 种食物的烹饪方式。ratings[i] 是第 i 种食物的最初评分。void changeRating(String food, int newRating) 修改名字为 food 的食物的评分。String highestRated(String cuisine) 返回指定烹饪方式 cuisine 下评分最高的食物的名字。如果存在并列,返回 字典序较小 的名字。注意,字符串 x 的字典序比字符串 y 更小的前提是:x 在字典中出现的位置在 y 之前,也就是说,要么 x 是 y 的前缀,或者在满足 x[i] != y[i] 的第一个位置 i 处,x[i] 在字母表中出现的位置在 y[i] 之前。
思路分析
今天的的算法题目是设计类题目。题目描述比较长,我们跟着例子来理解。
题目给出的是食物,评分,烹饪方式。highestRated() 需要返回指定烹饪方式 cuisine 下评分最高的食物的名字。如果存在并列,返回 字典序较小 的名字。根据这个要求分析,这里需要实现一个多纬度排序的功能。在 Java 中 TreeSet 类提供了使用树进行存储的 Set 接口的实现。对象按排序和升序存储。访问和检索时间非常快,这使得 TreeSet 成为存储必须快速找到的大量排序信息的绝佳选择。
我们自定义 FoodRate 类,存储 food,rate, cuisines 三个属性。方便在 TreeSet 中按照先 rate, 后 food 属性排序。定义 foodRateMap 存储对象关系。当调用 changeRating 方法的时候,评分变动,我们需要对 TreeSet 数据重新排序。先处理旧对象值的相关操作,然后在处理新对象的相关操作。保证数据的一致性。
具体实现代码如下,供参考。
通过代码
总结
在 Java 中排序,对于一般的纯数字,字符串排序,我们直接调用 sort() 系统函数即可, sort() 函数默认是自然排序。
当需要按照自然倒叙排列时候,在 sort() 中我们可以自定义 Comparator, Override compare() 方法实现排序。
当需要按照多个属性排序的时候,我们一般可以定义一个对象,包含需要排序的属性,然后自定义 Comparator,实现多属性纬度排序。比如:使用 TreeSet 这种数据结构,需要注意的是,当对象进行修改的时候,我们必须先删除旧的对象,然后在重新插入新的对象。
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/b4f3a7d34ca9642850ec6a49f】。文章转载请联系作者。
评论