牛客-编程题

（1）反转字符串

描述：写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

输入：

"abcd"

返回值：

"dcba"

 Python3版本：

class Solition:
    def solve(self,str):
        res = str[::-1]
        return res

（2）反转链表

描述：输入一个链表，反转链表后，输出新链表的表头。

输入：{1,2,3}

输出：{3,2,1}

 python3版本：

class Solution:
    def ReverseList(self,pHead):
            curr = pHead
            prv = None
            while curr is not None;
                    temp = curr.next
                    curr.next = prv
                    prv = curr
                    curr = temp
            return prv

说明：

 反转链表是指将链表的指针反转，这样子整个链表的方向就能反转:

第一步，现将后面的地址临时存起来（temp）

第二步，反转，就是将当前指针的next指向原来的前一项（prv）

第三步，去反转下一个元素，将保存的temp指向当前（curr）

 （3）排序题

描述：给定一个数组，请你编写一个函数，返回该数组排序后的形式。

输入：[5,2,3,1,4]

输出：[1,2,3,4,5]

（解法1）

直接采用集成函数

class Solution:
    def MySolution(self,arr):
        return sorted(arr)

(解法2)

快速排序算法

class Solution：
    def MySolution(self,arr):
        if len(arr) <= 2:
            return arr
        return self.quick_sort(arr)

    def quick_sort(self,arr):
        base = arr.pop(0)
        left = []
        right = []
        for i in arr:
            if i< base:
              left.append(i)
            else:
              right.append(i)
        return self.quick_sort(left)+[base]+self.quick_sort(right)
    return arr                  
                

                         

（解法3）

冒泡排序

class Solution:
    def MySolution(self,arr):
        return self.bubble.sort(arr)
    def bubble.sort(self,arr):
        for i in range(len(arr)-1):
            for j in range(len(arr)-i-1):
                if arr[j] > arr[j+1]
                    arr[j],arr[j+1] = arr[j+1],arr[j]
        return arr

(解法4)

插入排序

class Solution:
    def MySolution(self,arr):
        return self.insert_sort(arr)
    def insert_sort(self,arr):
        for i in range(1,len(arr)):
            key = arr[i]
            j = key-1
            while j >= 0 and arr[j]>key:
                arr[j+1] = arr[j]
                j = j-1
            arr[j+1] = key
        return arr

 （4）LRU缓存算法

　　说明LRU缓存：

　　LRU是一种常用的页面置换算法，在计算中，所有的文件操作都要放在内存中进行，然而计算机内存大小是固定的，所以我们不可能把所有的文件都加载到内存，因此我们需要制定一种策略对加入到内存中的文件进项选择。

常见的页面置换算法有如下几种：

• LRU 最近最久未使用
• FIFO 先进先出置换算法 类似队列
• OPT 最佳置换算法 （理想中存在的）
• NRU Clock置换算法
• LFU 最少使用置换算法
• PBA 页面缓冲算法

LRU原理

　　LRU的设计原理就是，当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。这就意味着，如果经常访问的数据，我们需要然其能够快速命中，而不常访问的数据，我们在容量超出限制内，要将其淘汰。

当我们的数据按照如下顺序进行访问时，LRU的工作原理如下：

　　正如上面图所表示的意思：每次访问的数据都会放在栈顶，当访问的数据不在内存中，且栈内数据存储满了，我们就要选择移除栈底的元素，因为在栈底部的数据访问的频率是比较低的。所以要将其淘汰。
Java实现引文链接：https://blog.csdn.net/qq_26440803/article/details/83795122

　　在软件或系统开发中，缓存总是必不可少，这是一种空间换时间的技术，通过将频繁访问的数据缓存起来，下一次访问时就可以快速获得期望的结果。

一个缓存系统，关键核心的指标就是缓存命中率，如果命中率很低，那么这个缓存除了浪费了空间，对性能的提升毫无帮助。

　　LRU是一种常用的缓存算法，即最近最少使用，如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小， LRU算法选择将最近最少使用的数据淘汰，保留那些经常被命中的数据

题目：

设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能

• set(key, value)：将记录(key, value)插入该结构
• get(key)：返回key对应的value值

[要求]

1. set和get方法的时间复杂度为O(1)
2. 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
3. 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。

若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案

输入：[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

返回值：[1,-1]
说明：

第一次操作后：最常使用的记录为("1", 1)
第二次操作后：最常使用的记录为("2", 2)，("1", 1)变为最不常用的
第三次操作后：最常使用的记录为("3", 2)，("1", 1)还是最不常用的
第四次操作后：最常用的记录为("1", 1)，("2", 2)变为最不常用的
第五次操作后：大小超过了3，所以移除此时最不常使用的记录("2", 2)，加入记录("4", 4)，并且为最常使用的记录，然后("3", 2)变为最不常使用的记录
（ps:还没有明白上面是示例具体什么意思。。。。所以代码实现看了也没有明白）

实现：

(5)二叉树的前序、中序和后序遍历
①关于二叉树前序、中序和后序
原文链接https://blog.csdn.net/chinesekobe/article/details/110874773
简单来说，前序就是遍历顺序为：根左右
　　　　   中序就是遍历顺序为：左中右
　　　　　后序就是遍历顺序为：左右中
题目：分别按照二叉树先序，中序和后序打印所有的节点。
输入:{1,2,3}
输出：[[1,2,3],[2,1,3],[2,3,1]]
实现：

Class TreeNode:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None

Class Solution:
    def mlr_dfs(self,root)
        if not root:
            return None
        self.result1.append(root.val)
        self.mlr_dfs(root.left)
        self.mlr_dfs(root.right)
    def  lmr_dfs(self,root):
        if not root:
            return None
        self.lmr_dfs(root.left)
        self.result2.append(root.val)
        self.lmr_dfs(root.right)
    def lrm_dfs(self,root):
        if not root:
            return None
        self.lrm_dfs(root.left)
        self.lrm_dfs(root.right)
        self.result3.append(root.val)

    def threeOrder(self,root):
        result = []
        self.result1 = []
        self.mlr_dfs(root)
        result.append(self.result1)
        self.result2 = []
        self.lmr_dfs(root)
        result.append(self.result2)
        self.result3 = []
        self.lrm(root)
        result.append(self.result3)
        return result

 (6)二叉树层序遍历

题目：给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]

输入：{1,2}

输出：[[1],[2]]

实现：

from collections import deque
class Solution:
    def levelOrder(self , root ):
        # write code here
        if not root:
            return []
        
        res = []
        que = deque()
        que.append(root)
        while que:
            lt = []
            # 这里一定要指定遍历次数！
            for i in range(len(que)):
                node = que.popleft()
                lt.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            
            res.append(lt)
            
        return res 

 (7)二叉树的重建

思路：【算法】重建二叉树（前+中、后+中） - gzshan - 博客园 (cnblogs.com)

代码实现：https://blog.csdn.net/qq_41805514/article/details/82709032