2021年3月3日

1、给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        results = [0]
        if num == 0:
            return results
        for i in range(1, num+1):
            # 如果i是偶数，它二进制中1的位数和i/2的位数是一样的
            if i % 2 == 0:
                results.append(results[i/2])
            else:
                results.append(results[i-1] + 1)
        return results

2、给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in nums:
            if (target - i) in nums[nums.index(i)+1: len(nums)]:
                return [nums.index(i), nums.index(target - i, nums.index(i)+1, len(nums))]
        return null

3、请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）

class MyQueue(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack_1 = MyStack()
        self.stack_2 = MyStack()
        self.size = 0

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        if self.stack_1.getSize() == -1:
            self.stack_2.pushToTop(x)
        else:
            self.stack_1.pushToTop(x)
        self.size += 1

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if self.stack_1.isEmpty():
            # 如果栈1空，说明元素都在栈2中，需要把元素都放进栈1中然后去除顶层元素
            for i in range(self.stack_2.len_1 + 1):
                self.stack_1.pushToTop(self.stack_2.popFromTop())
            ret = self.stack_1.popFromTop()
            for i in range(self.stack_1.len_1 + 1):
                self.stack_2.pushToTop(self.stack_1.popFromTop())
        else:
            # 如果栈2空，说明元素都在栈1中，需要把元素都放进栈2中然后去除顶层元素
            for i in range(self.stack_1.len_1 + 1):
                self.stack_2.pushToTop(self.stack_1.popFromTop())
            ret = self.stack_2.popFromTop()
            for i in range(self.stack_2.len_1 + 1):
                self.stack_1.pushToTop(self.stack_2.popFromTop())
        self.size -= 1
        return ret

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if self.stack_1.isEmpty():
            # 如果栈1空，说明元素都在栈2中，需要把元素都放进栈1中然后去除顶层元素
            for i in range(self.stack_2.len_1 + 1):
                self.stack_1.pushToTop(self.stack_2.popFromTop())
            ret = self.stack_1.peek()
            for i in range(self.stack_1.len_1 + 1):
                self.stack_2.pushToTop(self.stack_1.popFromTop())
            return ret
        else:
            # 如果栈2空，说明元素都在栈1中，需要把元素都放进栈2中然后去除顶层元素
            for i in range(self.stack_1.len_1 + 1):
                self.stack_2.pushToTop(self.stack_1.popFromTop())
            ret = self.stack_2.peek()
            for i in range(self.stack_2.len_1 + 1):
                self.stack_1.pushToTop(self.stack_2.popFromTop())
            return ret

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        if self.size == 0:
            return True
        else:
            return False


class MyStack:

    def __init__(self):
        # 模拟栈和栈顶指针
        self.list_1 = []
        self.len_1 = -1

    def pushToTop(self, n):
        self.list_1.append(n)
        self.len_1 += 1

    def peek(self):
        if self.isEmpty():
            return "栈空，无法输出栈顶元素！"
        else:
            return self.list_1[self.len_1]

    def popFromTop(self):
        if self.isEmpty():
            return "栈空，无法取出栈顶元素！"
        else:
            param = self.list_1.pop(self.len_1)
            self.len_1 -= 1
            return param

    def getSize(self):
        return self.len_1

    def isEmpty(self):
        if self.len_1 == -1:
            return True
        else:
            return False



# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

4、给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

# 暴力算法
class Solution(object):
    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        count = -1
        nums_len = len(nums)
        ret = []
        for i in nums:
            # 当前元素的下标
            count += 1
            # 记录往后遍历的元素的下表
            inner_count = count + 1
            # 当遍历下表等于当前元素下标时循环停止
            while inner_count % nums_len != count:
                if nums[inner_count % nums_len] > i:
                    ret.append(nums[inner_count % nums_len])
                    break
                inner_count += 1
            if inner_count % nums_len == count:
                ret.append(-1)
        return ret

#基于单调栈，直接运行即可看到运行过程一级结果
class Solution(object):

    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 单调栈
        stack = []
        nums_len = len(nums)
        ret = [-1]*nums_len
        for i in range(len(nums)*2):
            if (len(stack) == 0) or (nums[stack[-1]] > nums[i % nums_len]) or (nums[stack[-1]] == nums[i % nums_len]):
                print("=====================")
                print("栈空或者栈顶元素大于当前遍历元素，把元素压入栈中")
                stack.append(i % nums_len)
                print("输入的数组为：", nums)
                print("stack长度：", len(stack))
                print("栈顶元素大小为：", nums[stack[-1]])
                print("当前循环元素为：", nums[i % nums_len])
                print("stack:", stack)
            elif (len(stack) != 0) & (nums[stack[-1]] < nums[i % nums_len]):
                print("=====================")
                print("输入的数组为：", nums)
                print("stack长度：", len(stack))
                print("栈顶元素大小为：", nums[stack[-1]])
                print("当前循环元素为：", nums[i % nums_len])
                print("stack:", stack)
                while len(stack) != 0 and nums[stack[-1]] < nums[i % nums_len]:
                    print("=====================")
                    print("输入的数组为：", nums)
                    print("正在循环出栈")
                    print("当前stack长度：", len(stack))
                    print("栈顶元素大小为：", nums[stack[-1]])
                    print("当前循环元素为：", nums[i % nums_len])
                    ret[stack.pop()] = nums[i % nums_len]
                    print("stack:", stack)
                stack.append(i % nums_len)
            print("===============")
            print("遍历第", i, "次完成，stack当前状态为", stack)
            print("当前ret为：", ret)
        return ret


if __name__ == "__main__":
    solution = Solution()
    print(solution.nextGreaterElements([1, 2, 1]))