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

zltzlt

今天的题目：

给定一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是 “优美子数组”。

返回这个数组中 “优美子数组” 的数目。

示例 1：

输入：nums = [1,1,2,1,1]，k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1]。

示例 2：

输入：nums = [2,4,6]，k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。

示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2]，k = 2
输出：16

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

TJBEST

2020-1-17 10:32:19

def fun307(nums , k):
    M = len(nums)
    jiIndexArr = [i for i in range(0,len(nums)) if nums[i]%2 ]
    N = len(jiIndexArr)
    if N < k:
        return 0
    elif N == k:
        return (jiIndexArr[0] + 1)*(M - jiIndexArr[N - 1])
    else:
        res = 0
        res += (jiIndexArr[0] + 1)*(jiIndexArr[k] - jiIndexArr[k - 1])
        for i in range(1,N - k):
            res += (jiIndexArr[i+k] - jiIndexArr[i+k-1])*(jiIndexArr[i] - jiIndexArr[i - 1])
        res += (jiIndexArr[N-k]-jiIndexArr[N-k-1])*(M - jiIndexArr[N - 1])
        return res

跳转到最佳答案楼层

Croper

def func307(l:list,k):
    l.append(1)
    l2=[]
    ret=0
    v=1
    for i in l:
        if i % 2==0:
            v+=1
            continue
        l2.append(v)
        v=1
        if (len(l2)<=k):
            continue
        ret+=l2[-1]*l2[0]
        l2.pop(0)
    return ret

塔利班

def f307(nums,k):
    res=0
    s=[-1]
    for i in range(len(nums)):
        if nums[i]%2:
            s.append(i)
    s+=[i+1]
    for i in range(1,len(s)-k):
        res += (s[i]-s[i-1])*(s[i+k]-s[i+k-1])
    return res

爱尔兰咖啡

list1=[2,2,2,1,2,2,1,2,2,2]
k=2
def f(x):
        lst0=[]
        while len(x)>0:
                for i in range(len(x)):
                        lst0.append(x[0:i+1])
                x=x[1:]
        return lst0
def f1(x):
        n=0
        for i in x:
                if i%2==1:
                        n+=1
        return n
def main():
        lst0=f(list1)
        lst1=[]
        for i in lst0:
                if f1(i)==k:
                        lst1.append(i)
        print(lst1)
        print(len(lst1))
        return lst1,len(lst1)
if __name__=='__main__':
        main()

TJBEST

子数组若出现多次 是不是只算一次？比如 nums = [1,1,2,2,1,1]，k = 2
是不是 只有 [1,1] [1,1,2][1,1,2,2][1,2,2,1][2,2,1,1][2,1,1]共6个？

阴阳神万物主

试探.jpg

def solve(nums:'list of int',k:int)->int:
    le = len(nums)
    pos = [i for i in range(le) if nums[i]%2]
    lt = len(pos)
    if lt < k:
        return 0
    res = (pos[0]+1)*((pos[k] if lt>k else le)-pos[k-1])
    #print('调试',res,pos)
    for i in range(1,lt-k):
        each = pos[i-1:i+k+1]
        #print('调试',each)
        res += (each[1]-each[0])*(each[-1]-each[-2])
    else:
        res += ((le-pos[-1])*(pos[-k]-pos[-k-1]))if lt>k else 0
    return res
if __name__ == '__main__':
    print('示例1 输出：',solve(nums = [1,1,2,1,1],k = 3))
    print('示例2 输出：',solve(nums = [2,4,6],k = 1))
    print('示例3 输出：',solve([2,2,2,1,2,2,1,2,2,2],k = 2))

阴阳神万物主

塔利班 发表于 2020-1-16 21:35

咱俩想到一块儿去了，话说为啥不用列表推导式呢？

zltzlt

TJBEST 发表于 2020-1-16 22:26
子数组若出现多次 是不是只算一次？比如 nums = [1,1,2,2,1,1]，k = 2
是不是 只有 [1,1] [1,1,2][1,1,2,2 ...

不是。

TJBEST

def fun307(nums , k):
    M = len(nums)
    jiIndexArr = [i for i in range(0,len(nums)) if nums[i]%2 ]
    N = len(jiIndexArr)
    if N < k:
        return 0
    elif N == k:
        return (jiIndexArr[0] + 1)*(M - jiIndexArr[N - 1])
    else:
        res = 0
        res += (jiIndexArr[0] + 1)*(jiIndexArr[k] - jiIndexArr[k - 1])
        for i in range(1,N - k):
            res += (jiIndexArr[i+k] - jiIndexArr[i+k-1])*(jiIndexArr[i] - jiIndexArr[i - 1])
        res += (jiIndexArr[N-k]-jiIndexArr[N-k-1])*(M - jiIndexArr[N - 1])
        return res

kinkon

不知道会不会超时

from itertools import combinations as ct
def f307(nums, k):
    if len(nums) < k or k == 0: return 0
    cout, res = 0, []     
    nums = list(enumerate(nums))        
    for num in range(len(nums)):
        res += [num for num in set(ct(nums, num + k))]
        if nums[num][1]%2 != 0:cout += 1
    if cout < k:return 0
    res = sorted(res)    
    t1, t2 = 0, 0
    for i in res:
        for j in range(len(i)-1):
            if i[j+1][0] - i[j][0] == 1:
                if i[j][0]%2 != 0:
                    t1 += 1
            if t1 == k: t2 += 1
    return t2

zltzlt

kinkon 发表于 2020-1-17 11:27
不知道会不会超时

解答错误

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：3
打印：

[((0, 2), (1, 2)), ((0, 2), (1, 2), (2, 2)), ((0, 2), (1, 2), (2, 2), (3, 1)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (7, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (7, 2), (8, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (7, 2), (8, 2), (9, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (7, 2), (9, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (8, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (8, 2), (9, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (9, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (7, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (7, 2), (8, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (7, 2), (8, 2), (9, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (7, 2), (9, 2)), ((0, ...（被和谐）

预期结果：16

fan1993423

def fun307(lst,k):
    odd=[i for i in range(len(lst)) if lst[i]%2]
    new_odd=[-1]+odd+[len(lst)]
    result=0
    for i in range(len(odd)-k+1):
        start=new_odd[i+1]-new_odd[i]
        end=new_odd[i+k+1]-new_odd[i+k]
        result+=start*end
    return result

wanting-for

def solve(A:'haha',k:int):
    first,count,end,result,c = 0,0,0,0,0
    end , m = first+k,k
    while True:
        for i in A[first:end]:
            if i%2 == 1:
                count+=1
        if  count == m:
            result+=1
        if end - first == len(A) and c == 0:
            break
        if end == len(A):
            c+=1
            k+=1
            first = 0
            end = first+k
        if c==0:
            first+=1
            end = first+k
        c = 0
        count = 0
    return result
if __name__ == '__main__':
    print('示例1 输出：',solve(A = [1,1,2,1,1],k = 3))
    print('示例2 输出：',solve(A = [2,4,6],k = 1))
    print('示例2 输出：',solve(A = [2,2,2,1,2,2,1,2,2,2],k = 2)) 

一杯茶一包烟，一个BUG改一天！

newbison

又是一个暴力破解法

def func307(arr, k):
    res = 0
    odd_or_even = [1 if i%2 != 0 else 0 for i in arr]
    for i in range(0, len(arr)):
        for j in range(len(arr), i+1, -1):
            if arr[i:j].count(1) == k:
                res += 1
    return res

if __name__ == '__main__':
    print('示例一：', func307([1,1,2,1,1], 3))
    print('示例二：', func307([2,4,6], 1))
    print('示例三：', func307([2,2,2,1,2,2,1,2,2,2], 2))

newbison

def func307(arr, k):
    res = 0
    odd_or_even = [1 if i%2 != 0 else 0 for i in arr]
    for i in range(0, len(arr)):
        for j in range(len(arr), i+1, -1):
            if arr[i:j].count(1) == k:
                res += 1
    return res

if __name__ == '__main__':
    print('示例一：', func307([1,1,2,1,1], 3))
    print('示例二：', func307([2,4,6], 1))
    print('示例三：', func307([2,2,2,1,2,2,1,2,2,2], 2))

ouyunfu

def f307(L:list,k:int)->int:
    count=0
    for i in range(len(L)-1):
        for j in range(i,len(L)+1):
            if len(L[i:j])-[i%2 for i in L[i:j]].count(0)==k:
                count+=1
    return count

L = [2,2,2,1,2,2,1,2,2,2]
k = 2
print(f307(L,k))

776667

def fun307(nums,k):

    def odd_count(x,k):
        count = 0
        for i in x:
            if i%2:
                count += 1
            if count > k:
                return 'over'
        if count < k:
            return 'less'
        return 'equals'

    result = []
    for i in range(len(nums)-k+1):
        for j in range(i+k,len(nums)+1):
            if odd_count(nums[i:j],k) == 'equals':
                result.append(nums[i:j])
            if odd_count(nums[i:j],k) == 'over':
                break
    return len(result)

旅途Z

想问一下，每日一题是不再更新了嘛