中级农民
- 积分
- 121
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2014-4-11
- 最后登录
- 1970-1-1
|
本帖最后由 snowymo 于 2020-10-16 15:20 编辑
Day 1
今天刷了点高频的数组题,正好都是简单的,简单的题有的时候容易想很多,比如我的算法会不会太复杂了,或者我怎么还没有立刻想出答案来。。。
在我看来,数组题,字符串题,这类的题根本没有类型,不像DP啊Tree啊你立刻知道套用什么样的思路了,可能还是手生叭
一共刷了四个题
No.55 Max SubArray
我可能最近算和算多了,所以觉得如果要计算连续子序列的和就应该用sum[k]-sum[j]来表示
于是我的想法很直接 一个pointer指着开始 表示最小的sum[j],一个pointer向后移动,每次都计算一下当前element对于当前sum[j]的差,这个差也就是当前的子序列和,如果比现存的大就更新,
如果当前的sum勇创新低,那就以此更新sum[j]
——就感觉想得有点复杂但是逻辑没错
然后看了看别人的解法,是一种DP思路:
包含当前元素的最大子序列和memo[k]:要么就是元素本身nums[k](说明之前的和加起来为负),要么就是与之前的和连接起来nums[k]+memo[k-1](说明之前的和为正)
然后再比较当前结果memo[k]与现存的结果哪个大
——果然DP无处不在
No.88 Merge Sorted Array
首先是naive操作,就是得多占S(n) = O(n)的空间,虽然题目没有明说in-place操作,但实际上应该从in-place操作来考虑
然后我想了方法就是先把nums2的内容append到nums1之后,然后两个指针向后移动,<就移动,>就交换元素,结果发现这样并不能保证完全升序
(所以我看了discussion,原来in-place操作是从后往前的
于是再写了一下,其实这样就相当于nums1变成了一个全新的vector,因为每次赋值的位置都是不含有有效数值的位置,有意思
No.27 remove element
就感觉很简单不过也没有一次写对
想法就是2 pointer,一头一尾,如果尾巴是,就往前移,如果头是,就和尾巴换,因为这里的尾巴已经移动过了所以肯定不是,因此这时候头也可以安心地向后移。
下标出界搞了好一会(
感觉这个想法太跳脱了但不想看人家的解法了!
No.674 Longest Continuous Increasing Subsequence
一开始以为是非连续子串,还在思考怎么从O(N^2)降到O(N)
然后发现要求连续,于是我就走一遍遍历,如果发现增长就快乐+1,如果比现存的LCIS要长就更新为当前值;如果没有严格增长那就reset回1,然后继续呀继续
看到其他地方有变形题目为从左增长或者从右增长;懒得写了,一种就是走两遍,2-pass。一种就是多一倍变量记录从左的或者从右的就行
噶油 争取每天都刷点保持手感 |
|