【数据结构与算法】解题20240313

这里写目录标题

• 一、现场写一个代码，有两个字符串类型的数字，实现一个方法将它们进行相加，并返回相加后的数值。（要考虑数据的长度问题）
• 一、287. 寻找重复数
• 三、617. 合并二叉树

  一、现场写一个代码，有两个字符串类型的数字，实现一个方法将它们进行相加，并返回相加后的数值。（要考虑数据的长度问题）

  class S:
      def func(self,a,b):
          carry=0
          res=''
          i=len(a)-1
          j=len(b)-1
          while i>=0 or j>=0 or carry!=0:
              A=int(a[i]) if i>=0 else 0
              B=int(b(j)) if j>=0 else 0
              sumAB=A+B+carry
              if sumAB>10:
                  carry=1
                  sumAB=sumAB%10
              else:
                  carry=0
              i-=1
              j-=1
              res+=str(sumAB)
  r = S()
  num1 = "99"
  num2 = "999"
  print(r.func(num1, num2))
  

  一、287. 寻找重复数

  中等

  给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

  假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

  你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

  示例 1：

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

  
  （图片来源网络，侵删）

  输出：2

  示例 2：

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

  输出：3

  示例 3 :

  输入：nums = [3,3,3,3,3]

  
  （图片来源网络，侵删）

  输出：3

  解题思路

  首先明确前提，整数的数组nums中的数字范围是 [1,n]。考虑一下两种情况：

  一、如果数组中没有重复的数，以数组 [1,3,4,2]为例，我们将数组下标 n 和数 nums[n] 建立一个映射关

  其映射关系 n->f(n)为：

  0->1

  1->3

  2->4

  3->2

  我们从下标为 0 出发，根据 f(n)计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推，直到下标超界。这样可以产生一个类似链表一样的序列。

  0->1->3->2->4->null

  如果数组中有重复的数，以数组 [1,3,4,2,2] 为例,我们将数组下标 n 和数 nums[n] 建立一个映射关系 f(n)，

  其映射关系 n->f(n) 为：

  0->1

  1->3

  2->4

  3->2

  4->2

  同样的，我们从下标为 0 出发，根据 f(n)计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推产生一个类似链表一样的序列。

  0->1->3->2->4->2->4->2->……

  这里 2->4 是一个循环，那么这个链表可以抽象为下图：

  

  从理论上讲，数组中如果有重复的数，那么就会产生多对一的映射，这样，形成的链表就一定会有环路了，

  综上

  1.数组中有一个重复的整数——》链表中存在环

  2.找到数组中的重复整数 ——> 找到链表的环入口

  class S287:
      def func(self,nums):
          slow=0
          fast=0
          while True:
              slow=nums[slow]     #slow=slow.next
              fast=nums[nums[fast]]   #fast=fast.next.next
              if fast==slow:  #首次相遇点
                  break
          fast=0                  #fast回到起点
          while slow!=fast:       #再次相遇即为重复数字
              slow=nums[slow]
              fast=nums[fast]
  

  三、617. 合并二叉树

  简单

  给你两棵二叉树： root1 和 root2 。

  想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

  返回合并后的二叉树。

  注意: 合并过程必须从两个树的根节点开始

  

  class S:
      def func(self, root1, root2):
          if not root1:
              return root2
          if not root2:
              return root1
          root = TreeNode(root1.val + root2.val)
          root.left = self.func(root1.left, root2.left)
          root.right = self.func(root1.right, root2.right)
          return root
  

  ---