- 博客(107)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 [数据结构与算法] 二分查找II —变形问题
几种二分查找的变形问题。????????“十个二分九个错”。注意：终止条件、区间上下界更新方法、返回值选择。???????? 下述变形问题的前提是数据均以从小到大排序。变形一：查找第一个值等于给定值的元素???? 二分查找最简单的一种即有序数据集合中不存在重复的数据，在其中查找值等于某个给定值的数据。 将这个问题修改为：有序数据集合中存在重复的数据，找到第一个值等于给定值的数据，如下有序数组，其中，a[5]，a[6]，a[7]的值都等于 8，是重复的数据，要查找第一个等于 8 的数据，也就是下标
2021-11-03 17:44:48
339
原创 [数据结构与算法] 二分查找 I
一种针对有序数据集合的查找方法：二分查找（Binary Search），折半查找。二分思想二分查找是一种非常简单易懂的快速查找算法。猜测0-99中的目标数字，target = 23 。如果是 0 到 999 的数字，最多也只要 10 次就能猜中。对有序表折半查找，其最坏情况下查找一个元素的最大比较次数将介于1和 [ log2n ] + 1 ( n为元素的个数)之间。假设有 10 个订单，订单金额分别是：8，11，19，23，27，33，45，55，67，98。利用二分思想，每次都与区间的中间
2021-11-03 17:32:40
409
原创 [数据结构与算法] Recursion — 递归
Recursion — 递归递归是一种应用非常广泛的算法（或者编程技巧）。很多数据结构和算法的编码实现都要用到递归，比如 DFS 深度优先搜索、前中后序二叉树遍历等等。基本上，所有的递归问题都可以用递推公式来表示。递归需要满足的三个条件一个问题的解可以分解为几个子问题（子问题就是数据规模更小的问题）的解这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样存在递归终止条件如何编写递归代码？写递归代码最关键的是写出递推公式，找到终止条件，剩下的就是将递推公式转化为代码。上台阶、
2021-11-03 16:59:22
244
原创 [数据结构与算法] 链表 II
[数据结构与算法] 链表 II一、理解指针或引用的含义二、警惕指针丢失和内存泄漏（单链表）三、利用“哨兵”简化实现难度引入”哨兵“????♂️举例对比有无哨兵的情况四、重点留意边界条件处理五、举例画图，辅助思考六、多写多练一、理解指针或引用的含义有些语言有“指针”的概念，比如 C 语言；有些语言没有指针，取而代之的是“引用”，比如 Java、Python。不管是“指针”还是“引用”，都是存储所指对象的内存地址。将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个
2021-11-03 16:37:04
180
原创 [数据结构与算法] 链表 I
链表结构底层的存储结构 如上图，数组需要一块连续的内存空间来存储，对内存的要求比较高。如果申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。而链表并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，如果申请的是 100MB 大小的链表，根本不会有问题。三种最常见的链表结构，分别是：单链表、双向链表和循环链表。????单链表????链表通过指针将一组零散的内存块...
2021-11-03 14:42:23
150
原创 [数据结构与算法] 队列
CPU 资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 CPU 频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。当向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？这些问题并不复杂，其底层的数据结构就是队列（queue）。如何理解“队列”？队列：先进先出。栈只支持...
2021-11-02 21:48:18
119
原创 [数据结构与算法] 栈
关于“栈”，一个非常贴切的例子，就是一摞叠在一起的盘子。平时放盘子的时候，都是从下往上一个一个放；取的时候，也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。特定的数据结构是对特定场景的抽象，数组或链表暴露了太多的操作接口，操作上灵活自由，但使用时就比较不可控，自然也就更容易出错。当某个数据集合只涉及在一端插入和删除数据，...
2021-09-26 15:33:57
793
原创 [数据结构与算法] 复杂度分析
数据结构和算法解决的是“快”和“省”的问题，所以执行效率是算法一个非常重要的考量指标。什么是复杂度分析？数据结构和算法解决是“如何让代码运行得更快，如何让代码更省存储空间”，需从执行时间和占用空间两个维度来评估数据结构和算法的性能。 分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。 复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。为什么要进行复杂度分析？事后统计法有非常大的局限性。测试结果非常依赖测试环境。测试环境...
2021-09-26 15:08:42
257
原创 [数据结构与算法] 大框
10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。...
2021-09-26 15:03:00
61
原创 leetcode — 1245.树的直径
链接：树的直径__牛客网给定一棵树，求出这棵树的直径，即树上最远两点的距离。包含n个结点，n-1条边的连通图称为树。示例1的树如下图所示。其中4到5之间的路径最长，是树的直径，距离为5+2+4=11输入6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]输出11...
2021-09-24 21:24:42
1000
2
原创 [机器学习与数据分析] 集成学习结合策略
集成算法就是训练一堆基学习器，然后通过某种策略把各个基学习器的结果进行合成，从而得到集成学习器的结果。优点1）提高泛化性能 2）降低进入局部最小点的风险 3）扩大假设空间平均法简单平均、加权平均：对于数值类的回归预测问题，通常使用的结合策略是平均法，也就是说，对于若干个弱学习器的输出进行平均得到最终的预测输出。对数值型(连续)输出，最常见的结合策略为平均法。1）简单平均法(simple averaging)2）加权平均法(weig...
2021-09-22 21:26:20
1144
原创 leetcode — 103. 二叉树的锯齿形层序遍历(102、107)
给定一个二叉树，返回其节点值的锯齿形层序遍历（之字形）。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。例如：给定二叉树[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回锯齿形层序遍历如下：[ [3], [20,9], [15,7]]方法一：广度优先遍历此题是「102. 二叉树的层序遍历」的变种，最后输出的要求有所变化。...
2021-09-13 17:42:24
65
原创 leetcode — 234. 回文链表
给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。示例 1：输入：head = [1,2,2,1]输出：true示例 2：输入：head = [1,2]输出：false提示：链表中节点数目在范围[1, 105]内 0 <= Node.val <= 9进阶：你能否用O(n)时间复杂度和O(1)空间复杂度解决此题？方法一：将值复制到数组中后用双指针法复制链表值到数组...
2021-09-07 17:38:34
213
原创 leetcode — 125. 验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。示例 1:输入: "A man, a plan, a canal: Panama"输出: true解释："amanaplanacanalpanama" 是回文串示例 2:输入: "race a car"输出: false解释："raceacar" 不是回文串提示：1 <= s.length <= 2 * 105 字符串s..
2021-09-07 15:55:21
248
原创 [机器学习与数据分析] 集成学习(Ensemble Learning)
在机器学习的有监督学习算法中，目标是学习出一个稳定的且在各个方面表现都较好的模型，但实际情况往往不这么理想，有时只能得到多个有偏好的模型（弱监督模型，在某些方面表现的比较好）。集成学习就是组合这里的多个弱监督模型以期得到一个更好更全面的强监督模型，集成学习潜在的思想是即便某一个弱分类器得到了错误的预测，其他的弱分类器也可以将错误纠正回来。集成学习在各个规模的数据集上都有很好的策略。 数据集大：划分成多个小数据集，学习多个模型进行组合。 数据集小：利用Boo...
2021-09-03 16:04:45
929
原创 leetcode — 二叉树的层序遍历 I & II
二叉树层序遍历 II 102给你一个二叉树，请你返回其按层序遍历得到的节点值。 （即逐层地，从左到右访问所有节点）。// Definition for a binary tree node.public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } Tr...
2021-09-02 16:41:41
149
原创 leetcode — 33. 搜索旋转排序数组
整数数组nums按升序排列，数组中的值互不相同。在传递给函数之前，nums在预先未知的某个下标k（0 <= k < nums.length）上进行了旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。例如，[0,1,2,4,5,6,7]在下标3处经旋转后可能变为[4,5,6,7,0,1,2]。给你旋转后的数组nums和一...
2021-09-01 22:42:16
148
原创 leetcode — 46. 全排列（不含重复数字）
给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。示例 1：输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2：输入：nums = [0,1]输出：[[0,1],[1,0]]示例 3：输入：nums = [1]输出：[[1]]提示：1 <= nums.length <= 6 -10 <= nums...
2021-08-30 22:25:13
2341
原创 leetcode — 827. 最大人工岛
给你一个大小为n x n二进制矩阵grid。最多只能将一格0变成1。返回执行此操作后，grid中最大的岛屿面积是多少？岛屿由一组上、下、左、右四个方向相连的1形成。示例 1:输入: grid = [[1, 0], [0, 1]]输出: 3解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。示例 2:输入: grid = [[1, 1], [1, 0]]输出: 4解释: 将一格0变成1，岛屿的面积扩大为 4。示例 3:输入:...
2021-08-30 17:07:16
259
原创 leetcode — 695. 岛屿的最大面积
给定一个包含了一些0和1的非空二维数组grid。一个岛屿是由一些相邻的1(代表土地) 构成的组合，这里的「相邻」要求两个1必须在水平或者竖直方向上相邻。你可以假设grid的四个边缘都被0（代表水）包围着。找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)示例 1:[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0]...
2021-08-30 10:53:24
123
原创 leetcode — 470. 用 Rand7() 实现 Rand10()
已有方法rand7可生成 1 到 7 范围内的均匀随机整数，试写一个方法rand10生成 1 到 10 范围内的均匀随机整数。不要使用系统的Math.random()方法。示例 1:输入: 1输出: [7]示例 2:输入: 2输出: [8,4]示例 3:输入: 3输出: [8,1,10]提示:rand7已定义。 传入参数:n表示rand10的调用次数。进阶:rand7()调用次数的期望值是多少? 你能...
2021-08-29 22:12:28
287
原创 leetcode — 两数之和II
给定一个无序数组和一个目标值，找出数组中两个数之和等于目标值的所有组合，并指出其时间复杂度。例：数组arr = [3,5,3,5]，目标值是8。以结果是否可以重复为根本，分为3种情况。1、可完全重复。结果为 [0, 1] [0, 3] [1, 2] [2,3]，共4种下标组合。嵌套遍历。时间复杂度：O(n^2)。 哈希法。键存数组元素值，值存出现次数。时间复杂度：O(n)。 排序+双指针夹逼。时间复杂度：O(nlogn)。2、半重复。结果为 [0, 1] [2,3]，或 [...
2021-08-28 16:01:37
149
原创 leetcode — 面试题 17.24. 最大子矩阵
面试题 17.24. 最大子矩阵给定一个正整数、负整数和 0 组成的 N × M矩阵，编写代码找出元素总和最大的子矩阵。返回一个数组[r1, c1, r2, c2]（最大子矩阵的和），其中r1,c1分别代表子矩阵左上角的行号和列号，r2,c2分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。注意：本题相对书上原题稍作改动示例：输入：[ [-1,0], [0,-1]]输出：[0,1,0,1]解释：输入中标粗的元素即为输出所表示的矩阵...
2021-08-27 22:25:55
500
2
原创 leetcode — 53. 最大子序和
给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例 1：输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组[4,-1,2,1] 的和最大，为6 。示例 2：输入：nums = [1]输出：1示例 3：输入：nums = [0]输出：0示例 4：输入：nums = [-1]输出：-1示例 5：输入：nums = [-100000...
2021-08-27 22:20:40
92
原创 leetcode — 97. 交错字符串
给定三个字符串s1、s2、s3，请你帮忙验证s3是否是由s1和s2交错组成的。两个字符串s和t交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：s = s1+ s2+ ... + sn t = t1+ t2+ ... + tm |n - m| <= 1 交错是s1+ t1+ s2+ t2+ s3+ t3+ ...或者t1+ s1+ t2+ s2+ t3+ s3+ ...提示：a + b意味着字符...
2021-08-27 21:13:29
238
1
原创 [HuaWei] 8.25笔试
第一道：最大子矩阵题目描述求矩阵的最大子矩阵，比较大小的依据是子矩阵所有元素和的大小import java.util.*;// 最大子矩阵的和// 求矩阵的最大子矩阵，比较大小的依据是子矩阵所有元素和的大小public class Main1 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in);
2021-08-27 15:52:19
622
原创 leetcode — 字符串筛选（牛客小米）
链接：https://www.nowcoder.com/questionTerminal/511e2634cddc4195890916654286d28e给定一个长度为nnn字符串, 需要去除所有之前曾经出现过的字符，只保留第一次出现的字符输入"aab"输出"ab"说明删除了第二个a输入"hellowelcometoxiaomi"输出"helowcmtxia"说明只保留了第一次出现的字符备注:1000001≤n≤100000
2021-08-25 22:22:07
241
原创 [美团] 0822笔试 3 小美写作文
对于某个位置(pos1)的汉字x，最近的另外一个与其相同汉宇的位置(pos2的距离是多少，即 |pos1-pos2|。小美只学了26个汉字，用 a～z 代表。默认有一个 仅包含 a ～z 的字符串s，每次操作小美要么往字符串 s 末尾 增加一个指定字母，要么给出一个位置 pos1 (1 <= pos1 <=现在字符串s的长度)，询问 min{ |pos2-pos1|}，其中 pos2 满足，即不同于pos1的最近的另外一个pos2，使得这两个位置的字母相等。s[pos] 表示...
2021-08-24 21:20:12
161
原创 [美团] 0822笔试 1 小美的数字卡片（含重复数的全排列）
全排列II：https://leetcode-cn.com/problems/permutations-ii/n张数字卡片，在可以任意排列的情况下，能排列出多少中不同的排列，并按照字典序写出每种排列的方式。例1：[1, 2, 3]共有6种排列方式，分别为 [1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]。[2, 2, 3]共有3种排列方式，分别为 [2,2,3]、[2,3,2]、[3,2,2]。两个排列不同，当且仅当至少存在一个位置pos，两
2021-08-24 16:58:58
618
原创 [贝壳找房] 0813笔试 3
给出一个大小为n的数组 a 和整数 t，定义区间 [l, r] (0<=l<r<=n-1)，若存在下标i、j （1<=i <= j <= r）属于区间[l，r] ，且 a[i] ^a[j] = t，那么称 [l, r] 是非奇特区间，如不存在，则 [l, r] 是奇特区间。求a数组里的奇特区间个数。——> （可以与查找数组中是否两数之和等于target相等题目相对应，将键值对合理存储）输入[2, 4, 8], 6输出1先验：...
2021-08-17 16:42:30
382
1
原创 [贝壳找房] 0813笔试 1
用无人机给农田施肥，农田共有n行，无人机携带了m千克料。无人机的施肥方式为：给第1行施1千克肥料;给第2行施1千克肥料;......给第n-1行施1千克肥料;给第n行施1千克肥料;然后更改方向给第n-1行施1千克肥料;给第n-2行施1千克肥料;...即每次给整个农田施一遍肥料，无人机会自动更改方向继续施肥，直到无人机携带的肥料用完为止。现在想知道每行最终施了多少肥料。函数传入两个正整数 n 和 m 分别代麦农田的行数和无人机携带的肥料数。需要返回一个数组，假设数组为 a ，则 a
2021-08-16 10:33:31
151
原创 [贝壳找房] 0813笔试 2
一个只由小写字母组成的字符串 s ，接下来将字符串执行 k 次操作，每次操作都会把s中ASCII码最小的字母从 s 中删除，请返回 k 次操作之后的字符串。输入"caabeefa", 2输出"ceef"思路：按字典序从小到大清除字符串s中对应字符，清除k次删除k次，每次删去的元素为ASCII码最小的字母出现的所有位置的元素。——> 每次找到最小的ASCII码的字母，将该元素全部删除。——> 最直接的就是使用 空 替换。注：不需要对全部字符进行...
2021-08-15 17:57:01
462
原创 [贝壳找房] 0813笔试 4
牛牛有一棵二叉树，其根节点为root。牛牛想要在该二叉树中找到两棵子树，他们是同构的，且这两棵子树的大小是最大的。子树的大小为其节点个数。两操列是同构表示为该两棵树结构是相同的，如 o o / \ / \ o o o o / / o o两棵树是同构的。 o o / ...
2021-08-15 16:44:07
335
原创 leetcode — 652. 寻找重复的子树
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及相同的结点值。示例 1： 1 / \ 2 3 / / \ 4 2 4 / 4下面是两个重复的子树： 2 / 4和 4因此，你需要以列表的形式返回上述重复子树的根结点。题目给出了一棵二叉树 返回树中
2021-08-15 16:00:54
229
原创 leetcode — 463. 岛屿的周长
给定一个row x col的二维网格地图grid，其中：grid[i][j] = 1表示陆地，grid[i][j] = 0表示水域。网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。示例 1：输入：grid = [...
2021-08-12 15:03:45
203
转载 leetcode — 48. 旋转图像
给定一个n×n的二维矩阵matrix表示一个图像。请你将图像顺时针旋转 90 度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。示例 1：输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[[7,4,1],[8,5,2],[9,6,3]]示例 2：输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]输出：[[1...
2021-08-12 10:14:13
57
原创 leetcode — 117. 填充每个节点的下一个右侧节点指针 II
给定一个二叉树struct Node { int val; Node *left; Node *right; Node *next;}/*// Definition for a Node.class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(in
2021-08-10 21:15:22
123
原创 leetcode — 116. 填充每个节点的下一个右侧节点指针 I
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：struct Node { int val; Node *left; Node *right; Node *next;}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为NULL。初始状态下，所有next 指针都被设置为NULL。进阶：你只能使用常量级额外空间。 使用递归解题...
2021-08-09 22:12:22
81
原创 leetcode — 200. 岛屿数量
给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。示例 1：输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]]输出：1...
2021-08-07 16:43:13
631
原创 剑指 Offer 03. 数组中重复的数字
找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。示例 1：输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3 限制：2 <= n <= 100000方法一：哈希表 / Set利用数据结构特点，容易想到使用哈希表（Set）记录数组的各个数字，当查找到重复数字则直接返回。算...
2021-08-07 15:30:24
169
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人