4Sum @ LeetCode (Python)
先对num排序, 然后建一个dictionary d, d[num[p]+num[q]] = [(p,q) pairs 满足num[p] + num[q]], 而且这里的(p,q) pair总是满足p < q。然后用二层循环来搜, num[i]是四元组最小的数, num[j]是第二小的数, 判断d中有没有target - num[i] - num[j]这个key的时间是O(1), 如果有这个key, 就把找到的四元组加入最后的返回结果。res使用set()来去重, 否则对于输入[-3,-2,-1,0,0,1,2,3], 0会出现两个[-3, 0, 1, 2]和两个[-2, -1, 0, 3]。
First sort num, then build a dictionary d, d[num[p]+num[q]] = [(p,q) pairs which satisfy num[p] + num[q]], here all (p,q) pairs satisfy p < q. Then use a nested for-loop to search, num[i] is the min number in quadruplet and num[j] is the second min number. The time complexity of checking whether d has the key target - num[i] - num[j] is O(1). If this key exists, add one quadruplet to the result. Use set() to remove duplicates in res, otherwise for input [-3,-2,-1,0,0,1,2,3], 0 there will be two [-3, 0, 1, 2] and two [-2, -1, 0, 3].
class Solution:
# @return a list of lists of length 4, [[val1,val2,val3,val4]]
def fourSum(self, num, target):
numLen, res, d = len(num), set(), {}
if numLen < 4: return []
num.sort()
for p in xrange(numLen):
for q in xrange(p + 1, numLen):
if num[p] + num[q] not in d:
d[ num[p] + num[q] ] = [(p,q)]
else:
d[ num[p] + num[q] ].append( (p,q) )
for i in xrange(numLen):
for j in xrange(i + 1, numLen - 2):
T = target - num[i] - num[j]
if T in d:
for k in d[T]:
if k[0] > j: res.add( ( num[i], num[j], num[k[0]], num[k[1]] ) )
return [ list(i) for i in res ]
2014年4月24日 02:03
牛逼啊，我就剩一道word ladder ii了。看来这个4sum果然还是要用hash啊。题的原意可能就是要求用hash的，直接O(n^3)应该不是原题的意思。
2014年4月24日 02:09
@zuoyuan: 可能吧，我用O(n^3)过不了，你做的好快呀
2014年4月24日 02:11
@zuoyuan: word ladder ii 我也是一直没过, 不知道有什么好的思路
2014年4月24日 02:45
各种参考你的解答，也断断续续做了两个月，一点也不快啊，呵呵。
2014年5月05日 02:32
@kitt: 参考你word ladder的代码，险过word ladder ii，应该还可以优化
@zuoyuan
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dict):
lst = []#存end的前驱单词
queue1 = [start]#存当前要遍历的单词
queue2 = []#和queue1作比较，用来判断end可不可达
ddd = {}#存路径上所有单词的前驱单词，键是单词，值是前驱单词的列表
flag = True
dddict={}.fromkeys(dict)
if start in dddict:
del dddict[start]
if end in dddict:
del dddict[end]
while flag:
for pre in queue1 :
for i in xrange(len(pre)):
part1 = pre[:i]
part2 = pre[i+1:]
for j in 'abcdefghijklmnopqrstuvwxyz':
if pre[i] != j:
nextWord = part1 + j + part2
if nextWord == end:
if pre not in lst:
lst.append(pre)
else:
if nextWord in dddict:
if nextWord in ddd:
ddd[nextWord].append(pre)
else:ddd[nextWord] = [pre]
if nextWord not in queue2:
queue2.append(nextWord)
for tt in queue2:
del dddict[tt]
if len(lst)!=0:#最短路径在lst非0时出现
flag=False
if queue1==queue2:
return []
queue1 = queue2
queue2 = []
Solution.ret = []
for k in lst:#从end的前驱单词开始找路径
self.visit(k,[end],start,ddd)
return Solution.ret
def visit(self,root,onepath,start,d):
if root ==start:
onepath.append(root)
onepath.reverse()
Solution.ret.append(onepath)
elif root is not None:
onepath.append(root)
for x in d[root]:
self.visit(x,onepath[:],start,d)
return
2014年5月09日 04:27
http://www.cnblogs.com/zuoyuan/p/3697045.html
@cold: 我的代码供参考。
2022年9月16日 10:03
Session 2 of the Course is called Term 2, and the Class 2nd Standard students who prepared for their examination tests can download the NCERT 2nd Term Question Paper 2023 Pdf with Answers for all Languages and Subjects of the Course. Every Central Board and other Schools have conducted their examination tests as per the revised syllabus and curriculum designed and published by NCERT.NCERT Term 2 Sample Paper Class 2 Every year the NCERT has published the study and learning material for every 2nd class student studying at all locations of the country for both SA-2, FA3, FA-4 and Assignment exams to Hindi mediu.
2022年9月17日 13:21
All Andhra Pradesh State Class 10th (SSC) Students can download AP SSC Science model paper 2023 with Answer solutions in Chapter by Chapter for Physical Science, Chemistry, Biological Science and Environmental science for AP SSC Science Model Paper 2023 examination test for Unit Test-1, Unit Test-2, AP 10th General Science Question Paper Unit Test-3, Unit Test-4, and Quarterly, Half Yearly, Pre-Final with Annual final examination tests 2023. The Andhra Pradesh State Board of Secondary Education has published the General Science model paper with study material with practice paper with mock test question bank as AP 10th Biology, PS, Chemistry Model Paper 2023 for all examination tests conducted by BSEAP.