[数据结构与算法]2021-08-17

Code 1

Question

Given a non-negative integer x, compute and return the square root of x.
Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.
Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1

Input: x = 4
Output: 2

Example 2

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Answer

• 自己的解法（二分查找）

class Solution(object):
    def mySqrt(self, x):
        if x==0 :
            return 0
        low=1
        high=x
        mid=(high+low)//2
        while low<=high :
            if mid*mid<x :
                low=mid+1
            elif mid*mid>x :
                high=mid-1
            else :
                return mid
            mid=(low+high)//2
        return mid

• 标准答案

1. 二分查找

   class Solution(object):
       def mySqrt(self, x):
           l,r,ans=0,x,-1
           while l<=r :
               mid=(1+r)//2
               if mid*mid<=x :
                   ans=mid
                   l=mid+1
               else :
                   r=mid-1
           return ans
   

   • 注意判断条件是left<=right
   • 在含有等于的条件下赋值mid给ans
   • 初始化ans的值为-1这样就不用单独判断x=0的情况
2. 牛顿迭代法

class Solution(object):
    def mySqrt(self, x):
        if x==0 :
            return 0
        c,x0=float(x),float(x)
        while True :
            xi=0.5^(x0+c/x0)  # 切线在x轴上的截点
            if abs(x0-xi)<1e-7 : #如果这个点和上个点差的非常小
                break  #退出循环
            x0=xi #否则用截点对应的点再计算一次
        return int(x0)

用 $C$ 表示待求出平方根的那个整数。显然,$C$的平方根就是函数$y=f(x)=x^2?C$的零点。
牛顿迭代法的本质是借助泰勒级数，从初始值开始快速向零点逼近。我们任取一个 $x_0$ 作为初始值，在每一步的迭代中，我们找到函数图像上的点 $(x_i,f(x_i))$，过该点作一条斜率为该点导数$f^{\prime }(x_i)$的直线，与横轴的交点记为 $x_{i+1}$。$x_{i+1}$相较于 $x_i$?而言距离零点更近。在经过多次迭代后，我们就可以得到一个距离零点非常接近的交点。

Code 2

Question

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 steps

Answer

class Solution(object):
   def climbStairs(self, n):

       first_step=1
       second_step=2

       if n == 1:
           return 1
       elif n == 2:
           return 2

       all_step=3

       for i in range(3,n) :
           first_step = second_step
           second_step = all_step
           all_step=first_step+second_step

       return all_step   

• 第n个楼梯的走法=第n-1个楼梯的走法+第n-2个楼梯的走法

Code3

Question

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1

Input: head = [1,1,2]
Output: [1,2]

Example 2

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Answer

• 遍历法

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        l=head
        if not l :
            return head

        while l.next :
            if(l.val==l.next.val) :
                l.next=l.next.next
            else :
                l=l.next
        return head

由于链表是升序排列，相邻元素相等就是重复。

• 递归法

class Solution(object):
    def deleteDuplicates(self, head):
        if not head or not head.next :
            return head
        head.next=self.deleteDeplicates(head.next)
        if head.val==head.next.val :
            head=head.next
        return head

相当于从最后一个结点开始慢慢调整

Code 4*

Question

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Example 1

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2

Input: root = []
Output: []

Example 3

Input: root = [1]
Output: [1]

Example 4

Input: root = [1,2]
Output: [2,1]

Example 5

Input: root = [1,null,2]
Output: [1,2]

Answer

• 中序遍历的递归法（最普通）

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def inorderTraversal(self, root):
        res=[]
        self.inorder(root,res)
        return res

    def inorder(self,root,res):
        if not root :
            return
        self.inorder(root.left,res)
        res.append(root)
        self.inorder(root.right,res)

注意其实是可以再定义一个函数的。。居然没有想到

• 遍历方法

lass Solution(object):
    def inorderTraversal(self, root):
        stack=[]
        ans=[]
        while stack or root :
            if root:
                stack.append(root)
                root=root.left

            else :
                val=stack.pop()
                ans.append(val.val)
                root=val.right
        return ans

不断往左边走，当左边走不下去了，就打印节点，并转向右边，然后右边继续这个过程。

Code 5*

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3

Input: p = [1,2,1], q = [1,1,2]
Output: false

Answer

• 自己的方法

class Solution(object):
    def isSameTree(self, p, q):
        res1=[]
        res2=[]
        self.inorder(res1,p)
        self.inorder(res2,q)
        if res1==res2 :
            return True
        else :
            return False

    def inorder(self,res,t):
        if not t :
            return
        self.inorder(t.left)
        res.append(self.value)
        self.inorder(t.right)

比较二者中序遍历的结果，最后为了防止不同子树但中序遍历结果相同，多加了条件判断。总的来说也不是很好。

• 标准解法

1. 深度优先探索

class Solution(object):
    def isSameTree(self, p, q):
        if not p and not q :
            return True
        elif not p or not q :
            return False
        elif p.val!=q.val :
            return False
        else :
            return self.isSameTree(p.left,q.left)&self.isSameTree(p.right,q.right)

• 如果两个二叉树都为空，则两个二叉树相同。
• 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
• 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。

2. 广度优先探索

class Solution(object):
    def isSameTree(self, p, q):
        if not p and not q :
            return True
        if not p or not q:
            return True
        quene1=collections.deque([p])
        quene2=collections.deque([q])
        while quene1 and quene2 :
            node1=quene1.popleft()
            node2=quene2.popleft()
            if node1.val!=node2.val :
                return False
            left1,right1=node1.left,node1.right
            left2,right2=node2.left,node2.right
            if not left1 and not left2 :
                return False
            if not right1 and not right2 :
                return False
            if left1 :
                quene1.append(left1)
            if right1 :
                quene1.append(right1)
            if left2 :
                quene2.append(left2)
            if right2 :
                quene2.append(right2)

        return not quene1 and not quene2

• 首先判断两个二叉树是否为空，如果两个二叉树都不为空，则从两个二叉树的根节点开始广度优先搜索。
• 使用两个队列分别存储两个二叉树的节点。初始时将两个二叉树的根节点分别加入两个队列。每次从两个队列各取出一个节点，进行如下比较操作。
  1. 比较两个节点的值，如果两个节点的值不相同则两个二叉树一定不同。
  2. 如果两个节点的值相同，则判断两个节点的子节点是否为空，如果只有一个节点的左子节点为空，或者只有一个节点的右子节点为空，则两个二叉树的结构不同，因此两个二叉树一定不同。
  3. 如果两个节点的子节点的结构相同，则将两个节点的非空子节点分别加入两个队列，子节点加入队列时需要注意顺序，如果左右子节点都不为空，则先加入左子节点，后加入右子节点。
  4. 如果搜索结束时两个队列同时为空，则两个二叉树相同。
  5. 如果只有一个队列为空，则两个二叉树的结构不同，因此两个二叉树不同。

关注博主即可阅读全文