面试手撕合集

82.删除排序链表中的重复元素II

定义单个指针 cur,指向虚拟头节点。如果 cur.next == cur.next.next,说明 cur 后面的两个节点重复,例如 节点2 后面存在 2个节点3。我们令 节点2 -> 节点4,实现删除两个节点3的操作。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:

        dummyhead = ListNode(val = 0, next = head)
        cur = dummyhead
        
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                repeat_val = cur.next.val
                # 跳过某段重复
                while cur.next and cur.next.val == repeat_val:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dummyhead.next

240.搜索二维矩阵II

利用矩阵的递增性质:从左下角元素开始搜索,同列元素都小于此元素,同行元素都大于此元素。因此和 target 比较后,我们可以立即排除一行或者一列的元素。如下图:从右上角开始同理,这是由于这两处的元素大小处在所在行和列的所有元素中间,可以利用二分思想缩减搜索规模。而左上和右下角的元素处在所在行和列的所有元素的两端。

 

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 起始点定在矩阵左下角
        i, j = len(matrix) - 1, 0
        
        while i >= 0 and j <= len(matrix[0]) - 1:
            if matrix[i][j] > target:
                i -= 1
            elif matrix[i][j] < target:
                j += 1
            else:
                return True
        return False

冒泡排序

  • 遍历数组,每次交换相邻两个元素,一次遍历后,最大的数将会被移至末尾。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
  • 时间复杂度为 O(n^2)
def bubble_sort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):

        for j in range(0, n-i-1):
            # 遍历数组从0到n-i-1
            # 交换如果元素大于下一个元素
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

快速排序

  • 选择基准值:从数组中选择一个元素作为基准值。选择方法有多种,如选择第一个元素、最后一个元素、中间元素等。

  • 分区操作:重新排列数组,使得所有小于基准值的元素都排在基准前面,而所有大于基准值的元素都排在基准的后面(相等的数可以到任一边)。在这个分区退出之后,该基准就处于数组的中间位置。

  • 递归排序:递归地将小于基准值的子数组和大于基准值的子数组排序。

  • 时间复杂度为O(n log n)

def quick_sort(arr):
    # 分区函数:根据pivot(基准值)将数组分为两部分
    def partition(left, right):
        pivot = arr[left]  # 选择左边界的元素作为pivot
        while left < right:
            # 从右向左扫描,找到第一个小于pivot的元素,移动到左边
            while left < right and arr[right] >= pivot:
                right -= 1
            arr[left] = arr[right]

            # 从左向右扫描,找到第一个大于pivot的元素,移动到右边
            while left < right and arr[left] <= pivot:
                left += 1
            arr[right] = arr[left]

        # 循环结束,left和right相遇,这是pivot的正确位置,将pivot放回
        arr[left] = pivot
        return left  # 返回pivot的位置

    # 递归排序的辅助函数
    def quick_sort_recursive(left, right):
        if left < right:  # 至少包含两个元素的区间才需要排序
            pi = partition(left, right)  # 对当前区间进行分区,得到pivot的位置
            quick_sort_recursive(left, pi - 1)  # 递归排序pivot左侧的子数组
            quick_sort_recursive(pi + 1, right)  # 递归排序pivot右侧的子数组

    quick_sort_recursive(0, len(arr) - 1)  # 对整个数组进行快速排序
    return arr  # 返回排序后的数组

538.把二叉搜索树转换为累加树 

累加树(Greater Sum Tree)常见于二叉搜索树(Binary Search Tree)的变体。在累加树中,每个节点的值被修改为原始二叉搜索树中所有大于或等于该节点值的节点值之和。

举例

有以下BST:

反向中序遍历(右中左)

我们遍历的顺序是:9 -> 8 -> 5 -> 4 -> 3 -> 2。遍历时,我们累计已经访问过的节点值的和,并将这个累积和赋给当前节点。

  • 访问节点 9:当前累积和 = 9,更新节点 9 的值为 9
  • 访问节点 8:当前累积和 = 9 + 8 = 17,更新节点 8 的值为 17
  • 访问节点 5:当前累积和 = 17 + 5 = 22,更新节点 5 的值为 22
  • 访问节点 4:当前累积和 = 22 + 4 = 26,更新节点 4 的值为 26
  • 访问节点 3:当前累积和 = 26 + 3 = 29,更新节点 3 的值为 29
  • 访问节点 2:当前累积和 = 29 + 2 = 31,更新节点 2 的值为 31

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:

        self.sum = 0

        def dfs(node):
            # 递归终止条件
            if not node:
                return
            # 反向中序(右 -> 中 -> 左)
            # 右
            dfs(node.right)
            # 中
            self.sum += node.val
            node.val = self.sum  # 更新节点值
            # 左
            dfs(node.left)
        
        dfs(root)
        return root

1743.从相邻元素对还原数组

数组元素各不相同,有以下观察:

  • 每个元素(除了首尾元素)都会有两个相邻元素:前一个和后一个。
  • 数组的首元素 只有一个相邻元素,即它后面的元素。
  • 数组的尾元素 同样只有一个相邻元素,即它前面的元素。

因此,在从 adjacentPairs 构建的 adj_map 中,大多数键(代表 nums 中的元素)都会有两个条目在其对应的列表中,这两个条目分别表示它的前一个和后一个相邻元素。例外的是 nums 的首尾元素,它们在 adj_map 中的列表长度将是 1,因为它们各自只有一个相邻元素。

举例说明

考虑数组 nums = [1, 2, 3, 4],其相邻元素对可能包括:

  • [1, 2]
  • [2, 3]
  • [3, 4]

在通过这些对构建 adj_map 后,其内容将是:

  • 1 -> [2]
  • 2 -> [1, 3]
  • 3 -> [2, 4]
  • 4 -> [3]

由于顺序不限,我们随意选择其中一个长度为 1 的键作为起点,然后根据相邻关系依次添加元素到结果数组中,直到所有元素都被添加。

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        n = len(adjacentPairs) + 1
        # 构建关系哈希表
        adj_map = defaultdict(list)
        for u, v in adjacentPairs:
            adj_map[u].append(v)
            adj_map[v].append(u)
        # 找到 nums 的起始元素
        for key, val in adj_map.items():
            if len(val) == 1:
                start = key
                break
        # 构建 nums
        nums = []
        nums.append(start)
        nums.append(adj_map[start][0])
        while len(nums) < n:
            cur_val = nums[-1]
            pre_val = nums[-2]
            for next_val in adj_map[cur_val]:
                # cur_val键对应的值包含cur_val的前一个和后一个元素
                # 对于cur_val的后一个元素的确定,我们需要避免重复选择cur_val的前一个元素(pre_val)
                if next_val != pre_val:
                    nums.append(next_val)
                else:
                    continue
        return nums

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/546971.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

visual studio连接ubuntu不成功原因(SSH问题)及解决办法

原因1&#xff1a; 网络没有互通&#xff08;一般VMware&#xff09; 使用ping来看网络是不是可以互通&#xff0c;例如&#xff1a; //这里的ip是ubuntu的ip&#xff0c;也可以从ubuntu的客户端ping一下当前主机 ping 192.168.1.101原因2&#xff1a; SSH没有密钥&#xf…

从iPhone恢复已删除照片的最佳软件

本文分享了从iPhone恢复已删除照片的最佳软件。如果您正在寻找如何从iPhone恢复已删除的照片&#xff0c;请查看这篇文章。 为什么您需要软件从iPhone恢复已删除的照片&#xff1f; 没有什么比丢失iPhone上的重要数据更痛苦的了&#xff0c;尤其是一些具有珍贵回忆的照片。有时…

❤ vue3 使用报错

❤ vue3 项目使用报错 vue3语法变动 TypeError: Assignment to constant variable &#xff08;常量变量&#xff09; 背景&#xff1a; Vue3 项目使用 TypeError: Assignment to constant variable. 原因&#xff1a; 因为我对const定义的常量重新赋值了 解决方法&#…

JVM(Java虚拟机)内存管理基础理论

JVM&#xff08;Java虚拟机&#xff09;内存管理是Java开发和性能优化中的一个核心领域。理解JVM的内存结构和管理机制对于编写高效的Java程序和进行有效的性能调优非常重要。以下是一个关于JVM内存学习的大纲&#xff0c;涵盖了从基础知识到高级主题的各个方面&#xff1a; 1.…

EasyRecovery2024专业免费的电脑数据恢复软件

EasyRecovery数据恢复软件是一款功能强大的数据恢复工具&#xff0c;广泛应用于各种数据丢失场景&#xff0c;帮助用户从不同类型的存储介质中恢复丢失或删除的文件。 该软件支持恢复的数据类型非常广泛&#xff0c;包括但不限于办公文档、图片、音频、视频、电子邮件以及各种…

Hive on spark源码编译与调优

文章目录 一、编译环境准备1、hadoop和hive安装2、编译环境搭建3、Hive on Spark配置 二、Hive相关问题1、Hadoop和Hive的兼容性问题1.1 问题描述1.2 解决思路1.3 修改并编译Hive源码 2、Hive插入数据StatsTask失败问题3.1 问题描述3.2 解决思路 3、Hive和Spark兼容性问题3.1 问…

信也科技网络自动化实践-网络策略管理

1、背景 随着各种法律法规和行业标准的出台和更新&#xff0c;企业或组织需要遵守各种安全合规性要求。网络安全策略管理需要符合这些要求&#xff0c;从而保障企业或组织的安全和合规性。网络安全策略管理需要涵盖企业或组织的整个网络生命周期&#xff0c;包括网络规划、设计…

【JavaEE多线程】线程安全、锁机制及线程间通信

目录 线程安全线程安全问题的原因 synchronized 关键字-监视器锁monitor locksynchronized的特性互斥刷新内存可重入 synchronized使用范例 volatilevolatile能保证内存可见性volatile不保证原子性synchronized 也能保证内存可见性 wait 和 notifywait()方法notify()方法notify…

[BT]BUUCTF刷题第17天(4.15)

第17天&#xff08;共3题&#xff09; Web [强网杯 2019]高明的黑客 .tar.gz 是 Linux 系统下的压缩包&#xff0c;访问即可下载 打开后有3000多个php文件&#xff0c;通过题解得知需要写Python脚本找出合适的GetShell文件&#xff08;因为每个文件里都会通过system函数执行…

【Java开发指南 | 第九篇】访问实例变量和方法、继承、接口

专栏&#xff1a;Java开发指南 CSDN秋说 文章目录 访问实例变量和方法继承接口 访问实例变量和方法 通过已创建的对象来访问成员变量和成员方法&#xff0c;如下所示&#xff1a; /* 实例化对象 */ Object referenceVariable new Constructor(); /* 访问类中的变量 */ refer…

glitch功耗的问题在先进节点上更加突出

这个问题在 AI 加速器中尤为严重&#xff0c;修复这个问题需要一些tradeoff。 据估计&#xff0c;一些最先进和最复杂的芯片设计中总功耗的 20% 到 40% 被浪费了。 glitch功耗并不是一个新现象。在先进节点上&#xff0c;glitch功耗问题正变得越来越突出&#xff0c;没有一种解…

Android SQLite

一、使用SQLiteOpenHelper类创建数据库与版本管理 1、nCreate(database):首次使用软件时生成数据库表 2、onUpgrade(database,oldVersion,newVersion):在数据库的版本发生变化时会被调用&#xff0c; 一 般 在软件升级时才需改变版本号&#xff0c;而数据库的版本是由…

20240328-2-随机森林面试题RandomForest

随机森林面试题 1. 简单介绍随机森林 一种基于树模型的Bagging的优化版本&#xff0c;一棵树的生成肯定还是不如多棵树&#xff0c;因此就有了随机森林&#xff0c;解决决策树泛化能力弱的特点。 多次随机取样&#xff0c;多次随机取属性&#xff0c;选取最优分割点&#xff…

在Vue3中如何使用H.265视频流媒体播放器EasyPlayer.js?

H5无插件流媒体播放器EasyPlayer属于一款高效、精炼、稳定且免费的流媒体播放器&#xff0c;可支持多种流媒体协议播放&#xff0c;可支持H.264与H.265编码格式&#xff0c;性能稳定、播放流畅&#xff0c;能支持WebSocket-FLV、HTTP-FLV&#xff0c;HLS&#xff08;m3u8&#…

【uniapp踩坑记】——微信小程序转发保存图片

关于微信小程序转发&保存图片 微信小程序图片转发保存简单说明网络图片的转发保存base64流形式图片转发保存 已经好多年没写博客了&#xff0c;最近使用在用uniapp开发一个移动版管理后台&#xff0c;记录下自己踩过的一些坑 吃相别太难看&#xff0c;搞一堆下头僵尸号来点…

【YOLOv9】使用yolov9训练自己的数据集/验证 /推理 /参数分析

完胜V8的SOTA模型Yolov9(论文阅读笔记)内容 点击即可跳转 当今的YOLO系列武林盟主YOLOV9&#xff1a; YOLOv9的优秀表现&#xff1a; 环境&#xff1a; ubuntu20.04&#xff0c;无GPU&#xff0c;使用anaconda3创建的虚拟环境yolov9。 环境安装&#xff1a; conda create -n …

JavaSE图书管理系统

JavaSE图书管理系统 思路一.Main方法二.User包1.User类2.NormaUser类3.AdminUser类三.book包1.BookList类2.Book类四.operation包1.IOPeration接口2.AddOperation类新增图书3.BorrowOperation类借阅图书4.DelOperation类删除图书5.FindOperation类查找图书6.ReturnOperation类归…

Centos7配置IP地址

1、找到网卡名字 使用root用户登陆&#xff0c;输入命令 ifconfig 2、打开配置文件 输入命令&#xff0c;打开配置文件 vi /etc/sysconfig/network-scripts/ifcfg-ens33 3、添加IP地址 3.1修改BOOTPROTO 将“BOOTPROTOdhcp” 改为 “BOOTPROTOstatic” 3.2添加IP地址 在配…

【JavaEE多线程】从单例模式到线程池的深入探索

目录 多线程案例单例模式阻塞队列定时器线程池总结-保证线程安全的思路对比线程和进程 多线程案例 单例模式 单例模式是一种设计模式 设计模式&#xff0c;就是程序员的棋谱&#xff0c;这里介绍了很多典型场景&#xff0c;以及典型场景的处理方式&#xff0c;按照设计模式写…

火车头采集一键发布到Zblog

火车头采集发布到Zblog系统&#xff0c;主要操作步骤如下&#xff1a; 目录 1、Zblog火车头Web发布模块 2、内容发布参数映射&#xff0c;火车头发布到Zblog 3、简数一键发布到Zblog方法 1、Zblog火车头Web发布模块 自行编写Zblog火车头Web发布模块&#xff0c;一般要使用f…