- 博客(168)
- 收藏
- 关注
RSS订阅
1原创 【Leetcode】442. 数组中重复的数据
题目链接：数组中重复的数据题目描述：给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。分析：1）题目要求的时间复杂度为O(n)，空间复杂度为O(1)。说明需要使用哈希表，但不能借助另外的哈希表。2）又因为数组长度为n，索引是[0,n-1]，数据范围是[1,n]，所以可以
2022-05-11 16:22:32
196
原创 【Leetcode】398. 随机数索引
题目链接：随机数索引题目描述：给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。实现 Solution 类：Solution(int[] nums) 用数组 nums 初始化对象。int pick(int target) 从 nums 中选出一个满足 nums[i] == target 的随机索引 i 。如果存在多个有效的索引，则每个索引的返回概率应当相等。方法一：1）初始化时，将nums赋值
2022-04-25 21:19:33
224
原创 【Leetcode】386. 字典序排数
题目链接：字典序排数题目描述：给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。思路一：递归js代码如下：var lexicalOrder = function (n) { let arr = []; backtrack(1, n); function backtrack(num, n) { if (num > n) ret
2022-04-25 16:34:32
193
原创 【剑指Offer】46. 把数字翻译成字符串
题目链接：把数字翻译成字符串题目描述：给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。题目分析：1）每一位上的数字都可以单独翻译成一个字符，且该位和其前一位的构成的数字小于26时，也可以一起翻译成一个字符。2）动态规划，用dp[n]表示一个n位的数字能够翻译成的字符串的个数，那么将包含n位的数字转换成一个字符
2022-04-20 17:42:14
438
原创 【剑指Offer】38. 字符串的排列
题目链接：字符串的排列题目描述：输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。题目分析：此题目为字符串的全排列，1）使用回溯的方式，在回溯中对字符串进行遍历，同时标记某一个字符是否在当前排列中出现过，若出现过则跳过，没有出现过则加入排列。然后从下一个字符处开始进行回溯。因为字符串数组不能重复，所以使用哈希表set来进行去重。var permutation = function (s) { const length =
2022-04-20 17:05:49
811
原创 【剑指Offer】36. 二叉搜索树与双向链表
题目链接：二叉搜索树与双向链表题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。题目要求：1）排序
2022-04-20 16:11:50
373
原创 【Leetcode】380. O(1) 时间插入、删除和获取随机元素
题目链接：O(1)时间插入、删除和获取随机元素题目描述：实现RandomizedSet 类：RandomizedSet() 初始化 RandomizedSet 对象bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。int getRandom() 随机返回现有集合中的一项（测试用例保
2022-04-13 19:45:14
332
原创 【面试】数字转为千分位字符串
本博客来自一道被面试了两次的手撕题。要求如下：将数字123412，转换为字符串1,234.12。这道题很简单，但是第一次面试的时候思路很混乱，写的很麻烦。而且没有考虑负数情况。所以第二次面试官又让把这个题目再写一遍，人麻了。上来整个人是懵的。上次怎么写的也忘记了。然后就想到了一个更好一些的方法。js代码如下：function test(num){ let str=num.toString(); if(num<0) str=str.slice(1
2022-04-07 21:02:43
269
原创 【Leetcode】63. 不同路径 II
题目链接：不同路径II题目描述：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。分析：这个题目本来是用回溯写的，但是超时了。无奈之下，看了一眼题解，原来是DP!!!dp[i][j]表示从起点(0,0)到点(i,j)的路径
2022-04-06 20:03:15
184
原创 【剑指Offer】45. 把数组排成最小的数
题目链接：把数组排成最小的数题目描述：输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。题目分析：题目要求将数组排成一个最小的数，即对数组按照字符串的规则进行排序，规则如下：1）两个数字的位数一样，则较大的数字排在右边；2）两个数字的位数不一样，那么对于公有的位上的数字 ，对应位上数字较大的数排在右边；3）对于情况2），若两个数字公有位的数字都一样，那么需要将两个数字对应的字符串分别作为首尾进行拼接，即将数字A和B分别拼接成AB和BA，对A
2022-03-31 16:30:35
316
原创 【剑指 Offer】 26. 树的子结构
题目链接：树的子结构题目描述：输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)B是A的子结构， 即 A中有出现和B相同的结构和节点值。例如:给定的树 A:3/ \4 5/ \1 2给定的树 B：4/1返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。分析：此题目需要对树A中的每一个节点进行遍历，直到找到和树B相同的结构。1）递归对A进行先序遍历：先判断A...
2022-03-24 22:29:46
65
原创 【剑指 Offer】 20. 表示数值的字符串
题目链接：表示数值的字符串题目描述：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。数值（按顺序）可以分成以下几个部分：若干空格 一个小数或者整数 （可选）一个'e'或'E'，后面跟着一个整数 若干空格小数（按顺序）可以分成以下几个部分：（可选）一个符号字符（'+' 或 '-'） 下述格式之一： 至少一位数字，后面跟着一个点 '.' 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字 一个点 '.' ，后面跟着至少一位数字 ...
2022-03-23 21:35:38
92
原创 【剑指Offer】16. 数值的整数次方
题目链接：数值的整数次方题目描述：实现pow(x,n)，即计算 x 的 n 次幂函数。不得使用库函数，同时不需要考虑大数问题。分析：这道题要计算x的n次幂函数，最直接的想法是用循环求解。但是暴力循环是会超时的，所以要想办法减少循环的次数。如果n是偶数，那么x的n次方等于x的2*n/2次方，即等于x*x的n/2次方。如果n/2是偶数的话，就等于x*x*x*x的n/4次方，以此类推，可以将时间复杂度从O(n)降为O(log 2 n)。代码如下：// 减少循环的次数var myPow...
2022-03-21 17:19:23
337
原创 【剑指Offer】30.包含min函数的栈
题目链接：包含min函数的栈题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。分析：本题的关键难点在于用O(1)的时间复杂度寻找最小值。既然是O(1)的时间复杂度，那就不能遍历，只能拿空间换时间。这个空间应该也是一个数组。用一个主栈，一个辅助栈，辅助栈栈顶为当前主栈中的最小元素。当push(x)时，如果辅助栈为空，或者辅助栈的栈顶元素>=x，那么x入辅助栈。这样能够保证辅
2022-03-17 15:16:34
560
原创 【Leetcode】5227. K 次操作后最大化顶端元素
题目链接：K次操作后最大化顶端元素题目描述：给你一个下标从 0 开始的整数数组 nums ，它表示一个 栈 ，其中 nums[0] 是栈顶的元素。每一次操作中，你可以执行以下操作 之一 ：如果栈非空，那么 删除栈顶端的元素。如果存在 1 个或者多个被删除的元素，你可以从它们中选择任何一个，添加回栈顶，这个元素成为新的栈顶元素。同时给你一个整数k，它表示你总共需要执行操作的次数。请你返回 恰好 执行 k 次操作以后，栈顶元素的 最大值 。如果执行完 k 次操作以后，栈一定为空，...
2022-03-13 15:56:02
231
原创 【Leetcode】5203. 统计可以提取的工件
题目链接：统计可以提取的工作题目描述：存在一个 n x n 大小、下标从 0 开始的网格，网格中埋着一些工件。给你一个整数 n 和一个下标从 0 开始的二维整数数组 artifacts ，artifacts 描述了矩形工件的位置，其中 artifacts[i] = [r1i, c1i, r2i, c2i] 表示第 i 个工件在子网格中的填埋情况：(r1i, c1i) 是第 i 个工件 左上 单元格的坐标，且(r2i, c2i) 是第 i 个工件 右下 单元格的坐标。你将会挖掘网格中的一些单元
2022-03-13 15:44:56
169
原创 【Leetcode】6031. 找出数组中的所有 K 近邻下标
题目链接：K紧邻下标题目描述：给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。K 近邻下标 是 nums 中的一个下标 i ，并满足至少存在一个下标 j 使得 |i - j| <= k 且 nums[j] == key 。以列表形式返回按 递增顺序 排序的所有 K 近邻下标。题目分析：用双指针的方法，当nums[j]==key的时候，将其前后k个长度范围的下标i加入结果数组，可以使用双指针进行优化，减少重复判断。代码如下：// 双指针 var
2022-03-13 15:25:55
697
原创 【Leetcode】剑指 Offer II 016. 不含重复字符的最长子字符串
题目链接：不含重复字符的最长子字符串题目描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。方法：使用滑动窗口（双指针）。窗口中永远是不含重复字符的连续子字符串，求出其最大长度。// 滑动窗口var lengthOfLongestSubstring = function(s) { const length=s.length; if(length<=1) return length; let left=0,ri.
2022-03-06 21:16:38
211
原创 【面试题】返回数组中的每一个元素在其前面元素的排序中的索引
题目描述：对于每一个元素，从第一个元素到该元素为止的若干个元素，进行升序排序，得到该元素在排序中的下标。 即对于每一个元素，得出其前面有几个比它小的元素。方法一：O(n^2)将前面的每一个元素和当前元素进行比较，统计有几个比它小的元素。// O(n^2)function numIndex(nums) { const length = nums.length; const res = []; res.push(0); let time = 0;
2022-03-06 17:04:56
465
原创 【Leetcode】最短无序连续子数组
题目链接：最短无序连续子数组题目描述：给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的 最短 子数组，并输出它的长度。分析：由题意可以得知，nums由三部分组成，[numsA，numsB，numsC]，其中numsA和numsC是升序排列，numsB即为所求的需要进行升序排序的最短的子数组。找出numsB的上下界即可。方法一：排序将nums整体进行升序排序，将排序后的数组和原数组进行一一对比
2022-03-02 16:11:43
336
原创 【leetcode】560. 和为 K 的子数组
题目链接：和为K的子数组题目描述：给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。题目思路：方法一：暴力解法O(n^2) 超时var subarraySum = function(nums, k) { const length=nums.length; let num=0; for(let i=0;i<length;i++){ let sum=nums[i]; if(sum=
2022-03-01 16:58:30
394
原创 【JS】一些手写函数：深拷贝、bind、debounce等
深拷贝：前提知识：typeof ，==，值类型和引用类型，instanceof，for...in遍历，hasOwnPropertytypeof 1'number'typeof 1.2'number'typeof 'ss''string'typeof null'object'typeof undefined'undefined'typeof []'object'typeof {}'object'typeof true'boolean'typeof Symbol'fu
2022-02-27 22:05:50
503
原创 【Leetcode】637. 二叉树的层平均值
题目链接：二叉树的层平均值题目描述：给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。分析：求每一层的平均值，和求二叉树的右视图思路是类似的。使用广度优先搜索，进行层序遍历，求每一层节点值的和除以该层的节点数，记录下来其平均值。js代码如下：// 使用BFS广度优先搜索 var averageOfLevels = function(root) { if (root == null) ret
2022-02-25 16:21:19
236
原创 【Leetcode】199. 二叉树的右视图
题目链接：二叉树的右视图题目描述：给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。分析：右视图就是看到的每一层最右侧的一个节点。那么可以使用广度优先搜索，对二叉树进行层序遍历，记录下来每一层最右侧的节点，得到的数组即为所求。js代码如下：// BFS广度优先搜索，只记录每一层的最后一个元素var rightSideView = function (root) { if (root == null)
2022-02-25 15:58:14
283
原创 【Leetcode】416. 分割等和子集
题目链接：分割等和子集题目描述：给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。思路：将数组分割成两个等和的子集。那么：1）数组元素的和肯定得是偶数，并且数组长度必须大于1。2）问题转换为：数组中是否存在若干个元素，其和为数组所有元素和的一半。即寻找若干元素的和为target。本来的思路是：将元素排序，然后使用回溯的方法，通过了100多个样例。剩下几个样例错误，经过反复思考和尝试发现回溯的方法并不对。于是看了
2022-02-23 20:39:53
619
原创 【Leetcode】221. 最大正方形
题目链接：最大正方形题目描述：在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。方法一：暴力解法求只包含1的面积最大的正方形。1）对矩阵的每一个点进行遍历，值为“1”的单元格可能是正方形的左上角。2）对值为“1”的单元格周围一圈进行判断，即在保证构成的图形是正方形的前提下，判断右侧新增的一列和下放新增的一行是否全都为"1"，如果是，那么就再往外扩张一圈；否则，扩张结束。得到以当前单元格为左上角的最大的正方形面积。时间复杂度为O(m
2022-02-22 20:44:48
421
原创 【Leetcode】79. 单词搜索
题目链接：单词搜索题目描述：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。题目分析：判断单词是否存在于网格中，要求单词的字母在网格中是相邻且连续的。就需要对网格中的每一个字符和单词中的每一个字符进行一一比对：当一个字符满足条件时，就将.
2022-02-21 20:57:12
364
原创 【LeetCode】494. 目标和
题目链接：目标和题目描述：给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。分析：数组中的每一个数字都要用到，而且每一个数字都有两种情况，+或者-。方法一：回溯（递归，df
2022-01-21 20:04:13
477
原创 【Leetcode】394. 字符串解码
题目链接：394. Decode String题目描述：给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像3a或2[4]的输入。分析：此题目需要一个栈，当遇到数...
2022-01-21 19:13:44
302
原创 【LeetCode】539. 最小时间差
今天做了两个简单题，一个中等题，就写一下中等题的题解吧。题目链接：最小时间差题目描述：给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。分析：求出最小的时间差，需要先进行排序再比较。因为24小时，每小时60分钟，数据范围为0-1439，所以可以使用基于比较的排序，也可以使用基于桶排序思想的计数排序。还有一个小trick就是，24小时内最多有1440分钟，如果题目给定的字符串的长度是大于1440的，即给定了大于1440个时间点，那
2022-01-18 21:29:12
235
原创 【LeetCode】108. 将有序数组转换为二叉搜索树
好久没刷题了，被封到宿舍近三周时间，因为状态不好一直没刷，今天第一天来实验室，先做一个简单题找一下感觉 。题目描述：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。分析：一个二叉搜索树的中序遍历序列是一个升序序列。所有这里使用中序遍历的思想。又因为要求高度平衡，所以每次都从序列中间分割为左右两部分。需要用到递归。js代码如下：// 中序遍
2022-01-17 15:41:08
247
原创 【Leetcode】347. 前 K 个高频元素
题目链接：347. Top K Frequent Elements题目内容：给你一个整数数组nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。思路：就是统计每一个数字出现的次数，然后找到出现次数前k大的k个元素。统计数字出现的次数可以用哈希表。然后问题就转换成了求n个数中前k大的k个数。方法一：k个元素的小端堆遍历数组nums，放入哈希表中，map<key,value>，key是数据，value是出现的次数。将map中的key-...
2021-12-23 20:40:41
580
原创 【Leetcode】打家劫舍
题目链接：198. House Robber 213. House Robber II 337. House Robber III1、打家劫舍I相邻两家不能同时打劫，dp[i]表示打劫到第i家能够盗取到的最高金额。用动态规划，状态转移方程为：dp[i]=max(dp[i-2]+nums[i],dp[i-1])因为求dp[i]只需用到前面两个数dp[i-1],dp[i-2]，所以可以不用数组，直接用两个变量表示即可。代码如下：var rob = function (nums...
2021-12-22 21:48:10
621
原创 【CSS】实现元素水平垂直居中
html结构如下：<div class="container"> <div class="item" style="width: 100px; height: 100px; background: #999;"> 块状元素 </div> </div> <div class="container"> <div class="item">不定高宽
2021-12-21 21:34:13
143
原创 【Leetcode】322. 零钱兑换
题目链接：零钱兑换题目描述：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回-1 。你可以认为每种硬币的数量是无限的。思路：这道题的思路和“完全平方数”那道题的思路是一致的，只是需要注意更多限制条件。方法一：动态规划dp[j]表示最少多少枚硬币能够组成总金额为j。状态转移方程为dp[j]=min (dp[j-i]) +1，其中i<=.
2021-12-21 16:29:45
131
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人