剑指offer牛客网练习20200130

待我称王封你为后i 2023-07-02 13:25 1阅读 0赞

1.丑数

找2\*2没乘过的丑数、3\*3没乘过的丑数、5\*5没乘过的丑数，三者的最小值作为新丑数

# -*- coding:utf-8 -*-
    class Solution:
        def GetUglyNumber_Solution(self, index):
            # write code here
            if index<7:return index
            result=[1]
            t2,t3,t5=0,0,0
            for i in range(1,index):
                result.append(result[t2]*2)
                if result[i]>result[t3]*3:
                    result[i]=result[t3]*3
                if result[i]>result[t5]*5:
                    result[i]=result[t5]*5
                if result[i]==result[t2]*2:
                    t2+=1
                if result[i]==result[t3]*3:
                    t3+=1
                if result[i]==result[t5]*5:
                    t5+=1
            return result[index-1]

2.第一个只出现一次的字符

python大法好

# -*- coding:utf-8 -*-
    class Solution:
        def FirstNotRepeatingChar(self, s):
            # write code here
            for i in range(0,len(s)):
                if s[i] not in s[:i]+s[i+1:]:
                    return i
            return -1

3.数组中的逆序对

尝试写归并排序居然还是超时了，通过了75%的案例

class Solution:
        def __init__(self):
            self.count=0
        def Merge(self,left,right):
            i=0
            j=0
            result=[]
            while(i<len(left) and j<len(right)):
                if left[i]<=right[j]:
                    result.append(left[i])
                    i+=1
                else:
                    result.append(right[j])
                    self.count+=len(left)-i
                    j+=1
            result+=right[j:]
            result+=left[i:]
            return result
        def clip(self,data):
            print(data)
            if len(data)>=2:
                left=self.clip(data[:int(len(data)/2)])
                right=self.clip(data[int(len(data)/2):])
                return self.Merge(left,right)
            else:
                return data
        def InversePairs(self, data):
            # write code here
            self.clip(data)
            return self.count%1000000007

还有一个，参看这里[这里][Link 1]

我试着写了也没通过= =？然后我看了python通过的代码，是很奇怪的一行？？？？

4.两个链表的第一个公共结点

我还以为公共结点的意思是只有值相等，next是不一样的

其实并不是，相遇之后尾部都一样了

因此将两个列表压入两个栈，之后同时pop一个，直到遇到不相等的，答案就是不相等的前一个

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        def FindFirstCommonNode(self, pHead1, pHead2):
            # write code here
            t1=pHead1
            t2=pHead2
            l1=[]
            l2=[]
            while(t1 or t2):
                if t1:
                    l1.append(t1)
                    t1=t1.next
                if t2:
                    l2.append(t2)
                    t2=t2.next
            result=None
            while(l1 and l2):
                t1=l1.pop()
                t2=l2.pop()
                if t1==t2:
                    result=t1
                else:
                    break
            return result

5.数字在排序数组中的次数

排序数组是啥意思= =升序还是降序

先写个简单的试试

# -*- coding:utf-8 -*-
    class Solution:
        def GetNumberOfK(self, data, k):
            # write code here
            count=0
            flag=False
            for i in data:
                if k==i:
                    count+=1
                    flag=True
                if k!=i and flag:
                    break
            return count

过了= =。。。。。。

看了下讨论区都是用二分法啊

我也写个看看

6.二叉树的深度

递归写法

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def goTree(self,root,count):
            if not root:
                return count
            count+=1
            cl=count
            cr=count
            if root.left:
                cl=self.goTree(root.left,count)
            if root.right:
                cr=self.goTree(root.right,count)
            return cl if cl>cr else cr
        def TreeDepth(self, pRoot):
            # write code here
            result=self.goTree(pRoot,0)
            return result

7.平衡二叉树

平衡二叉树的特点就是左子树右子树高度不超过1

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def __init__(self):
            self.flag=True
        def getDepth(self,root):
            if not root or not self.flag:
                return 0
            left=self.getDepth(root.left)
            right=self.getDepth(root.right)
            if abs(left-right)>1:
                self.flag=False
            return max(left,right)+1
        def IsBalanced_Solution(self, pRoot):
            # write code here
            self.getDepth(pRoot)
            return self.flag

8.数组中只出现一次的数字

利用字典的思路不写了，python有个collections库的Counter有个most\_common()方法

# -*- coding:utf-8 -*-
    class Solution:
        # 返回[a,b] 其中ab是出现一次的两个数字
        def FindNumsAppearOnce(self, array):
            # write code here
            if not array:
                return []
            num=0
            for i in array:
                num^=i
            #获取低位（右边数）1的位置
            idx=0
            while(num & 1)==0:
                num>>=1
                idx+=1
            a,b=0,0
            for i in array:
                if (i>>idx)&1:
                    a^=i
                else:
                    b^=i
            return [a,b]

[Link 1]: https://blog.csdn.net/u010005281/article/details/80099333