中级农民
- 积分
- 121
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2014-4-11
- 最后登录
- 1970-1-1
|
Day3
突然刷到一道hard(虽然一年前做过(但还是花了好久
首先是daily challenge,读着题目觉得搞biology不会写代码也不行啊x
31. Next Permutation
感觉全排列好像是一道起码medium的DP题,不过这道题不是全排列那就——
先进行了人工思考,如果给出我一组数我怎么用初等数学给出下一个排序
方法就是从后往前找第一组增序的,因为如果全部降序,那就是最大排序了那我们就可以快乐swap给出最小排序
找到增序的item以后(index=i),需要从i+1---end里找一个比它大的数,这里就得有内循环了,所以我觉得也许还能优化,
找到了比它大的数index=j就和index=i交换,也就是把index=j的值放在了index=i的位置上,然后i+1---end需要给出最小排序,所以交换只是为了把index=i的那个数放进来进行排序,
因为之前找index=i的时候就确认了i+1---end都是降序的,所以并不需要nlog(n)排序,只需要首位swap就行
所以时间复杂度应该是O(n)找增序,O(n)找要替换的j,O(n)进行swap,所以整体还是O(n)的
因为有重复的数字,所以要确保swap i和j之后依然是降序就要把寻找j的评判条件放宽到>=
(就搞得很复杂这个逻辑(但我也没看答案因为速度够快了x
33. Search in Rotated Sorted Array
第一反应,我loop一下不就行了嘛O(n)我也很快落x
所以是binary search,binary search我一直不太擅长判断边界,所以我就偷懒每次判断mid的时候把left和right一起判断了。。。
rotate之后就是至少其中有一段是严格增序的
所以每次判断我就看左边是不是增,是的话我就看target会不会落在左边,是就去左边,否就去右边,
然后如果左边不是增,那就右边增,于是重复一下看会不会落在右边。
一开始只判断mid然后发现边界会出状况于是我一股脑全判断了!
121. Best Time to Buy and Sell Stock
很紧张总觉得要DP,但又写着easy
结果发现就往后scan就行,记录一下当前最小的price,每次要么更新profit,要么更新最小price,就还挺直观
42. Trapping Rain Water
是hard题!我有印象我做过然后这这样样想起来是left view和right view
主要是判断两个view互相间是怎么判断能不能灌水,以及取并取差还是怎样
所以结果是取交集
写了有点久——
好啦休息一下 |
|