一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1739|回复: 40
收起左侧

[算法题] 请教4道题目的最优做法(G家真题)

[复制链接] |试试Instant~ |关注本帖
孤笑客 发表于 2015-10-29 22:13:24 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 孤笑客 于 2015-10-30 10:09 编辑

随便提供一些思路也好。先谢谢各位了!
1.  Given an array of elements, return an array of values pertaining to how
many elements are greater than that element remaining in the array.

Ex. [3,4,5,9,2,1, 3], return [3, 2, 1, 0, 1, 1, 0]
First element is 3 because 3<4,5,9. Second element is 2 because 4< 5,9 etc

2.  Given a string which only contains lowercase. You need delete the
repeated letters only leave one, and try to make the lexicographical order
of new string is smallest.
Ex. bcabc
Delete the first 'b' and first 'c', the new string will be abc which is
smallest.

3.  Given 2 large number A and B, create a new number C using the digits
from A which needs to be grater than B. (修正: 应该增加一个条件,C越小越好。不然太简单了。你懂的。)
e.g. A = 5281, B = 7443
C = 8125.

4.  Given an integer:N and an array int arr[], you have to add some
elements to the array so that you can generate from 1 to N by using
(add) the elements in the array.

Please keep in mind that you can only use each element in the array once
when generating a certain x (1<=x<=N). Return the count of the least adding
numbers.

For example:
N=6, arr = [1, 3]
1 is already in arr.
add 2 to the arr.
3 is already in arr
4 = 1 + 3
5 = 2 + 3
6 = 1 + 2 + 3
So we return 1 since we only need to add one element which is 2.

评分

2

查看全部评分

本帖被以下淘专辑推荐:

readman 发表于 2015-10-30 01:01:26 | 显示全部楼层
z928czzc 发表于 2015-10-30 00:59
第一题只是排序的某种变形。Partial heap sort就能解决。

第二题比较interesting,想了几分钟,答案如下 ...

第二题我咋觉得即使boolean count[26] 看一下有几个出现过, 然后扫一下string, 有就放上去...
回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-10-30 00:00:07 | 显示全部楼层
比如第1题你可以这样:从后向前扫,每扫一个元素p就将其插入一个平衡二叉树T中,同时找到此时它在T中的位置。这可以在O(logN)时间内做到,所以最后的时间复杂度是O(NlogN)。

如无其他限制,这就是此题的最优时间复杂度。理由是:假如我现在有一个O(N)的算法A能找到“每个元素P之后大于P的元素个数”,那么我就也能很简单地找到一个“每个元素P之前大于P的元素个数”的O(N)解法A'(只要把数组逆转,再调用A,再将结果逆转回来即可)。那么,对任何数组,我只要对其先应用算法A,再应用算法A',然后将两者得到的结果相应元素相加,我就得到了“每个元素P之前和之后大于P的元素数目”,也就是“P的逆序下标”。换言之,我们就得到了一个O(N)的能够对任意数组排序的算法。这是不可能的,因此,算法A的最低复杂度不可能小于O(NlogN)。
回复 支持 反对

使用道具 举报

dwl1222 发表于 2015-10-30 00:19:41 | 显示全部楼层
stellari 发表于 2015-10-30 00:00
比如第1题你可以这样:从后向前扫,每扫一个元素p就将其插入一个平衡二叉树T中,同时找到此时它在T中的位置 ...

是说BST吗。insert的时候怎么保证Balance
回复 支持 反对

使用道具 举报

dwl1222 发表于 2015-10-30 00:26:50 | 显示全部楼层
stellari 发表于 2015-10-30 00:00
比如第1题你可以这样:从后向前扫,每扫一个元素p就将其插入一个平衡二叉树T中,同时找到此时它在T中的位置 ...

直接用一个sorted arraylist存可以把。search logN insert logN
回复 支持 反对

使用道具 举报

ryancooper 发表于 2015-10-30 00:47:25 | 显示全部楼层
dwl1222 发表于 2015-10-30 00:26
直接用一个sorted arraylist存可以把。search logN insert logN

No. Insert是O(N)的
回复 支持 反对

使用道具 举报

ryancooper 发表于 2015-10-30 00:48:41 | 显示全部楼层
dwl1222 发表于 2015-10-30 00:19
是说BST吗。insert的时候怎么保证Balance

手写Balanced BST的话,比较好写的可以试试Treap。这题也可以用BIT来存,相对代码更简单
回复 支持 反对

使用道具 举报

ryancooper 发表于 2015-10-30 00:48:50 | 显示全部楼层
dwl1222 发表于 2015-10-30 00:19
是说BST吗。insert的时候怎么保证Balance

手写Balanced BST的话,比较好写的可以试试Treap。这题也可以用BIT来存,相对代码更简单
回复 支持 反对

使用道具 举报

readman 发表于 2015-10-30 00:58:55 | 显示全部楼层
stellari 发表于 2015-10-30 00:00
比如第1题你可以这样:从后向前扫,每扫一个元素p就将其插入一个平衡二叉树T中,同时找到此时它在T中的位置 ...

- - 证的好啊..
其实想想, 如果有o(n), 那么rank(p)就是o(n)....quick select 就是o(n)...
回复 支持 反对

使用道具 举报

z928czzc 发表于 2015-10-30 00:59:09 | 显示全部楼层
本帖最后由 z928czzc 于 2015-10-30 01:03 编辑

第一题只是排序的某种变形。Partial heap sort就能解决。

第二题比较interesting,想了几分钟,答案如下:
先scan一遍这个string,用一个map记录一下每种character出现次数。
对于bcabc,a出现一次,b出现两次,c出现两次。
然后开始扫描,用删除的可行性来定位第一个元素。显然第一个元素要越小越好:
for(int i=0, i<string.size();i++) // 从头扫描。
  if(delete all characters from 0 to i is feasible) // 根据记录的map,确定删除0到i的元素是否可行。
    record the current smallest character // 这个character就是new string的第一个元素。
对于bcabc这个例子,可以发现删除前三个元素都是可行的,其中a是最小元素。
之后,将发现的最小的可删除元素之前的所有character删除,把它的之后的replication也删除。
比如bcabcdabc,删除第一个a之前的元素,删除之后重复的a,得到abcdbc
对于上面过程重复元素的个数的次数就好(对于bcdbc重复三次,因为还有bcd三个元素)。

第三题的问题描述不全。可以把A的digit按照大小重拍组成的数字即可。
A = 5281。其中8>5>2>1。所以新数字是8521就好(然后再比较B)。

第四题是codeforce problem。讨论见
http://www.careercup.com/question?id=5717521992777728
回复 支持 反对

使用道具 举报

ryancooper 发表于 2015-10-30 01:01:52 | 显示全部楼层
对于第4题,要是全部输入的都是正整数的话,应该有个线性的算法
回复 支持 反对

使用道具 举报

z928czzc 发表于 2015-10-30 01:05:24 | 显示全部楼层
本帖最后由 z928czzc 于 2015-10-30 01:06 编辑
readman 发表于 2015-10-30 01:01
第二题我咋觉得即使boolean count[26] 看一下有几个出现过, 然后扫一下string, 有就放上去...


无法保证order。

对于例子bcacb。算法结果是bac。然而你会产生abc或者bca。
回复 支持 反对

使用道具 举报

readman 发表于 2015-10-30 01:08:16 | 显示全部楼层
z928czzc 发表于 2015-10-30 01:05
无法保证order。

对于例子bcab。算法结果是bca。然而你会产生abc。

- - 我没说清楚. 第二次扫数组的时候, 是看当前char是否应该保留. 保留了需要update count[].
回复 支持 反对

使用道具 举报

z928czzc 发表于 2015-10-30 01:11:21 | 显示全部楼层
readman 发表于 2015-10-30 01:08
- - 我没说清楚. 第二次扫数组的时候, 是看当前char是否应该保留. 保留了需要update count[].

对于例子bcacb。算法结果是bac。其中b是保留第一个b,而c是保留第二个c。你无法区分保留与否。
回复 支持 反对

使用道具 举报

z928czzc 发表于 2015-10-30 01:12:37 | 显示全部楼层
readman 发表于 2015-10-30 01:08
- - 我没说清楚. 第二次扫数组的时候, 是看当前char是否应该保留. 保留了需要update count[].

例子错了。。。等等。。。
回复 支持 反对

使用道具 举报

z928czzc 发表于 2015-10-30 01:14:19 | 显示全部楼层
readman 发表于 2015-10-30 01:08
- - 我没说清楚. 第二次扫数组的时候, 是看当前char是否应该保留. 保留了需要update count[].

你无法区分保留的顺序。

对于cabac。结果是abc。但是a是保留第一个,c是保留第二个。
回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-10-30 01:41:28 | 显示全部楼层
z928czzc 发表于 2015-10-30 00:59
第一题只是排序的某种变形。Partial heap sort就能解决。

第二题比较interesting,想了几分钟,答案如下 ...

第二题用这个思路怎么样?
从后往前扫描string,同时保存当前出现的最小valid string。比如bcabc,从后往前扫描出来的顺序就是下面这样的:c->bc->abc->abc->abc。如果是abcab,顺序就是b->ab->cab->bca->abc

回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-10-30 01:43:33 | 显示全部楼层
gorilazz 发表于 2015-10-30 01:41
第二题用这个思路怎么样?
从后往前扫描string,同时保存当前出现的最小valid string。比如bcabc,从后 ...

class Solution:

    def minValid(self, s):
        appeared = {}
        top = None
        for i in range(len(s)-1, -1, -1):
            if not s in appeared:
                appeared[s] = i
                top = s
            else:
                if ord(s)<ord(top):
                    appeared[s] = i
                    top = s
        buf = []
        for c in appeared:
            buf.append((appeared[c], c))
        buf.sort()
        result = "".join([item[1] for item in buf])
        return result
        
sol = Solution()
result = sol.minValid("bcabc")
print(result)
回复 支持 反对

使用道具 举报

z928czzc 发表于 2015-10-30 02:15:25 | 显示全部楼层
本帖最后由 z928czzc 于 2015-10-30 02:16 编辑
gorilazz 发表于 2015-10-30 01:41
第二题用这个思路怎么样?
从后往前扫描string,同时保存当前出现的最小valid string。比如bcabc,从后 ...


无法保存和更新当前出现的最小valid string (or need exponential time)?在当前index的最小valid string可能和前后index的最小valid string没有任何关系。

举个反例还挺麻烦的。。。应该是 acbdefafedcb
你如何从afedcb切换到acbdef的???

回复 支持 反对

使用道具 举报

CrowSquad 发表于 2015-10-30 02:19:14 | 显示全部楼层
第一题用线段树啊!多好的东西啊!树状数组也行,实现起来还更方便。。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 02:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表