LeetCode Weekly Contest 18A

作者 QIFAN 日期 2017-02-06
LeetCode Weekly Contest 18A

一个半小时三道题。

第一题:500. KeyBoard Row

简单的,用三个字符串分别表示第一行第二行第三行,对每个单词遍历查找。注意大小写。

第二题:508. Most Frequency SubTree Sum

给定一个树,返回子树和出现次数最多的那些和。

我用一个 HashMap> ,以<子树和,节点值集合> 来表示键值对,先遍历一遍数把 map 建起来。然后遍历 map ,找到长度最长的和。时间复杂度 O(N) 。

第三题:502. IPO

LeetCode 准备上市要集资,可以投资 k 次,有一笔初始资金 W ,有两个数组分别代表项目成本和项目净利润,要求最后资金的最大值。每一次投资后都可以把净利润用于下一次投资。

我先把成本和利润重组一下成为一个二维数组 s ,s[i][0] 表示第 i 的项目的成本,s[i][1] 表示第 i 的项目的利润。
然后按成本对 s 排序。再用一个 priorityQueue 以利润倒序存入所有可投资的项目。每次先从上一次的位置遍历 S ,把所有成本小于当前资金的元素存入 PQ ,然后 pop 出利润最大的项目投资,直到投资了 k 个项目。


对自己来说,做的还算挺快的了,能够根据题目较快的想到对应的数据结构和比较时间复杂度,进步挺大。