数据结构与算法列表及习题部分

怼烎@ 2022-02-19 00:55 184阅读 0赞

一、数组排序问题  
1、题型1：快速排序  
例1：  
三路快排：  
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:  
不能使用代码库中的排序函数来解决这道题。  
只能在数组上进行修改

示例:

输入: \[2,0,2,1,1,0\]  
输出: \[0,0,1,1,2,2\]  
进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。  
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。  
你能想出一个仅使用常数空间的一趟扫描算法吗？  
代码：

class Solution(object):
        def sortColors(self, nums):
            """
            :type nums: List[int]
            :rtype: None Do not return anything, modify nums in-place instead.
            """
            d={
        }
            for i in nums:
                if i in d:
                    d[i]=d[i]+1
                else:
                    d[i]=1
            index=0
            for j in d.keys():
                for i in range(d[j]):
                    nums[index]=j
            return nums

解析：首先这个题有两个难点，一是题目不能用排序程序，二是题目要求只能在原数组进行修改，且根据题意我们可以知道，只需要将相同的元素排列在一起就行了，不一定要按顺序，如答案为\[2, 2, 0, 0, 1, 1\]也正确。  
思路：  
1、先统计数组中的元素的出现频率  
2、声明一个游标index  
3、不断替换原数组的元素，每次index加+1，知道数组替换完成

方法2：

class Solution(object):
        def sortColors(self, nums):
            """
            :type nums: List[int]
            :rtype: None Do not return anything, modify nums in-place instead.
            """
            zero=-1 #nums[0,....zeros]==0
            two=len(nums)      #nums[two,...n-1]==2
            i=0
            while i < two:
                if nums[i]==0:
                    zero+=1
                    nums[i],nums[zero]=nums[zero],nums[i]
                    i+=1
                elif nums[i]==1:
                    i+=1
                else:#nums[i]==2:
                    two=two-1
                    nums[two],nums[i]=nums[i],nums[two]
            return nums

解析：三路排序，分别设置指标zeros，two,nums\[0,…zeros\]为0，nums\[two,…n-1\]为2，i指针用于判断，当前元素为何值，如果等于1，i指针右移，等于2时，two指针左移，和i元素交换，此时i指针保持不动，如果等于0，zeros+1，i和zeros交换然后右移  
难点：  
这种三路排序的难点在于，  
（1）要使用while循环，这个是为了防止指针不动的情况  
（2）two和zeros指针一开始都是没有值的，只有当i查到了不为1的元素时，两边指针所指向的内容才有值。  
2、归并数组  
例2：  
leedcode 88

例2：  
数组排序问题  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]

class Solution(object):
        def moveZeroes(self, nums):
            """
            :type nums: List[int]
            :rtype: None Do not return anything, modify nums in-place instead.
            """
            lis2=[]
            for i in nums:
                if i!=0:
                    lis2.append(i)
            index=0
            for i in lis2:
                nums[index]=i
                index=index+1
            #index始终等于当前元素的个数加1
            while index<len(nums):
                nums[index]=0
                index=index+1
            return nums

思路：先将数组中非零的数取出来，存储在一个列表中，再将这个列表中的非零元素一个个替换到数组中，替换完成后如果列表中还有其他元素全部替换成0.  
难点：  
（1）、循环问题：  
我们以index=0进入循环，每次执行完操作后index=index+1,那么我们完成了n次操作，实际上index显示n，但我们在第n次就跳出来了，实际上index只执行了n-1次  
如：

a=[1,2,3,4,5,6]
    index=0
    while index<len(a):
        print(a[index])
        index+=1

![在这里插入图片描述][20190415164331175.png]  
我们想以index记录循环的操作数，如我们打印列表a,打印了6次，此时index为6，从0开始算起，index执行了7次这个操作，证明index始终比循环的操作次数大1，如执行第0次循环，index=1,执行第一次循环，index等于2，即跳出来的index值始终比循环的次数大1，即index等于6，证明执行了0-5（6次循环），不是0-6,7次循环。  
（2)、辅助空间  
由于我们这个算法需要申请一个数组来存储，nums中的非零元素。  
**方法2**：  
不使用辅助空间，直接在上面进行操作  
思路：  
方法1：  
设置两个指针，一个i用于遍历数组，一个k用于记录数组中的非零元素，当发现非0元素时，我们将k指针右移一个单位，直接将这个非0元素赋予给k，（表明找到一个元素），并且i指针继续向前，如果为0，则不替换，i指针继续遍历。直到i指针遍历完成，然后将其余的元素替换为0

#方法1：
    class Solution(object):
        def moveZeroes(self, nums):
            """
            :type nums: List[int]
            :rtype: None Do not return anything, modify nums in-place instead.
            """
            i = 0  # 用于遍历数组
            k = -1  # 用于记录数组中的非零元素
            while i < len(nums):
                if nums[i] == 0:
                    i += 1
                else:  # nums[i]不等于0
                    k += 1
                    nums[k] = nums[i]
                    i += 1
            while k < len(nums)-1:  # 从k指标的下一个元素开始循环，直到最后一个元素
                k = k + 1
                nums[k] = 0
            return nums

时间复杂度：o(n)  
空间复杂度：o(1)  
方法3：我们还可以在2的基础上进行优化，我们在i指针遍历完成以后要将k指针后面的元素替换为0，我们可以在之前利用交换的方法来优化整个操作

class Solution(object):
        def moveZeroes(self, nums):
            """
            :type nums: List[int]
            :rtype: None Do not return anything, modify nums in-place instead.
            """
            i = 0  # 用于遍历数组
            k = -1  # 用于记录数组中的非零元素
            while i < len(nums):
                if nums[i] == 0:
                    i += 1
                else:  # nums[i]不等于0
                    k += 1
                    nums[i],nums[k] =nums[k],nums[i]
                    i += 1
            return nums

试题3：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]

class Solution(object):
        def removeElement(self, nums, val):
            """
            :type nums: List[int]
            :type val: int
            :rtype: int
            """
            i=0#遍历整个数组的指针
            k=-1#第[0.k]全为非val的值
            while i<len(nums): #当i超出nums数组范围时 终止循环
                if nums[i]==val:
                    i+=1
                else: #nums[i]!=value
                    k+=1
                    if i!=k:
                        nums[i],nums[k]=nums[k],nums[i]
                    else:
                        pass
                    i+=1
            #print(k)
            return len(nums[0:k+1])

难点：  
（1）必须在原数组下完成，即不能申请额外的数组空间  
（2）这题也不能使用del 函数，因为，每次del相当于遍历了一遍数组，且会改变数组的装态  
（3）我们在将列表切片时，注意：a\[1:3\]，是不包含a\[3\]这个元素的  
解析：同样设置两个指标，一个进行全数组遍历，一个进行记录非val的值，使得\[0,k\]都为非val值，再进行切片即可。  
试题4：调整数组种奇数和偶数的位置  
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。  
如：  
\[1,2,3,4,5,6,7\]  
排序后：  
\[1, 3, 5, 7, 2, 4, 6\]

class Solution:
        #不用保持相对位置不变的，使用双指针法即可
        def reOrderArray(self, array):
            # write code here
            i,j=0,len(array)-1
            while True:
                if i==j:
                    break
                if array[i]&1==1:
                    i+=1
                else:
                    if array[j]&1==0:
                        j-=1
                    else:
                        array[j],array[i]=array[i],array[j]
            return array
        #要保持相对位置不变的，采用两个数组实现
        def reOrderArray2(self,array):
            array1=[]
            array2=[]
            while array:
                u=array.pop(0)
                if u&1==1:
                    array1.append(u)
                else:
                    array2.append(u)
            array1.extend(array2)
            return array1
    #测试
    print(Solution().reOrderArray([1,2,3,4,5,6,7]))
    print(Solution().reOrderArray2([1,2,3,4,5,6,7]))

解析：这里用了两种方法，一种是使用双指针，时间复杂度为O(n)，但是不能保证排序后相对位置不变，第二种方法申请了额外的辅助空间，为O(n)，但是可以保持数字排序后相对位置不变  
二、数组寻找问题  
试题1：寻找数组中的重复数字  
输入一个数组的长度n，和n个整数，这n个整数都在0-n-1的范围内，输出其中的重复数字，但是要求时间复杂度为O(n),空间复杂度为O(1).  
示例：  
输入  
7  
2 3 1 0 2 5 3  
输出：2 3  
解析：这道题目的难点在于要求空间复杂度为O(1),如果是将数字存为字典的形式，可以采用时间复杂度为o(n)，空间复杂度为o(1)来解决这个题目，但是要求空间复杂度为o(1),代表要在原数组进行修改。

"""例题1:寻找数组的重复元素"""
    n=int(input())
    a=list(map(int,input().split()))
    #print(n)
    #print(a)
    """设置指标i进行数组的遍历，设置指标j，使得j==list[i]，即j始终等于i下标的元素"""
    i=0
    j=-1
    while i<n:
        #print("循环开始")
        while a[i]!=i:
            #print("第二层循环")
            j = a[i]
            a[j],a[i] = a[i],a[j]
            #print(a[i],a[j])
            if a[i] == a[j]:
                print(a[i], end=" ")
            break
        i+=1

试题2：统计数组中给定的重复出现的元素  
给定一个已经排序好的数组及数字，统计数组中这个元素出现了多少次，如果数组中没有这个元素则返回0。

#统计数字k在排序数组中出现的次数
    list1=[1,2,3,4,5,2,3,2]
    print(list1.count(2))
    print(list1.count(2))
    利用count函数

试题3：寻找数组中数值和下标相等的元素  
给定一个递增的数组，且里面的所有值都是唯一的，编写一个函数找出其中数值和等于其下标的元素相等的元素

#方法1：时间复杂度为o(n)的做法
    def GetNumberSameAsindex(list1):
        n=len(list1)
        if n==0:
            return
        count=0
        for i in range(n):
            if count==list1[i]:
                return list1[i]
            else:
                count+=1
        return print("无此类数字")
    list1=[-3,-1,1,3,5]
    print(GetNumberSameAsindex(list1))
    
    #方法2：利用二分搜索的方式进行数字的查找
    class solution:
        def __init__(self):
            self.count=0
        def GetNumberSameAsindex(self,list1):
            num=self.half_search(list1)
            return num
        def half_search(self,list1):
            n=len(list1)
            if n==0:
                return print("无此类数字")
            if n==1:
                if list1[0]==self.count:
                    return list1[0]
                else:
                    return 
            mid=n//2
            if self.count+mid==list1[mid]:
                return list1[mid]
            if self.count+mid>list1[mid]:
                self.count+=mid+1
                return self.half_search(list1[mid+1:])
            if self.count+mid<list1[mid]:
                return self.half_search(list1[:mid])
    ##测试
    list1=[-3,-1,1,3,5]
    list2=[-3,-2,1,3,4]
    
    print(solution().GetNumberSameAsindex(list1))
    print(solution().GetNumberSameAsindex(list2))
    ##结果：
    3
    4

三、数组的输出问题  
例1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]  
例如：  
输入：  
4 4  
3 4 5 6  
输出：  
1  
2  
3  
1

解法：  
首先我们先对得到的数组进行排序，排序完之后进行去重处理，这时我们判断，这个数组是不是0数组，如果是直接print(0),否则比较去重之后的数组长度与k的值，  
如果k值大于数组长度，则我们最后肯定会输出0  
如果k值小于数组长度，则我们最后循环k次  
我们通过找规律会发现，每一次进行，进行循环除了第一次输出的值是第一个值之外，每次输出的值都为去重后的列表的后一个值-前一个值。  
所以：我们只需要不断print(i) i从1到k，时间复杂度o（nlogn）,因为有排序

num,k=map(int,input().split())
    list1=list(map(int,input().split()))
    list1.sort
    list2=list(set(list1))
    if list2[0]==0 and list2[-1]==0:
            print(0)
    else:
        print(list2[0])
    for i in range(1,k):
        print(list2[i]-list2[i-1])

四、列表常见考题  
例1：如何求数组的所有子集  
给定一个字符串，求其中的全部子集，如给定‘abc’,求解子集为a,b,c,ab,ac,bc,abc.子集个数与原字符串中元素个数的关系为：Sn=2^n-1.  
代码：

#求集合中的全部子集
    class solution:
        def getAllsubset(self,str):
            if str==None or len(str)==1:
                return
            arr=[]
            length=len(str)
            i=0
            while i<length-1:
                #print(arr)
                str1=str[i]
                arr.append(str1)
                length2=len(arr)
                j = 0
                while j<length2:
                    arr.append(arr[j]+str[i+1])
                    j+=1
                i+=1
            arr.append(str[-1])
            return arr
    print(solution().getAllsubset("abc"))
    print(solution().getAllsubset("abcdef"))

解析： 采用蛮力法  
每次向列表中添加一个字符串元素，每次循环时都是原字符串中所有字符串加上后面的元素，然后将所有字符串归入列表中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 3]  
例2：求数组中出现次数超过一半的数字

numbers=[1,2,3,2,2,2,2,5,4]
    class Solution:
        def MoreThanHalfNum_Solution(self, numbers):
            # write code here
            if len(numbers)==0:
                return
            length=len(numbers)
            times=1
            result=numbers[0]
            for i in range(1,length):
                #print(i)
                if times==0:
                    result=numbers[i]
                    times=1
                elif numbers[i]==result:
                    times+=1
                else:
                    if numbers[i]!=result:
                        times-=1
                #print(times,result)
            #通过上述检验，result保留的值可能是几种可能的数，一、出现次数大于一半的数
            #因为只有出现次数大于一半，才有可能在正负相消中被保留下来 二、前一个次数为
            #0的数，及上次循环为result=3,times=0,下一次循环的数不等于三（假如为4），则
            #变为4,1。三、上一次循环为times=1,这次循环两者又不相等，times变为0
            #综上所述，最后一个数字可能是次数超过一半的数字，也可能是别的数字，最后要对
            #这个数字进行次数统计如果次数大于一半则返回这个数字否则。返回None
            if self.count_than_half(numbers,result):
                return result
            return
        def count_than_half(self,numbers,result):
            times=0
            for i in numbers:
                if result==i:
                    times+=1
            if times*2>len(numbers):
                return True
            else:
                return False
    print(Solution().MoreThanHalfNum_Solution(numbers))

解析：找出出现次数超过一半的数字，那么这个数字一定比其他所有数组出现的次数加起来都要多，比如数组\[2,2,2,3\],2是出现次数大于一半的数字，那么一定比其他所有数字出现次数的总和更多，所以这里我们可以进行保存两个值result 数字,times次数,如果遍历时，result等于当前遍历的数字，则times+=1,否则times-=1,当times=0时下一次循环时将其替换为数组中的下一个数。  
例1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]  
例如：  
输入：  
4 4  
3 4 5 6  
输出：  
1  
2  
3  
1

二、排序及问题  
1、求一个数组中第k大的元素是多少。如输入\[1,2,3,4,5\],第二大的元素为2.

class solution:
        def partion(self,arr):
            p=arr[0]
            left=[i for i in arr[1:] if i<=p]
            right=[i for i in arr[1:] if i>p]
            return (left,right,p)
        def find_k(self,arr,k):
            if len(arr)==0:
                return
            self.pos=0
            left,right,p = self.partion(arr)
            self.pos+=len(left)+1
            #print(self.pos)
            while self.pos!=k:
                if self.pos>k:
                    left,right,p=self.partion(left)
                    self.pos=self.pos-len(right)-1
                else: #self.pos<k
                    left,right,p=self.partion(right)
                    self.pos+=len(left)+1
            return p
    print(solution().find_k([7,7,3,11,1,1,9,9],2))
    print(solution().find_k([7,7,5,3,11,1,1,1,9,9],5))
    print(solution().find_k([2,2,3,2,1,2,3],3))
    print(solution().find_k([1,2,3,4,5,6],5))
    ##结果：
    1
    5
    2
    5

解析 ：求数组中第k大的元素，可以采用快速排序中的分治，即以第一个数为标杆，将数组分为小于这个数和大于这个数的数组，并根据分组后的长度来计算其位置信息，注意：每次以开头的数为标杆，但是搜索的话是从后一位开始搜索。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 4]

三、时间效率、空间效率的计算  
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。  
代码：  
方法1;

class Solution:
        def GetUglyNumber_Solution(self, index):
            i,j=1,2
            while i<index:
                if self.isugly(j):
                    i+=1
                j+=1
                #print(i,j)
            return j
        def isugly(self,num):
            if num<0:
                return False
            i=2
            while True:
                num1=num%i
                if num1!=0:
                    break
                num/=i
                if num1==0 and num==1:
                    return True
            i=3
            while True:
                num1=num%i
                if num1!=0:
                    break
                num/=i
                if num1==0 and num==1:
                    return True
            i=5
            while True:
                num1=num%i
                if num1!=0:
                    break
                num/=i
                if num1==0 and num==1:
                    return True
                else:
                    return False

解析：先写程序判断这个数是不是丑数，可以知道，如果能被2、3、5除尽，或者这个数能依次被2、3、5整除，那么这个数是丑数，比如10.10%2=0，5%2除不尽，则5%3除不尽，则5%5可以除尽，则10是一个丑数，那么7就不行。  
然后从1开始递增，判断哪些是丑数，判断依次，计算器加1，但是这个方法计算了很多不是丑数的数，时间效率太慢了。  
方法2：前面的算法效率低的原因在于这个算法把是否是丑数的都考虑了，但其实我们通过观察可以发现，丑数都是丑数乘以2，3，5得来的，比如4是由2*2，8是由4*2，所以可以考虑算法通过丑数推出丑数，将数组中已经存储的最大丑数记作M，则将其中每个丑数乘以2，在乘以2的时候，如果得到的数小于等于M，则肯定已经在丑数中不再进行考虑。我们只需要得到第一个大于M的三个数，即M2，M3，M5，找出这三者的最小值作为一个新的丑数加入数组，不断重复这个过程，来扩充数组，其中找出M2、M3、M5我们采用三个指针t2,t3,t5来实现。t2指向数组中乘以2刚好大于数组中临界值的数，t3指向数组中乘以3大于临界值的数，同理t5，这样不断从原来的数组中找出最小的丑数加入数组，循环index次便能找出第N大的丑数。

class Solution:    
        def GetUglyNumber_Solution(self, index):
            if index<1:
                return
            arr=[1]
            t2=t3=t5=0
            i=1
            while True:
                #选出当前所有丑数中乘以2，乘以3，乘以5刚好大于数组的最大数的结果
                min_num=min(arr[t2]*2,arr[t3]*3,arr[t5]*5)
                arr.append(min_num)
            
                while arr[t2]*2<=min_num:
                    #使t2所指为超过数组最大值的最小值
                    t2+=1
                while arr[t3]*3<=min_num:
                    #使t3所指为超过数组最大值的最小值
                    t3+=1
                while arr[t5]*5<=min_num:
                    #使t5所指为超过数组最大值的最小值
                    t5+=1
                #每循环一次找一次最大值
                i+=1
                if i==index:
                    break
                #print(arr)
            return arr[-1]
                                              
    print(Solution().GetUglyNumber_Solution(6))
    print(Solution().GetUglyNumber_Solution(1500))
    #结果
    6
    85996339

习题4：寻找一列数据组中固定长度的数组的最小和为多少  
输入：  
第一行：数组长度、需要选取的数组长度  
第二行：一个数组  
输出：固定数组长度的起始位置

例：  
7 1  
1,2,6,1,1,7,1

import numpy as np
    list1=[1,2,6,1,1,7,1]
    n=7
    m=1
            
    class solution:
        def search_len(self,n,m,list1):
            min_num=np.inf
            pos=-1
            for i in range(len(list1)-m+1):
                if i==0:
                    list2=list1[i:i+m]
                    num=sum(list2)
                else:
                    self.start=list1[i-1]
                    num=num-self.start
                    num+=list1[i+m-1]
                if min_num>num:
                  min_num=num
                  pos=i
            return pos+1
    solution().search_len(n,m,list1)  
    while True:
        try:
            list1=list(map(int,input().split()))
            m,n=list1[0],list1[1]
            list2=list(map(int,input().split()))
            print(solution().search_len(m,n,list2))          
        except:
            break

解析：做这道题的关键在于计算固定长度数组的数组和，然后记下每个数组和对应起始位置，选择最小的数组和和对应的起始索引。但是这样做的话，至少要计算n-m+1次m个数的和，有没有优化的算法呢，有，就是只计算第一个固定数组和，后面的数组和利用减去前一个数组和的第一个数和加上最新数组和的最后一个数即可。

习题5：将10进制转换为二进制并计算二进制中101的个数

"""
    给一个10进制的数
    将其转化为二进制，从最右边开始算第0位,从右向左计算101的个数，
    返回101的个数和起始的位数
    输入:21
    0000 0000 0001 0101
    输出:2 0
    
    输入：6
    0000 0000 0000 0110
    输出
    0 -1
    
    输入：-16
    二进制的负数比较特别
    -16的编码为  1000 0000 0001 0000（最前面1是符号位）
    -16的反码为  1111 1111 1110 1111
    -16的补码位  1000 0000 0001 0000
    输出：
    0 -1
    
    输入：-5
    原码：1000 0000 0000 0101
    反码：1111 1111 1111 1010
    补码：1111 1111 1111 1011
    """
    def num_to_two(num):
        num=num    
        arr=[]
        while num!=1:
            num1=num%2
            num=num//2
            arr.append(str(num1))
        arr.append(str(1))
        #print(arr)
        str1=('').join(arr[::-1])
        str1='0'*(16-len(arr))+str1
        return str1
    def str_replace(str1,i,str2):
        str1=list(str1)
        str1[i]=str2
        return ("").join(str1)
    
    def num_to_two1(num):
        num=abs(num)
        num1=num_to_two(num)
        num1='1'+'0'*(15-len(num1))+num1        
        for i in range(1,len(num1)):
            if num1[i]=='0':
                str_replace(num1,i,'1')
            if num1[i]=='1':
                str_replace(num1,i,'0')
        if num1[-1]=='0':
            str_replace(num1,len(num1)-1,'1')
        else:
            for i in range(1,len(num1)-1):
                if num1[i]=='0':
                    str_replace(num1,i,'1')
                if num1[i]=='1':
                    str_replace(num1,i,'0')
            str_replace(num1,len(num1)-1,'0')
        return num1
    
    def count_101(str1):
        arr=[]
        n=len(str1)
        triger=[]
        count=0
        str1=str1[::-1]
        pos=-1
        for i in range(len(str1)):
            if str1[i]=='1':
                if i+2<=len(str1):
                    str2=str1[i:i+3]
                    if str2=='101':
                        count+=1
                        triger.append(i)
        if triger==[]:
            pos=-1
        else:
            pos=triger[0]
        return count,pos
    while True:
        try:
            list1=list(map(int,input().split()))
            num=list1[0]
            #num=-16
            if num>0:
                print(1)
                num1=num_to_two(num)
                print(num1)
                count,pos=count_101(num1)
                print(count,' ',pos)
            if num==0:
                print(2)
                print(0,' ',-1)
            if num<0:
                print(3)
                num1=num_to_two1(num)
                print(num1)
                count,pos=count_101(num1)
                print(count,' ',pos)
        except:
            break

习题6：将姓名排序

"""
    输入多行，每行两个单词，代表人的姓和名
    将这些人的名字按照一定的顺序排序
    首先先按照这些人的姓出现的次数排序
    其次如果两人的姓出现的一样多，按照名单出现的顺序排序
    例：
    输入：
    zhang san
    li si
    wang wu
    wang liu 
    wang qi
    zhang wu
    li wu 
    输出：
    wang wu
    wang liu 
    wang qi
    zhang san
    li si
    zhang wu
    li wu
    """
    #方法2：
    arr=[]
    while True:
        try:
            list1=list(input().split())
            if list1==[]:
                break
            arr.append(list1)
            #print(arr)
            arr
            list1=arr.copy()
            list2=[i for i in range(len(list1))]
            dict1={
        }
            for i in list1:
                dict1[i[0]]=dict1.get(i[0],0)+1
            list3=[dict1[i[0]] for i in list1]
            for i in range(len(list1)-1):
                for j in range(i+1,len(list1)):
                    if list3[j]>list3[i]:
                        list1[i],list1[j]=list1[j],list1[i]
                        list3[i],list3[j]=list3[j],list3[i]
                        list2[i],list2[j]=list2[j],list2[i]
                    if list3[j]==list3[i]:
                        if list2[j]<list2[i]:
                            list1[i],list1[j]=list1[j],list1[i]
                            list2[i],list2[j]=list2[j],list2[i]
                            list3[i],list3[j]=list3[j],list3[i]
            print(list1)
        except:
            break

2、求解股票收益的最大值

'''
    求解股票的最大利润
    给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
    如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
    注意你不能在买入股票前卖出股票。
    例1：
    输入: [7,1,5,3,6,4]
    输出: 5
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
         注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
    示例 2:
    
    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
    '''
    
    from math import *
    list1=[7,1,5,3,6,4]
    list1=[7,6,4,3,1]
    list1=input().split()
    list1=[]
    def max_get(list1):
        if list1==[]:
            return 0
        min_num=inf
        max_get=-inf
        buyer_index=-1
        seller_index=-1
        for index,value in enumerate(list1):
            if value<min_num:
                min_num=value
                buyer_index=index
            num1=value-min_num
            if num1>max_get:
                seller_index=index
                max_get=num1
        return max_get
    #max_get(list1)
    '''
    解析：
    当扫描到第i个数字的时候，min记住前min中的最小值，就可算出在当前价位卖出时可能得到的最大利润。
    然后输出最大利润
    '''   
    '''
    题目2：如果可以交易两次怎么计算呢
    例3：
    list1=[2,1,3,6,7,2,5,3,2,9,2,3]
    输出：13
    '''
    list1=[2,1,3,6,7,2,5,3,2,9,2,3]
    max_profit=-inf
    for i in range(len(list1)):
        get1=max_get(list1[:i])
        get2=max_get(list1[i:])
        if (get1+get2)>max_profit:
            max_profit=get1+get2
    print(max_profit)
    '解析：交易两次,将交易数从中分割成两个列表，求两个列表的收益和最大'

习题8：求两个坐标点之间能否形成最大、最小区间  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 7]

#方法1：循环法，分别求出所有数字组合，看是否能形成包含原数组的最大最小区间，如果能
    #n+=1，缺点我们发现这个算法需要对数组进行o（n**2）的查找，时间复杂度过高
    num=int(input())
    list1 = list(map(int,input().strip().split()))
    list1=[abs(i) for i in list1]
    list1.sort()
    n=0
    for i in :
        for j in range(i+1,num):
            print(i,j)
            num1= abs(list1[i]+list1[j])
            num2= abs(list1[i]-list1[j])
            num3= max(list1[i],list1[j])
            num4= min(list1[i],list1[j])
            if num2<=num4:
                print(list1[i],list1[j])
                n+=1
            else:
                break
    print(n)
    
    #方法2：
    '''
    对于我们可以尝试找找规律，我们发现[1,2]这个区间1+2必定大于2，所以只用考虑下半部分，
    那么2-1要大于1的条件是什么呢，就是这个区间的上限不能大于2*下限，
    比如[1,3] 3>1*2,所以不行，我们将原数组取绝对值再顺序排列，
    如[1,2,5,7,10,10,11,19],
    1、首先从当前数向后找<=i*2的数
    2、利用start_positon,last_position记录元素的重复值
    3、用last_position-i得到当前符合条件的元素长度，用count记
    4、用count1记录元素的重复个数，当重复时start_position和last_position指向统一个位置
    5、如果循环的元素j>max_num,后面的元素不用找了
    6、如果两者
    '''
    num=int(input())
    list1 = list(map(int,input().strip().split()))
    list1=[abs(i) for i in list1]
    list1.sort()
    if num==2:
        a,b=list1[0],list1[1]
        if b-a<=a and b+a>=b:
            print(1)
        else:
            print(0)
    else:
        n=0
        count=0 #计算每一次有几个数在区间内
        count1=0 #计算元素的重复个数
        last_position=0 #指向重复元素的最后一个位置
        start_position=0 #重复元素的第一个位置
        for i in range(num-1):
            num1=list1[i]
            max_num=num1*2
            for j in range(start_position,num):
                if j==i:
                    continue
                if list1[j]<=max_num:
                    if list1[j]==list1[j-1]: #判断当前元素是否重复
                        count1+=1
                        last_position=j
                    else:
                        start_position=j
                        last_position=j
                        count1=0
                    print('当前元素为',list1[j],'start_position',start_position,'last_positon',last_position)
                else:#当前元素比之前大
                    break
                if start_position+1==num: 
                    #start_position为最后一个元素,start_postion不能再继续向后推进了
                    start_position-=1                    
            count=last_position-i
            print(count)
            n+=count
    print(n) 
    ##测试
    num=7
    list1=[1,2,2,3,4,8,10]
    num=6
    list1=[1,2,3,4,5,6]

腾讯笔试题8：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 8]  
腾讯笔试题2：

'''
    腾讯笔试题2：
    有两个数组，A,B,分别含有m和n个元素，其中元素有正有负
    从A中拿走一个元素，在最坏情况下A中剩余的元素
    与B中某个元素之积最大为多少
    输入：
    n,m
    A1,A2,A3,...Am
    B1,B2,B3...Bn
    
    2 2
    20 18
    2 14
    输出：252
    拿走的时20，18*14=252
    
    5 3
    -1 0 1 2 3
    -1 0 1
    输出：2
    拿走3 输出1*2=2
    思路：我们可以发现最终乘积的数都是其中的两边的最大值，次大值，最小值，次小值
    求的数最大，那么B中要么取出最大值，要么取出最小值
    如例2中取出 min=-1 max=1
    对于A来说，最大的值是 -1*-1=1 或者 -1*3=-3 或者 1*-1=-1 或者 1*3=3
    那么取走最有利的数为3，这时我们发现，最大值和最小值可能依然留在A中，因为
    不知道最大情况是B中的最大值还是最小值，所以我们还需要将A中次小的，和次大的
    取出来加入原来的数组进行比较 次小0 次大2
    0*-1=0 0*1=0 2*-1=-2 2*1=2
    最终最大的可能性是2
    当然这是n>=4时的情况,因为要取出两个最大、最小
    当n<=4时可以采取保留的遍历法
    测试：
    5,3
    [-2,-1,0,1,3]
    [-2,0,1]
    输出：3
    '''
    n, m = input().split()
    line1 = list(map(int,input().split()))
    line2 = list(map(int,input().split()))
    
    arr=[]
    if len(line1) == 2:
        a1,b1=line1[0],line1[1]
        A1= max(line2)
        B1= min(line2)
        arr.append(a1*A1)
        arr.append(a1*B1)
        arr.append(b1*A1)
        arr.append(b1*B1)
        s = max(arr)
        arr.remove(s)
        print(max(arr))
    
    if len(line1) == 3:
        line1.sort()
        a1,b1,c1=line1[0],line[1],line[2]
        A1= max(line2)
        B1= min(line2)
        arr.append(a1* A1)
        arr.append(a1* B1)
        arr.append(b1* A1)
        arr.append(b1* B1)
        arr.append(c1* A1)
        arr.append(c1* B1)
        s = max(arr)
        arr.remove(s)
        print(max(arr))
    
    if len(line1) >= 4:
        a=max(line1)
        line1.remove(a)
        b=min(line1)
        line1.remove(b)
        c=max(line2)
        d=min(line2)
        arr.append(a*c)        
        arr.append(a*d)        
        arr.append(b*c)        
        arr.append(b*d)
        num1=max(arr)
        arr.remove(num1)
        A=max(line1)        
        B=min(line1)
        arr.append(A*c)        
        arr.append(A*d)        
        arr.append(B*c)        
        arr.append(B*c)
        print(max(arr))

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]: /images/20220219/065e16cf3d604d539d7cd02b0d8b34e7.png
[20190415164331175.png]: /images/20220219/a1e3a2b8d58049e38fd6b765d29708d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]: /images/20220219/c3a50bd3223247f1a69a13dd3aafdc14.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]: /images/20220219/f1361079844e4a669cd094dabf78dd84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 3]: /images/20220219/917bd09e232e444ba598fc920832d028.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 4]: /images/20220219/cbb605d5cd1b43dd8a2b7b96ea8972dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 5]: /images/20220219/e82611512fc24076bc97cff1c16a19bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 6]: /images/20220219/d58da329a5aa4d89b954ed6abff628ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 7]: /images/20220219/914f471eb82f45d2810c4857fffb35ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 8]: /images/20220219/f5877eefe34a47efa8a044049b1bfb7a.png