每日算法题【20】:二叉树中和为某一值的路径
题目描述给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例示例 1:
12输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22输出:[[5,4,11,2],[5,8,4,5]]
示例 2:
12输入:root = [1,2,3], targetSum = 5输出:[]
示例 3:
12输入:root = [1,2], targetSum = 0输出:[]
提示
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
难度中等
解法一:深度优先搜索解题思路我们可以采用深度优先搜索的方式,枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点,且此时路径和恰为目标和时,我们就找到了一条满足条件的路径。
代码1234567891011121314151617181920 ...
每日算法题【19】:机器人的运动范围
题目描述地上有一个 m 行 n 列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如,当 k 为 18 时,机器人能够进入方格 [35, 37] ,因为 3+5+3+7=18。但它不能进入方格 [35, 38],因为 3+5+3+8=19。请问该机器人能够到达多少个格子?
来源:力扣(LeetCode)链接:https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
示例示例 1:
12输入:m = 2, n = 3, k = 1输出:3
示例 2:
12输入:m = 3, n = 1, k = 0输出:1
提示
1 <= n,m <= 100
0 <= k <= 20
难度中等
解法一:深度优先遍历 DFS解题思路
深度优先搜索: 可以理解为暴力法模拟机器 ...
webpack构建性能优化
前言现目前,前端开发使用打包工具更多的还是 webpack,再加上不管是通过 vue-cli、vite、create-react-app 来生成 Vue 项目还是 React 项目,这些脚手架都已经将 webpack 打包工具集成进去了。这对于我们开发者来说省去很多时间去单独配置 webpack,但是有时候也需要去额外配置一些工具,使得集成的 webpack 更加便捷快速,所以这次就给你们来点狠货,分享一些 webpack 的优化技巧。
无论是日常开发还是面试,都应该掌握一些 webpack 的优化技巧,总之你来看了这篇文章是不会吃亏的,反而会让你在今后的工作中得心应手。
性能分析俗话说:工欲善其事,必先利其器。
要想进行 Webpack 的性能优化,先要知道性能问题出现在哪?所以我们需要对 webpack 的构建进行分析。
依赖分析使用 webpack 编译源码时,用户可以生成一个包含模块统计信息的 JSON 文件。这些统计信息可以用来分析应用中的依赖关系图,从而优化 webpack 的编译速度。
使用方法该文件通常由以下 CLI 命令生成:
1npx webpack --profi ...
每日算法题【18】:矩阵中的路径
题目描述给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如,在下面的 3×4 的矩阵中包含单词 “ABCCED”(单词中的字母已标出)。
示例 1:
12输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输出:true
示例 2:
12输入:board = [["a","b"],["c"," ...
每日算法题【17】:两个链表的第一个公共节点
题目描述输入两个链表,找出它们的第一个公共节点。
如下面的两个链表:
在节点 c1 开始相交。
示例 1:
12345输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出:Reference of the node with value = 8输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
示例 2:
12345输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1输出:Reference of the node with value = 2输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9, ...
实现虚拟列表的两种方式
1 前言在web开发的过程中,或多或少都会遇到大列表渲染的场景,例如全国城市列表、通讯录列表、聊天记录列表等等。当列表数据量为几百条时,依靠浏览器本身的性能基本可以支撑,一般不会出现卡顿的情况。但当列表数量级达到上千,页面渲染或操作就可能会出现卡顿,而当列表数量突破上万甚至十几万时,网页可能会出现严重卡顿甚至直接崩溃。为了解决大列表造成的渲染压力,便出现了虚拟滚动技术。本文主要介绍虚拟滚动的基本原理。
方案一:滚动定位法基本原理首先来看一下直接渲染的大列表的实际表现。以有10万条子项的简单大列表为例,页面初始化时,FP时间大概在4000ms左右,大量的时间被用于执行脚本和渲染。而当快速滚动列表时,网页的FPS维持在35左右,可以明显的感觉到页面的卡顿。借助谷歌Lighthouse工具,最终网页的性能得分仅为49。通过实际访问体验和性能相关数据可以看出,直接渲染的大列表在加载操作方面体验是十分糟糕的。点击 链接,体验实际效果。
通过以上的测试数据可以看到,在页面初始化时脚本的执行和DOM渲染占据的大部分的时间。而随着列表子项的减少,页面初始 ...
每日算法题【16】:股票的最大利润
题目描述假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?
示例 1:
1234输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
123输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
限制:
0 <= 数组长度 <= 10^5
解题思路遍历数组,使用min、max记录当前最大最小值,存在一下两种边界情况
当prices[i] < min时,更新min、max值为prices[i],因为后面的遍历,最小值为prices[i],需要重新计算prices[i]右侧的最大值
当prices[i] > max时,只需更新最大值即可
每移动一位,使用max-min得出利润并记录最大的利润
代码1234567891011121314151617181920fun ...
每日算法题【15】:树的子结构
题目描述输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如:给定的树 A:
12345 3 / \ 4 5 / \ 1 2
给定的树 B:
123 4 / 1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1:
12输入:A = [1,2,3], B = [3,1]输出:false
示例 2:
12输入:A = [3,4,5,1,2], B = [4,1]输出:true
限制:
0 <= 节点个数 <= 10000
解题思路对A树进行遍历,判断A树当前节点值是否等于B树当前节点值
不等于则递归使用A的左右子树与B进行对比,
等于则递归对比A、B的子树是否相等,
如果A、B的子树不相等则继续递归使用A的左右子树与B进行对比
A、B的子树是否相等的函数isSameNode的边界条件如下:
B为null,则为true,因为B没有子节点的地方A可以有子节点
B不为nullA为null时则为false,因为B有 ...
每日算法题【14】:二维数组中的查找
题目描述在一个 n * m 的二维数组中,每一行都按照从左到右 非递减 的顺序排序,每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下:
1234567[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]
给定 target = 5,返回 true。
给定 target = 20,返回 false。
限制:
0 <= n <= 1000
0 <= m <= 1000
解题思路由于二维数组每一行每一列都是非递减 的顺序排序,则:
nus[i][j] 小于 target 时,nus[i-n][j-m] 一定小于target
nus[i][j] 大于 target 时,nus[i+n][j+m] 一定大于target
所以沿对角线遍历数组nums,当nus[i] ...
每日算法题【13】:复杂链表的复制
题目描述请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
示例 1:
12输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2:
12输入:head = [[1,1],[2,1]]输出:[[1,1],[2,1]]
示例 3:
12输入:head = [[3,null],[3,0],[3,null]]输出:[[3,null],[3,0],[3,null]]
示例 4:
123输入:head = []输出:[]解释:给定的链表为空(空指针),因此返回 null。
提示:
-10000 <= Node.val <= 10000
Node.random 为空(null)或指向链表中的节点。
节点数目不超过 1000 。
解题思路第一次遍历复制各个节点及next节点,同时使用map记录新旧节点的映射关系 ...