一.问题介绍

在排序数组中查找左右边界，可用于在排序数组中查找某个值出现的位置与次数等

二.刷题沉淀

①两个栈实现队列

# 类似于负负得正的思想，append时直接放入栈1，delete时如果栈2为空，那么把栈1移入栈2（负负得正，栈1最先放进去的最后弹出来，在栈2中最后放进去的最先弹出来），再pop栈2；如果原来栈2不为空，那么表示上次放入的还有剩（上次放入的一定比这次早），直接pop；如果移入后栈2仍为空，返回-1
class CQueue:

    def __init__(self):
        self.A,self.B = [],[]

    def appendTail(self, value: int) -> None:
        self.A.append(value)

    def deleteHead(self) -> int:
        if not self.B:
            if not self.A:
                return -1
            else:
                while self.A:
                    self.B.append(self.A.pop())
        
        return self.B.pop()


# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

②队列实现栈

# 双队列实现栈，等于把一个队列B存放之前的结果，把新的元素放入A后，再把B中之前的元素放入A
执行用时：32 ms, 在所有 Python3 提交中击败了94.87%的用户
内存消耗：15 MB, 在所有 Python3 提交中击败了35.37%的用户
from collections import deque
class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.A,self.B = deque(),deque()
        self.size = 0
    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.A.append(x)
        while self.B:
            self.A.append(self.B.popleft())
        self.A,self.B = self.B,self.A
        
        self.size += 1

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        self.size -= 1
        return self.B.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.B[0]

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return self.size == 0

# 单队列实现栈，存储原有元素数量n，把新元素放入队列中后，执行n次pop-append操作，把之前的元素重新放入队列中
执行用时：40 ms, 在所有 Python3 提交中击败了61.83%的用户
内存消耗：14.8 MB, 在所有 Python3 提交中击败了93.24%的用户
from collections import deque
class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.A = deque()
        self.size = 0
    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.A.append(x)

        n = self.size
        while n > 0:
            self.A.append(self.A.popleft())
            n -= 1
        
        self.size += 1

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        self.size -= 1
        return self.A.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.A[0]

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return self.size == 0

③字符串匹配——KMP

https://leetcode-cn.com/problems/implement-strstr/solution/zhe-ke-neng-shi-quan-wang-zui-xi-de-kmp-8zl57/
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        a=len(needle)
        b=len(haystack)
        if a==0:
            return 0
        next=self.getnext(a,needle)
        p=-1
        for j in range(b):
            while p>=0 and needle[p+1]!=haystack[j]:
                p=next[p]
            if needle[p+1]==haystack[j]:
                p+=1
            if p==a-1:
                return j-a+1
        return -1

    def getnext(self,a,needle):
        next=['' for i in range(a)]
        k=-1
        next[0]=k
        for i in range(1,len(needle)):
            while (k>-1 and needle[k+1]!=needle[i]):
                k=next[k]
            if needle[k+1]==needle[i]:
                k+=1
            next[i]=k
        return next

④摩尔投票——选出数组中超过半数的值

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # n = len(nums)

        # dic_nums = Counter(nums)
        # for key in dic_nums.keys():
        #     if dic_nums[key] > n/2:
        #         return key

        # return -1

        # 狼人杀归票算法
        # 第一轮找到最可能出局的那个人
        n = len(nums)
        ans = -1
        count = 0
        for num in nums:
            # 没有票数，暂时认为是当前的人
            if not count:
                ans = num
            # 有相同的人上票，票数加一；否则票数减一
            if num == ans:
                count += 1
            else:
                count -= 1
        # 第二轮确定这个人的票数确实过半
        return ans if count and nums.count(ans) > n // 2 else -1