程序员的自我修养
Home » Java语言 » LeetCode编程练习(2)

LeetCode编程练习(2)

7条评论9,552次浏览

Max Points on a Line

题目

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

答案

思路:时间复杂度O(n^3)的情况下是肯定可以算出结果的,那么意味着通过空间换时间应该是可以让时间复杂度达到O(n^2),这是我自己发明的定律。首先定义静态内部类Line,用于表示两点计算出来的直线,考虑到Double类型的精度损失问题,Line采用三个属性来保证精度上的完整性。然后重写hashCode()equals(..)方法,使得同一条直线相等,且在Hash值上相等。如此通过2个 \(n(n-1)\over 2\) 次循环即可获取到结果,时间复杂度为O(n^2)。

Trapping Rain Water

题目

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
rainwatertrap

答案

思路:若在最尾端添加一个无限高的bar,则整个题目变的十分容易:由于最后一个bar是无限高的,所以盛下水后的形状就是一个梯度上升的阶梯状,只需要扫面一遍,遇到比当前最大值小的则表示可以盛下水。现在的问题是,没有这么一块无限高的bar,那怎么办?很简单,扫面一遍,找出最高的bar,然后以此为分界线,看成是2个带有无限高bar的阶梯状就OK了。

Word Break II

题目

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given

s = "catsanddog",

dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

答案

思路:没有思路,递归+一个Stack就可以了。时间复杂度,应该是O(n^2)?

吐槽:采用前序遍历+深度优先方式会出现Time Limit Exceeded,原因是有一个测试用例是:"aaaaaaaaaaa..aaab",["a","aa","aaa","aaaa",...,"aaaaaaaaaa"]。所以采用前序深度遍历会出现超时。采用后续是不是则不会遇到这个问题?必须不是,只是刚好没有类似"baaaaaaaaaaa..aaa",["a","aa","aaa","aaaa",...,"aaaaaaaaaa"]这样的测试用例而已。

那么问题来了:要是有这样的用例该怎么办?(吐槽能让你吐出好程序么。。)

(转载本站文章请注明作者和出处 程序员的自我修养 – SelfUp.cn ,请勿用于任何商业用途)
分类:Java语言
标签:,
7条评论
  1. ashley说道:

    இдஇ #求何总添加留言表情#

    • Vina说道:

      Voor je lijf, niet je gezicht! Deze scrub is juist zo mild dat je hem elke dag kunt gebruiken. Niet dat ik dagelijks scrub, want mijn douche staat te vol met allemaal fijne dopuueschllen ;)De tube bevat 200 ml, minder klein dan ie lijkt dus :)

发表评论


profile
  • 文章总数:79篇
  • 评论总数:331条
  • 分类总数:31个
  • 标签总数:44个
  • 运行时间:1072天

大家好,欢迎来到selfup.cn。

这不是一个只谈技术的博客,这里记录我成长的点点滴滴,coding、riding and everthing!

最新评论
  • 增达网: 受教了!呵呵!
  • Anonymous: :!: :smile: :oops: :grin: :eek: :shock:
  • 27: :razz: dsa会报错,rsa不会
  • Anonymous: 看错了 忽略我
  • Anonymous: UserSideCF这个类在哪里
  • 晴子: 在主节点初始化CM5数据库的时候报错误:Verifying that we can write to /opt/cm-5.9.0/etc/cloudera-scm -server log4j:ERROR Could not...
  • zhangnew: 就4题 :?:
  • linxh: “ 但要是遇到预先并不知道数组的长度而又需要获取正确的(或者称之 为原始的)split长度时,该如何处理呢。。? ” 印象中可以split函数参数传-1?
  • linxh: 班门弄斧一下: ssh host cmd 和直接ssh上后cmd结果不一样是因为ssh直接运行远程命令 是非交互非登录模式与ssh上去得到一个登录交互式Shell二 者加载的环境变量不一样。
  • 匿名: 其实文本分类和数字分类是一样的,只是文本分类需要多一个步骤, 就是计算它的tf-idf值将其转换为double类型
  • yurnom: 可能苹果最近又改变了返回值吧,最近没做测试了。 BadDeviceToken一般测试环境和正式环境弄错的情况 下会出现。
  • Anonymous: :razz: 博主,良心贴啊, 最近也在弄apns推送。 有个问题想请教你一下啊。 你博客中写的 Unregistered 错误,有准确的说明吗, 我看你博客中写的:...
  • 一波清泉: 回复邮箱: 1004161699@qq.com 多谢
  • Anonymous: 17/02/09 01:15:02 WARN Utils: Service ‘SparkUI’ could not bind on port 4040. Attempting port...
  • pacificLee: :twisted:
  • 小码: 为什么没有后面的呢,只有前10个
  • Anonymous: :lol:
  • Anonymous: :razz: 楼主是属于会聊天的。 我想问,sqoop发了几个版本了,应该没这些问题了吧。
  • Anonymous: Config.kafkaConfig.kafkaGroupI d 这个是指自己配置的group id 还是从 import org.apache.kafka.common.config .Config 这个类...
  • Anonymous: ZkUtils.getPartitionsForTopics (zkClient, Config.kafkaConfig.topic) 那个方法是在 spark-streaming_2.10 中 kafka...