3准确秤量任务

两个空烧杯容量是9升和11.25升：

C9AuEl812n.png

容许用这些动作：

从水龙头处完全灌满一个容器
将一个容器内的水完全倒在地上
把一个容器倒入另一个容器中，直到它完全装满或倒入的那个容器完全空了为止，
你能准确地测量出以下哪一个数量？

提示：想一想你能测出的最小的量。四个选项有一是？
1.5升
3.25升
5升
6.75升

容许下面的操作：
99升的容器盛满水后，倒入11.2的容器。
再次填满9升的容器。接着将9升的容器倒入11.25的容器中，直到后者被装满。
这时，9升容器里还剩下6.75升，而另一个容器已经满了。正好测出6.75升。

解法
考虑两个比所给的容器大4倍的容器：
一个能容纳9×4=36升
另一个能容纳11.25×4=45升
如果我们能用这两个容器量出N升，那么我们就可以用原来的9升和11.25升的容器来测量 N/4升

我们可以用36升和45升的容器测量出的水的总量，其形式为
36x+45y
36x+45y
其中x和y是整数。如果x是正数，那么36升的容器就被装了x次。如果它是负数，那么36升的容器已经被清空了|x|次。y和45升容器的情况也是如此。

36x+45y的表达式必然是9的倍数，因为
36x=9(4x)
36x=9(4x)
和
45y=9(5y)。
45y=9(5y)。
也就是说，两个容器中的水的总量是9升的倍数。

那么，对于99升和11.2511.25升的容器，水的总量是 9/4 = 2.25的倍数
2.25在给定的选项中，只有 6.75=3×2.25是可能的。

我们可以用以下的动作顺序来测量。
装满9升的容器。
将99升的容器倒入11.25的容器。
再次填满9升的容器，然后
将9升的容器倒入11.25的容器中，直到后者被装满。这时，9升容器里还剩下6.75升，而另一个容器已经满了--把它倒出来，我们正好测出6.75升。

任务升级

包括6.75升，还有哪些可以准确秤量出的容量？

option = [1.5,3.25,5,6.75]

def pourMin(u,U): # u=small, U=larger
    i,j,s = 2,1,True
    ans = [float('INF')]
    minvol = u*i - U*j
    step = 0
    while minvol <= u+U:#minvol <= 两个杯子容量之和
        s = not(s)
        minvol = abs(u*i - U*j)
        i += s
        j += not(s)
        ans.append(minvol)      
    return sorted(set(ans))[:-2],[i for i in set(ans) if i in option]
u,U = 9,11.25
print(pourMin(u,U))

([0.0, 2.25, 4.5, 6.75, 9.0, 11.25, 13.5, 15.75, 18.0, 20.25],
 [6.75])

共有 9 个不同的称量结果：
2.25, 4.5, 6.75, 9.0, 11.25, 13.5, 15.75, 18.0, 20.25

符合题目的是 6.75

继续上面的任务，熟悉函数式编程

[0.0, 2.25, 4.5, 6.75, 9.0, 11.25, 13.5, 15.75, 18.0, 20.25, 22.5, inf]
以上是pourMin函数的返回值。目标是删除不符合任务要求的0.0和inf

ans = []
for n in pourMin(u,U)[0]:
    if n > 0 and n <= (u+U):      
        ans.append(n)

print('for_loop',ans)
[2.25, 4.5, 6.75, 9.0, 11.25, 13.5, 15.75, 18.0, 20.25]

导入模块 itertoolts里的dropwhile，takewhile
首先要定义过滤条件，两个容器的容量之和是上限，即不可能通过规则准确秤量出超过22.5升的水

def isVolum(x):
    return x <= u+U

下面例子体会takewhile和dropwhile的不同

from itertools import dropwhile
print('dropwhile:',list(dropwhile(isVolum,pourMin(u,U)[0])))
dropwhile: [22.5, inf]

dropwhile是找出不符合过滤条件的

from itertools import takewhile
print('takewhile:',list(takewhile(isVolum,pourMin(u,U)[0])))

takewhile是找符合条件的数值，直到第一个不符合的元素截止。

span函数是一个需要了解的好函数。它接受一个数组和一个谓词函数并返回两个数组。第一个数组包含了参数数组中的所有元素，直到导致谓词第一次失败的那一项。第二个返回的数组包含原始数组的其余部分。原始数组不被修改。

https://docs.python.org/3/library/itertools.html

函数式程序

任务：你有一个值的序列和一些关于这些值的谓词。你想删除最长的元素前缀，使每个元素的谓词都为真。我们称这个为 dropWhile 函数。它接受两个参数。第一个是值的序列，第二个是谓词函数。该函数不会改变原始序列的值。

def isEven(num):
  return num % 2 == 0
arr = [2,4,6,8,1,2,5,4,3,2] 。

dropWhile(arr, isEven) == [1,2,5,4,3,2] # True

你的任务是实现dropWhile函数。如果你身边有一个span函数，这就是一个单行本！或者，如果你有一个takeWhile函数，这就是一个单行本。或者，如果你手上有一个takeWhile函数，那么结合dropWhile函数，你可以在一行中实现span函数。这就是函数式编程的魅力所在：有一大堆有用的函数，其中许多都可以相互实现。

from itertools import dropwhile

def drop_while(arr, pred):
    return list(dropwhile(pred, arr))

加权作业调度

难度等级 : 中等
最后更新 : 2022年3月23日
给出N个工作，每个工作由以下三个元素代表。
开始时间 完成时间 利润或相关价值(>=0)
寻找最大利润的工作子集，使子集中没有两个工作重合。

例子:
输入: 工作数量 n = 4
工作细节{开始时间，结束时间，利润}。
工作1：{1，2，50}。
工作2：{3，5，20}。
工作3：{6，19，100}。
工作4：{2，100，200}。

输出: 最大的利润是250。
我们可以通过安排工作1和4获得最大利润。
请注意，工作1、2和3有可能有较长的时间表。
但这个计划的利润是20+50+100，小于250。

这里讨论的是这个问题的一个简单版本，每个工作都有相同的利润或价值。活动选择的贪婪策略在这里不起作用，因为有更多工作的时间表可能有更小的利润或价值。

上述问题可以用以下的递归方案来解决。

1. 首先根据完成时间对工作进行分类。
2. 现在应用以下递归过程。
   这里arr[]是n个工作的数组。
   findMaximumProfit(arr[], n)
   {
   a) 如果 (n == 1) 返回 arr[0]。
   b) 返回以下两种利润的最大值。
   (i) 排除当前工作的最大利润，即。
   findMaximumProfit(arr, n-1)
   (ii) 通过包括当前工作的最大利润
   }

如何找到包括当前工作的利润？
我们的想法是在当前工作之前找到最新的工作（在
排序的数组），与当前工作'arr[n-1]'不冲突。
一旦我们找到这样的工作，我们就递归所有工作，直到该工作，并将当前工作的利润加到结果中。
将当前工作的利润加入到结果中。
在上面的例子中，"工作1 "是最近的一个不冲突的工作。
工作4"，"工作2 "是 "工作3 "的最新非冲突工作。
下面是上述天真的递归方法的实现。

# Python3程序用于加权作业调度，使用
# 天真递归法
 
# 导入以下模块对数组进行排序
# 基于我们自定义的比较函数

from functools import cmp_to_key

一个工作有开始时间、结束时间和利润

class Job:     
    def __init__(self, start, finish, profit):         
        self.start = start
        self.finish = finish
        self.profit = profit

事件的完成时间前后排序

# 一个实用函数，用于
# 根据完成时间对事件进行排序

def jobComparator(s1, s2):     
    return s1.finish < s2.finish

当前事件时间不重叠或也称之为不冲突的事件

# 找到最新的工作（在排序的数组中），并且
# 与job[i]不冲突。如果没有
# 没有兼容的工作，那么它就会返回-1

def latestNonConflict(arr, i):     
    for j in range(i - 1, -1, -1):
        if arr[j].finish <= arr[i - 1].start:
            return j             
    return -1 

递归的实现

# 一个递归函数，从给定的
# 数组中的工作返回 最大可能的利润
# 数组中的工作必须根据完成时间进行排序

def findMaxProfitRec(arr, n):
     
    # Base case
    if n == 1:
        return arr[n - 1].profit
 
    # Find profit when current job is included
    inclProf = arr[n - 1].profit
    i = latestNonConflict(arr, n)
     
    if i != -1:
        inclProf += findMaxProfitRec(arr, i + 1)
 
    # Find profit when current job is excluded
    exclProf = findMaxProfitRec(arr, n - 1)
    return max(inclProf, exclProf)
 
# 创建一个数组来存储子问题的解决方案。
# table[i]存储工作的利润，直到arr[i]。
# (包括arr[i])

def findMaxProfit(arr, n):
     
    # Sort jobs according to finish time
    arr = sorted(arr, key = cmp_to_key(jobComparator))
    return findMaxProfitRec(arr, n)
 
# Driver code
values = [ (3, 10, 20), (1, 2, 50),
           (6, 19, 100), (2, 100, 200) ]
arr = []
for i in values:
    arr.append(Job(i[0], i[1], i[2]))
     
n = len(arr)
 
print("The optimal profit is", findMaxProfit(arr, n))

输入和输出

values = [ (3, 10, 20), (1, 2, 50),
           (6, 19, 100), (2, 100, 200) ]
arr = []
for i in values:
    arr.append(Job(i[0], i[1], i[2])
     
n = len(arr)
 
print("最佳利润是", findMaxProfit(arr, n))

这段代码是由Kevin Joshi贡献的代码

输出最佳利润是250

上述解决方案可能包含许多重叠的子问题。例如，如果lastNonConflicting()总是返回前一个作业，那么findMaxProfitRec(arr, n-1)就会被调用两次，时间复杂度就变成了O(n*2n)。

作为另一个例子，当lastNonConflicting()返回前一个工作时，有两个递归调用，分别为n-2和n-1。在这个例子中，递归变得与斐波那契数相同。

因此，这个问题同时具有动态规划、最佳替代结构和重叠子问题的特性。
像其他动态编程问题一样，我们可以通过制作一个存储子问题解决方案的表格来解决这个问题。

下面是一个基于动态规划的实现。

# Python3程序用于加权工作调度
# 使用动态规划 
# 导入以下模块对数组进行排序
# 基于我们自定义的比较函数

from functools import cmp_to_key 
# 一个工作有开始时间、结束时间和利润
class Job:
 
    def __init__(self, start, finish, profit):
 
        self.start = start
        self.finish = finish
        self.profit = profit

# 一个实用的函数，用于根据完成时间分类
# 事件根据完成时间进行排序
  
def jobComparator(s1, s2): 
    return s1.finish < s2.finish
 

找到最新的工作（在排序的数组中），并且
与job[i]不冲突。如果没有
没有兼容的工作，那么它就会返回-1

def latestNonConflict(arr, i):

   for j in range(i - 1, -1, -1):
       if arr[j].finish <= arr[i - 1].start:
           return j

   return -1

主函数返回最大可能的
从给定的工作数组中获得利润

def findMaxProfit(arr, n):

   # 根据完成时间对工作进行排序
   arr = sorted(arr, key=cmp_to_key(jobComparator))

   # 创建一个数组来存储子问题的解决方案。
   # table[i]存储工作的利润，直到arr[i]。
   # (包括arr[i])
   table = [None] * n
   table[0] = arr[0].profit

   # 使用递归属性填充M[]中的条目
   for i in range(1, n):

       # 找到包括当前工作在内的利润
       inclProf = arr[i].profit
       L = latestNonConflict(arr, i)

       if L != -1:
           inclProf += table[l]

       # 存储包括和不包括的最大值
       table[i] = max( inclProf, table[i - 1])

   # 存储结果并释放动态内存
   # 分配给table[]
   result = table[n - 1] 
   return result

驱动代码

values = [(3, 10, 20), (1, 2, 50),
          (6, 19, 100), (2, 100, 200)]
arr = []
for i in values:
    arr.append(Job(i[0], i[1], i[2])
 
n = len(arr)
 
print("最佳利润是", findMaxProfit(arr, n))

这段代码是由Kevin Joshi贡献的

输出最佳利润是250

上述动态编程解决方案的时间复杂度为O(n2)。
请注意，上述解决方案可以通过在 latestNonConflict()中使用二进制搜索而不是线性搜索来优化为O(nLogn)。感谢Garvit提出的这个优化建议。详情请参考下面的帖子。

少见的module- Attrgetter

Reference case of usage

class AnOject:
    def __int__(self,a,b,c,d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

myobj = AnOject
#myobj(a=17,b=23,c=42,d=99)
myobj.d,myobj.a,myobj.b,myobj.c = 17,23,42,99
a,b,c,d =17,23,42,99
#myobj = [a,b,c,d]
#print(myobj.a,myobj.b,myobj.c)

import operator
s = operator.attrgetter("a","b","c")(myobj)
print(s)

(23, 42, 99)

Codewars题库成功提交后，见到排名前面的代码！

长方形可由多少个正方形拼成，输出正方形的边长和数量

jUPGUtrc4V.png

# Eric solve

def sqInRect(lng, wdth):
    ans = []
    lng, wdth = sorted([lng,wdth])[::-1]
    if lng == wdth:
        return None
    while True:
        ans.append(wdth)
        if lng - wdth > wdth:
            lng,wdth = lng-wdth,wdth

        elif lng > wdth:
            lng, wdth = wdth, lng-wdth

        elif lng <= wdth:           
            return ans

输入
lng, wdth = 5,3
#lng, wdth = 20, 14
lng, wdth = 37, 14
输出
print(sqInRect(lng,wdth))

[14, 14, 9, 5, 4, 1, 1, 1, 1]

2nd 果然高手

def sqInRect(a, b):
    if a == b:
        return None
    res = []
    while b:
        b, a = sorted([a, b])
        res += [b]
        a, b = b, a - b
    return res

3rd 递归写法

# Recursive solution
def sqInRect(lng, wdth, recur = 0):
    if lng == wdth:
        return (None, [lng])[recur]            
# If this is original function call, return None for equal sides (per kata requirement);
# if this is recursion call, we reached the smallest square, so get out of recursion.
    lesser = min(lng, wdth)
    return [lesser] + sqInRect(lesser, abs(lng - wdth), recur = 1)

recursion_2nd

def sqInRect(a, b, inner=False):
    if a < b:
        return sqInRect(b, a, True)
    elif a > b:
        return [b] + sqInRect(a-b, b, True)
    elif inner:
        return [a]

recursion 3rd_solve

def sqInRect(a, b):
    if a < b:
        a, b = b, a

    if a == b:
        return None
    elif b == 0:
        return []
    else:
        return [b] * (a // b) + sqInRect(b, a % b)

推荐codewars趣味题库，见证全球高手的代码