image.png

1、DNA如何编程解决？

dna = "T T T T T G G G A C C C C C C G A A"

def dnaCunt(dna):
    dna = "".join(dna.split(" ")) + '0'
    # 原字符串含有空格，需去掉空格
    # for循环截止在A会漏掉末尾的两个A，增加一个’0‘

    s,cnt = '',1
    for i in range(len(dna)-1):

        if dna[i] == dna[i+1]:
            cnt += 1
        else:
            s += f"{dna[i]}{cnt}"
            cnt = 1
    return s
print(dnaCunt(dna))

T5G3A1C6G1A2

再修改输出，得到字符串长度的变化

def dnaCunt(dna):
    dna = "".join(dna.split(" ")) + '0'
    # 原字符串含有空格，需去掉空格
    # for循环截止在A会漏掉末尾的两个A，增加一个’0‘

    s,cnt = '',1
    for i in range(len(dna)-1):

        if dna[i] == dna[i+1]:
            cnt += 1
        else:
            s += f"{dna[i]}{cnt}"
            cnt = 1
    return len(dna) - len(s)-1
print(dnaCunt(dna))

6

image.png image.png

#2、CAT 18 5th problem
流程图

def func(a):
    b = 0
    while a > 10:
        a -= 10
        b += 1
    b += a
    return b
inp = [23, 47, 119, 123456]
ans = len([func(i) for i in inp if not func(i)%2])
print(ans)

image.png

3 三向机器人扫地机

几何简单知识加一点技巧
数数总共有多少个1点钟、5点钟和9点钟方向,
1点钟方向：共有 6 步（右上）
5点钟方向：共有 8 步（右下）
9点钟方向：共有 9 步（左）

假设机器人每步步长是 1 单位，出发位置在坐标系原点 O(0,0)

先看 X轴位移的情况
1点钟方向和5点钟方向在水平方向的投影长度是：
(6+8)/2 = 7, sin 30=0.5，要除以2，水平向右移动 7 个单位，
抵消水平向左的 9点钟方向位移后，水平向左 7-9 = -2
即得到：X = -2

再看Y轴位移的情况
9点钟方向与X轴平行，不贡献Y轴的位移！
只需看1和5点钟在Y轴方向的位移：（6 - 8) * sin 60 ,
即得到：Y= - 3**0.5

机器人完成指令后位于出发点(0,0)左下方向的 (-2, - 3**0.5)位置

回到出发点，X轴方向向右移动 2 个单位；Y轴向上移动 30.5单位
显然9点钟方向无法做出贡献；
仅依赖1点钟和5点钟方向指令抵达原点：
1点钟和5点钟每一步贡献X轴方向向右移动 0.5个单位；
1点钟和5点钟每一步贡献Y轴方向向右移动 + 0.5(30.5),或 - 0.5(3**0.5)个单位；

由此可见，需要满足两点：
1点钟方向步数需要多于5点钟方向步数 2 步；
1点钟方向和5点钟方向在X轴方向共移动 2个单位距离
得到结果：
1点钟方向走3步，5点钟方向走1步，见下图示：

image.png

如何运用turtle解决，也许是锻炼turtle的好机会！

# 增加 4 步 1点钟方向走3步，5点钟方向走1步，
steps = [60,60,60,-60]  # 追加的4步

angles = [-60,-60,180,60,180,180,-60,180,
          60,180,60,180,180,-60,-60,-60,60,
          180,60,60,180,-60,-60]

mid = len(angles)
angles.extend(steps)
print(angles)

t.dot(10,'red')
for i,e in enumerate(angles):
    if i == mid:
        t.dot(17,'purple') #机器人在紫色位置停留

    t.speed(2)
    t.left(e)
    t.forward(80)
    t.left(-e)
t.dot(10,'blue')
t.done()

image.png

代码块

image.png

4. 简单算法任务名称 ： 加1，减1

image.png

伪代码是表达算法的一种方式。
重复（循环）是用While . . . EndWhile。

决定是用If . . EndIf或If . 否则 . . EndIf.

寻找两个数字中较大的一个。
函数1：
输入A和B
如果A>B, 最大是 A; 否则, 最大的数是B
结束条件判断

函数2：
数字1, . . . , 10 总数 ← 0 N ← 1
当N≤10时，将N加到总和中
将1加入到N中，
EndWhile：结束循环

执行算法由以下伪代码表示：
输入A和B
如果A > B：A赋值给C, B赋值给D
否则, B赋值给C, A赋值给D

while C>D时, 一直执行：
从C中减去1
给D加1
EndWhile：直到不满足C>D时退出循环执行
输出C

以下输入四对(A,B)是执行算法的输入。
(10,2); (9,17); (100,200); (1001,2005).
有多少个输出是偶数的？

def cal(x,y):
    x,y = sorted([x,y],reverse=True)
    while x > y:
        x -= 1
        y += 1
    return x
inp = [(10,2), (9,17),(100,200), (1001,2005)]

ans = [cal(x,y) for x,y in inp]
print(ans)

[6, 13, 150, 1503]
共有 2 个结果是偶数！

5、Python中队列的完整指南

什么是队列以及如何在Python中实现队列

image.png

在编程术语中，队列是一个抽象数据类型，它存储项目被添加到结构中的顺序，但它只允许添加到队列的末端，而只允许从队列的前面删除。在这样做的时候，它遵循先入先出（FIFO）的数据结构。

从本质上讲，这就像你期望一个队列在现实中的表现一样，例如当排队进入商店时，那些先到的人将会先到。然而，与现实生活不同的是，我们构建这个结构的方式是为了确保不会出现插队的情况。

当我们想把输出存储在一个结构中，保留它们的顺序，然后按照给定的顺序执行动作时，就可以使用这些方法。在编程中常见的例子包括为你的计算机CPU调度工作，为打印机排队以确保先发送的工作得到执行，为企业进行订单处理，或消息处理。

考虑到这一点，知道了我们想让数据未来做什么以及我们想如何与之交互，我们就可以开始考虑如何在Python的实际数据结构中实现这一点。通常与此相关的关键方法包括。
enqueue(item)。将一个项目添加到队列的末端
dequeue(): 删除并返回队列前端的项目
peek()。返回队列前面的项目，而不删除它
is_empty()。如果队列是空的，返回True
size()。返回队列里有多少个项目

这意味着我们需要使用一个Python数据类型来构建，这个数据类型是可变的，可以用来存储有序的项目集合。我们可以问自己的第一件事是，在Python中是否有一个已经实现的数据类型可以为我们做这个？

一个列表! 我们可以使用一个列表!
我们知道列表是可变的，它可以被改变，而且我们可以简单地从开头和结尾添加和删除项目，使用列表已经内置的功能来实现队列。

在使用列表时，我们必须定义一个使用该功能的类，但只具有允许用户以我们想要的方式与之交互的特定功能。为此，我们可以使用 Python 的类结构，以便能够定义数据结构所包含的信息和我们想要使用的方法。

那么要做的第一件事就是把这个类命名为Queue，并为这个新类创建构造函数。我们想要的是，一旦创建了一个新的对象实例，就要初始化一个空的列表，可以使用.items属性进行访问。这方面的代码可以如下。

class Queue:

    #create the constructor
    def __init__(self):
    
        #create an empty list as the items attribute
        self.items = []
        
<<<中文解释代码块>>>
class Queue:    #创建构造函数
    def __init__(self):        #创建一个空列表作为items属性
        self.items = []

这意味着当我们创建一个Queue类的实例时，项目属性将代表一个空列表。
然后我们可以开始为Queue类添加主要功能。我们要做的第一件事是向队列中添加一个项目。在这一点上，重要的是能够确定哪一端是我们获取数据的队列前端，哪一端是我们可以添加项目的队列末端。

这对每个过程所需的时间有影响，因为改变列表开头的东西会导致时间复杂度为O(n)，因为我们必须改变列表中所有后续项目的索引，以便将所有东西移到右边。然而，如果我们在列表的末尾操作东西，那么时间复杂度为O(1)，因为我们只在删除或添加项目时改变列表末尾的索引。

然而，这其实并不太重要，因为无论你选择添加或删除哪一方，其他函数的时间复杂度还是一样的。所以，考虑到这一点，我们可以实现enqueue(item)方法来向我们的队列添加一个项目。

  def enqueue(self, item):
        """
        Add item to the left of the list, returns Nothing
        Runs in linear time O(n) as we change all indices
        as we add to the left of the list
        """
        #use the insert method to insert at index 0
        self.items.insert(0, item)

<<<中文解释代码块>>>

    def enqueue(self, item):
        """
        将项目添加到列表的左边，返回Nothing 运行时间为线性时间O(n)，
        因为我们改变了所有的索引
        因为我们向列表的左边添加
        """        #使用插入方法，在索引0处插入
        self.items.insert(0, item)

这将简单地把一个项目添加到我们队列的最后（左边）。在这种情况下，我们并不太关心我们添加到队列中的内容，只是我们可以添加它。当然，你可以在此基础上添加更多的功能，但现在这样就可以了。

这意味着，当我们想从队列类的右端列表中删除项目时。在这样做的时候，我们需要注意一个相当简单的边缘情况，即我们的队列是否是空的。

在这种情况下，如果 Queue 是空的，我们可以简单地返回 None，这样我们仍然在返回一些东西，程序也不会抛出错误，但是如果它不是空的，那么我们可以返回队列中的 "第一个 "项目并将其返回。由于我们使用的是Python的

由于我们使用的是 Python 内置的 list 类，我们可以简单地使用 .pop() 方法，在 Python 3.6+ 中，该方法从一个列表中删除第 1 个项目并返回它。这个方法的运行时间是恒定的 O(1)，因为我们只是删除列表中的项目，而不影响任何其他的索引。因此，这可以被实现为。

   def dequeue(self):
        """
        Removes the first item from the queue and removes it
        Runs in constant time O(1) because we are index to
        the end of the list.
        """
        #check to see whether there are any items in the queue
        #if so then we can pop the final item
        if self.items:
            
            return self.items.pop()
        #else then we return None
        else:
            return None

<<<中文解释代码块>>>

    def dequeue(self):
        """
        从队列中移除第一个项目，并将其移除。 运行时间为恒定的O(1)，因为我们的索引是到
        列表的末尾。
        """        #检查队列中是否有任何项目
        #如果有，我们就可以取出最后一个项目
        如果self.items:
            
            return self.items.pop() #else then we return None
        否则：返回None

这样我们就实现了队列的主要功能，确保我们只向队列的一端添加项目，并从队列的另一端删除项目。这将保持队列中项目的顺序，并确保我们按照添加到队列中的相同顺序使用这些项目。

然后我们可以考虑其他补充方法，以帮助在实际程序中使用队列数据结构。那么，我们可以增加的第一个附加功能是允许用户查看下一个从队列中删除的项目，而不需要实际将其删除。

这个功能的实现将遵循与dequeue()方法类似的结构，但我们可以不使用.pop()，而是用列表中的最后一个项目来暗示访问该项目。这意味着我们的时间复杂度为O(1)，因为我们使用索引来访问该项目，使其变得简单而漂亮。

  def peek(self):
        """
        Returns the final item in the Queue without removal
        
        Runs in constant time O(1) as we are only using the index
        """
        #if there are items in the Queue 
        if self.items:
            #then return the first item
            return self.items
        
        #else then return none
        else:
            return None

<<<中文解释代码块>>>

    def peek(self):
        """
        返回队列中的最后一个项目，不需要移除。
        
        由于我们只使用了索引，所以运行时间恒定为O(1)
        """        #如果队列中存在项目 
        如果self.items。
            #则返回第一个项目
            return self.items
        
        #else then return none
        否则。
            返回None

我们还可以提供一种方法来检查队列是否为空。如果队列确实是空的，这将简单地返回一个布尔值：True，如果不是，则返回False。这也是以恒定时间运行的，因为它只是检查队列中的列表是否存在

    def is_empty(self):
        """
        Returns boolean whether Queue is empty or not
        Runs in constant time O(1) as does not depend on size
        """
        return not self.items
      
<<<中文解释代码块>>>

    def is_empty(self):
        """
        返回布尔值，即队列是否为空 由于不依赖于大小，所以运行时间为恒定的O(1)
        """ 返回 not self.items

我们可以创建一个方法来返回队列的大小。这可以告诉我们队列的大小，就像对待一个列表一样，并告诉我们有多少个项目被添加，或者队列中还有多少个项目。

  def size(self):
        """
        Returns the size of the stack 
        Runs in constant time O(1) as only checks size
        """
        #len will return 0 if empty
        #so don't need to worry about empty condition
        return len(self.items)

<<<中文解释代码块>>>

    def size(self):
        """
        返回堆栈的大小 在恒定时间内运行 O(1) 因为只检查大小
        """        #len如果为空，将返回0
        #所以不需要担心空的情况
        return len(self.items)

最后，我们要确保我们试图打印出一个Queue类的实例，它对于个人来说实际上是可读的，可以看到它是Queue和Queue包含的内容。为此，我们使用该类中特殊的 str dunder 方法来告诉解释器我们想如何打印出该类的实例。在本例中，我们只是想返回堆栈中包含的整个列表，可以实现为

    def __str__(self):
        """Return a string representation of the Stack""""
        return str(self.items)

<<<中文解释代码块>>>

    def __str__(self):
        ""返回 Stack 的字符串表示"""" 
          return str(self.items)

唷! 那么把这一切放在一起呢？
最终的产品是这样的。

class Queue:

    #create the constructor
    def __init__(self):
    
        #create an empty list as the items attribute
        self.items = []
        
    
    def enqueue(self, item):
        """
        Add item to the left of the list, returns Nothing
        Runs in linear time O(n) as we change all indices
        as we add to the left of the list
        """
        #use the insert method to insert at index 0
        self.items.insert(0, item)
        
    def dequeue(self):
        """
        Removes the first item from the queue and removes it
        Runs in constant time O(1) because we are index to
        the end of the list.
        """
        #check to see whether there are any items in the queue
        #if so then we can pop the final item
        if self.items:
            
            return self.items.pop()
        #else then we return None
        else:
            return None
          
          
    def peek(self):
        """
        Returns the final item in the Queue without removal
        
        Runs in constant time O(1) as we are only using the index
        """
        #if there are items in the Queue 
        if self.items:
            #then return the first item
            return self.items
        
        #else then return none
        else:
            return None
          
    def is_empty(self):
        """
        Returns boolean whether Queue is empty or not
        Runs in constant time O(1) as does not depend on size
        """
        return not self.items
      
      
    def size(self):
        """
        Returns the size of the stack 
        Runs in constant time O(1) as only checks size
        """
        #len will return 0 if empty
        #so don't need to worry about empty condition
        return len(self.items)
      
    def __str__(self):
        """Return a string representation of the Stack"""
        return str(self.items)

在这一点上，你可能会想为什么我需要知道这些？嗯，这种数据结构在编程中的常见应用包括。

在CPU中调度工作
图形遍历算法
订单处理
打印队列

当你在构建这些程序时，知道这种数据结构在Python中的样子是很好的，并为你提供了能够处理这些挑战的功能。

这在软件工程师或数据科学面试中也会出现，比如要求你构建一个使用队列的打印机，或者创建图的遍历算法，如深度优先搜索。

就这样，你知道了如何在Python中实现队列，也知道了它的一些用途!

经典的场景可以比作与计算机科学有关的线程池的想法，与同时运行多个进程有关
超市的自助收银台有一个排队的队伍。你的任务是写一个函数来计算所有顾客结账所需的总时间!

输入customers：一个代表队列的正整数数组。每个整数代表一个顾客，其值是他们结账所需的时间。 n：一个正整数，结账台的数量。 输出 函数应该返回一个整数，即所需的总时间。

重要事项 请看下面的例子和说明，以确保你能正确理解这个任务 :)

示例 queue_time([5,3,4], 1)

应该返回12
因为当n=1时，总时间只是各时间之和。
queue_time([10,2,3,3], 2)

应该返回10
因为这里n=2，队列中的第二、第三和第四个人在第一个人完成之前就完成了。
队列中的第二、第三和第四个人在第一个人完成之前完成。
queue_time([2,3,10], 2)

应该返回12
澄清：只有一个队列服务于许多收银台，队列的顺序永远不会改变，队列中最前面的人（即数组/列表中的第一个元素）一旦有空就会去收银台。注意：你应该假定所有的测试输入都是有效的，如上所述。

class Queue:
    def __init__(self, arr=[]):
        self.arr = arr
        self.wait_time = sum(i for i in arr)
    
    def enqueue(self, num):
        self.arr.append(num)
        self.wait_time += num
    
    def dequeue(self):
        return self.arr.pop(0)
    
def queue_time(customers, n):
    # TODO
    customer_queue = Queue(customers)
    if n == 1:
        return customer_queue.wait_time
    
    queues = [Queue([]) for i in range(n)]
    while len(customer_queue.arr)>=1:
        wait = [k.wait_time for k in queues]
        for i in queues:
            if i.wait_time == min(wait) or i.wait_time == 0:
                i.enqueue(customer_queue.dequeue())
                break
                
    return max([i.wait_time for i in queues])

queue_time([1,2,3,4,5,6], 3))
9

print(queue_time([8,2,3,5,4,4], 3))
11

queue_time([1,2,3,4,5], 1)
15

queue_time([1,2,3,4,5], 100)
5

queue_time([2,2,3,3,4,4], 2)
9

排队问题解决了，接下来图形遍历呢？

6 水槽最大存水量问题

在下图中，第一个槽有高度3、2和1米的挡板，而第二个槽有高度3、1和2米的挡板。挡板相距1米，槽有1米宽，所以第一个槽可容纳3立方米，第二个槽容纳4立方米。

image.png

请问如果有一个长的水槽有9个隔板，隔板高度分别是9 3 6 8 4 5 7 4 2。请问水槽最多能储存的水量？

image.png

由于理解不透彻，容易理解为算法：相邻两个隔板取最小，可惜算法是不对的！
不过可以尝试练习python的循环地址和min函数用法

#容易犯的错误算法
volum = 0
for i in range(len(hights)-1):
    volum += min(hights[i],hights[i+1]) * 1
print(volum)

31

算法二：左隔板算起向右取余下隔板中最高的，并记录两个隔板之间的距离

s = len(hights)
i,volum , j = 0,0, s-1
# 滑动窗口 左右边界i,j

while i < j and j < s:
    left = hights[i]
    right = max(hights[i+1:])

    for r in range(s-1,0,-1):
        if hights[s-r] == right:
            volum += (s-r - i) * 1 * min(left,right)
            i = s-r
            j = len(hights)-1
            print(left, right, volum)
print(volum)

输出：

9 8 24
8 7 45
7 4 37
7 4 49
4 2 51
51

正确答案是 51

三、洗牌

你有两张桌子，标签是A和 B。从一开始，桌子上有一排纸牌 A. 每张卡片上都有一个数字，所以卡片线一起形成一个数字。B为空。您希望将卡片移动到B中，并制作一个尽可能大的数字。

image.png

移动X：从A中取出最左边的牌，并将其放在B的最右端

移动Y：从A中取出最右边的牌，放在的最右端 B. 例如，

假设A上有三张卡构成数字123。
上图说明了移动YXX，给出了的最终数字312
注意312不是最大组合，👆例子仅说明X,Y的移动
如果A上的牌是3 7 1 2 6 5 4 ，那么B的最大的第四位数字是多少？

第一种思路运用数组结构

image.png

第二种思路运用双向队列

image.png

from collections import deque

cards = '3712654'
def shuffle(cards):
    d = deque(cards)
    ans = ''
    while d:
        if d[0] > d[-1]:
            ans += d.popleft()
        else:
            ans += d.pop()
        print(ans)
    return ans[3]  #输出第4位数
print(shuffle(cards))

4
45
456
4563
45637
456372
4563721
3

整个过程如下：
4->45->456->4563->45637->456372->4563721
第四位数是： 3