[已解决]Python：每日一题 304

Croper · 发表于 2020-1-13 00:03:31

阴阳神万物主发表于 2020-1-13 00:01
这样还有不对的吗，我这小脑瓜还是太嫩了

输入[2,1,5],预期结果是1对，输出2对。。

Croper · 发表于 2020-1-13 00:09:24

Croper 发表于 2020-1-13 00:03
输入[2,1,5],预期结果是1对，输出2对。。

你把这一段拿去自己试试呗：

from random import randint
def solve2(lst:'list of int',rep=False)->int:
res = 0
temp = sorted(lst) if rep else sorted(set(lst))
for each in lst:
if each in temp[1:]:
res += temp.index(each)
temp.remove(each)
return res
def func304(l:list):
l2=[]
map={}
for i in l:
exist=False
p,q=0,len(l2)
while (p<q):
n=(p+q)//2
if (i==l2[n]):
exist=True
map[i]=n
break
if (l2[n]<i):
q=n
else:
p=n+1
if (not exist):
l2.insert(p,i)
map[i]=p
ret=0
for n in map.values():
ret+=n
return ret
for i in range(2000):
l=[randint(1,10) for _ in range(randint(i//100+2,i//50+2))]
ret1=solve2(l[:])
ret2=func304(l[:])
if (ret1!=ret2):
print()
print("error")
print(l)
print("your result=",ret1)
print("my result=",ret2)
break
if (i//50==0):
print(".",end="")
else:
print("correct!")

复制代码

阴阳神万物主 · 发表于 2020-1-13 00:23:07

本帖最后由阴阳神万物主于 2020-1-13 00:27 编辑

Croper 发表于 2020-1-13 00:09
你把这一段拿去自己试试呗：

我已经将能有的规律重新思考了一遍，无非就是全升、全降、升降升、降升降，所以这个应当对(思考状)

def solve2(lst:'list of int',rep=True)->int:
res = 0
temp = sorted(lst) if rep else sorted(set(lst))
for i in range(len(lst)):
each = lst[i]
if each in temp[1:]:
res += temp.index(each)
temp.remove(each)
elif each in temp[:1]:
if each not in lst[i+1:]:
temp.remove(each)
return res

复制代码

Stubborn · 发表于 2020-1-13 00:37:13

本帖最后由 Stubborn 于 2020-1-13 01:00 编辑

阴阳神万物主发表于 2020-1-13 00:23
我已经将能有的规律重新思考了一遍，无非就是全升、全降、升降升、降升降，所以这个应当对(思考状)

考虑下并归

# -*- coding: utf-8 -*-
# !/usr/bin/python3
"""
@ version: ??
@ author: Alex
@ file: Algorithm
@datetime: 2020/1/13 - 0:53
@explain:
"""
import random
from functools import wraps
import time
def thisTime(func):
@wraps(func)
def wrapper(funcc, count):
start = time.time()
print(f"{count} This result-> {func(funcc(count))}")
print(f"{count} This time -> {start - time.time()}")
return wrapper
def create_random(count):
"""Create random unordered data"""
data = list(range(count))
random.shuffle(data)
return data
def create_reversed(count):
"""Create reversed data"""
return list(range(count, 0, -1))
@thisTime
def func304(array:list):
"""归并"""
def merge(arr, left, mid, right, res):
"""合并"""
l,r,start = left, mid + 1, left
Array = [0 for _ in range(len(arr))]
while l <= mid and r <= right:
if arr[l] < arr[r]:Array[start],l,start = arr[l],l+1 , start+1
else:Array[start], r, start,res = arr[r], r+1, start +1, res + mid - l + 1
while l <= mid:Array[start],l, start = arr[l], l+1, start+1
while r <= right:Array[start], r, start = arr[r], r+1, start+1
for i in range(left, right + 1):arr[i] = Array[i]
return res
def sort(arr, left, right, res):
if left >= right: return res # 出口
mid = (left + right) >> 1
# 分
l = sort(arr, left, mid, res)
r = sort(arr, mid+1, right, res)
# 并
return merge(arr, left, mid, right, l + r)
return sort(array, 0, len(array)-1, 0)
func304(create_random, 1000)
func304(create_reversed, 1000)
func304(create_random, 5000)
func304(create_reversed, 5000)

复制代码

Unicorn# · 发表于 2020-1-13 00:48:03

来了
尝试归并

# -*- coding: utf-8 -*-
def solve(nums):
count = 0
def f(i, j):
if i == j or i == j-1:
return
nonlocal count, nums
sep = (i + j)//2
f(i, sep)
f(sep, j)
temp = []
x = i
y = sep
while x < sep and y < j:
if nums[x] > nums[y]:
temp.append(nums[x])
count += 1
x += 1
else:
temp.append(nums[y])
y += 1
for t in range(x, sep):
temp.append(nums[t])
for t in range(y, j):
temp.append(nums[t])
nums[i:j] = temp
f(0, len(nums))
return count

复制代码

Unicorn# · 发表于 2020-1-13 00:53:17

Stubborn 发表于 2020-1-13 00:37
考虑下并归

巧了，我第一反应也是归并
(毕竟这是归并的例题)

kinkon · 发表于 2020-1-13 08:33:47

这样会超时吗？

def fun304(n):
c, res = 0, []
while len(n) > 1:
res = n.pop(0)
for i in n:
if res > i:
c += 1
return c
if __name__ == '__main__':
print('示例1 输出：',fun304([2,4,1,3,5]))
print('示例2 输出：',fun304([1,2,3,4]))

复制代码

TJBEST · 发表于 2020-1-13 10:57:33

本帖最后由 TJBEST 于 2020-1-13 13:30 编辑

我这次一反常态，来了一个较短的代码，速度貌似还不慢

def fun304(arr):
if len(arr)< 2:
return 0
sortedList = sorted(arr)
result = 0
for each in arr:
index = sortedList.index(each)
result = result + index
del sortedList[index]
return result

复制代码

fan1993423 · 发表于 2020-1-13 12:57:41

阴阳神万物主发表于 2020-1-13 00:23
我已经将能有的规律重新思考了一遍，无非就是全升、全降、升降升、降升降，所以这个应当对(思考状)

我要求不重复的序列对哦,[5,1,1,5,1]结果应该是1

cxzmgs · 发表于 2020-1-13 14:46:01

厉害啊

kinkon · 发表于 2020-1-13 16:30:12

用迭代速度还可以吧

from itertools import combinations as c
def p304(n):
res, ct = [], 0
res.extend(list(c(n, 2)))
for i in res:
if i[0] > i[1]: ct += 1
return ct

复制代码

kinkon · 发表于 2020-1-13 16:39:40

TJBEST 发表于 2020-1-13 10:57
我这次一反常态，来了一个较短的代码，速度貌似还不慢

向前辈学习，速度真不错

阴阳神万物主 · 发表于 2020-1-13 17:25:02

本帖最后由阴阳神万物主于 2020-1-13 17:31 编辑

fan1993423 发表于 2020-1-13 12:57
我要求不重复的序列对哦,[5,1,1,5,1]结果应该是1

哦，那层楼没说，要把rep参数设置为False，我补充一下说明

def solve2(lst:'list of int',rep=True)->int:
'''
该函数的功能是：
统计并返回待查询列表中的逆序对总数
必要参数：
lst 为待查询列表。
可选参数：
rep 是一个布尔值，为是否需要统计重复的逆序对。
为真，则统计重复的；
为假，则不统计，
默认值为真。
'''
res = 0
temp = sorted(lst) if rep else sorted(set(lst))
for i in range(len(lst)):
each = lst[i]
if each in temp[1:]:
res += temp.index(each)
temp.remove(each)
elif each in temp[:1]:
if each not in lst[i+1:]:
temp.remove(each)
return res

复制代码

阴阳神万物主 · 发表于 2020-1-13 17:47:18

Stubborn 发表于 2020-1-13 00:37
考虑下并归

但是，归并的话，如何剔除重复的逆序对呢？记忆化搜索吗？

Stubborn · 发表于 2020-1-13 18:13:02

阴阳神万物主发表于 2020-1-13 17:47
但是，归并的话，如何剔除重复的逆序对呢？记忆化搜索吗？

题目有说要去重吗

阴阳神万物主 · 发表于 2020-1-13 18:58:11

Stubborn 发表于 2020-1-13 18:13
题目有说要去重吗

但我那一楼是在回复别人提的去重的拓展32楼
我对于本题的解法最后是在26楼

记忆的欠片 · 发表于 2020-1-13 19:54:43

def counter(arry):
count = 0
for i in arry:
      for j in arry[arry.index(i):]:
         if j < i:
            count += 1
return count

776667 · 发表于 2020-1-14 10:10:45

def fun304(x):
count = 0
for i in range(len(x)-1):
for j in range(len(x))[i+1:]:
if x[i] > x[j]:
count += 1
return count

复制代码

zltzlt · 发表于 2020-1-15 07:48:53

阴阳神万物主发表于 2020-1-12 23:37
看了看别人的出错数据，感觉这回稳

还是会超时，原因在于 temp.index(each)

zltzlt · 发表于 2020-1-15 07:51:16

阴阳神万物主发表于 2020-1-13 00:23
我已经将能有的规律重新思考了一遍，无非就是全升、全降、升降升、降升降，所以这个应当对(思考状)

超时

账号		自动登录	找回密码
密码			立即注册

[已解决]Python：每日一题 304

评分

评分

评分

评分

评分

评分

评分

评分