剑指offer牛客网练习20200128

雨点打透心脏的1/2处 2023-07-02 08:25 14阅读 0赞

1.二叉树中和为某一值的路径

最初没有太看懂题目，以为从根节点到下面的子节点的某一部分就OK了，不知道要遍历到根节点= =对自己很无语啊

写出了下面的代码，迷惑行为

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回二维列表，内部每个列表表示找到的路径
        def FindPath(self, root, expectNumber):
            # write code here
            path=[]
            result=[]
            stack=[]
            if not root:
                return [[]]
            stack.append(root)
            path.append([root.val])
            while stack:
                if sum(path[0])==expectNumber:
                    result.append(path[0])
                if sum(path[0])<expectNumber:
                    if stack[0].left:
                        stack.append(stack[0].left)
                        path.append(path[0]+[stack[0].left.val])
                    if stack[0].right:
                        stack.append(stack[0].right)
                        path.append(path[0]+[stack[0].right.val])
                stack.pop(0)
                path.pop(0)
            return result[::-1]

稍加修改，添加了左节点和右节点是否存在的判断

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回二维列表，内部每个列表表示找到的路径
        def FindPath(self, root, expectNumber):
            # write code here
            path=[]
            result=[]
            stack=[]
            if not root:
                return []
            stack.append(root)
            path.append([root.val])
            while stack:
                if sum(path[0])==expectNumber and (not stack[0].left or not stack[0].right):
                    result.append(path[0])
                if sum(path[0])<expectNumber:
                    if stack[0].left:
                        stack.append(stack[0].left)
                        path.append(path[0]+[stack[0].left.val])
                    if stack[0].right:
                        stack.append(stack[0].right)
                        path.append(path[0]+[stack[0].right.val])
                stack.pop(0)
                path.pop(0)
            return result[::-1]

做这题特别学习了一下python的值传递和地址传递，以及深拷贝浅拷贝赋值的区别

2.复杂链表的复制

首先这个题目我又没看懂，直到看到讨论区里面说深拷贝= =好吧

这个思路很明确，主要分三步，1.先在本来链表上复制链表，random不处理2.处理random3.拆分链表

注意2和3不能同时进行，因为后面的ramdom可能会指向前面的链表= =我个撒子，想不明白

我自己的代码

# -*- coding:utf-8 -*-
    # class RandomListNode:
    #     def __init__(self, x):
    #         self.label = x
    #         self.next = None
    #         self.random = None
    class Solution:
        # 返回 RandomListNode
        def Clone(self, pHead):
            # write code here
            if not pHead:
                return None
            temp=pHead
            while temp:
                new=RandomListNode(temp.label)
                new.next=temp.next
                temp.next=new
                temp=new.next
            temp=pHead
            result=temp.next
            while temp:
                #random的赋值，注意random可能为NULL
                if temp.random:
                    temp.next.random=temp.random.next
                temp=temp.next.next
                #拆分列表，temp存在temp.next即t肯定存在
            temp=pHead
            while temp:
                t=temp.next
                temp.next=t.next
                if temp.next:
                    t.next=temp.next.next
                temp=temp.next
            return result

3.二叉搜索树与双向链表

= =想了好久，讨论区看不懂，所以没咋看，自己总结，最后弄出来一个奇怪的递归

原则就是对于任何一个结点，left需要指向左子树的右叶节点、若为NULL则取节点本身，right须需指向右子树的左叶节点

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def findLeft(self,root):
            while(root.right):
                root=root.right
            return root
        def findRight(self,root):
            while(root.left):
                root=root.left
            return root
        def Convert(self, pRootOfTree):
            # write code here
            if not pRootOfTree:
                return None
            result=pRootOfTree
            if pRootOfTree.left:
                result=self.Convert(pRootOfTree.left)
                left=self.findLeft(pRootOfTree.left)
                pRootOfTree.left=left
                left.right=pRootOfTree
            if pRootOfTree.right:
                self.Convert(pRootOfTree.right)
                right=self.findRight(pRootOfTree.right)
                pRootOfTree.right=right
                right.left=pRootOfTree
            return result

最后返回的是左叶节点

这道题太摧残我自己了，我都不想看讨论区= =

网上搜了个这个[python版本的][python]

4.字符串排列

1）python有个库有个函数[参考这个][Link 1]

2）递归法

主要是不停的从剩余的里面抽取下一位

# -*- coding:utf-8 -*-
    class Solution:
        def dfs(self,ss,temp,result):
            if not ss and temp not in result:
                result.append(temp)
            for i in range(0,len(ss)):
                self.dfs(ss[:i]+ss[i+1:],temp+ss[i],result)
        def Permutation(self, ss):
            # write code here
            result=[]
            ss=list(ss)
            if not ss:
                return []
            temp=''
            self.dfs(ss,temp,result)
            return result

5.数组中出现次数超过一半

# -*- coding:utf-8 -*-
    class Solution:
        def MoreThanHalfNum_Solution(self, numbers):
            # write code here
            d={}
            for i in numbers:
                d[i]=d.get(i,0)+1
                if d[i]>len(numbers)/2:
                    return i
            return 0

python的偷懒

我觉得讨论区那个分形叶很妙，就是由于数字数量超过数组的一半，不断去除两个不同的数字，最后剩下的一个或者两个就是那个数组，带回原数组查看个数即可

6.最小的k个数

# -*- coding:utf-8 -*-
    class Solution:
        def GetLeastNumbers_Solution(self, tinput, k):
            # write code here
            temp=[]
            if not tiput or k>len(tinput):
                return []
            for j in range(0,k):
                mini=999
                minii=-1
                for i in range(0,len(tinput)):
                    if tinput[i]<mini:
                        mini=tinput[i]
                        minii=i
                temp.append(mini)
                tinput.pop(minii)
            return temp

7.连续子数组的最大和

之前学过还有印象，如果目前的子序列和为负数那么就没必要继续下去了

# -*- coding:utf-8 -*-
    class Solution:
        def FindGreatestSumOfSubArray(self, array):
            # write code here
            result=[]
            maxs=-999
            for i in array:
                maxs=maxs if maxs>sum(result)+i else sum(result)+i
                if sum(result)+i<0:
                    result=[]
                else:
                    result.append(i)
            return maxs

[python]: https://blog.csdn.net/u010005281/article/details/79657259
[Link 1]: https://blog.csdn.net/fuxuemingzhu/article/details/79363903