Coursera 两道题版本的OA

segment这题应该可以O(N)解决，遍历number，用deque存升序number的index（当前number <=deque.back()的时候就pop_back（）），同时要从deque的front开始deque中所存index的值小于  i - x (当前index- window size)的都pop掉， 保证deque中只有当前window。 deque的front存的就是segment中最小值。  当然这题只需要求最小值中的最大值， 可能还会有更简洁高效的办法。


补充内容 (2016-9-23 02:00):
JAVA的话只要任何一个可以进行头尾操作的container都可以

mymax2009 发表于 2016-9-23 01:39
segment这题应该可以O(N)解决，遍历number，用deque存升序number的index（当前number

嗯嗯 用queue做O(N)复杂度 ， 不过我的做法是pq里面存pair<nums[i],i> 然后做法和你一样啦

lovely number我想的算法复杂度是O(q) 每个区间是O(1).

Sorrow雨 发表于 2016-9-23 01:47
lovely number我想的算法复杂度是O(q) 每个区间是O(1).

可以share一下你的idea吗~同学

mymax2009 发表于 2016-9-22 09:58
可以share一下你的idea吗~同学

同求share，就是现在手上没有大米了。。

然后其实我想问的是  Ashley 这题， 121算不算是repeated digit number，还是要连续的？

mymax2009 发表于 2016-9-23 02:03
然后其实我想问的是  Ashley 这题， 121算不算是repeated digit number，还是要连续的？

121 应该是算repeated number的
我的思路是先计算1到m不重复的个数减去1到n-1的不重复个数
举个例子吧 比如说要算1-223中不重复的个数，先存1-9，10-99的不重复个数90个，当算到最高位2时，我们开始算100-199的个数，百位有1众取法“1”，十位9种，个位8种，就是72，接下来算200-219的个数，这时候用个vector保存已经用过的数字，十位有“0，1”两种取法，个位有8种，总共16种，220-223，有0个。关键就在于每次计算当前位数字取整减一不重复数字的个数。最后累加起来。每次计算一个数字的复杂度就是O(1)，因为m，n digit最多为5位。这是我的想法。

忆梦前尘 发表于 2016-9-23 02:02
同求share，就是现在手上没有大米了。。

我写了思路，可以讨论一下

Sorrow雨 发表于 2016-9-23 02:31
我写了思路，可以讨论一下

nice, 我开始想的有点复杂了，应该是这个排列组合的思路

lovely number 很像leetcode357.