栈的反转、滑动窗口、数组变树

迈不过友情╰ 2022-06-09 02:26 48阅读 0赞

*   *   *  栈的反转
         *  滑动窗口
         *  数组变树

--------------------

### 栈的反转 ###

实现一个栈的逆序，但是只能用递归函数和这个栈本身的pop操作来实现，而不能自己申请另外的数据结构。

给定一个整数数组A即为给定的栈，同时给定它的大小n，请返回逆序后的栈。

测试样例：
    [4,3,2,1],4
    返回：[1,2,3,4]

**我的提交**

# -*- coding:utf-8 -*-
    
    class StackReverse:
        def reverseStack(self, A, n):
            # write code here
            if n == 0:
                return
            last = self.getLast(A, n)
            self.reverseStack(A, n - 1)
            A.append(last)
            return A
    
        def getLast(self, A, n):
            result = A.pop()
            if (n-1) == 0:
                return result
            last = self.getLast(A, n-1)
            A.append(result)
            return last
    
    if __name__ == '__main__':
        r= StackReverse()
        print(r.reverseStack([230,272,224,399,126],5))

--------------------

### 滑动窗口 ###

有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。 返回一个长度为n-w+1的数组res，res\[i\]表示每一种窗口状态下的最大值。 以数组为\[4,3,5,4,3,3,6,7\]，w=3为例。因为第一个窗口\[4,3,5\]的最大值为5，第二个窗口\[3,5,4\]的最大值为5，第三个窗口\[5,4,3\]的最大值为5。第四个窗口\[4,3,3\]的最大值为4。第五个窗口\[3,3,6\]的最大值为6。第六个窗口\[3,6,7\]的最大值为7。所以最终返回\[5,5,5,4,6,7\]。

给定整形数组arr及它的大小n，同时给定w，请返回res数组。保证w小于等于n，同时保证数组大小小于等于500。

测试样例：
    [4,3,5,4,3,3,6,7],8,3
    返回：[5,5,5,4,6,7]

**我的提交**

# -*- coding:utf-8 -*-
    
    class SlideWindow:
        def slide(self, arr, n, w):
            # write code here
            indexs = []
            result = []
    
            for i in range( n):
                if not indexs or arr[indexs[-1]] > arr[i]:
                    indexs.append(i)
                else:
                    while indexs and arr[indexs[-1]] <= arr[i]:
                        indexs.pop()
                    indexs.append(i)
                # print("i = " + str(i) + " --> " + str(indexs)) 
                if i >= (w - 1):
                    while indexs and (i - indexs[0]) >= w:
                        indexs.pop(0)
                    result.append(arr[indexs[0]])
            return result
    
    if __name__ == '__main__':
        slide = SlideWindow()
        print(slide.slide([4,3,5,4,3,3,6,7],8,3))

--------------------

### 数组变树 ###

对于一个没有重复元素的整数数组，请用其中元素构造一棵MaxTree，MaxTree定义为一棵二叉树，其中的节点与数组元素一一对应，同时对于MaxTree的每棵子树，它的根的元素值为子树的最大值。现有一建树方法，对于数组中的每个元素，其在树中的父亲为数组中它左边比它大的第一个数和右边比它大的第一个数中更小的一个。若两边都不存在比它大的数，那么它就是树根。请设计O(n)的算法实现这个方法。

给定一个无重复元素的数组A和它的大小n，请返回一个数组，其中每个元素为原数组中对应位置元素在树中的父亲节点的编号，若为根则值为-1。

测试样例：
    [3,1,4,2],4
    返回：[2,0,-1,2]

> 参考： [http://blog.csdn.net/sinat\_28108651/article/details/51781867][http_blog.csdn.net_sinat_28108651_article_details_51781867]

[http_blog.csdn.net_sinat_28108651_article_details_51781867]: http://blog.csdn.net/sinat_28108651/article/details/51781867